PaperlayerView exact revision on arXiv

Source-linked AI summary

Simulation of quantum circuits by low-rank stabilizer decompositions

Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, Mark Howard

arXiv:1808.00128v2quant-ph

TL;DR

The paper develops mathematical tools for exact and approximate stabilizer decompositions and simulation algorithms beyond the Clifford+T setting. These methods support broader circuit classes and simulations of quantum algorithms with dozens of qubits and non-Clifford gates.

  • Problem

    Existing stabilizer-decomposition methods focused heavily on Clifford+T circuits, although synthesizing arbitrary single-qubit gates there can require several hundred T gates for error below 10^-10.

  • Method

    The paper combines approximate stabilizer-rank theory, a Sparsification Lemma, and simulation methods for arbitrary-angle Z-rotations, CCZ gates, and suitable diagonal gates.

  • Results

    The methods enable simulations including a 50-qubit QAOA circuit with about 60 non-Clifford gates and a Hidden Shift algorithm, while improving simulation runtime for broader gate sets.

  • Takeaways & Limitations

    The resulting Clifford-based simulators apply to large-scale circuits without locality requirements when Clifford gates dominate and can sample output distributions rather than only individual amplitudes.

  • Takeaways & Limitations

    Generating a single full n-bit sample with small error can have overall runtime O(kn^6), making this sampling method quickly impractical.

Abstract

from arXiv · show

Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of stabilizer rank, which for a pure state $ψ$ is defined to be the smallest integer $χ$ such that $ψ$ is a superposition of $χ$ stabilizer states. Here we develop a comprehensive mathematical theory of the stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of $χ\sim10^6$ stabilizer states and sample from the full n-bit output distribution, improving on previous simulations which used $\sim 10^3$ stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 T gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.

1 Introduction

The paper develops stabilizer-rank theory and broader simulation algorithms for circuits dominated by Clifford operations, including arbitrary diagonal gates. These methods support simulations with substantially larger stabilizer decompositions and non-Clifford components than earlier approaches.

  • Stabilizer rank measures the smallest number of stabilizer states needed to express a pure state and quantifies the cost of stabilizer-operation simulation.It is analogous to Schmidt rank as a measure of computational nonclassicality.
  • The paper generalizes stabilizer-decomposition methods beyond Clifford+T circuits to arbitrary-angle Z rotations and CCZ gates.Clifford+T synthesis may require several hundred T gates for high-precision arbitrary single-qubit gates.
  • χ ∼10^6 stabilizer states were simulated with about 50 qubits on a laptop, improving on earlier χ ∼10^3 simulations.The methods include more efficient routines for Clifford gates and Pauli measurements on large stabilizer superpositions.
  • Figure 1 distinguishes strong simulation of one output probability from weak simulation by sampling the output distribution.Runtime is exponential in the non-Clifford gate count m and polynomial in the qubit and Clifford-gate counts.
  • The theory introduces sparsification, stabilizer fidelity, and Stabilizer Extent to construct and analyze approximate stabilizer decompositions.The Sparsification Lemma converts dense decompositions into sparse ones without requiring magic-state gadgets.
  • The methods target noisy intermediate-size circuit verification, including circuits with few nonzero or uniformly small diagonal-rotation angles.The discussion identifies circuits dominated by Clifford gates as a relevant regime for large-scale, potentially nonlocal circuits.

2 Main results

The paper uses the stabilizer formalism, Clifford operators, and Pauli operators to define the states and operations underlying its decomposition and simulation results.

  • Stabilizer states are obtained by applying Clifford operators to the all-zero computational basis state.The Clifford group is generated by H, S, and CX gates.

2.1 Tools for constructing low-rank stabilizer decompositions

