Reopening the one clean qubit case of a semi-grand challenge

Introduction

The challenge. In 2005, Aaronson asked whether a quantum computer that is always in a separable mixed state can be simulated by a classical computer in polynomial time [1]. The question asks whether a restriction on the states visited during a computation is enough to guarantee an efficient classical account of its observable output. The one clean qubit model of quantum computation provides an intriguing setting in which to investigate this question.

The model. Introduced by Knill and Laflamme [2], the one clean qubit model of quantum computation involves just one pure qubit, known as the clean qubit, and $n$ maximally mixed qubits (see Figure 1). The complexity class associated with this model is known as deterministic quantum computation with one qubit (or DQC1 for short). Despite the lack of purity, this model is remarkably powerful [3 Chapter 22]. Estimating the normalized trace of a unitary matrix is a DQC1-complete task for which no polynomial-time classical algorithm is likely to exist [4], and related sampling tasks are classically hard under plausible complexity-theoretic assumptions [5, 6, 7]. We use the trace-estimation formulation throughout.

What the circuit estimates. In the trace-estimation formulation, a Hadamard gate prepares the clean qubit in $\lvert+\rangle$. It then controls an efficiently implementable register unitary $U$, as in Figure 1. The expectation values of $X$ and $Y$ on the clean qubit are, respectively, the real and imaginary parts of the normalized trace $\tau(U)=2^{-n}\operatorname{Tr}[U]$, which is the average of the eigenvalues of $U$. Throughout, $n$ denotes the number of register qubits, and the operations upon them are always controlled by the clean qubit. Appendix § 11 gives the readout formulas and their derivation.

The importance. At first glance, estimating the trace of an exponentially large unitary matrix does not seem like it has many applications. However, normalized trace estimation connects DQC1 to knot and 3-manifold invariants [8, 9, 10], partition functions [11], infinite-temperature out-of-time-order and multi-time correlation functions [12], topological data analysis [13, 14, 15], Schatten norms [16], variational quantum compiling [17], and restricted quantum computer access [18], to name a few.

DQC1 is also of fundamental interest, both as an intermediate model in complexity theory [19, 20] and as a testbed for non-classical correlations and resource theories [21, 22, 23, 24]. Experimentally, the need for every operation to be controlled by the clean qubit appears daunting. Despite this, neutral-atom systems have demonstrated high-fidelity three-qubit gates [25], which supports proposals in which a single atom natively controls a large register [26]. This strengthens the prospects for a sizeable implementation of this model.

The claimed resolution. We now turn to the work of Yoganathan and Cade [27], and its revised treatment in Chapter 4 of Yoganathan’s thesis [28]. These works aimed to provide an exhaustive characterization of fully separable one clean qubit circuits and argued that the eigenvalues of their final unitaries could be efficiently sampled. They thus claimed that one clean qubit circuits that are always in separable mixed states can indeed be simulated by classical computers in polynomial time.

Our counterexample. In § 3, we analyze the quantum circuit in Figure 2 and show that it is fully separable after each discrete gate. In § 5, we prove that the final register unitary cannot be put in the required canonical form. The resulting structural obstruction invalidates the proposed simulation argument and reopens the one clean qubit case of the semi-grand challenge.

Organization. § 2 gives the properties of the gates that ensure the state of the circuit is always fully separable. § 3 applies this criterion to our counterexample. § 4 introduces the canonical form of fully separable circuits and § 5 proves that our counterexample cannot be put into this form. § 6 gives a uniform family of counterexamples and describes the consequences for classical simulations of one clean qubit circuits. Finally, § 7 provides a conclusion and an outlook.

