RECORD
Power of Uninitialized Qubits in Shallow Quantum Circuits
Quantum Physics · Submitted 25 Aug 2016
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | contribution 0.76 | 0.38 | 0.05 | unclear 0.52 |
| s1 | First, we show that such a circuit can compute any symmetric function on $n$ bits that is classically computable in polynomial time. | result 1.00 | 0.94 | 0.24 | asserted 1.00 |
| s2 | 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. | result 0.95 | 0.92 | 0.12 | asserted 1.00 |
| s3 | 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. | interpretation 1.00 | 0.59 | 0.72 | hedged possibility 0.93 |
| s4 | 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. | limitation 0.60 | 0.95 | 0.11 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
References
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites
Cites as background 1 paper
-
Much attention has been paid to the computational power of shallow (i.e., polylogarithmic-depth) quantum circuits [ref] .
Quantum advantage with shallow circuits · Background and Main Results · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.