This section develops exact and approximate stabilizer-rank tools, including extent, fidelity, sparsification, multiplicativity results, and bounds for important magic states.

  • Exact stabilizer rank χ(ψ) is the smallest number of stabilizer states in a decomposition of ψ.
  • Approximate stabilizer rank χδ(ψ) is the smallest exact rank of a state within distance δ of normalized ψ.
  • Approximate stabilizer rank: Theorem 1 gives an upper bound on χδ from any stabilizer decomposition, using randomized sparsification to construct an approximation.The construction samples stabilizer states from the supplied decomposition and produces approximately δ^-2∥c∥_1^2 terms.
  • Stabilizer Extent: Stabilizer Extent ξ is a more tractable quantity than exact or approximate stabilizer rank for many simulation-relevant states.It is defined by minimizing the squared coefficient norm over stabilizer decompositions.
  • Stabilizer fidelity: Stabilizer fidelity F(ψ) is the maximum squared overlap between ψ and a normalized stabilizer state.
  • Multiplicativity: Stabilizer fidelity is multiplicative for stabilizer-aligned states, and failure of alignment implies a tensor-product violation for some partner state.The class of stabilizer-aligned states is closed under tensor products.
  • Clifford magic states: For diagonal third-level gates, state injection reduces gate implementation to preparing a Clifford magic state modulo stabilizer operations.The associated ancillary state is |V⟩ = V|+⟩^⊗t.
  • Multiplicativity: For Clifford magic states, ξ(ψ) = F(ψ)^−1, while ξ is multiplicative for collections of states involving at most three qubits.Multiplicativity of ξ remains open for arbitrary collections of states.

2.2 Subroutines for manipulating low-rank stabilizer decompositions

The paper provides subroutines for estimating probabilities and sampling outputs from approximate stabilizer decompositions, combining Clifford simulation, norm estimation, and alternative sampling strategies.

  • The simulation task is to sample bit strings from P_U(x) = |⟨x|U|0^n⟩|^2, allowing approximate stabilizer decompositions of U|0^n⟩.The approximation P(x) is intended to remain close to the true output distribution when δ is small.
  • Marginal probabilities reduce to squared norms of projected decompositions, because computational-basis projectors map stabilizer states to stabilizer states.This connects probability estimation to the same low-rank representation.
  • The heuristic Metropolis sampler implements each step in O(kn), but its mixing time is generally unknown.
  • The improved norm-estimation subroutine achieves approximately 50X speedup over the method of Ref. [11].It estimates norms using inner products with randomly drawn stabilizer states rather than evaluating all cross terms.
  • The rigorous chain-rule sampler has runtime O(kn^6) for a full n-bit sample, while sampling w bits costs O(kn^3w^3).The partial-output regime may therefore be practical for small w.

2.3 Simulation algorithms

The paper develops gadget-based and sum-over-Cliffords simulation methods for circuits with Clifford and non-Clifford gates, extending applicability beyond Clifford+T circuits. Approximate stabilizer decompositions enable sampling from output distributions while controlling simulation cost and error.

  • Sum-over-Cliffords method: For T gates, sum-over-Cliffords has the same asymptotic cost as the gadget-based method while generally being simpler and potentially faster.Its cost is governed by ξ-optimal decompositions of the constituent non-Clifford gates.
  • Gadget-based methods: Gadget-based simulation replaces non-Clifford gates with state-injection gadgets whose measurement-dependent corrections must be simulated.For diagonal gates in the third level of the Clifford hierarchy, the corrections are Clifford operators.
  • Resource-state decompositions: State injection relates the exact stabilizer rank of the circuit output to that of the combined magic state resource.This identity lets decompositions of the resource state yield decompositions of the simulated output state.
  • Gadget-based methods: The fixed-sample gadget method requires exact stabilizer decompositions because approximation errors can be amplified by postselection.An approximate resource state can produce simulation error proportional to 2^(τ/2)δ.
  • Gadget-based methods: The random-sample gadget method supports approximate decompositions and average-case error O(δ), but generally cannot estimate an individual output probability accurately.Its correction handling is straightforward when each non-Clifford gate is diagonal and belongs to the third level of the Clifford hierarchy.
  • Sum-over-Cliffords method: Sum-over-Cliffords simulation decomposes the circuit into weighted Clifford unitaries and samples from an approximate stabilizer superposition.The method applies to more general non-Clifford gates and uses norm estimation or heuristic Metropolis sampling.

2.4 Implementation and simulation results

