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 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.

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 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.

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.

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$.

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.

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$.

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 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.

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.