Quantum circuit

A quantum circuit is a finite composition of quantum gates acting on quantum registers. Reading the diagram from input to output gives the order in which its unitary operations are applied.

For two quantum circuits with corresponding unitary gates, their difference is a sum of terms containing one gate difference and exact or perturbed products on either side. Unitary invariance and the triangle inequality for the operator norm therefore bound the circuit difference by the sum of individual gate errors. Tensoring a gate with an identity leaves that norm unchanged. On a normalized input, the same bound controls the output vector distance with gate phases retained. This is a worst-case coherent bound; cancellation can make a particular circuit less sensitive, but cannot be assumed without further information.

Expand a quantum circuit matrix element by inserting computational basis resolutions between gates, then enumerate the intermediate strings depth first. The active stack stores one basis label and accumulator per quantum circuit layer, using polynomial space for polynomially many qubits and gates. Recompute entries rather than storing an exponential matrix or state vector. The output probability requires the Born rule sum of squared amplitude moduli.

A stoquastic circuit verifier uses reversible classical quantum gates, represented by permutation matrices, with zero and plus-state ancilla qubits and a final Hadamard basis output measurement. A basis input remains an entrywise nonnegative state; a general quantum witness need not be a basis input. The resulting acceptance structure is used in StoqMA.

If the output of a stoquastic circuit is $|0⟩|r_0⟩+|1⟩|r_1⟩$ with nonnegative amplitudes, its plus-outcome probability is $1/2+\mathrm{Re}⟨r_0|r_1⟩\ge 1/2$. Basis quantum witnesses with zero and plus ancilla qubits always have this property. A soundness threshold below one half cannot hold for every such input.

A computational history state coherently records a circuit's intermediate states with orthogonal clock labels: $(T+1{)}^{-1/2}{\sum }_{t=0}^T|{\psi }_t⟩|c_t⟩$. A propagation term penalizes a mismatch between adjacent time labels and the corresponding gate. With correct propagation, uniform coefficients form a zero-energy ground state within the history subspace.

A Feynman-Kitaev Hamiltonian penalizes incorrect input initialization, disagreement between successive quantum circuit steps and clock labels, and optionally a rejecting output. Its propagation quadratic form is a sum of $\frac{1}{2}\Vert {\eta }_t-U_t{\eta }_{t-1}{\Vert }^2$. Without output penalty, its zero-energy space consists of correctly initialized computational history states. A nonlocal quantum clock makes the propagation formula simple but does not supply fixed qubit locality by itself.

After undoing quantum circuit propagation, the Hamiltonian without output penalty is $Q\otimes |0⟩⟨0|+I\otimes E$. The common kernel is the valid input space times the uniform clock vector. On its orthogonal complement, the smallest angle between two subspaces obeys $\cos \vartheta =\sqrt{T/(T+1)}$. The Kitaev geometrical lemma and path gap $2/(T+1{)}^2$ give $\Delta \ge (T+1{)}^{-3}$. Degenerate valid quantum witnesses must be removed together when computing this angle.

The input penalty of a history Hamiltonian tests the prescribed ancilla qubits at clock time zero and leaves the quantum witness unrestricted. Zero ancilla qubits are tested by $|1⟩⟨1|$, and plus ancilla qubits by $|-⟩⟨-|$. Their sum $Q$ is positive and has positive integer eigenvalues. Together with propagation, its kernel selects histories of valid initial data.

A nonlocal quantum clock records quantum circuit time in an abstract $T+1$ dimensional register. A binary encoding uses logarithmically many qubits, but transitions $|t⟩⟨t-1|$ need not have bounded qubit locality. Extra diagonal penalties may exclude unused binary labels. A unary quantum clock provides a different encoding for fixed-locality constructions.

A unary quantum clock represents step $t$ of a $T$-gate circuit by $|1{⟩}^{\otimes t}|0{⟩}^{\otimes (T-t)}$. Clock strings are orthogonal, and adjacent legal strings differ at one qubit. Local patterns around that change permit a history-subspace propagation Hamiltonian with bounded locality.

In the orthonormal history basis $|e_t⟩=|{\psi }_t⟩|c_t⟩$, circuit propagation restricts to $E=\frac{1}{2}{\sum }_{t=1}^T(|e_t⟩-|e_{t-1}⟩)(⟨e_t|-⟨e_{t-1}|)$. This is a graph Laplacian on a path. Its uniform zero-energy vector is the computational history state, while initialization restricts to $D=I-|e_0⟩⟨e_0|$.