Conventions. Formally, $\mathrm{DQC1}_{\mathrm{sep}}$ is the class of decision problems that can be efficiently decided in the one clean qubit model with no entanglement across any cut during the computation. This terminology may be used informally (e.g., “$\mathrm{DQC1}_{\mathrm{sep}}$ circuits”) where there is no risk of misunderstandings arising. We employ the gate convention of Refs. [27, 28] where each displayed one- or two-qubit gate is additionally controlled by the clean qubit. By efficient classical simulation, we mean polynomial-time estimation of the final clean-qubit measurement probabilities to inverse-polynomial additive accuracy, as in the cited work. Here, polynomial is with respect to the number of qubits. The decision-class inclusion claimed in Refs. [27, 28] is $\mathrm{DQC1}_{\mathrm{sep}} \subseteq\mathrm{BPP}$, where BPP denotes efficient randomized classical decision computation.

Depending on context, we may use $\lvert x_{\pm}\rangle= \lvert\pm\rangle= (\lvert0\rangle\pm\lvert1\rangle)/\sqrt{2}$ and $\lvert y_{\pm}\rangle= (\lvert0\rangle\pm i\lvert1\rangle)/\sqrt{2}$ to respectively denote the $\pm1$ eigenvectors of the Pauli operators $X$ and $Y$. Similarly, $\lvert z_+\rangle= \lvert0\rangle$ and $\lvert z_-\rangle= \lvert1\rangle$ are the eigenvectors of the Pauli $Z$ operator.

Separability in DQC1sep circuits

Clarifying separability. A mixed state is separable across a bipartition if it can be written as a probabilistic mixture of pure states that are tensor products across that bipartition [28 Definition 4.2.1]. It is fully separable if it is a probabilistic mixture of tensor products of one-qubit states. For the main counterexample, we use the discrete-gate formulation of $\mathrm{DQC1}_{\mathrm{sep}}$, which requires that there is no entanglement across any bipartition after each gate [28 Section 4.2].

Required eigenproperties. Definition 4.2.3 of Ref. [28] states that an $n$-qubit unitary $U$ has a separable eigendecomposition if (a) there exists a set of separable eigenvectors $\{\lvert u_j\rangle\}_j$ and (b) there is a probability distribution $p$ such that $\sum_j p_j\lvert u_j\rangle\langle u_j\rvert= I/2^n$. Each $n$-qubit unitary related to our counterexample has a set of $2^n$ eigenvectors that are fully separable and orthonormal to one another. Such unitaries satisfy condition (b) with a uniform probability distribution.

Why these properties guarantee separability. As explained in Ref. [28], it is conceptually helpful to express the maximally mixed state of the register qubits as $(I/2^n) = 2^{-n}\sum_i\lvert u_i\rangle\langle u_i\rvert$, where $\{\lvert u_i\rangle\}$ is an orthonormal eigenbasis for $U$. It is notationally convenient to denote the mixed state $\sum_i p_i\lvert\psi_i\rangle\langle\psi_i\rvert$ as $\{p_i,\lvert\psi_i\rangle\}_i$, where $p$ is a probability distribution. The initial state of the circuit is therefore $\{2^{-n},\lvert+\rangle\lvert u_i\rangle\}_i$. Let $\lambda_i$ be the eigenvalue of $\lvert u_i\rangle$. When $U$, controlled by the clean qubit, is applied, the state becomes

This equation clearly has no entanglement if $\{\lvert u_i\rangle\}_i$ is a separable eigendecomposition. The final state before the measurement is a probabilistic mixture of these states and is therefore fully separable.

The counterexample and its separability

We first describe the counterexample circuit shown in Figure 2 and then prove that it is fully separable after every gate.

Quantum circuit

The register and gates. The register has three maximally mixed qubits, $a$, $b$ and $c$. The clean qubit that controls the operations on these qubits is not shown. Initially, a CNOT gate is applied with $a$ as the control and $b$ as the target. This is followed by a gate that consists of an open-controlled $Z$ on $c$ that is controlled by $a$, and a $T$ gate on $a$. Finally, a CNOT gate is applied with $b$ as the control and $c$ as the target. These gates can be specified as:

G_3 = \operatorname{CNOT}_{b\to c}.

