Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910583747510272 |
|---|---|
| author | Delavenne, Hugo Gall, François Le |
| author_facet | Delavenne, Hugo Gall, François Le |
| contents | This work investigates the relationships between quantum state synthesis complexity classes (a recent concept in computational complexity that focuses on the complexity of preparing quantum states) and traditional decision complexity classes. We especially investigate the role of the synthesis error parameter, which characterizes the quality of the synthesis in quantum state synthesis complexity classes. We first show that in the high synthesis error regime, collapse of synthesis classes implies collapse of the equivalent decision classes. For more reasonable synthesis error, we then show a similar relationships for BQP and QCMA. Finally, we show that for quantum state synthesis classes it is in general impossible to improve the quality of the synthesis: unlike the completeness and soundness parameters (which can be improved via repetition), the synthesis error cannot be reduced, even with arbitrary computational power. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_02907 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction Delavenne, Hugo Gall, François Le Quantum Physics Computational Complexity This work investigates the relationships between quantum state synthesis complexity classes (a recent concept in computational complexity that focuses on the complexity of preparing quantum states) and traditional decision complexity classes. We especially investigate the role of the synthesis error parameter, which characterizes the quality of the synthesis in quantum state synthesis complexity classes. We first show that in the high synthesis error regime, collapse of synthesis classes implies collapse of the equivalent decision classes. For more reasonable synthesis error, we then show a similar relationships for BQP and QCMA. Finally, we show that for quantum state synthesis classes it is in general impossible to improve the quality of the synthesis: unlike the completeness and soundness parameters (which can be improved via repetition), the synthesis error cannot be reduced, even with arbitrary computational power. |
| title | Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2407.02907 |