For $M(s)=(1-s)D+sE$ in the unary history subspace, the first Gershgorin disc lies in $[0,s]$ and every other disc has real part at least $1-s$. For $s<1/2$, the first disc is isolated and contains the unique ground state energy. Thus the spectral gap is at least $1-2s$, in particular at least $1/3$ for $s\le 1/3$.

For a path with $T+1$ vertices and edge weight $1/2$, the eigenvalues are $1-\cos [\pi k/(T+1)]$, $k=0,\dots ,T$. The corresponding coefficients are proportional to $\cos [\pi k(t+1/2)/(T+1)]$. The zero mode is uniform, and the spectral gap is at least $2/(T+1{)}^2$. The endpoint difference equations use reflecting ghost values, not periodic ones.

A unitary operation on a fixed number of qubits used as a component of a quantum circuit. Examples include the Hadamard gate and Controlled-Z gate. Measurements are described separately by quantum measurement; a gate is a reversible operation on its full input state.

A unitary gate on two quantum systems is entangling if it maps at least one pure state that is a product state to an entangled state. The controlled-NOT gate qualifies because it maps $|+⟩|0⟩$ to a Bell state. A gate that merely exchanges the two systems need not be a local unitary operation, but cannot create quantum entanglement from a product state.

For two $d$-dimensional unitary matrices, this normalized absolute trace lies in $[0,1]$ and equals one exactly when $V=e^{i\gamma }U$. The triangle inequality on the eigenphases of $U^{†}V$ proves both statements. It ignores an overall global phase and compares complete propagators. It is not the same definition as average gate fidelity; for unitary implementations that latter quantity is $(d{\mathcal{F}}^2+1)/(d+1)$.

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.

Apply a controlled-NOT gate from data $a|0⟩+b|1⟩$ to the resource $|A⟩$, then measure the resource in the standard basis. Outcome zero leaves data $T|\psi ⟩$; outcome one leaves $e^{i\pi /4}{T}^{†}|\psi ⟩$. Both outcomes have probability $1/2$. Correct outcome one with $S$, using $S{T}^{†}=T$, so the data has undergone the T gate irrespective of the measurement result. The resource is consumed, and its Bloch vector lies outside the stabilizer octahedron.

A two-qubit gate is a unitary operator on two qubit lines, extended by the identity on the others. It may be entangling, as a CNOT gate is, or a product of local operations. In a Hamiltonian simulation model allowing arbitrary two-qubit gates, the exponential of a Hermitian term supported on two lines counts as one such gate. Compiling it into a fixed discrete universal quantum gate set introduces a separate approximation cost.

A two-qubit gate in which an interaction shifts the energy of a selected joint computational basis state and thereby accumulates a relative quantum phase. With Hamiltonian operator $H=\Omega |01⟩⟨01|$, where $\Omega$ has units of energy, an interaction time $\tau$ gives $U_{\varphi }=\mathrm{diag}(1,e^{-i\varphi },1,1)$ with $\varphi =\Omega \tau /\hslash$. The selected basis state is part of the convention: this gate differs from the usual Controlled-Z gate at $\varphi =\pi$. Conjugation by a Pauli X gate on the first qubit gives $(X\otimes I)U_{\pi }(X\otimes I)=\mathrm{CZ}$, because the conjugation interchanges $|01⟩$ and $|11⟩$.

A diagonal two-qubit gate with entries $e^{i{\varphi }_{jk}}$ is a product of local diagonal gates, up to global phase, exactly when $\delta =0$ modulo $2\pi$. This follows by factoring the two-by-two array of phases; its determinant vanishes precisely in that case. If the determinant is nonzero, applying the gate to $|+⟩\otimes |+⟩$ produces an entangled state by the two-qubit product-state determinant criterion. In particular $\mathrm{diag}(-1,1,1,-1)=-Z\otimes Z$ is local, whereas $\mathrm{diag}(1,1,1,-1)$ is the entangling Controlled-Z gate.

Every two-qubit gate has the displayed form with local elements of the special unitary group and real interaction parameters. The three Pauli-product generators commute, so the central exponential is the product of three interactions. Local basis changes turn an Ising coupling into either of the other Pauli-product couplings. A fixed entangling controlled phase together with arbitrary local rotations can also synthesize each variable interaction, for example through two CNOT gates enclosing a variable $z$ rotation.

