On the Need for Large Quantum Depth
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915382335373312 |
|---|---|
| author | Chia, Nai-Hui Chung, Kai-Min Lai, Ching-Yi |
| author_facet | Chia, Nai-Hui Chung, Kai-Min Lai, Ching-Yi |
| contents | Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates, and thus a potential way to use these quantum devices is using a hybrid scheme that interleaves them with classical computers. For example, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Along the line, it seems possible that a general quantum computer may only be polynomially faster than a hybrid quantum-classical computer. Jozsa raised the question of whether $BQP = BPP^{BQNC}$ and conjectured that they are equal, where $BQNC$ means $polylog$-depth quantum circuits. Nevertheless, Aaronson conjectured an oracle separation for these two classes and gave a candidate. In this work, we prove Aaronson's conjecture for a different but related oracle problem. Our result also proves that Jozsa's conjecture fails relative to an oracle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1909_10303 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | On the Need for Large Quantum Depth Chia, Nai-Hui Chung, Kai-Min Lai, Ching-Yi Quantum Physics Computational Complexity Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates, and thus a potential way to use these quantum devices is using a hybrid scheme that interleaves them with classical computers. For example, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Along the line, it seems possible that a general quantum computer may only be polynomially faster than a hybrid quantum-classical computer. Jozsa raised the question of whether $BQP = BPP^{BQNC}$ and conjectured that they are equal, where $BQNC$ means $polylog$-depth quantum circuits. Nevertheless, Aaronson conjectured an oracle separation for these two classes and gave a candidate. In this work, we prove Aaronson's conjecture for a different but related oracle problem. Our result also proves that Jozsa's conjecture fails relative to an oracle. |
| title | On the Need for Large Quantum Depth |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/1909.10303 |