On the Need for Large Quantum Depth

2019/09/23 by Nai-Hui Chia, Chia, Nai-Hui, Kai-Min Chung +3 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Computational Physics and Python Applications

paper · doi:10.48550/arxiv.1909.10303

Abstract

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.

Cited by

• A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Related

• Oracle separations of hybrid quantum-classical circuits
• BQP and the Polynomial Hierarchy
• Improved separation between quantum and classical computers for sampling and functional tasks
• Pseudorandom generators and the BQP vs. PH problem
• Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false