Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond

M. Van den Nest

Source-linked AI summary

Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond

M. Van den Nest

arXiv:0811.0898v2Nov 6, 2008quant-ph

TL;DR

The paper asks how classical simulation of quantum computation can be understood beyond the Gottesman-Knill theorem. It reduces Clifford circuits to an equivalent normal form and uses this structure to study extensions. The resulting circuits can be weakly simulated efficiently even though strong simulation is #P-complete, separating the two notions.

Problem
The paper examines classical simulation of quantum computation and the limited computational power of Clifford circuits despite their high entangling power.
Method
The paper efficiently reduces each Clifford circuit to an equivalent normal form and uses that form to analyze simulation and extensions beyond Clifford circuits.
Results
The studied extensions are efficiently weakly simulatable by classical sampling, while strong simulation of their output probabilities is #P-complete.
Takeaways & Limitations
The results establish a separation between weak and strong classical simulation and connect Clifford simulation with the standard embedding of classical computation into quantum circuits.
Takeaways & Limitations
The simulation statements use the standard input |0⟩, while the paper notes that other product eigenstate inputs can be locally rotated into this state.

Abstract

from arXiv · show

We study classical simulation of quantum computation, taking the Gottesman-Knill theorem as a starting point. We show how each Clifford circuit can be reduced to an equivalent, manifestly simulatable circuit (normal form). This provides a simple proof of the Gottesman-Knill theorem without resorting to stabilizer techniques. The normal form highlights why Clifford circuits have such limited computational power in spite of their high entangling power. At the same time, the normal form shows how the classical simulation of Clifford circuits fits into the standard way of embedding classical computation into the quantum circuit model. This leads to simple extensions of Clifford circuits which are classically simulatable. These circuits can be efficiently simulated by classical sampling ('weak simulation') even though the problem of exactly computing the outcomes of measurements for these circuits ('strong simulation') is proved to be #P-complete--thus showing that there is a separation between weak and strong classical simulation of quantum computation.

1 Introduction

The paper examines why Clifford circuits are efficiently classically simulatable despite generating substantial entanglement, and develops a normal-form perspective on their limited computational power. It also distinguishes weak from strong simulation and presents circuits separating the two notions.

Clifford circuits use Hadamard, PHASE, and CNOT gates and can be efficiently simulated classically when initialized in |0⟩ and measured computationally.
Efficient classical simulability does not prevent Clifford circuits from generating highly entangled states, so entanglement alone is not sufficient for quantum computational speed-up.
Clifford circuits can be simulated using only NOT and CNOT gates, placing their classical computational power in ⊕L rather than the full power of classical computation.
The paper reduces each Clifford circuit to an equivalent, manifestly simulatable normal form and uses it to explain the circuits' limited computational power and relation to classical computation.
The paper distinguishes strong simulation, which computes output probabilities, from weak simulation, which samples from the output distribution.
For the paper's extensions, weak simulation is efficient while strong simulation is #P-complete, establishing a separation between the two simulation notions.

2 Classical simulation of quantum computation

This section separates classical simulation into strong probability computation and weak distribution sampling, while noting that prior work has focused mainly on strong simulation.

Strong simulation evaluates measurement probabilities to high accuracy in polynomial time in the circuit size and requested precision.
Most prior classical-simulation results, including Gottesman-Knill and matchgate methods, concern strong rather than weak simulation.

3 The Gottesman-Knill theorem

The section states the Gottesman-Knill theorem and situates it within stabilizer-based proofs and the ⊕L complexity class. It also notes the paper's alternative proof strategy and the sampling convention used for circuits.

Every uniform Clifford-circuit family acting on |0⟩ and followed by a first-qubit Z measurement can be efficiently simulated classically in the strong sense.
The standard proof uses stabilizer groups, whereas the paper provides an alternative proof that does not use stabilizer techniques.
The paper treats quantum circuits as uniform families and notes that simulation generally permits sufficiently accurate sampling rather than requiring exact equality of distributions.
The GOTTESMAN-KNILL decision problem is ⊕L-complete under logarithmic-space reductions, linking Clifford simulation to NOT-CNOT circuit computation.
Problems such as solving linear equations and multiplying matrices over Z2 are associated with the ⊕L class.

