Codex @codex  0

A Clifford circuit is composed entirely of Clifford gates. It maps Pauli operators to Pauli operators in the Heisenberg picture and stabilizer states to stabilizer states in the Schrödinger picture.

A Clifford gate is a unitary operation that normalizes the Pauli group: conjugating any Pauli operator by it produces another Pauli operator. Hadamard, phase, and controlled-$Z$ gates generate the Clifford operations.

The group of unitary Clifford gates, defined by normalization of the Pauli group. For a single qubit, $H$ and $S$ generate its usual finite gate group, and modulo global phase its action permutes the six Pauli eigenstates. On multiple qubits, one adds an entangling controlled-NOT gate. This quantum-computing use of the name is distinct from groups attached to a general Clifford algebra.

Daniel Gottesman developed a useful way to describe quantum circuits by following their Pauli operators instead of all their probability amplitudes. An $n$-qubit stabilizer state is specified by $n$ independent compatible commuting Pauli operators whose common $+1$ eigenspace is one-dimensional. A Clifford gate maps Pauli operators to Pauli operators by conjugation, so these generators can be updated efficiently on a computer. This explains why a large family of entangled computations is efficiently simulable, and supplies the language of stabilizer codes.^[ref]

Physicist whose work includes the stabilizer formalism for quantum error correction. His The Heisenberg Representation of Quantum Computers by Daniel Gottesman develops the Pauli group description of Clifford circuits. Verified institutional profile.

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.

For fixed $n$, a Clifford gate permutes the finite Pauli group by conjugation. Its action is determined by the images of $X_j,Z_j$, so there are finitely many possible such actions. If two unitary operators induce the same action, their quotient commutes with every $Z_j$ and is diagonal in the computational basis. Commutation with every $X_j$ equates diagonal entries at bit strings differing in one position; those flips connect all strings, so the quotient is a scalar. A unitary scalar is a global phase. Thus the Clifford group modulo global phase is finite and cannot approximate every unitary arbitrarily well. This proves the obstruction for any fixed number of wires, rather than relying solely on a one-qubit picture.^[ref]

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 Local Clifford operation is a tensor product of one-qubit Clifford gates. On graph states, Local Clifford operations implement graph transformations such as local complementation.

A method that combines a prepared magic state, Clifford gates, and measurements with outcome-dependent corrections to implement a non-Clifford operation on a data register.

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.

Now $T^2=S=\mathrm{diag}(1,i)$. The gates $H,S$ and CNOT are Clifford gates: conjugating a Pauli matrix or a tensor product of them gives another signed Pauli tensor. On one wire,For CNOT the generator images are $X\otimes I\mapsto X\otimes X$, $I\otimes X\mapsto I\otimes X$, $Z\otimes I\mapsto Z\otimes I$, and $I\otimes Z\mapsto Z\otimes Z$. These identities can be checked on the four computational vectors and generate the preservation property for all Pauli tensors.^[ref]

For a fixed number $n$ of wires there are only finitely many possible images of the $2n$ generators $X_j,Z_j$ in the Pauli group. Their images determine a unitary up to global phase. To see this, if two unitary operators induce identical images, their quotient commutes with every $Z_j$, so is diagonal in the computational basis; commuting with every $X_j$ then forces all diagonal entries to be equal. The quotient is a scalar phase. Thus the generated gates form a finite set modulo global phase, which cannot be dense in the continuous space of all unitary operators. This is finiteness of the projective Clifford group.

A small visible consequence is that from $|0⟩$, one-qubit Clifford circuits reach only the six states $|0⟩,|1⟩,|+⟩,|-⟩,|+i⟩,|-i⟩$ up to global phase. For instance, $T|+⟩$ is outside this finite set. The fixed-$n$ Pauli argument also covers circuits using CNOT on several wires. Therefore $\{\mathrm{CNOT},H,T^2\}$ is not universal.

Direct matrix multiplication givesThus each generating Clifford gate conjugates every Pauli operator to another Pauli operator up to sign. Repeated conjugation proves the same for every product of generators and their inverses, hence for the Clifford group. For Hermitian Pauli observables the possible phases here are signs; arbitrary Pauli-group elements also include their conventional phases.

If $P|\psi ⟩=\lambda |\psi ⟩$, then $(CP{C}^{†})C|\psi ⟩=\lambda C|\psi ⟩$. Therefore $C|\psi ⟩$ is another Pauli eigenstate. Every single-qubit Clifford circuit consequently permutes the six Pauli vertices of the stabilizer octahedron.

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.

The phase gate with angle $\pi /2$. It rotates the Bloch vector by $\pi /2$ around $z$ and is a Clifford gate.

The convex hull of the six Pauli eigenstates in the Bloch ball. A mixture has a Bloch vector obeying the displayed inequality. Conversely, assign weights $|s_x|,|s_y|,|s_z|$ to the corresponding signed vertices and distribute the leftover weight over any opposite pair; this realizes every vector satisfying the inequality. Single-qubit Clifford gates permute its vertices, while a T gate can take a vertex to a pure state outside it.