Power of Uninitialized Qubits in Shallow Quantum Circuits
arXiv:1608.07020 · doi:10.1016/j.tcs.2020.11.039
Abstract
We study the computational power of shallow quantum circuits with initialized and uninitialized ancillary qubits, where 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 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 qubits. Since it seems unlikely that these tasks can be done with only initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only 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 bits.
arXiv comment23 pages, 10 figures; v3: Theorem 1 improved, title changed, text substantially rewritten
References in corpus (12)
- Elementary gates for quantum computation
- The Physical Implementation of Quantum Computation
- On the Power of One Bit of Quantum Information
- Quantum advantage with shallow circuits
- An approximate Fourier transform useful in quantum factoring
- On the hardness of classically simulating the one clean qubit model
- Quantum Circuits with Unbounded Fan-out
- Fast parallel circuits for the quantum Fourier transform
- 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