Measurement-based quantum computation prepares an entangled resource quantum state, then applies single-qubit quantum measurements, potentially adapting later bases to earlier outcomes. Pauli frame tracking and classical outcome processing convert random physical branches into a specified logical computation. Graph states and one-bit teleportation provide a concrete construction.

A path graph state on three qubits simulates two successive gates $U(\theta )=H\mathrm{diag}(1,e^{-i\theta })=J(-\theta )$. Measure vertex one in the equatorial qubit measurement basis $|v_r(\alpha )⟩=(|0⟩+(-1{)}^r{e}^{i\alpha }|1⟩)/\sqrt{2}$, then vertex two at angle $(-1{)}^r\beta$, obtaining bits $r,s$. Two one-bit teleportations and $U(\theta )X=e^{-i\theta }ZU(-\theta )$ leave vertex three in $X^s{Z}^{r}U(\beta )U(\alpha )|+⟩$, up to global phase. A computational output bit $z$ is corrected to $z\oplus s$; the $Z$ factor affects only phase. Adaptive sign choice is required for general angles, although the final bit correction is purely classical.

A graph state with edges $13,24,34,45$ simulates $J_2(\gamma )E_{12}(J_1(\alpha )\otimes J_2(\beta ))$ on $|++⟩$. Measure vertices 1 and 2 at angles $\alpha ,\beta$, with results $s_1,s_2$, and vertex 4 at $(-1{)}^{s_2}\gamma$, with result $s_4$. One-bit teleportation and Pauli frame propagation leave output frames $X_3^{s_1}{Z}_3^{s_2}$ and $X_5^{s_4\oplus s_1}{Z}_5^{s_2}$. Computational outputs are therefore corrected by $s_1$ and $s_4\oplus s_1$ respectively.

Label a four-cycle $0-1-2-3-0$. Measure vertex $0$ in the computational basis with result $r$, then vertex $1$ in the equatorial qubit measurement basis at angle $\alpha$ with result $s$. Graph-state vertex deletion and one-bit teleportation leaveFinal computational basis measurements with raw results $d_2,d_3$ therefore simulate the ideal circuit $E_{23}J(\alpha {)}_2$ on $|++⟩$ after the classical correction $k=d_2\oplus r\oplus s$, $l=d_3$. The output probability distribution is correct in every prior branch; no physical Pauli frame correction is needed.

A measurement pattern specifies the resource quantum state, the measured qubits, their measurement bases, outcome-dependent basis choices and output corrections or classical relabellings. The dependence of a basis on earlier outcomes determines the logical depth of a measurement pattern. Preparing the resource and processing the final classical results are separate costs.

Logical measurement depth is the number of sequential measurement layers required by outcome-dependent basis choices. Depth one means all bases are fixed in advance, so the quantum measurements on distinct qubits can be simultaneous. Classical output corrections may still depend on all outcomes. This does not assert depth-one graph-state preparation or constant-depth classical processing.

An $R(\alpha )=J(\alpha )J(0)$ gadget with input Pauli frame $X^p{Z}^q$, angle-zero outcome $s$, and arbitrary-angle outcome $t$ uses angle $(-1{)}^{s\oplus q}\alpha$ and produces frame $X^{p\oplus t}{Z}^{q\oplus s}$. The CNOT gate gadget also updates its $Z$ frames without any dependence on incoming $X$ frames. Therefore all adaptive angle signs depend solely on angle-zero outcomes. Measure all those vertices first, compute every sign, and measure all remaining vertices in a second layer. The result is the desired logical circuit in a known Pauli frame. Computational output measurements can share the second layer.

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.

Compile each CNOT gate into a Hadamard gate, a Controlled-Z gate, and another Hadamard gate on its target. Every one-bit teleportation implementing a Hadamard gate uses a fixed angle-zero basis. A Pauli frame propagates by classical binary updates without changing a measurement basis. All internal measurements, and any fixed computational output measurements, therefore share one simultaneous layer. Resource preparation and classical processing are not included in this logical measurement depth.

A quantum register is a named tensor product factor of a quantum circuit's Hilbert space, usually a collection of qubits. Registers separate data, control, output and workspace roles; uncomputation returns workspace to a fixed quantum state without destroying coherence in the data.

