REVIEW
Reopening the one clean qubit case of a semi-grand challenge
Quantum Physics · Submitted 3 Nov 2026 · 31 references
Pith's verdict: A clean, checkable counterexample that plausibly breaks the claimed DQC1sep⊆BPP proof; the verdict hinges on one externally checkable question about how the cited thesis proof is structured.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
A fully separable one-clean-qubit circuit whose final unitary cannot be put in canonical form breaks the claimed proof of classical simulability and reopens the 2005 semi-grand challenge.
The reading
What carries the argument
The load-bearing object is the accumulated register unitary $C_3 = G_3 G_2 G_1$ together with the notion of canonical form defined in the cited characterization: a unitary is in canonical form when a set of qubits with fixed bases defines a common branching tree, each leaf carrying a phase and a tensor product of single-qubit unitaries on the remaining qubits. A qubit has a fixed basis when the unitary decomposes as $|e_0\rangle\langle e_0|_j \otimes U_0 + |e_1\rangle\langle e_1|_j \otimes U_1$ in some orthonormal basis. The argument's engine is a block-dependence contradiction: canonical form forces the sub-blocks of $C_3$ in the $|0\rangle\langle 0|_a \otimes |0\rangle\langle 0|_b$ and $|0\rangle\langle 0|_a \otimes |1\rangle\langle 1|_b$ sectors to be scalar multiples of a common single-qubit unitary, hence linearly dependent, while the actual blocks are $Z_c$ and $(XZ)_c$, which are linearly independent. The same machinery, with spectator qubits appended by tensor products with the identity, delivers the uniform family of Theorem 2.
Extended reading notes
Core claim
The central claim is Theorem 1: the final register unitary $C_3$ of the Figure 2 circuit cannot be put into canonical form, even though the circuit is a DQC1sep circuit, meaning a one-clean-qubit circuit with no entanglement across any bipartition after each gate, whose state is fully separable after each gate. The gates are $G_1 = \mathrm{CNOT}_{a\to b}$, $G_2 = |0\rangle\langle 0|_a \otimes Z_c + e^{i\pi/4}|1\rangle\langle 1|_a \otimes I_c$, and $G_3 = \mathrm{CNOT}_{b\to c}$, each additionally controlled by the clean qubit; direct calculation shows the accumulated unitaries $C_0,\dots,C_3$ each have a fully separable orthonormal eigenbasis, which is exactly the property the cited characterization [28] treats as decisive for membership in the class. The proof of noncanonicality runs on fixed bases: qubit $a$ has the $Z$ basis as its unique fixed basis, qubits $b$ and $c$ have no fixed basis at all, and any canonical representation of $C_3$ would force the two blocks indexed by $|0\rangle\langle 0|_a \otimes |0\rangle\langle 0|_b$ and $|0\rangle\langle 0|_a \otimes |1\rangle\langle 1|_b$ to be linearly dependent scalar multiples of one single-qubit unitary, whereas direct substitution gives $Z_c$ and $(XZ)_c$, which are diagonal and off-diagonal and hence linearly independent. The paper identifies the gap this exposes in the earlier proof as a false necessity condition: Theorems 4.4.4 and 4.4.5 of [28] required the two updated branches of a two-qubit gate to have a fixed basis in the same direction, while this circuit satisfies the requirement in different directions. The obstruction is then extended to a uniform family $C^{(n)}_3 = C_3 \otimes I^{\otimes(n-3)}$ for all $n \geq 3$ (Theorem 2), and a continuous-time implementation of the same circuit keeps the state fully separable at every intermediate time and ends at the same noncanonical $C_3$.
Load-bearing premise
The conclusion that the challenge is reopened rests on the paper's reading of the cited thesis [28]: that the proof of Theorem 4.3.9 genuinely depends on the necessity claims of Theorems 4.4.4 and 4.4.5 (that both updated branches share a fixed basis in the same direction), and that the simulation algorithm genuinely requires the final unitary to be in canonical form; if the thesis has an alternative route, or canonical form is not actually necessary, the counterexample would not invalidate the claimed inclusion.
Editorial extensions
If this is right
- Any repaired proof of $\mathrm{DQC1sep} \subseteq \mathrm{BPP}$ must accommodate branches whose control directions differ: the counterexample's updated branches are basis-controlled in the $Z$ basis of qubit $b$ and the $X$ basis of qubit $c$ respectively, a possibility the earlier necessity claims excluded.
- The obstruction is not isolated to one circuit: padding with identity on spectator qubits gives a uniform family $C_3^{(n)} = C_3 \otimes I^{\otimes(n-3)}$ whose every member is a DQC1sep circuit with a noncanonical final unitary (Theorem 2).
- The circuit admits a continuous-time implementation that stays fully separable at every intermediate time (Proposition B.1), so the failure of canonical form is not an artifact of discrete gating.
- The counterexample's normalized trace is zero, so its output distribution is a fair coin and the circuit is classically trivial; the paper's role is to obstruct a proof rather than to exhibit quantum advantage, and the underlying question remains open.
Reading between the lines
- The same block-dependence trick may generate many more counterexamples: any gate sequence whose final unitary places linearly independent single-qubit gates in sub-blocks that canonical form forces to be dependent would evade the claimed characterization, and a computational search over short gate sequences could show whether the phenomenon is generic.
- If the shared-fixed-basis necessity claim is indeed false, the natural repair is a generalized canonical form whose control basis may change from branch to branch; whether such a representation still supports polynomial-time eigenvalue sampling is the key technical question this paper leaves implicit.
- The counterexample suggests that what governs classical simulability here is the structure of the evolving eigenbasis, which qubit controls in which basis at each stage, rather than state separability alone, a reading that would sharpen the original question rather than merely reopen it.
- A sharper test of the diagnosis would be a search for other DQC1sep circuits with noncanonical final unitaries and nonzero normalized trace: one that is still classically simulable would show the canonical-form route is dispensable, while one that is classically hard would settle the challenge in the negative.
Original abstract
In his 2005 list of semi-grand challenges for quantum computing theory, Scott Aaronson asked whether a quantum computer that is always in a separable mixed state can be simulated by a classical computer in polynomial time. An affirmative answer was claimed for the one clean qubit model of quantum computation. The supporting mathematical arguments relied on an exhaustive characterization of circuits that stay in separable states. Here, we give a counterexample where one pure qubit, known as the clean qubit, controls a sequence of three gates that act on a maximally mixed three-qubit register. The overall unitary that accumulates as these gates are applied has the properties that ensure the state of all four qubits remains fully separable. Crucially, we show that the final unitary cannot be put into the form required by the claimed simulation result. We also give a continuous-time implementation of the same circuit that keeps the qubits fully separable throughout and ends at the same unitary. We extend our counterexamples to a uniform family, and pinpoint the gap in the earlier proof. Since our circuits are themselves efficient to simulate classically, this work does not settle Aaronson's question. It does, however, reopen the semi-grand challenge for an actively researched model of quantum computation.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. 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.
The abstract, sentence by sentence
In his 2005 list of semi-grand challenges for quantum computing theory, Scott Aaronson asked whether a quantum computer that is always in a separable mixed state can be simulated by a classical computer in polynomial time. An affirmative answer was claimed for the one clean qubit model of quantum computation. The supporting mathematical arguments relied on an exhaustive characterization of circuits that stay in separable states. Here, we give a counterexample where one pure qubit, known as the clean qubit, controls a sequence of three gates that act on a maximally mixed three-qubit register. The overall unitary that accumulates as these gates are applied has the properties that ensure the state of all four qubits remains fully separable. Crucially, we show that the final unitary cannot be put into the form required by the claimed simulation result. We also give a continuous-time implementation of the same circuit that keeps the qubits fully separable throughout and ends at the same unitary. We extend our counterexamples to a uniform family, and pinpoint the gap in the earlier proof. Since our circuits are themselves efficient to simulate classically, this work does not settle Aaronson's question. It does, however, reopen the semi-grand challenge for an actively researched model of quantum computation.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In his 2005 list of semi-grand challenges for quantum computing theory, Scott Aaronson asked whether a quantum computer that is always in a separable mixed state can be simulated by a classical computer in polynomial time. | background 1.00 | 0.03 | 0.03 | asserted 0.89 |
| s1 | An affirmative answer was claimed for the one clean qubit model of quantum computation. | background 0.99 | 0.05 | 0.04 | asserted 0.99 |
| s2 | The supporting mathematical arguments relied on an exhaustive characterization of circuits that stay in separable states. | background 1.00 | 0.04 | 0.03 | asserted 1.00 |
| s3 | Here, we give a counterexample where one pure qubit, known as the clean qubit, controls a sequence of three gates that act on a maximally mixed three-qubit register. | contribution 0.90 | 0.94 | 0.23 | asserted 1.00 |
| s4 | The overall unitary that accumulates as these gates are applied has the properties that ensure the state of all four qubits remains fully separable. | result 0.90 | 0.89 | 0.09 | asserted 1.00 |
| s5 | Crucially, we show that the final unitary cannot be put into the form required by the claimed simulation result. | result 0.91 | 0.95 | 0.47 | asserted 1.00 |
| s6 | We also give a continuous-time implementation of the same circuit that keeps the qubits fully separable throughout and ends at the same unitary. | contribution 0.70 | 0.96 | 0.07 | asserted 1.00 |
| s7 | We extend our counterexamples to a uniform family, and pinpoint the gap in the earlier proof. | contribution 0.94 | 0.96 | 0.16 | asserted 1.00 |
| s8 | Since our circuits are themselves efficient to simulate classically, this work does not settle Aaronson's question. | limitation 0.88 | 0.81 | 0.18 | asserted 0.99 |
| s9 | It does, however, reopen the semi-grand challenge for an actively researched model of quantum computation. | interpretation 0.99 | 0.63 | 0.48 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v1
- 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
Figures
Figures reproduced from arXiv:2611.05046 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.