The accumulated unitaries. Let $C_t$ denote the accumulated unitary after $t$ gates have been applied. That is, $C_t = G_tG_{t-1}\cdots G_1$. Direct calculation gives:

where

Separability after every gate

Each of the accumulated 3-qubit unitaries, $C_0$ to $C_3$, has a set of 8 fully separable, orthonormal eigenvectors. Direct calculation shows that the accumulated unitaries $C_0$ to $C_2$ have degenerate eigenvalues, while $C_3$ is non-degenerate. One set of separable, orthonormal eigenvectors that conveniently works for $C_0$, $C_1$ and $C_2$ is

with signs chosen independently and subscripts, $a$, $b$ and $c$, read from left to right, suppressed for clarity. Inspection of Eqs. (3) and (4) gives the eigenvectors of $C_3$ as shown in Table 1.

Eigenvector	Eigenvalue	$k$	Eigenvector	Eigenvalue	$k$
$\lvert0\rangle\lvert0\rangle\lvert0\rangle$	$1$	$0$	$\lvert1\rangle\lvert x_+\rangle\lvert+\rangle$	$e^{i\pi/4}$	$1$
$\lvert0\rangle\lvert0\rangle\lvert1\rangle$	$-1$	$4$	$\lvert1\rangle\lvert x_-\rangle\lvert+\rangle$	$-e^{i\pi/4}$	$5$
$\lvert0\rangle\lvert1\rangle\lvert y_+\rangle$	$-i$	$6$	$\lvert1\rangle\lvert y_+\rangle\lvert-\rangle$	$i e^{i\pi/4}$	$3$
$\lvert0\rangle\lvert1\rangle\lvert y_-\rangle$	$i$	$2$	$\lvert1\rangle\lvert y_-\rangle\lvert-\rangle$	$-i e^{i\pi/4}$	$7$

Continuous version. In Appendix B, we give explicit unitary interpolations that connect $C_0$, $C_1$, $C_2$ and $C_3$ while keeping a separable, orthonormal eigenbasis at every intermediate time. Each gate acts on its original pair of register qubits, with the earlier gates already completed. The resulting evolution stays fully separable throughout and has the same final accumulated unitary, $C_3$.

The canonical form of DQC1sep circuits

We first use the block decomposition of a unitary to define fixed bases and their branches. This feeds into the definition of canonical form. For completeness, we also point the reader towards the parts of Ref. [28] that describe the role of canonical form in the efficient, classical simulations of DQC1sep circuits.

Fixed bases

Definition. If, for a unitary, $U$, there exists a block decomposition of the form

where $\lvert e_0\rangle$ and $\lvert e_1\rangle$ form an orthonormal basis for qubit $j$, and the unitaries $U_0$ and $U_1$ act on the other qubits, then qubit $j$ is said to have a fixed basis. If no such block decomposition exists, then qubit $j$ does not have a fixed basis. This is equivalent to the fixed basis line of Definition 4.3.7 in Ref. [28], which requires that inputting $\lvert e_0\rangle$ or $\lvert e_1\rangle$ on qubit $j$, with arbitrary inputs on the other qubits, returns the same basis state on qubit $j$.

Uniqueness. If $U_0 \ne U_1$, then qubit $j$ has a fixed basis formed by $\lvert e_0\rangle$ and $\lvert e_1\rangle$ that is unique up to phases and reordering. If, on the other hand, $U_0 = U_1$, then $U = I_j \otimes U_0$, so qubit $j$ has a fixed basis that is not unique (i.e., its fixed basis could be any orthonormal single-qubit basis).

Branching example. It is convenient to describe $U_0$ and $U_1$ as the branches or the branch unitaries of the fixed basis. A pertinent example is that of $C_3$, with its unique branching structure illustrated in Figure 3.

Canonical form