A one-qubit rotation gate is $R_{\alpha }(\theta )=e^{-i\theta {\sigma }_{\alpha }/2}$, where ${\sigma }_{\alpha }$ is a Pauli matrix. It rotates the Bloch vector by angle $\theta$ about the corresponding axis.

For chronological equatorial rotations $R_{\varphi }(\pi )R_{2\varphi }(\pi )R_{\varphi }(\pi )$, the ideal propagator is $iX$. If all pulse angles have the same fractional error $ϵ$, choose $\cos \varphi =-1/2$ to cancel the quadratic term of the trace-overlap gate fidelity. With $x=\pi ϵ/2$, its exact fidelity is $|\cos x(1+{\sin }^{2}x/2)|$, whose leading infidelity is $3x^4/8$. This correction compensates a systematic amplitude error, not arbitrary axis or timing errors.

The rotation gate about the Pauli X gate axis commutes with $X$. The J gate convention gives $J(\alpha )J(0)=H\mathrm{diag}(1,e^{i\alpha })H=e^{i\alpha /2}{R}_x(\alpha )$, differing from the standard axis rotation only by global phase.

The one-qubit rotation gatesatisfies $R_y(2\theta )|0⟩=\cos \theta |0⟩+\sin \theta |1⟩$ and $R_y(\alpha )R_y(\beta )=R_y(\alpha +\beta )$. The latter identity enables a binary-angle implementation of a quantum variable rotation.

The one-qubit rotation gate is $R_z(\theta )=\mathrm{diag}(e^{-i\theta /2},e^{i\theta /2})$. It implements the two relative phases needed in simulation of a computable diagonal Hamiltonian.

A universal quantum gate set can approximate every finite-qubit unitary operator arbitrarily accurately using finite circuits over the set.

Universality is a property of a set of quantum logic gates: finite circuits from the set approximate arbitrary unitary transformations.

If every generator of a universal quantum gate set has an exact finite implementation over another set, the latter is also universal. For a target unitary and tolerance $\epsilon >0$, first choose an approximating circuit over the universal set, then replace each generator by its exact implementation. The compiled circuit has the same operator and therefore the same approximation error. Overall global phases can be ignored under the usual physically projective convention. Exact synthesis of an already universal family is sufficient; it does not imply exact synthesis of every possible unitary with a finite alphabet of gates.

The largest pure-state norm distance between outputs of two unitary operators on the same normalized input. By definition of the operator norm, it is ${\sup }_{\Vert \psi {\Vert }_2=1}\Vert (U-V)|\psi ⟩{\Vert }_2$. If it is at most $\epsilon$, every input is approximated to that accuracy. A version disregarding the operation's global phase minimizes $\Vert U-e^{i\gamma }V{\Vert }_{\mathrm{op}}$ over one common $\gamma$. Error in a finite quantum circuit accumulates at most additively by the quantum circuit gate-error telescoping bound.

For a suitable finite inverse-closed universal quantum gate set, the Solovay--Kitaev theorem approximates a fixed-dimensional unitary to operator norm error $\epsilon$ with a gate sequence of length polynomial in $\log (1/\epsilon )$.

Quantum state preparation constructs a circuit $B$ that maps a simple reference state to a desired state, $B|0^n⟩=|\psi ⟩$. Efficient amplitude encoding requires structure or suitable oracle access to avoid reading exponentially many arbitrary amplitudes.

For a semiprime $N=pq$ with distinct known primes, this quantum state is uniform over the reduced residue classes. With $n$ binary digits in $N$, its fraction among all $2^n$ computational labels is $a=(p-1)(q-1)/2^n\ge 1/4$. An ancilla qubit whose one probability is $1/(4a)$ dilutes the joint good probability to exactly $1/4$. A reversible range-and-greatest common divisor predicate marks the good labels with ancilla qubit one, and a single exact amplitude amplification iteration produces $|{\xi }_N⟩|1⟩$. Known prime factors provide the cardinality; the membership test itself needs only $N$. Polynomial gate complexity presumes ideal one-qubit rotations at the specified amplitudes.

In an $N$-dimensional computational basis, the uniform superposition state isMeasurement in that basis gives the uniform distribution on a finite set. For $N=2^n$, Hadamard gates prepare it from $|0^n⟩$. Its reflection $2|s_N⟩⟨s_N|-I$ is a Grover diffusion operator.

Hierarchical probability-distribution state preparation recursively bisects a classical probability distribution. At each level, a controlled rotation splits every parent interval's amplitude between its two children according to their conditional probabilities.

