(英) |
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. |