The authors implement their methods on QAOA and Hidden Shift circuits, using laptop-scale simulations to test output estimates and compare decompositions of non-Clifford components. The experiments demonstrate simulation of 50-qubit QAOA instances and savings from direct CCZ representations.

  • Experimental overview: The experiments simulate QAOA with 50 qubits, about 60 non-Clifford gates, and a few hundred Clifford gates using sum-over-Cliffords.They also evaluate Hidden Shift circuits with Clifford+T, Clifford+CCZ, and sum-over-Cliffords methods.
  • Quantum approximate optimization algorithm: The simulator’s QAOA estimates are checked against an independent Monte Carlo computation of the expected cost function.This cross-check is a stated reason QAOA circuits are useful for benchmarking classical simulators.
  • Hidden Shift algorithm: Hidden Shift circuits vary the number of non-Clifford gates through even numbers of Toffoli gates, exposing the exponential simulation overhead.The study compares T-based and CCZ-based gadget decompositions with sum-over-Cliffords simulation.
  • Hidden Shift algorithm: Direct CCZ gates or states yield significant savings over decomposing each CCZ into four T gates or states.The differing slopes of the T- and CCZ-based simulations in Fig. 5 illustrate the scaling advantage.
  • Method comparison: Sum-over-Cliffords is broadly applicable and was observed to be as fast as or faster than the gadget-based method despite implementation-dependent comparisons.Its performance can improve for gates outside the third Clifford-hierarchy level and for small-angle rotations away from the T-gate angle.

3 Discussion

The paper positions stabilizer-based simulators as complements to vector- and tensor-based methods, especially for large, nonlocal circuits dominated by Clifford gates. It also identifies sampling and decomposition quality as practical advantages and continuing challenges.

  • Comparison with other simulators: Clifford simulators handle large-scale circuits without locality requirements when Clifford gates dominate.Tensor-based simulators scale as 2^(n−o(n)) for geometrically non-local circuits of polynomial size.
  • Comparison with other simulators: Stabilizer-based methods can sample the full output distribution, whereas tensor-based simulations typically compute a single output amplitude.A heuristic sum-over-Cliffords run can produce thousands of approximate output samples.
  • Implementation: The sum-over-Cliffords simulator is publicly available in Qiskit-Aer for circuits above 30 qubits, with parallel processing over stabilizer states.This implementation uses Metropolis sampling and parallelizes the Metropolis step over the decomposition.
  • Comparison with quasiprobability methods: Quasiprobability methods differ from stabilizer-rank simulators in their treatment of stabilizer operations and output-distribution sampling.Their runtime depends on Wigner negativity, and sampling output distributions requires small multiplicative errors in individual probabilities.
  • Open questions: Improving low-rank decompositions of multi-qubit magic states remains an open problem relevant to more efficient Clifford+CCZ simulation.The paper also leaves open questions about stabilizer extent multiplicativity and exponential lower bounds for stabilizer rank.

4 Subroutines

This section develops efficient stabilizer-state representations and simulation subroutines, including phase-sensitive CH-form updates, inner-product-based norm estimation, and output sampling. The methods provide exact or approximate computations with explicit runtime bounds.

  • 4.1 Phase-sensitive Clifford simulator: CH-form represents stabilizer states using C-type and H-type Clifford operators, a computational-basis vector, and a global phase.The representation is not necessarily unique and includes phase information needed to preserve relative phases.
  • 4.1 Phase-sensitive Clifford simulator: The CH-form Clifford simulator runs in O(n) time for S, CZ, and CX gates and O(n^2) time for Hadamard gates.It also computes amplitudes, samples from the output distribution, and simulates projective Pauli gates in O(n^2) time.
  • 4.1 Phase-sensitive Clifford simulator: Hadamard updates are reduced to CH-form transformations involving O(n) C-type gates, yielding an overall O(n^2) update cost.The construction uses identities that commute the Hadamard through the C- and H-layers while updating the stabilizer tableau.
  • 4.3 Fast norm estimation: Norm estimation samples random stabilizer states and uses η = 2^n|⟨φ|ψ⟩|^2 as an unbiased estimator of ||ψ||^2.The estimator has standard deviation approximately ||ψ|| and can be computed in O(kn^3) time for a rank-k decomposition.
  • 4.3 Fast norm estimation: The improved norm-estimation method samples equatorial stabilizer states and uses CH-form-based exponential-sum computations.Equatorial-state sampling requires tossing an unbiased coin O(n^2) times.
  • 4.3 Fast norm estimation: Averaging L = 4ϵ^-2 independent estimates achieves the target norm approximation with probability at least 3/4.The error probability can be reduced using K = O(log δ^-1) independent estimates.
  • 4.3 Fast norm estimation: Full-output sampling via norm estimation and the chain rule has runtime O(kn^6), while sampling only w bits costs O(kn^3w^3).The method requires multiplicative error O(n^-1) at each of O(n) chain-rule steps to control accumulated error.