Quantum arithmetic implements a classical numerical function reversibly on computational-basis registers and therefore coherently on their superpositions. Temporary work values must be uncomputed to avoid unwanted entanglement.

The $n$-qubit Pauli group consists of tensor products of $I,X,Y,Z$ multiplied by phases $\pm 1$ or $\pm i$.

For tensor products of Pauli factors from $\{I,X,Y,Z\}$, let $k$ count the sites where both factors are nonidentity and different. Distinct nonidentity Pauli matrices anticommute, and equal or identity factors commute. Reversing the product site by site therefore gives $PQ=(-1{)}^{k}QP$. Thus two Pauli strings commute exactly when $k$ is even. The criterion applies to the perfect-correlation observables in the GHZ theorem.

Store a Pauli group element with binary exponents $a_j,b_j$ and a phase exponent $s$ modulo four. This ordered $XZ$ convention uses $2n+2$ bits for $n$ qubits. Since $XZ=-iY$, phase factors are essential when converting to Hermitian Pauli operators and evaluating measurement probabilities.

Modulo scalar phases, the n-qubit Pauli group is the additive space ${\mathbb{F}}_2^{2n}$, with label $(a,b)$ for $X^a{Z}^b$. Multiplication adds labels, and commutation contributes the sign $(-1{)}^{\omega }$. The displayed alternating form is nondegenerate. An isotropic subspace $L$ satisfies $L\subseteq L^{\perp }$, hence $\dim L\le n$; it labels commuting stabilizers.

A subspace $L$ is isotropic when the symplectic pairing vanishes between every pair of its vectors. Its binary Pauli labels therefore commute. Nondegeneracy identifies the ambient space with its dual, so the map to $L^{\ast }$ is surjective and $\dim L^{\perp }=2n-\dim L$. Since $L\subseteq L^{\perp }$, it follows that $\dim L\le n$. This explains the maximum number of independent generators of a stabilizer group.

Conjugation by a Controlled-Z gate leaves the $a$ bits unchanged and updates the displayed $b$ bits and phase, using the old bits. The phase occurs when the extra $Z$ from one line is moved past $X$ on the other line. These constant-size updates support Heisenberg propagation of a Pauli observable through a Clifford circuit.

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.

An $n$-qubit Pauli operator is a tensor product of single-qubit Pauli matrices, possibly multiplied by a phase. Hermitian Pauli operators have eigenvalues $+1$ and $-1$.

One of the six pure single-qubit eigenstates of $X,Y,Z$. Their Bloch vectors are the six coordinate unit vectors with both signs. Their convex hull is the stabilizer octahedron.

The two eigenstate rays of the Pauli Y gate have the displayed normalized representatives and respective eigenvalues $+1$ and $-1$. They form an orthonormal basis. Multiplication by $Y$ changes only the global phase of each of these states; it does not exchange their eigenvalue labels.

Every linear map from a qubit into the tensor product of that qubit and an environment can be expanded in the Pauli matrix orthonormal basis of operators. If $V|0⟩=|0⟩|e_{00}⟩+|1⟩|e_{01}⟩$ and $V|1⟩=|0⟩|e_{10}⟩+|1⟩|e_{11}⟩$, then the four coefficient vectors areThese environment vectors need not be orthogonal, so this is an operator expansion rather than a claim that the quantum channel is a classical Pauli channel. Physical isometries additionally preserve the inner products of the two input basis states.

The weight of a tensor-product Pauli operator is the number of nonidentity local factors; its global phase is ignored. Products satisfy $\mathrm{wt}(P^{†}Q)\le \mathrm{wt}(P)+\mathrm{wt}(Q)$ because their support is contained in the union of the two supports. The quantum code distance uses this weight to measure the smallest undetectable nontrivial action on logical information.

The tensor products of single-qubit Pauli matrices form an orthogonal basis of the operator space on $n$ qubits, so every linear error operator has a Pauli expansion. Using $X^a{Z}^b$, with scalar phases absorbed into the coefficients, its computational basis action is $E|x⟩={\sum }_{a,b}{c}_{a,b}(-1{)}^{b\cdot x}|x+a⟩$, with binary arithmetic. This describes coherent errors as well as individual Pauli errors; it does not assume that the noise is a probabilistic Pauli channel. A physical noise map has Kraus operators of this form when the usual quantum channel description applies, for instance when the initial system and environment are uncorrelated.

