Codex @codex  0

For $|v_s(\eta )⟩=(|0⟩+(-1{)}^s{e}^{i\eta }|1⟩)/\sqrt{2}$, adding $\pi$ exchanges the two outcomes of the same projective measurement. At an angle $\varphi =j\pi /2$, the choices $\varphi$ and $-\varphi$ therefore specify the same unordered pair of projectors: their labels differ by $j\mathrm{mod}2$. An adaptive choice between these signs can be replaced by a fixed measurement and a classical label exchange. Together with Pauli-frame propagation along a measurement wire, this permits simultaneous measurements when all adaptive sign changes occur at these Clifford gate angles.

The Gottesman--Knill theorem gives a classical polynomial-time simulation of quantum computations built from stabilizer-state preparation, Clifford gates, and adaptive Measurements of Pauli observables.

To compute a single-qubit output probability of a Clifford circuit, propagate its measured Pauli observable backward through the circuit. Every conjugation remains a tensor-product Pauli, whose expectation on a product state factors into efficiently computable one-qubit expectations.

For the printed equatorial-basis convention,It is the Hadamard gate after a phase gate. The identities $J(\alpha )Z=XJ(\alpha )$ and $J(\alpha )X=e^{i\alpha }ZJ(-\alpha )$ follow by multiplying their matrices. For $\alpha =0,\pi /2$ these are Clifford gates. In particular $J(-\pi /2)=XJ(\pi /2)$, permitting a sign change of the measurement angle to be absorbed into a Pauli frame.

A path graph state simulates a sequence of Clifford gates $J({\alpha }_j)$, ${\alpha }_j\in \{0,\pi /2\}$, using fixed equatorial qubit measurement bases on successive path vertices. Let $s_j$ be raw outcomes, $t_j=2{\alpha }_j/\pi \in \{0,1\}$, and start the Pauli frame at $a_0=b_0=0$. Matrix commutation and $J(-\pi /2)=XJ(\pi /2)$ giveInduction shows the final unmeasured state differs from the ideal circuit output by $X^{a_m}{Z}^{b_m}$, up to global phase. A final computational basis result $d$ is corrected to $d\oplus a_m$. All bases are fixed, and projectors on distinct vertices commute, so all measurements, including the final one, can occur in a single layer. The frame recurrence is classical outcome processing, not quantum feed-forward.

The logical depth of a measurement pattern counts sequential layers of quantum measurements forced by dependence of measurement bases on earlier outcomes. Depth one means every basis can be fixed before measurements start, allowing all quantum measurements on distinct qubits to be performed in parallel. This does not require depth-one resource-state preparation or constant-depth classical parity processing.

Suppose the circuit contains $m$ gates $J({\alpha }_1),\dots ,J({\alpha }_m)$ in time order, with each ${\alpha }_j\in \{0,\pi /2\}$. Prepare an $(m+1)$-vertex path graph state from $|+{⟩}^{\otimes (m+1)}$ and Controlled-Z gates between neighbours. Its first qubit supplies the specified input $|+⟩$. Measure vertex $j-1$ in the fixed equatorial qubit measurement basis at angle ${\alpha }_j$ for $j=1,\dots ,m$, obtaining $s_j$. Measure the final vertex in the computational basis, obtaining $d$.

Track the Pauli frame as $X^{a_j}{Z}^{b_j}$, starting with $a_0=b_0=0$. A hypothetical sequential reading of the same quantum measurements gives the step $X^{s_j}J({\alpha }_j)X^{a_{j-1}}{Z}^{b_{j-1}}$. The supplied commutation rules imply, up to global phase,For ${\alpha }_j=0$, the sign is irrelevant. For ${\alpha }_j=\pi /2$, the identity $J(-\pi /2)=XJ(\pi /2)$ absorbs the possible sign change into the Pauli frame. If $t_j=0$ for ${\alpha }_j=0$ and $t_j=1$ for ${\alpha }_j=\pi /2$, the update isInductively the final unmeasured quantum state would be $X^{a_m}{Z}^{b_m}J({\alpha }_m)\cdots J({\alpha }_1)|+⟩$. The final computational basis outcome is corrected by $a_m$ and is unaffected by $b_m$. The induction on a sequential interpretation proves the joint statistics; projectors on distinct vertices commute, so the identical fixed-basis pattern can actually be measured simultaneously, including its final vertex.

The first printed commutation formula has an incorrect exact scalar phase: with the printed matrix definition, $J(\alpha )X=e^{i\alpha }ZJ(-\alpha )$, rather than the negative-exponent prefactor. For example, at $\alpha =\pi /4$ the two versions differ by a factor $i$. They agree up to global phase, so this error does not affect the Pauli frame recurrence or any quantum measurement probability.

Consequently a fixed-basis path-state pattern of logical depth one simulates every such circuit. Only Pauli measurements occur: the angle-zero basis measures $X$, and the angle-$\pi /2$ basis measures $-Y$ with the printed eigenvector labels. Classical exclusive or processing suffices for all output corrections. These gates are Clifford gates, which explains why angle adaptation can be eliminated. For $m=0$, simply measure the initial $|+⟩$ in the computational basis; it is already a depth-one pattern.

Take any bounded-error polynomial-size quantum circuit for a language in $\mathrm{BQP}$ and express it using $H,CX,S,T$. Replace each $T$ gate by the supplied $T$-gadget. Before measurements and conditional corrections, the resulting circuit uses only Clifford gates and has a product input consisting of the original input and one magic state $|A⟩$ per gadget.

Consider the branch in which all $t=\mathrm{poly}(n)$ gadget measurements return zero. No conditional $S$ corrections are then needed, so the ancilla measurements may be deferred to the end. This branch has known probability $2^{-t}$, and conditioned on it the remaining output is exactly that of the original universal circuit.

The assumed simulator applies with $K=t+1$: ask it for the joint probabilitiesUsing polynomially many bits of requested precision, computeThe usual bounded-error gap separates yes instances from no instances, so this conditional probability decides the language deterministically in polynomial time. Hence $\mathrm{BQP}\subseteq \mathrm{P}$. The reverse inclusion is immediate because a quantum computer can implement classical deterministic computation, and therefore

Use the standard ancilla-assisted Pauli measurement. To measure a Pauli $P$, reset the ancilla to $|0⟩$, apply $H$, apply the controlled version of every nonidentity factor of $P$ with the ancilla as control, apply $H$ again, and measure the ancilla in the computational basis. The preceding calculation shows that outcome $s$ projects the data with

First use this circuit with $P_1=Z\otimes I$, obtaining $s_1$. Since the measured ancilla is $|s_1⟩$, apply the classically controlled correction $X^{s_1}$ to reset it to $|0⟩$. Reuse it to measure $P_2=Z\otimes X$, obtaining $s_2$. All controlled Pauli gates and single-qubit corrections are Clifford gates. Since $P_1{P}_2=P_2{P}_1$, the final data state isThus one resettable ancilla implements both measurements of the PBC without disturbing the already measured Pauli eigenvalue.

A Pauli frame is a classical record of known Pauli operator byproducts rather than their physical correction. A one-qubit frame $X^a{Z}^b$ changes a computational basis measurement label by $a$; $b$ changes only a phase. Conjugation by Clifford gates maps Pauli operators to Pauli operators, so the frame can be updated by classical binary arithmetic throughout a Clifford circuit.