The Heisenberg Representation of Quantum Computers

• Classical bits are macroscopic 0-or-1 objects, whereas qubits can be superpositions of 0 and 1.Source: §1 · pp. 1–2
• 2^N-dimensional quantum states require 2^N −1 complex numbers for classical description, making quantum systems difficult to represent directly.Source: §1 · p. 2
• Polynomial quantum algorithms may solve problems lacking known polynomial classical algorithms, changing the computational possibilities of physical computers.Source: §1 · p. 2
• Shor’s factoring algorithm [1] finds the period r through a quantum superposition and discrete Fourier transform, yielding polynomial-time factoring where known classical algorithms are exponential.Source: §1 · p. 2
• The difficulty of analyzing quantum gate networks motivates following operator evolution instead of directly tracking states.Source: §1 · pp. 2–3

• Applying U transforms an operator N by conjugation to UNU†, reproducing how N acted before the operation.Source: §2 · p. 3
• Linearity means a spanning set of operators can reconstruct the evolution of the state vector.Source: §2 · p. 3
• The Pauli group contains tensor products of I, X, Y, and Z with overall phases ±1 or ±i.Source: §2 · p. 3
• Multiplicativity allows the evolution of every Pauli-group element to be deduced from the generators {X1, …, Xn, Z1, …, Zn}.Source: §2 · p. 4

3 The Clifford Group

• Restricting gates to those that map Pauli-group elements to Pauli-group elements keeps the operator description manageable.Source: §3 · p. 4
• The Clifford group C is the normalizer of the Pauli group in U(2^n), and is smaller than the full unitary group while containing useful operations.Source: §3 · p. 4
• In CNOT(j → k), qubit j is the control and qubit k is the target; single-qubit gates are denoted R(j) and P(j).Source: §3 · p. 4
• Hadamard, phase, and CNOT gates generate the full Clifford group and have specified transformations on Pauli matrices.Source: §3 · p. 4

• The operator analysis uses the evolution of selected Pauli operators through each gate to determine the circuit’s overall transformation.Source: §4 · p. 5
• Tracking four logical operators reveals that Alice’s three-CNOT network exchanges X1 ↔ X2 and Z1 ↔ Z2, so it swaps the two qubits.Source: §4 · p. 5
• The examples use circuit-analysis diagrams that pair each gate network with the corresponding operator evolution.Source: Figure 1 · p. 6, Figure 2 · p. 7, Figure 3 · p. 7
• Bob can realize CNOT(2 →1) because switching X and Z together with qubits 1 and 2 reproduces the original CNOT transformation.Source: §4 · p. 6
• Analyzing an unfamiliar ancient Hittite gate network yields its final operator transformation, which can then be converted back to the ket formalism by following basis-state eigenvalues.Source: §4 · p. 6

Circuit examples

• The analyzed restricted circuits still swap the first and second qubits, including when two CNOTs require the second input qubit to be |0⟩.The original first qubit migrates to the second, while the overall operation remains a swap.Source: §5 · pp. 8–9

Stabilizer groups

• The stabilizer S is the Abelian group of Pauli operators for which allowed input states are +1 eigenvectors, with k independent generators for k fixed qubits.Its elements have phases ±1 and square to +1, and S is isomorphic to (Z2)^k.Source: §5 · p. 9

Bell states

• Applying the stabilizer analysis to the Bell-state network yields {I ⊗I, X ⊗X, −Y ⊗Y, Z ⊗Z}, whose unique common +1 eigenstate is a Bell state.The state is uniquely characterized, up to normalization, by these stabilizer conditions.Source: §5 · p. 10

Heisenberg analysis

• Following the evolution of 2n generators, {X1, …, Xn, Z1, …, Zn}, determines the behavior of every Pauli-group operator.The stabilizer generators can be exchanged or relabelled without changing the generated group.Source: §5 · p. 10

Scope

• Stabilizer states are completely specified by their stabilizer, although many Hilbert-space states are not stabilizer states.For an incompatible stabilizer containing −Z ⊗Z in the example, the constructed state would be null unless the initial state changed.Source: §5 · p. 10

Bell-state transformations

