pith. sign in

arxiv: 1907.08224 · v1 · pith:LZ5GYNQ6new · submitted 2019-07-18 · 🪐 quant-ph

The one clean qubit model without entanglement is classically simulable

Mithuna Yoganathan , Chris Cade This is my paper

Pith reviewed 2026-05-24 19:35 UTC · model grok-4.3

classification 🪐 quant-ph
keywords one clean qubitentanglementclassical simulationmixed statesquantum computationquantum advantage
0
0 comments X

The pith

The one clean qubit model without entanglement is efficiently classically simulable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the one clean qubit model, in which a computation begins with one pure qubit and the remainder in the maximally mixed state. It establishes that any computation in this model that is further restricted to produce no entanglement can be simulated efficiently by a classical computer. This shows that entanglement remains necessary for the model to offer any advantage over classical methods. A sympathetic reader would care because the result clarifies the resource requirements for mixed-state quantum computation.

Core claim

The central claim is that the one clean qubit model, when restricted so that no entanglement is generated at any point during the computation, admits an efficient classical simulation.

What carries the argument

The restriction of one-clean-qubit computations to those that generate no entanglement.

If this is right

  • Any quantum advantage in the one clean qubit model requires the generation of entanglement.
  • The limited entanglement already known to appear in the model is still essential to its power.
  • Forbidding entanglement removes the possibility of efficient quantum solutions for problems that are hard classically.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same style of argument might separate the role of entanglement in other mixed-state models of quantum computation.
  • One could test the boundary by constructing explicit non-entangling circuits and checking whether they remain classically hard for any natural problem.
  • The result suggests examining whether small amounts of entanglement suffice for hardness or whether a quantitative threshold exists.

Load-bearing premise

The one clean qubit model admits a well-defined restriction to computations that generate no entanglement at any point, and this restriction still permits comparison to the model's claimed classical hardness.

What would settle it

An explicit problem that remains hard for all efficient classical algorithms yet can be solved by a non-entangling one-clean-qubit circuit would falsify the claim.

Figures

Figures reproduced from arXiv: 1907.08224 by Chris Cade, Mithuna Yoganathan.