Definition 4.3.10 of Ref. [28] states that an $n$-qubit unitary, $U$, is in canonical form if there exist $s$ wires, collectively called $B$, with fixed bases $\{\lvert b_0^{(i)}\rangle,\lvert b_1^{(i)}\rangle\}$, and single-qubit unitaries $W_{T_j}^{j,x}$ acting on the remaining $q=n-s$ qubits, denoted $T_1,\ldots,T_q$, such that

The equation has a natural branching interpretation (see Figure 4). The fixed basis qubits in $B$ define a common, ordered, branching tree. At stage $i$, the current branch splits according to the value $x_i$ of the $i$th control qubit in its fixed basis. Each leaf, $x\in\{0,1\}^{s}$, then carries the phase $e^{i\theta_x}$ and the target unitary is a tensor product of single-qubit unitaries, $\bigotimes_{j=1}^{q}W_{T_j}^{j,x}$, acting on the remaining qubits.

A unitary can be put in canonical form if it is possible to make a single, consistent choice about which qubits with fixed bases are members of $B$ (and which aren’t), and to specify their fixed bases, phases and tensor products of single-qubit unitaries.

Canonical form and efficient classical simulation

Figure 5 summarizes the simulation argument of the thesis [28] and, anticipating § 5, shows where our counterexample lies in relation to it. Theorem 4.2.5 of the thesis [28] states that each accumulated unitary of a $\mathrm{DQC1}_{\mathrm{sep}}$ circuit must have a separable eigendecomposition. The thesis defines a product control unitary as one implemented by a product control circuit. These circuits are built up, gate by gate, according to specified rules so that each accumulated unitary has a separable eigendecomposition. Theorem 4.3.9 asserts that every $\mathrm{DQC1}_{\mathrm{sep}}$ circuit is a product control circuit.

Taken together, the aforementioned theorems claim that product control circuits are the only type of $\mathrm{DQC1}_{\mathrm{sep}}$ circuit (see Figure 5(a)). In other words, product control circuits exhaustively characterize $\mathrm{DQC1}_{\mathrm{sep}}$ circuits. Theorems 4.4.4 and 4.4.5 are used in the proof of Theorem 4.3.9, and their proofs both contain the necessity claim (see § 5.2) that our counterexample shows is false.

The proof of Theorem 4.3.11 of the thesis [28] contains an efficient classical algorithm that takes a polynomial-size description of a product control circuit as input and outputs a compact representation of its final accumulated unitary in canonical form: the fixed bases, together with a way of efficiently computing, for any control string $x\in\{0,1\}^{s}$, the phase $e^{i\theta_x}$ and the single-qubit unitaries $W_{T_j}^{j,x}$ of Equation (6).

The proof of Theorem 4.3.12 contains an efficient classical algorithm that takes this compact representation as input, uniformly samples the (possibly degenerate) eigenvalues of the final accumulated unitary, and thereby estimates the normalized trace to inverse-polynomial additive accuracy (see Figure 5(b)). All together, this decides any problem in DQC1sep, which is how the thesis concludes that DQC1sep $\subseteq$ BPP.

Proof that the counterexample cannot be put into canonical form

We first determine the fixed-basis qubits of the final accumulated unitary, $C_3$, of our counterexample circuit. We analyze the possible branching structures to rule out every canonical representation. The correctness of this analysis implies that there must be a gap in the proof of Ref. [28]. We identify this as a false necessity condition, and describe how our counterexample evades it.

Fixed bases and noncanonicality

Proof. Unique fixed basis for $a$. By Equation (3), qubit $a$ has a fixed basis, namely the $Z$ basis. Since the two branch unitaries, $C_{3,0}$ and $C_{3,1}$, of Equation (4) are unequal, this basis is unique, up to phases and reordering, which establishes part 1 of the theorem.