• A singlet can be produced from the current Bell state by applying an operator such as Y ⊗I that flips the signs of both X ⊗X and Z ⊗Z.More generally, any Pauli operator anticommuting with both stabilizer generators works.Source: §5 · p. 11

Error detection

• Measuring stabilizer generators detects any single-qubit Pauli error because each such error anticommutes with at least one generator and changes its sign.All +1 outcomes indicate no error or at least two errors; general errors are reduced to Pauli errors by measurement.Source: §6 · p. 12

Error-detecting codes

• The four-qubit stabilizer code detects one error and has distance 2, meaning it detects errors affecting fewer than two qubits.The code is completely determined by its stabilizer and is therefore a stabilizer code.Source: §6 · p. 12

Error correction

• To correct a single error, the code must identify which Pauli error occurred and apply its inverse to restore the original state.Distinguishing E|ψ⟩ from F|ψ⟩ reduces to detecting EF|ψ⟩ relative to |ψ⟩.Source: §6 · p. 12

Code distance

• A code correcting t arbitrary errors should have distance 2t + 1, while the smallest one-error-correcting code encodes one qubit in five qubits with distance three.The latter is called a [5, 1, 3] or [[5, 1, 3]] quantum code.Source: §6 · p. 13

Code conditions

• A stabilizer code of distance d requires every Pauli error of weight below d either to anticommute with a stabilizer element or to belong to the stabilizer itself.The latter case defines a degenerate code; otherwise the code is nondegenerate.Source: §6 · p. 13

Fault tolerance

• Quantum error correction allows environmental interactions to be small enough for correction to occur, rather than requiring a quantum computer with essentially no uncontrolled interaction.Logical operators can also be analyzed to perform operations on encoded data without first decoding it.Source: §6 · p. 13

Measurement applications

• The measurement framework also shows how Pauli measurements and corrections can synthesize gates, including a P gate from CNOT, Pauli operations, and measurement.A P† operation is obtained first; applying it three times or applying Z once to the output produces a regular P gate.Source: §7 · p. 14

Measurement update rules

• A −1 measurement result can be corrected by applying M, ensuring the post-measurement state is always the +1 eigenstate of A.The resulting stabilizer contains A, whereas M is removed from the updated stabilizer.Source: §7 · p. 15
• Measurement adds A to the stabilizer and replaces each anticommuting generator N with MN, while commuting generators remain unchanged.The removed generator M is the one that anticommutes with A; this preserves a stabilizer description of the post-measurement state.Source: §7 · p. 15

Quantum teleportation

• In quantum teleportation, Alice and Bob use an EPR pair, local operations, and two classical measurement bits so Bob can apply corrections and recover Alice’s qubit.Measured qubits may be dropped when they are completely determined and never reused; partially entangled measurements require retaining remaining degrees of freedom.Source: §7 · pp. 15, 17

Remote XOR

• A remote XOR uses one shared EPR pair, one local CNOT and measurement per party, and one classical bit in each direction to implement Alice’s CNOT on Bob’s qubit.The Heisenberg analysis is given alongside the network description in Figure 9.Source: §7 · p. 17

Heisenberg representation

• For Clifford networks with Pauli measurements, tracking at most 2n Pauli generators encoded by 2n + 1 bits makes classical time and space polynomial in n rather than exponential.This avoids following the exponentially many coefficients in full state vectors or 2n × 2n unitary matrices.Source: §8 · p. 17

Efficient simulation

• Clifford gates, Pauli measurements, and classically conditioned Clifford operations can be perfectly simulated in polynomial time on a probabilistic classical computer.This is stated as Knill’s theorem and includes conditioning on earlier measurement results.Source: §8 · pp. 17, 19

Universality boundary

• Clifford gates and Pauli measurements are not universal; adding an appropriate non-Clifford gate yields a universal gate set dense in U(2n).Examples of suitable additions include a quantum Toffoli gate, a π/8 rotation, or the square root of controlled-NOT.Source: §8 · p. 19

Applications

• Clifford-only networks remain useful for stabilizer error-correcting codes, quantum teleportation, communication tasks, and subroutines within larger quantum computations.The theorem implies that quantum computational power beyond classical simulation requires gates outside the Clifford group.Source: §8 · p. 19