Figure 1
Figure 1. Figure 1: Since these gates will always be 2-qubit gates, we will write U B,C A to represent a basis-controlled unitary controlled on the second qubit, and acting on the first. A B/C [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: All possible choices of product eigenbases for a 2-qubit unitary. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: This figure gives an example of a circuit that can be constructed using Table [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Changing the target qubit for a multi-controlled diagonal gate. [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: U(U A V0,x,V1,x ) = U O E,F implies that U = U A V † 0,x,V † 1,x U O E,F . 19 [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: UPABx = U E Hx,Kx implies that U = U E Hx,Kx PABx † The results so far can be summed up by the following theorem. Theorem 5.8. Applying a 2-qubit gate U to qubits i and j after applying the circuit C, whilst maintaining that the final circuit UC has a product eigenbasis, places the following constraints on U: i j U Proof Control with basis A Control with basis B Diagonal in A ⊗ B Corollary 5.7 Control with… view at source ↗
Figure 7
Figure 7. Figure 7: U E Hx,Kx PABx †PABx0 † . where P (b) ABxx0 is the action of PABxx0 on qubit j when qubit i is in state |bi ∈ {|ai, |a ⊥i}. For this circuit to be a valid basis-controlled unitary, then either A = E, or Hx and Kx are diagonal in B, or both. In the first case, for some x 0 , the resulting circuit must be a control-unitary of the form U A U (a) x0 ,U(a⊥) x0 . In the second case, where Hx and Kx are diagonal … view at source ↗
read the original abstract

Entanglement has been shown to be necessary for pure state quantum computation to have an advantage over classical computation. However, it remains open whether entanglement is necessary for quantum computers that use mixed states to also have an advantage. The one clean qubit model is a form of quantum computer in which the input is the maximally mixed state plus one pure qubit. Previous work has shown that there is a limited amount of entanglement present in these computations, despite the fact that they can efficiently solve some problems that are seemingly hard to solve classically. This casts doubt on the notion that entanglement is necessary for quantum speedups. In this work we show that entanglement is indeed crucial for efficient computation in this model, because without it the one clean qubit model is efficiently classically simulable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript claims to prove that the one clean qubit model, when restricted to circuits that generate no entanglement at any point, is efficiently classically simulable. This is presented as evidence that entanglement is necessary for any quantum advantage in the model, despite prior results showing only limited entanglement in general one-clean-qubit computations.

Significance. If the central claim holds with a rigorous definition and proof, the result would resolve an open question on the necessity of entanglement for mixed-state quantum speedups, reinforcing entanglement as a key resource even when the input state is highly mixed. It directly engages prior work on the model's limited entanglement and would provide a clean separation between entangling and non-entangling regimes.

major comments (2)
  1. [Abstract] The definition of the 'no entanglement' restriction is not made explicit. The abstract states that the model 'without it' (entanglement) is simulable, but does not specify the precise condition for mixed-state inputs (one pure qubit tensor (n-1) maximally mixed qubits): whether the global state must remain fully separable at every step, whether the clean qubit must remain unentangled with the mixed register, or a weaker condition such as absence of distillable entanglement. This choice directly determines the scope of the simulability claim and whether it rules out all potentially hard non-entangling subclasses.
  2. [Abstract] No derivation steps, algorithm, or error analysis for the claimed classical simulation are supplied in the abstract or visible high-level description. The soundness of the simulability result cannot be assessed without the explicit construction or reduction that maps the restricted circuits to a classical algorithm.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful comments on the abstract. We will revise the abstract to explicitly define the no-entanglement condition and include a high-level outline of the classical simulation algorithm, while keeping the full proof in the body.

read point-by-point responses

  1. Referee: [Abstract] The definition of the 'no entanglement' restriction is not made explicit. The abstract states that the model 'without it' (entanglement) is simulable, but does not specify the precise condition for mixed-state inputs (one pure qubit tensor (n-1) maximally mixed qubits): whether the global state must remain fully separable at every step, whether the clean qubit must remain unentangled with the mixed register, or a weaker condition such as absence of distillable entanglement. This choice directly determines the scope of the simulability claim and whether it rules out all potentially hard non-entangling subclasses.

    Authors: We agree the abstract should be explicit. Our definition is that the global state remains fully separable (product state) between the clean qubit and the mixed register at every step of the circuit; equivalently, the clean qubit never entangles with the mixed qubits. This is the condition under which our classical simulation holds, as separability allows the mixed register to remain maximally mixed and the clean qubit's reduced state to be tracked via classical means. We will add this precise wording to the abstract. We chose this strong condition because it directly addresses whether entanglement is required for advantage; weaker notions like no distillable entanglement are not needed for our result. revision: yes

  2. Referee: [Abstract] No derivation steps, algorithm, or error analysis for the claimed classical simulation are supplied in the abstract or visible high-level description. The soundness of the simulability result cannot be assessed without the explicit construction or reduction that maps the restricted circuits to a classical algorithm.

    Authors: The abstract is high-level by design, but we will add a one-sentence outline of the algorithm: under the separability condition the mixed qubits remain maximally mixed and can be ignored, while the clean qubit evolves under a convex combination of unitaries that can be sampled and simulated classically in poly time with bounded error. The full reduction, including the explicit classical algorithm and error bounds (via standard approximation of quantum channels on a single qubit), appears in the main text. We will make this high-level description visible in the revised abstract. revision: yes

Circularity Check

0 steps flagged

No significant circularity; simulability shown by direct constructive proof.

full rationale

The paper establishes classical simulability of the one-clean-qubit model under an explicit no-entanglement restriction via a direct proof. The abstract frames the result as an independent simulation argument that does not rely on fitted parameters, self-referential definitions, or load-bearing self-citations. No step reduces the claimed result to its inputs by construction, and the derivation remains self-contained against external benchmarks of classical simulation complexity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard definitions of the one-clean-qubit model and the notion of entanglement from quantum information theory; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (2)
  • standard math Standard axioms of quantum mechanics and linear algebra for defining states, evolution, and entanglement
    Invoked implicitly to define the model and the no-entanglement restriction.
  • domain assumption The one clean qubit model is a valid mixed-state quantum computation framework
    Background assumption required to interpret the simulability claim.

pith-pipeline@v0.9.0 · 5647 in / 1144 out tokens · 36655 ms · 2026-05-24T19:35:24.378016+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · 12 internal anchors

  1. [1]

    Ten semi-grand challenges for quantum computing theory, 2005

    Scott Aaronson. Ten semi-grand challenges for quantum computing theory, 2005

    work page 2005

  2. [2]

    The Computational Complexity of Linear Optics

    Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 333–342. ACM, 2011. arXiv:1011.3245. 3This is not the only method, see Ref [12, 8]. 24

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  3. [3]

    Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

    Michael J Bremner, Richard Jozsa, and Dan J Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Pro- ceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 467(2126):459–472, 2010. arXiv:1005.1407

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  4. [4]

    Average-case complexity versus approximate simulation of commuting quantum computations

    Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical review letters, 117(8):080501, 2016. arXiv:1504.07999

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  5. [5]

    The quantum complexity of computing schatten p- norms

    Chris Cade and Ashley Montanaro. The quantum complexity of computing schatten p- norms. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik,

    work page 2018

  6. [6]

    Entanglement and the Power of One Qubit

    Animesh Datta, Steven T Flammia, and Carlton M Caves. Entanglement and the power of one qubit.Physical Review A, 72(4):042316, 2005. arXiv:quant-ph/0505213

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  7. [7]

    On the role of entanglement and correlations in mixed-state quantum computation

    Animesh Datta and Guifre Vidal. Role of entanglement and correlations in mixed-state quantum computation. Physical Review A , 75(4):042310, 2007. arXiv:quant-ph/0611157

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  8. [8]

    Power of Quantum Computation with Few Clean Qubits

    Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani. Power of quantum computation with few clean qubits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. arXiv:1509.07276

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  9. [9]

    On the role of entanglement in quantum computational speed-up

    Richard Jozsa and Noah Linden. On the role of entanglement in quantum- computational speed-up. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences , 459(2036):2011–2032, 2003. arXiv:quant-ph/0201143

    work page internal anchor Pith review Pith/arXiv arXiv 2036

  10. [10]

    On the Power of One Bit of Quantum Information

    Emanuel Knill and Raymond Laflamme. Power of one bit of quantum information. Physical Review Letters, 81(25):5672, 1998. arXiv:quant-ph/9802037

    work page internal anchor Pith review Pith/arXiv arXiv 1998

  11. [11]

    Hardness of classically sampling one clean qubit model with constant total variation distance error

    Tomoyuki Morimae. Hardness of classically sampling the one-clean-qubit model with constant total variation distance error. Physical Review A , 96(4):040302, 2017. arXiv:1704.03640

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  12. [12]

    On the hardness of classically simulating the one clean qubit model

    Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical review letters , 112(13):130502, 2014. arXiv:1312.2496

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  13. [13]

    Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect

    David Poulin, Robin Blume-Kohout, Raymond Laflamme, and Harold Ollivier. Ex- ponential speedup with a single bit of quantum information: Measuring the average fidelity decay. Physical review letters, 92(17):177906, 2004. arXiv:quant-ph/0310038. 25

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  14. [14]

    Estimating jones polynomials is a complete problem for one clean qubit

    Peter W Shor and Stephen P Jordan. Estimating jones polynomials is a complete problem for one clean qubit. Quantum Information & Computation , 8(8):681–714,

    work page

  15. [15]

    Efficient classical simulation of slightly entangled quantum computations

    Guifr´ e Vidal. Efficient classical simulation of slightly entangled quantum computa- tions. Physical review letters, 91(14):147902, 2003. arXiv:quant-ph/0301063. 26

    work page internal anchor Pith review Pith/arXiv arXiv 2003