No fixed basis for $b$ or $c$. Suppose that qubit $b$ had a fixed basis $\{|e_0\rangle, |e_1\rangle\}$. Then Equation (5) would imply that every eigenvector of $C_3$ has qubit $b$ in $|e_0\rangle$ or $|e_1\rangle$. Because $C_3$ is non-degenerate, its eigenbasis is unique up to phases and reordering. This eigenbasis is shown in Table 1, where $b$ appears in six different states, $|x_+\rangle$, $|y_+\rangle$ and $|z_+\rangle$, rather than in a single orthonormal pair, as is required. Hence, $C_3$ cannot be put into a form in which $b$ has a fixed basis. The same argument applies to qubit $c$. This establishes part 2 of the theorem.

Candidates for $B$. Qubit $a$ is the only qubit with a fixed basis, so either $B=\varnothing$ or $B=\{a\}$ (i.e., either $B$ is empty or it contains qubit $a$).

Canonical form. If $B=\varnothing$, then a canonical representation (Equation (6)) would require that $C_3=e^{i\theta}(W_a\otimes W_b\otimes W_c)$. If $B=\{a\}$, then it would require that $C_3=|0\rangle\langle0|_a\otimes e^{i\theta_0}(W_b^0\otimes W_c^0)+|1\rangle\langle1|_a\otimes e^{i\theta_1}(W_b^1\otimes W_c^1)$.

Implications for the block decomposition. Let us consider the $|0\rangle\langle0|_a$ block of these updated accumulated unitaries. In the former case, it is of the form $e^{i\theta}\,{}_a\langle0|W_a|0\rangle_a(W_b\otimes W_c)$. In the latter case, it is simply $e^{i\theta_0}(W_b^0\otimes W_c^0)$.

Let us proceed to consider the $|0\rangle\langle0|_a\otimes|0\rangle\langle0|_b$ and the $|0\rangle\langle0|_a\otimes|1\rangle\langle1|_b$ blocks. In the former case, they are of the forms $e^{i\theta}\,{}_a\langle0|W_a|0\rangle_a\,{}_b\langle0|W_b|0\rangle_bW_c$ and $e^{i\theta}\,{}_a\langle0|W_a|0\rangle_a\,{}_b\langle1|W_b|1\rangle_bW_c$, respectively. Both are scalar multiples of $W_c$, so they are linearly dependent.

In the latter case, they are of the forms $e^{i\theta_0}\,{}_b\langle0|W_b^0|0\rangle_bW_c^0$ and $e^{i\theta_0}\,{}_b\langle1|W_b^0|1\rangle_bW_c^0$, respectively. Both are scalar multiples of $W_c^0$, so they are linearly dependent.

Finding a contradiction. According to Equations (3) and (4), the $|0\rangle\langle0|_a\otimes|0\rangle\langle0|_b$ block of $C_3$ is $Z_c$, and the $|0\rangle\langle0|_a\otimes|1\rangle\langle1|_b$ block is $(XZ)_c$. Since the former is diagonal and the latter is off-diagonal, they are clearly linearly independent. This is a contradiction with the block decomposition implied by the required canonical form. Hence, $C_3$ cannot be put into canonical form, which establishes part 3 of the theorem.

The false necessity condition in the characterization argument

After $G_2$ has been applied, $b$ has only experienced $\mathbb{I}$ or $X$, and $c$ has only experienced $Z$ or $\mathbb{I}$, depending on $a$. Those alternatives are diagonal in fixed bases but depend nontrivially on another qubit. The thesis [28] calls qubits such as $b$ and $c$ ‘ambiguous.’ Its Theorem 4.4.4 claims to constrain the next two-qubit gate between two such lines, which, in our case, is $G_3$ [29].

Recall that the branch unitaries of $C_2$ are $C_{2,0}=\mathbb{I}_b\otimes Z_c$ and $C_{2,1}=e^{i\pi/4}(X_b\otimes\mathbb{I}_c)$, so the updated branches are $C_{3,x}=G_3C_{2,x}$ for $x\in\{0,1\}$. The proof starts by requiring that in each updated branch (in our notation, $C_{3,x}$), at least one qubit ($b$ or $c$ or both) must have a fixed basis. Importantly, each updated branch can satisfy this requirement in its own way.