5 Stabilizer rank

The section develops exact and approximate stabilizer-rank bounds using symmetric-subspace arguments, sparsification, numerical search, and stabilizer fidelity. It derives favorable bounds for tensor powers, identifies limitations beyond five copies, and connects decompositions to simulation overhead.

  • Exact stabilizer rank: χ(Sym_n,t) is defined as the minimum number of stabilizer states whose span contains the symmetric subspace.For ψ⊗t ∈ Sym_n,t, this gives χ(ψ⊗t) ≤ χ(Sym_n,t).
  • Exact stabilizer rank: For all n and t ≤5, rank(σ_n,t) = rank(Π_n,t), yielding χ(ψ⊗t) ≤ t + 1 for every single-qubit state.The proof uses stabilizer states of the form |φ_j⟩⊗t and the dimension of the permutation-symmetric subspace.
  • Exact stabilizer rank: For t >5, the symmetric-space rank equality fails because a stabilizer-testing projector distinguishes σ_n,6 from Π_n,6.Specifically, there exists W with Tr[Wσ_n,6] = 0 but Tr[WΠ_n,6] ≠ 0, implying rank(σ_n,6) < rank(Π_n,6).
  • Exact stabilizer rank: Numerical searches support equality in the single-qubit bound for typical states and conjecture tightness exactly when the state has no Clifford symmetries.The searches use random stabilizer states, Pauli-projector updates, and simulated-annealing acceptance.
  • Approximate stabilizer rank: Theorem 1 converts a dense stabilizer decomposition into a δ-approximation with k = (∥c∥1/δ)^2 stabilizer terms.This follows from the Sparsification Lemma and produces a sparse approximate decomposition.
  • Approximate stabilizer rank: Stabilizer fidelity F(ψ) determines the minimum coefficient 2-norm for a decomposition using a closest stabilizer state, while multiplicativity enables tensor-power bounds.For Clifford magic states, the relation ξ(ψ) = F(ψ)^−1 extends to a wider class including the face state.
  • Approximate stabilizer rank: For CCZ states, χ_δ(CCZ⊗t) ≤ δ^−2(9/16)^t ∼ δ^−2 1.778^t, slower than synthesizing each CCZ with four T gates.The bound comes from an explicit decomposition, while ξ supplies only an upper bound on approximate stabilizer rank.
  • Lower bounds: Stabilizer-rank lower bounds remain difficult: the paper studies approximating T-type magic states but notes no unconditional super-polynomial lower bounds are known.The paper reports partial progress through a simplified problem.

6 Stabilizer fidelity and Stabilizer extent

The paper relates stabilizer extent to stabilizer fidelity through convex duality and studies when these quantities behave multiplicatively under tensor products. It proves multiplicativity for stabilizer-aligned states and, in particular, for tensor products of states involving at most three qubits.

  • 6 Stabilizer fidelity and Stabilizer extent: The stabilizer extent ξ is easier to work with than approximate stabilizer rank and can be computed by convex optimization, although the computation scales poorly with n.For tensor products of 1-, 2-, and 3-qubit states, Proposition 1 establishes multiplicativity of ξ.
  • 6 Stabilizer fidelity and Stabilizer extent: Convex duality recasts ξ(ψ) as a maximization over n-qubit witness states, with an optimal witness achieving the bound.Choosing ω = ψ provides a lower bound, and Clifford magic states attain this lower bound tightly.
  • 6 Stabilizer fidelity and Stabilizer extent: Stabilizer-aligned states are defined by F_m(φ) ≤ F_0(φ) for all m, where F_0 is the stabilizer fidelity.The paper characterizes this condition using stabilizer projectors of rank 2^m.
  • 6 Stabilizer fidelity and Stabilizer extent: For stabilizer-aligned φ and ψ, their tensor product is stabilizer-aligned and stabilizer fidelity is multiplicative.Conversely, a non-aligned state has a partner that violates multiplicativity, yielding necessary and sufficient conditions for tensor-product multiplicativity.
  • 6 Stabilizer fidelity and Stabilizer extent: All states of at most three qubits are stabilizer-aligned, while typical sufficiently large n-qubit states are not.This distinction explains why multiplicativity results apply broadly to products of few-qubit states but not necessarily to arbitrary states.
Loading 1808.00128v2…