A Pauli gate applies a Pauli matrix as a unitary operator to a qubit. The Pauli X gate, Pauli Y gate and Pauli Z gate are common correction operations in quantum teleportation.

A Pauli correlator is the expectation value of a tensor product of Pauli matrices, such as $⟨X\otimes Z⟩$. It measures a specified correlation between qubit observables.

A stabilizer group is an abelian subgroup of the Pauli group that does not contain $-I$. Its simultaneous positive eigenspace is its stabilizer subspace.

A stabilizer group excludes $-I$, so each element squares to $I$ and is Hermitian; an imaginary-phase Pauli element would square to $-I$. A nonidentity stabilizer contains at least one nonidentity local Pauli matrix and has zero trace, since the trace of a tensor product is the product of local traces. Its eigenvalues are therefore $\pm 1$ with equal multiplicities. This trace fact also gives $\dim {\mathcal{X}}_S=2^n/|S|$ from the stabilizer-projector formula.

A set of stabilizer generators is an independent commuting family of Hermitian Pauli operators whose products form a stabilizer group.

A stabilizer state on $n$ qubits is the unique simultaneous positive eigenstate of a stabilizer group with $n$ independent generators.

Stabilizer-state preparation starts from a computational-basis state and applies a Clifford circuit, producing a stabilizer state.

A stabilizer tableau represents each Pauli generator by a binary row $[x_1\cdots x_n\mid z_1\cdots z_n]$, with one additional bit when its sign is retained. Clifford gates update these rows by arithmetic over ${\mathbb{F}}_2$.

For an undirected graph $G=(V,E)$, the graph state is

Let $1$ be a leaf with neighbour $2$ and let the graph on the other vertices be generated by the Controlled-Z gate product $E_{\mathrm{rest}}$. If the leaf has Pauli Z gate frame $Z_1^r$, measuring it at angle $\alpha$ with result $s$ applies one-bit teleportation and leavesAny known Pauli Z gate frames on other vertices remain as additional factors before those vertices' input states. The identity $J(\alpha )Z^r=X^{r}J(\alpha )$ combines the leaf byproduct with the measurement result.

For a graph state $|G⟩={\prod }_{ij\in E}C{Z}_{ij}|+{⟩}^{\otimes |V|}$, measuring vertex $v$ in the computational basis with result $r$ gives the normalized stateEach Controlled-Z gate from $v$ to a neighbour acts as $Z_u^r$ after projecting $v$ onto $|r⟩$; all other edges remain unchanged. The projection contributes $1/\sqrt{2}$, so either result has probability $1/2$. For a four-cycle, deleting one vertex leaves a path and adds byproducts on its two endpoints.

The graph-state stabilizer generator at vertex $v$ is $S_v=X_v{\prod }_{u\in N(v)}{Z}_u$. Two such generators commute because adjacent vertices contribute two Pauli anticommutations and nonadjacent vertices contribute none.

Local complementation at a vertex $v$ toggles every edge between neighbors of $v$. It is implemented on graph states, up to global phase, by the local Clifford operator

The stabilizer subspace of a commuting family $S$ of Hermitian Pauli operators isIf there are $r$ independent generators on $n$ qubits, its dimension is $2^{n-r}$.

For a stabilizer group $G=⟨g_1,\dots ,g_l⟩$, the orthogonal projector onto its stabilizer subspace is

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.

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]

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.

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.

The extended Gottesman--Knill theorem allows arbitrary product-state inputs to a unitary Clifford circuit. Computational-basis output is weakly simulable for any number of measured qubits and strongly simulable for logarithmically many measured qubits.

A Clifford frame records a known Clifford transformation classically instead of applying it physically. Updating the frame changes the Pauli observables used for later measurements while preserving the represented quantum computation.

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 strong classical simulation computes a quantum circuit's specified output probabilities in classical polynomial time to the requested polynomial precision. This is stronger than weak simulation, which only samples from the output distribution.

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 binary phase representation of a Pauli string, these local rules implement $P\mapsto U^{†}PU$ for the Hadamard gate and the phase gate $S=\mathrm{diag}(1,i)$. In particular $S^{†}XS=-iXZ$, so the phase update differs in sign from forward conjugation. Use the old input bits, and reduce $s$ modulo four.

A weak classical simulation samples in classical polynomial time from the output distribution of a quantum circuit, exactly or within a prescribed small total-variation distance.