4 Embedding classical in quantum computation

HT circuits embed probabilistic classical computation into quantum circuits by applying Hadamards followed by classical gates. They support efficient weak simulation, whereas strong simulation is #P-complete.

HT circuits: HT circuits apply Hadamard gates to a subset of qubits, followed by a circuit of classical gates such as NOT, CNOT, and Toffoli.Classical gates map computational basis states to computational basis states.
Classical computation embedded in quantum circuits: Every probabilistic classical computation can be represented by an HT circuit acting on the all-zero input and followed by a single-qubit computational-basis measurement.
Consequences: Thus HT circuits have the computational power of probabilistic classical computation while separating efficient weak simulation from efficient strong simulation.
Weak simulation: HT circuits can be weakly simulated efficiently by sampling a uniformly random input string, computing the classical function, and outputting its first bit.The resulting bit has the same probability distribution as the quantum measurement outcome.
Strong simulation: Strong simulation of HT circuits is #P-complete because exact measurement probabilities encode counting problems in #P.Computing the probabilities exactly is at least #P-hard, and the paper concludes #P-completeness.

5 Clifford circuits as HT circuits

Each Clifford circuit can be reduced to a normal form whose state amplitudes are supported on an affine subspace with efficiently computable phase functions. This form yields efficient weak and strong classical simulation.

Normal form: Each Clifford circuit can be reduced, modulo redundant phases, to an equivalent HT circuit that is manifestly classically simulatable.The reduction provides an alternative proof of the Gottesman-Knill theorem without stabilizer techniques.
State representation: A Clifford output state has amplitudes supported on an affine subspace A, with linear and quadratic phase functions that can all be computed efficiently.The affine subspace, linear phase, and quadratic phase jointly describe the general state form produced from |0⟩ by Clifford circuits.
State representation: The state representation is preserved inductively when applying H, PHASE, or CNOT gates, allowing A, l, and q to be updated sequentially through the circuit.
Weak simulation: Sampling a uniformly random m-bit string u, computing Ru + t, and reading the first bit gives an efficient weak simulation of Clifford measurements.
Strong simulation: Clifford measurement probabilities have the form 2^-γ, where γ is obtained by solving linear equations over Z2, so strong simulation is efficient as well.

6 Normal form

The paper reduces each Clifford circuit’s action on |0⟩ to an efficiently computable three-round normal form, exposing a simple classical simulation structure. The form preserves the output state, not generally the entire unitary circuit, and extends to a matrix-level decomposition with one Hadamard round.

State normal form: Theorem 2 gives an efficiently computable circuit C′ with C|0⟩=C′|0⟩, consisting of Hadamard, NOT/CNOT, and PHASE/CPHASE rounds.The normal form is a Clifford circuit, but equivalence is guaranteed only on the standard input state.
Scope of equivalence: The reduction preserves the output state for |0⟩ but generally does not preserve equality as 2^N × 2^N matrices.The relevant object for computational-basis output is the single column corresponding to C|0⟩.
Interpretation: The normal form maps distributed Hadamard operations and interference into a superposition followed by NOT and CNOT gates, making the circuit’s classical weakness explicit.This also connects the simulation to the ⊕L characterization of NOT/CNOT computation.
Matrix normal form: Every n-qubit Clifford operation has the matrix-level form C ∝ M2HM1, where M1 and M2 use CNOT, PHASE, and CPHASE gates and H is a single tensor product of Hadamards.All three components can be determined efficiently and have polynomial size.
State normal form: The first two rounds of C′ form a restricted HT circuit, while the final diagonal round is invisible to computational-basis measurement.Thus the measured output can be simulated using the Hadamard and classical-gate portion alone.

