A conjecture of Jozsa [Jozsa06] states that any polynomial-time quantum computation can be simulated by polylogarithmic-depth quantum computation interleaved with polynomial-depth classical computation. Separately, Aaronson [Aaronson05, Aaronson11, Aaronson14] conjectured that there exists an oracle O such that BQPO≠(BPPBQNC)O. These conjectures are intriguing allusions to the unresolved potential of combining classical and low-depth quantum computation. In this work we show that the Welded Tree Problem, which is an oracle problem that can be solved in quantum polynomial time as shown by Childs et al. [ChildsCDFGS03], cannot be solved in BPPBQNC, nor can it be solved in the class that Jozsa describes. This proves Aaronson's oracle separation conjecture and provides a counterpoint to Jozsa's conjecture relative to the Welded Tree oracle problem. More precisely, we define two complexity classes, HQC and JC whose languages are decided by two different families of interleaved quantum-classical circuits. HQC contains BPPBQNC and is therefore relevant to Aaronson's conjecture, while JC captures the model of computation that Jozsa considers. We show that the Welded Tree Problem gives an oracle separation between either of {JC,HQC} and BQP. Therefore, even when interleaved with arbitrary polynomial-time classical computation, greater "quantum depth" leads to strictly greater computational ability in this relativized setting.

1 aCoudron, Matthew1 aMenda, Sanketh uhttps://arxiv.org/abs/1909.1050302278nas a2200121 4500008004100000245012000041210006900161260001500230520183200245100002102077700002102098856003702119 2020 eng d00aQuasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits0 aQuasipolynomial Time Approximation of Output Probabilities of Co c12/10/20203 aWe present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit C, and any bit string x∈{0,1}n, can compute the quantity |<x|C|0⊗n>|2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is #P-hard to compute this same quantity to within 2−n2 additive error [Mov20]. The previous best known algorithm for this problem used O(2n1/3poly(1/ε)) time to compute probabilities to within additive error ε [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit "pieces" produced this way.

1 aCoble, Nolan, J.1 aCoudron, Matthew uhttps://arxiv.org/abs/2012.05460