The proof proceeds to suppose that the original branches can be written as $C_{2,0}=KQ_0$ and $C_{2,1}=KQ_1$, where $Q_0$ and $Q_1$ are both diagonal in some common product basis. The idea is that since $K$ is a general two-qubit unitary, this product basis does not have to coincide with either the $X$ basis of $b$ or the $Z$ basis of $c$. Substituting this equation for the original branches into the one for the updated branches gives $C_{3,x}=G_3(KQ_x)=(G_3K)Q_x$.

From here, the proof claims that $G_3K$ must have at least one fixed basis (on $b$ or $c$ or both) that coincides with the bases in which $Q_0$ and $Q_1$ are diagonal. However, $G_3K$ has no branch-dependence. Consequently, this requirement implies that the updated branches satisfy this requirement in the same way (namely, that the same qubit has the same fixed basis in both updated branches). Although satisfying the requirement in the same way is sufficient, it is not necessary (see § 3.2 and § 5.1).

How the counterexample evades the claimed necessity

Building on the previous subsection, we now describe how the counterexample circuit evades the claimed necessary condition. If $Q_0$ and $Q_1$ are diagonal in a product basis, then $Q_0^\dagger Q_1$ must also be diagonal in that basis. We can find this basis by evaluating $C_{2,0}^\dagger C_{2,1} = (KQ_0)^\dagger(KQ_1) = Q_0^\dagger Q_1 = e^{i\pi/4}(X_b \otimes Z_c)$, which despite being degenerate necessitates that any product eigenvector must have an $X$ eigenvector on $b$ and a $Z$ eigenvector on $c$. Although this basis did not have to coincide with either the $X$ basis of $b$ or the $Z$ basis of $c$, for our counterexample circuit, it did.

We can now test whether $G_3K$ can be controlled in this basis by seeing if it commutes with $X_b \otimes I_c$ or $I_b \otimes Z_c$. Since $C_{2,0}$, $C_{2,1}$, $Q_0$ and $Q_1$ are all diagonal in the product of the $X$ basis on $b$ and the $Z$ basis on $c$, and $C_{2,x} = KQ_x$, we know that $K$ is also diagonal in this basis. Consequently, $[G_3K, X_b \otimes I_c] = [G_3, X_b \otimes I_c]K$ and $[G_3K, I_b \otimes Z_c] = [G_3, I_b \otimes Z_c]K$. Since $K$ is unitary, $G_3K$ commutes with these operators if and only if $G_3$ does.

Recall that $G_3$ is a CNOT gate with $b$ as the control and $c$ as the target. Direct calculation shows that $G_3$ commutes with neither $X_b \otimes I_c$ nor $I_b \otimes Z_c$. Since $C_3$ nevertheless has a separable eigendecomposition (see § 3.2), this contradicts the necessity conditions asserted in the proof of Theorem 4.4.4 and Case 1 of the proof of Theorem 4.4.5. Our counterexample is therefore not captured by the forms claimed to be exhaustive. The omitted possibility is that the updated branches are basis-controlled in different directions: $C_{3,0}$ in the $Z$ basis of $b$ and $C_{3,1}$ in the $X$ basis of $c$ (see Figure 3).

Uniform families and classical simulation

We first extend the counterexample to a uniform family and prove that every padded member has a noncanonical final register unitary. We then show that it is efficient to classically simulate this family. Finally, we discuss what a repaired simulation argument would need to establish.

A uniform family of counterexamples

Complexity-theoretic statements such as $\mathrm{DQC1}_{\mathrm{sep}} \subseteq\mathrm{BPP}$ concern families of circuits, one for each number $n$ of register qubits, with $n+1$ qubits in each complete DQC1 circuit. A family is uniform if a classical algorithm can output a description of its member indexed by $n$ in time polynomial in $n$. The characterization and canonicalization claims of Ref. [28] are stated for uniform families, so we embed the counterexample in one.