7 Slightly beyond Gottesman-Knill

The paper extends Gottesman–Knill with circuits that remain efficiently weakly simulatable while encompassing Clifford-generated states and full probabilistic classical computation.

Significance: These extensions can efficiently generate every output state efficiently generated by arbitrary Clifford circuits and also encompass full probabilistic classical computation.The extension therefore broadens the simulatable class beyond Clifford circuits while retaining weak simulation.
Circuit class: Arbitrary local unitaries followed by Toffoli and diagonal gates can be efficiently simulated classically in the weak sense for computational-basis measurements.After the first round, the register is a complete product state, enabling the subsequent sampling argument.
Circuit class: The final state is expressed using an efficiently computable invertible Boolean function f and computational-basis-dependent phases.The amplitudes are determined by product-state coefficients, while f maps input bit strings to output basis strings.
Weak simulation: Measurement probabilities equal the total product-state probability of sampled strings whose transformed bits match the observed outcomes.For measured subset S, π(α) sums |χ_x|^2 over strings satisfying f(x)_j = α_j for every j in S.
Weak simulation: Sampling an N-bit string from p(x)=|χ_x|^2 and applying f yields measurement outcomes with the correct distribution.The distribution p(x) is efficiently samplable because it is a simple product distribution.
Generalization: The first circuit round can be generalized to any unitary U whose computational-basis output distribution on |0⟩ is efficiently samplable.This preserves classical weak simulability after the later circuit operations.

8 Conclusion

The conclusion presents a normal-form account of Clifford simulation, connects it to probabilistic classical computation, and contrasts weak simulation with stronger computational demands.

Conclusion: Each Clifford circuit can be reduced to an equivalent simple circuit C′ producing the same output state on input |0⟩.This reduction supplies a proof of Gottesman–Knill without using stabilizer techniques.
Conclusion: The normal form explains how Clifford-operation simulation fits the standard embedding of probabilistic classical computation into quantum circuits.The connection is related to HT circuits.
HT circuits: HT circuits are classically simulatable by sampling, while exactly computing their measurement outcomes is treated as a distinct strong-simulation problem.The section emphasizes that these circuits differ from several other known simulatable circuit families.
HT circuits: Adding a final round of Hadamard gates to an HT circuit can implement Shor’s factoring algorithm through phase estimation.This illustrates the computational significance of a modest extension involving local basis changes.

Appendix A: Updating the triple (A, l, q)

The appendix proves that Clifford gates preserve a structured state representation by efficiently updating its affine-space, linear-function, and quadratic-function components.

Claim: Applying H, P, or CNOT to a state represented by (A,l,q) preserves that representation with efficiently computable updates.The claim is established by treating phase, CNOT, and Hadamard gates separately.
Representation: The affine space A can be parameterized as Ru+t, allowing quadratic and linear functions on A to be represented as functions of the m-bit parameter u.The transformed functions are computationally easy to derive in either direction.
Hadamard gate: A lemma supplies efficient reduction of quadratic and linear functions after eliminating one variable, completing the Hadamard-update argument.The resulting functions are defined on Z2^(K−1) up to a multiplicative constant independent of the remaining variables.
Phase gate: A phase gate preserves the form because its phase factor is rewritten using the identity i^a i^b = (−1)^ab i^(a+b).The exponent a+b is computed modulo 2.
CNOT gate: A CNOT performs a linear transformation over Z2 within the computational-basis ket, so the structured representation is retained with updated parameters.The updated R′ and t′ are obtained directly from the gate action.
Hadamard gate: Hadamard updating is the nontrivial case because removing a row from R can leave either full rank or rank m−1.The rank-deficient case requires a change of variables and an additional summation argument.
Hadamard gate: In the rank-deficient Hadamard case, solving a Z2 linear system constructs an invertible change of variables that isolates a summable coefficient.The relevant linear-algebra computation is an ⊕L problem, and the transformed quadratic and linear functions remain efficiently computable.