Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914795554340864 |
|---|---|
| author | Chia, Nai-Hui Hsieh, Min-Hsiu Hung, Shih-Han Kuo, En-Jui |
| author_facet | Chia, Nai-Hui Hsieh, Min-Hsiu Hung, Shih-Han Kuo, En-Jui |
| contents | This work investigates the oracle separation between the physically motivated complexity class of noisy quantum circuits, inspired by definitions such as those presented by Chen, Cotler, Huang, and Li (2022). We establish that with a constant error rate, separation can be achieved in terms of NP. When the error rate is $Ω(\log n/n)$, we can extend this result to the separation of PH. Notably, our oracles, in all separations, do not necessitate error correction schemes or fault tolerance, as all quantum circuits are of constant depth. This indicates that even quantum computers with minor errors, without error correction, may surpass classical complexity classes under various scenarios and assumptions. We also explore various common noise settings and present new classical hardness results, generalizing those found in studies by Raz and Tal (2022) and Bassirian, Bouland, Fefferman, Gunn, and Tal (2021), which are of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07137 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy Chia, Nai-Hui Hsieh, Min-Hsiu Hung, Shih-Han Kuo, En-Jui Quantum Physics Computational Complexity This work investigates the oracle separation between the physically motivated complexity class of noisy quantum circuits, inspired by definitions such as those presented by Chen, Cotler, Huang, and Li (2022). We establish that with a constant error rate, separation can be achieved in terms of NP. When the error rate is $Ω(\log n/n)$, we can extend this result to the separation of PH. Notably, our oracles, in all separations, do not necessitate error correction schemes or fault tolerance, as all quantum circuits are of constant depth. This indicates that even quantum computers with minor errors, without error correction, may surpass classical complexity classes under various scenarios and assumptions. We also explore various common noise settings and present new classical hardness results, generalizing those found in studies by Raz and Tal (2022) and Bassirian, Bouland, Fefferman, Gunn, and Tal (2021), which are of independent interest. |
| title | Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2405.07137 |