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 s t a b i l i z e r 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 χ ∼ 10 6 stabilizer states and sample from the full n -bit output distribution, improving on previous simulations which used ∼ 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.
Improving the simulation of quantum circuits on classical computers is important for understanding quantum advantage and increasing development speed. In this paper, we explore a way to express stabilizer states and further improve the speed of simulating stabilizer circuits with a current existing approach. First, we discover a unique and elegant canonical form for stabilizer states based on graph states to better represent stabilizer states and show how to efficiently simplify stabilizer states to canonical form. Second, we develop an improved algorithm for graph state stabilizer simulation and establish limitations on reducing the quadratic runtime of applying controlled Pauli
Z gates. We do so by creating a simpler formula for combining two Pauli-related stabilizer states into one. Third, to better understand the linear dependence of stabilizer states, we characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our controlled Pauli
Z algorithm, we improve runtime for inner product computation from
O(n3) to
O(nd2), where
d is the maximum degree of the graph encountered during the calculation.
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 \ns\nt\na\nb\ni\nl\ni\nz\ne\nr\n \nrank\n, which for a pure state \nψ\n is defined to be the smallest integer \nχ\n such that \nψ\n is a superposition of \nχ\n 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 \nχ\n∼\n10\n6\n stabilizer states and sample from the full \nn\n-bit output distribution, improving on previous simulations which used \n∼\n10\n3\n stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 \nT\n gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.
Various algorithms have been developed to simulate quantum circuits on classical hardware. Among the most prominent are approaches based on \emph{stabilizer decompositions} and \emph{tensor network contraction}. In this work, we present a unified framework that bridges these two approaches, placing them under a common formalism. Using this, we present two new algorithms to simulate an
n-qubit circuit
C: one that runs in
O~(Ttw(C)) time and the other in
O~(Tγ⋅tw(C)) time, where
tw(C) and
rw(C) refer to the the tree-width and rank-width, respectively, of a tensor network associated to
C,
T is the number of non-Clifford gates in
C, and
γ≈3.42. The proposed algorithms are simple, only require a linear amount of memory, are trivially parallelizable, and interact nicely with ZX-diagram simplification routines. Furthermore, we introduce the refined complexity measures \emph{focused tree-width} and \emph{focused rank-width}, which are always at least as efficient as their standard equivalent; these can be directly applied within our simulation algorithms, allowing for a more precise upper bound on the run time.
Despite the widespread belief that quantum computers cannot be efficiently simulated classically, efficient simulation is known to be possible in certain restricted regimes. In particular, the Gottesman-Knill theorem states that Clifford circuits can be efficiently simulated. We begin this thesis by reviewing and comparing several known techniques for efficient simulation of Clifford circuits: the stabilizer formalism, CH form, affine form, and the graph state formalism. We describe each simulation method and give four different proofs of the Gottesman-Knill theorem. \n \nNext we review a recent work [15], which shows that restricting the geometry of Clifford circuits can lead to a further speedup. We give an algorithm for simulating Pauli basis measurements on a planar graph state in time
widetildeO(nomega/2), where
omega<2.373 is the matrix multiplication exponent. This algorithm achieves a quadratic speedup over using Clifford simulation methods directly. As an application of this algorithm, we consider a depth-
d Clifford circuit whose two-qubit gates act along edges of a planar graph and describe how to sample from its output distribution or compute an output probability in time $\\widetilde{O}(n^{\\omega/2}d^\\omega)$. For
d=O(logn), both of these results are quadratic speedups over using Clifford simulation methods directly. \n \nFinally, we extend these simulation algorithms to universal circuits by using stabilizer rank methods. We follow a previously known gadgetization procedure [9] to show that given a depth-
d Clifford+
T circuit with
t T gates and whose two-qubit gates act along edges of a planar graph, we can sample from its output distribution in time
widetildeO(20.7926tn5/2t6d3) and can compute output probabilities in time
widetildeO(20.3963tn3/2t6d3). Previous work [9,6], applied to the case
d=O(logn), gives algorithms for sampling in time
O(20.3963tn6t6) and computation of output probabilities in time
O(20.3963tn3t3). Our sampling algorithm offers improved scaling in
n but poorer scaling in the exponential term, while our algorithm for computing output probabilities offers improved scaling in
n with identical scaling in the exponential term.
In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of m copies of the magic state | T ⟩ = 2 − 1 ( | 0 ⟩ + e i π / 4 | 1 ⟩ ) in the limit of large m . In particular, we show that | T ⟩ ⊗ m can be exactly expressed as a superposition of at most O ( 2 α m ) stabilizer states, where α ≤ 0.3963 , improving on the best previously known bound α ≤ 0.463 . This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an n -qubit Clifford + T circuit U with m uses of the T gate to within a given inverse polynomial relative error using a runtime p o l y ( n , m ) 2 α m . We also provide improved upper bounds on the stabilizer rank of symmetric product states | ψ ⟩ ⊗ m more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and m instances of any (fixed) single-qubit Z -rotation gate with runtime poly ( n , m ) 2 m / 2 . We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.