Classification of Stabilizer Simulators

[Fe-r-oz]

Classification of Stabilizer Simulators

1. Aaronson and Gottesman's Simulator

• Reference: Improved Simulation of Stabilizer Circuit
• Efficient for Stabilizer Circuits: Introduced a classical simulation algorithm efficient for stabilizer circuits.
• Simulates Non-Stabilizer Circuits: Handles non-stabilizer circuits with exponential run-time cost depending on the number of non-stabilizer gates.
• Limitation: The run-time does not depend on the specific properties of the additional non-stabilizer gates, incurring a heavy penalty even for small deviations from stabilizer gates.

---

2. Research Categories to Overcome Limitation

Born Rule Probability Estimators

• Quasi-Probabilistic Representation: Uses density matrix representations
  • Quantifying quantum speedups: improved classical simulation from tighter magic monotones
  • From estimation of quantum probabilities to simulation of quantum circuits
  • On the classical simulability of quantum circuits
  • Estimating outcome probabilities of quantum circuits using quasiprobabilities
  • Simulation of Qubit Quantum Circuits via Pauli Propagation
  • Application of a resource theory for magic states to fault-tolerant quantum computing
  • Negative Quasi-Probability as a Resource for Quantum Computation
  • Positive Wigner functions render classical simulation of quantum computation efficient

Pure-State Sampling Simulators

• References:
  • Improved classical simulation of quantum circuits dominated by Clifford gates
  • Efficient Inner-product Algorithm for Stabilizer States
  • On the geometry of stabilizer states
  • Trading classical and quantum computational resource
• Key Advances:
  • Bravyi and Gosset estimation and sampling algorithms
    • References:
      • Improved classical simulation of quantum circuits dominated by Clifford gates
      • Simulation of quantum circuits by low-rank stabilizer decompositions

---

3. Bravyi and Gosset Algorithms

• BG-Estimation Algorithm: Produces multiplicative precision estimates of Born rule probabilities.
• BG-Sampling Algorithm: Samples approximately from the quantum circuit outcome distribution.

Methodology:

• State Representation: Initial states are expressed as a linear combination of stabilizer states.
• Efficiently Simulable Circuits:
  • Superposition of polynomially many stabilizer states.
  • Clifford gates and computational basis measurements.
• Promoting Universality: Allowing magic states in initial conditions.

Run-Time Dependence:

• Linear in the stabilizer rank of the state.
• Stabilizer Rank: Minimal number of stabilizer states required to represent the state as a linear combination.
• Approximation and Stabilizer Extent: Approximate stabilizer rank can be bounded by the stabilizer extent $\xi$ divided by $\epsilon^2$, where $\epsilon$ is the approximation error.

---

4. Sum Over Cliffords Algorithm

• Reference:
  • Simulation of quantum circuits by low-rank stabilizer decompositions
• Variant: Simulates non-Clifford gates using a linear combination of Clifford gates.
• Run-Time: Scales linearly with the stabilizer extent of states like $|T_\phi^\dagger \rangle$.

---

5. Quasi-Probabilistic Simulators

• Purpose: Produce additive precision estimates of Born rule probabilities.
• Representation: Density matrices are expressed as a linear combination of a preferred set of operators (frame).

Frame Choices:

• Examples:
  • Weyl-Heisenberg displacement operators
    • From estimation of quantum probabilities to simulation of quantum circuits
    • On the classical simulability of quantum circuits
    • Simulation of Qubit Quantum Circuits via Pauli Propagation
  • stabilizer states
    • Quantifying quantum speedups: improved classical simulation from tighter magic monotones
    • Application of a resource theory for magic states to fault-tolerant quantum computing
  • phase-point operators
    • Estimating outcome probabilities of quantum circuits using quasiprobabilities
    • Negative Quasi-Probability as a Resource for Quantum Computation
    • Positive Wigner functions render classical simulation of quantum computation efficient

Special Mention:

• Dyadic Frame Simulator:
  • Introduced in Quantifying quantum speedups: improved classical simulation from tighter magic monotones
  • Decomposes density matrices into stabilizer dyads $|L\rangle\langle R|$.
  • Circuits promoted to universality using magic states.

Run-Time:

• Depends quadratically on the dyadic negativity.
• Dyadic negativity measures deviation from convex combinations of stabilizer dyads.

---

6. Mixed-State Stabilizer Rank Simulator

• Introduced in Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Improvements:
  • Generalized BG-sampling algorithm to include mixed states.
  • Improved run-time dependence on error tolerance for approximate sampling.

Mixed-State Extent:

• Definition: Quantity governing run-time for mixed-state simulators.
• Comparison: For $n$-qubit product states, dyadic negativity, stabilizer extent, and mixed-state extent are equivalent.

---

Inspired from:

Section III.A of the paper Fast Estimation of Outcome Probabilities for Quantum Circuits provides an nice survey of stabilizer and Clifford+T simulators. The corresponding C repository for this paper can be found here. Note: This paper shares significant overlap with the foundational work Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates by Bravyi and Gosset.

[Fe-r-oz]

Hi Stefan,

The classification of stabilizer simulators might be helpful for record-keeping. Often, papers on Clifford+T circuits don't specify which "category" their approach belongs to. I hope this is helpful!

[Krastanov]

this is indeed pretty neat. Something like this might make sense in the documentation, near the suggested readings page