For each $n \ge3$, apply the three gates of § 3.1 to the first three register qubits and leave the other wires untouched. The resulting accumulated unitaries are

Every member is described by the same three gates, so its description can be written down in time polynomial in $n$, and the family is uniform. Putting the eigenbases shown in § 3.2 into a tensor product with the computational basis on the remaining qubits shows that every accumulated unitary has a set of $2^n$ fully separable, orthonormal eigenvectors. Hence every circuit in the family is a $\mathrm{DQC1}_{\mathrm{sep}}$ circuit.

Proof. For $n > 3$, consider one spectator qubit, $l$. Assume, for the sake of contradiction, that $C_3^{(n)} = C_3^{(n-1)} \otimes I_l$ has a canonical representation (see Equation (6)). There are two possibilities, either $l$ is in $C_3^{(n)}$’s set $B$ or it isn’t, and for each of these, we need to ensure that $C_3^{(n-1)}$ can be put into canonical form. If $l \in B$, we can let the first branch of $C_3^{(n)}$ correspond to the two vectors of qubit $l$’s fixed basis, which we could denote $|e_0\rangle_l$ and $|e_1\rangle_l$. Since $C_3^{(n)} = C_3^{(n-1)} \otimes I_l = |e_0\rangle\langle e_0|_l \otimes C_3^{(n-1)} + |e_1\rangle\langle e_1|_l \otimes C_3^{(n-1)}$, either branch gives a canonical representation of $C_3^{(n-1)}$ with $l$ removed from set $B$.

If $l \notin B$, then $l$ is a target qubit. Since each branch acts trivially on $l$, every leaf must have a factor $e^{i\phi_x}I_l$ for some phase $e^{i\phi_x}$. Absorbing $e^{i\phi_x}$ into the existing branch phase and removing $I_l$ from every leaf gives a canonical representation of $C_3^{(n-1)}$ with the same set $B$.

Since a canonical representation for $C_3^{(n)}$ would yield one for $C_3^{(n-1)}$ for all $n > 3$, one can arrive at a canonical representation for the original counterexample accumulated unitary, $C_3$. This would contradict Theorem 1. Therefore, no member of the padded family can be put in canonical form.

Efficient simulation of the counterexample

The counterexample of § 3 has a normalized trace equal to zero. Furthermore, padding preserves the normalized trace:

Consequently, the output distribution of the counterexample circuit can be efficiently classically simulated by a fair coin.

What a repaired simulation argument would require

A repair based on tracking controlled branches must accommodate the possibility identified in § 5.2, namely that the control direction may be different in different branches. The nested description in Figure 3 illustrates this additional freedom, but the example does not establish that such descriptions suffice for every permitted circuit. A general structural repair must cover the separability promise of § 2 at every prefix and prove that the information used by its classical simulator can be obtained from the input circuit with polynomial resources. If it updates that information gate by gate, its representation and update rules must remain valid through every allowed transition, including changes of control direction.

Conclusion and outlook

Aaronson asked whether a quantum computer that is always in a separable mixed state can be simulated by a classical computer in polynomial time [1]. Ref. [27], refined in Ref. [28], argued for an affirmative answer for the one clean qubit model. However, our counterexample is fully separable after every gate even though its final unitary, $C_3$, cannot be put into the canonical form required by that argument. We build on this by pinpointing the gap in this proof. Nevertheless, the properties of our counterexample circuits and the insights gained from this work have not let us answer Aaronson’s question one way or another.

