Power of Uninitialized Qubits in Shallow Quantum Circuits

Abstract

We study the computational power of shallow quantum circuits with $O(\log n)$ initialized and $n^{O(1)}$ uninitialized ancillary qubits, where $n$ is the input length and the initial state of the uninitialized ancillary qubits is arbitrary. First, we show that such a circuit can compute any symmetric function on $n$ bits that is classically computable in polynomial time. Then, we regard such a circuit as an oracle and show that a polynomial-time classical algorithm with the oracle can estimate the elements of any unitary matrix corresponding to a constant-depth quantum circuit on $n$ qubits. Since it seems unlikely that these tasks can be done with only $O(\log n)$ initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only $O(\log n)$ initialized ancillary qubits. Lastly, to understand the limitations of uninitialized ancillary qubits, we focus on near-logarithmic-depth quantum circuits with them and show the impossibility of computing the parity function on $n$ bits.

23 pages, 10 figures; v3: Theorem 1 improved, title changed, text substantially rewritten

References in corpus (6)

• Quantum advantage with shallow circuits
• On the hardness of classically simulating the one clean qubit model
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Average-Case Quantum Advantage with Shallow Circuits
• Commuting quantum circuits: efficient classical simulations versus hardness results