By reopening the one clean qubit case of Aaronson’s semi-grand challenge, we hope to spur further research in this area. Our counterexample had a key property: different branches were controlled in different directions. Theoretically, it would be interesting to study whether this property could be tracked efficiently. Experimentally, the neutral atom systems that were once proposed as promising platforms for realizing one clean qubit protocols [26] have made substantial progress toward scalable fault-tolerant quantum computing [30, 31]. Models of quantum computation related to the one clean qubit model have even been proposed as interfaces to cloud-accessed quantum computers that could limit their cryptanalytic power while still enabling useful scientific applications [18]. We therefore expect that future work, both theoretical and experimental, will be of considerable interest to quantum computing researchers.

Acknowledgments

I would like to acknowledge Leo Ouchi, Mario Duran-Vega, Cuauhtémoc Daniel Suárez Ramírez, Silvia Bergamini and Aleksei Kodukhov for helpful discussions. I acknowledge the use of OpenAI models, especially GPT-6 Astra, and Anthropic’s Claude Opus for assistance, through extensive dialogue, with refining the mathematical arguments, as well as drafting and revising the text and figures. I take full responsibility for the manuscript.

Dedication

I dedicate this work to my late father.

References

Further background on the one clean qubit model

This appendix derives the readout formulas of the one clean qubit protocol for normalized trace estimation (see Figure 1 for the circuit diagram). In the computational basis of the clean qubit, the state of the system after the controlled unitary is

This is the same state as that of the ensemble described in Equation (1). Tracing out the register gives the reduced density matrix of the clean qubit

The expectation values of Pauli measurements of the clean qubit are therefore

Equivalently, the probability of the $\pm1$ outcome in an $X$ measurement is $\frac{1}{2}(1 \pm\operatorname{Re}[\operatorname{Tr}(U)]/2^n)$. For $Y$, it is $\frac{1}{2}(1 \pm\operatorname{Im}[\operatorname{Tr}(U)]/2^n)$. Repeating either measurement polynomially many times estimates the corresponding expectation value to inverse-polynomial additive accuracy with bounded failure probability [28 Section 4.1].

Continuous counterexample

Proof. Interpolating the gates. For $P \in\{X, Z\}$ and $0 \le t \le1$, define

This enables the following continuous gates to be defined.

The paths begin at the identity and end at $G_1$, $G_2$ and $G_3$, respectively. Applying them sequentially gives the accumulated unitary

which, recalling Equation (3), agrees with the accumulated unitaries of the discrete counterexample at integer values of $s$.

During the first two stages (i.e., $0 \le s \le2$), $C(s)$ is diagonal in the tensor product of the $Z$ basis on $a$, the $X$ basis on $b$ and the $Z$ basis on $c$. The accumulated unitary during the final stage (i.e., $2 < s \le3$) can be expressed as

where

The eigenvectors of $C(s)$, for $2 < s \le3$, are shown in Table 2. They form a separable, orthonormal eigenbasis. Crucially, $C(s=3) = C_3$ and by Theorem 1, $C_3$ cannot be put into canonical form.

$a=0$ branch		$a=1$ branch
Eigenvector	Eigenvalue	Eigenvector	Eigenvalue
$|0\rangle|0\rangle|0\rangle$	$1$	$|1\rangle|x_+\rangle|+\rangle$	$e^{i\pi/4}$
$|0\rangle|0\rangle|1\rangle$	$-1$	$|1\rangle|x_-\rangle|+\rangle$	$-e^{i\pi/4}$
$|0\rangle|1\rangle|\widetilde{z}_-\rangle$	$-e^{i\pi t/2}$	$|1\rangle|\widetilde{x}_+\rangle|-\rangle$	$e^{i\pi t/2}e^{i\pi/4}$
$|0\rangle|1\rangle|\widetilde{z}_+\rangle$	$e^{i\pi t/2}$	$|1\rangle|\widetilde{x}_-\rangle|-\rangle$	$-e^{i\pi t/2}e^{i\pi/4}$

Following Section 6 on uniform families, let $C^{(n)}(s)=C(s)\otimes I^{\otimes(n-3)}$. Putting the eigenbases above into a tensor product with the computational basis states on the spectator wires proves full separability throughout every padded implementation.