The Gottesman-Knill theorem says that a stabilizer circuit---that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates---can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely available program called CHP (CNOT-Hadamard-phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class $\ensuremath{\bigoplus}\mathsf{L}$, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any
n-qubit stabilizer circuit into a ``canonical form'' that requires at most
O(n2∕logn) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.
Simulation of quantum information processing remains a major challenge with important applications in quantum computer science and engineering. Generic quantum-circuit simulation appears intractable for conventional computers and may be unnecessary because useful quantum circuits exhibit significant structure that can be exploited during simulation. For example, Gottesman and Knill identified an important subclass, called stabilizer circuits, which can be simulated efficiently using the Heisenberg representation for quantum computers. Stabilizer circuits are exclusively composed of stabilizer gates -- Hadamard, Phase and CNOT -- followed by one-qubit measurements in the computational basis. Such circuits are applied to a computational-basis state and produce so-called stabilizer states. Aaronson and Gottesman generalized stabilizer-circuit simulation to additionally handle a small number of non-stabilizer gates. We design new, more efficient data structures and algorithms for such beyond-stabilizer simulation using superpositions of stabilizer states. One such data structure, a stabilizer frame, offers more compact storage than previous approaches but require additional algorithms to maintain the global phases of each state in the superposition. To explore the advantages and limitations of our technique, we analyze the geometric structure of stabilizer states and their embedding in Hilbert space. Our analysis includes results on the computational geometry of stabilizer states such as efficient algorithms for computing distances, angles and volumes between them. The main advantages of using stabilizer-state superpositions to simulate quantum circuits are: (i) stabilizer subcircuits are simulated with high efficiency, (ii) superpositions can be restructured and compressed on the fly during simulation to reduce resource requirements, and (iii) operations performed on such superpositions lend themselves to distributed or asynchronous processing. Our software implementation, called Quipu, simulates certain quantum arithmetic circuits (e.g., reversible ripple-carry adders) and quantum Fourier transform circuits in polynomial time and space for specific input states. On such instances, known linear-algebraic simulation techniques, such as the (state-of-the-art) BDD-based simulator QuIDDPro, take exponential time. We simulate quantum fault-tolerant circuits using Quipu, and the results indicate that our stabilizer-based technique empirically outperforms QuIDDPro in all cases. While previous structure-aware simulations of quantum circuits were difficult to parallellize, we demonstrate a parallel version of Quipu that achieves a nontrivial speedup.
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.
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.
With this thesis project, we improve the classical simulation of quantum computers using stabilizers in the GSLC formalism. We do this in two ways: we present new algorithms that speed up their simulation and extend their applicability by defining new operations and subroutines for existing general circuit simulation using GSLC. To be precise: we present multiple new algorithms that speed up the simulation of the CZ gates, the most computationally expensive quantum operation in GSLC formalism. We define two new operations on GSLC that are useful when simulating stabilizer circuits: calculating fidelity (a measure of 'closeness' between two quantum states), and tracing out qubits (throwing away the information about the state contained in these qubits) from a GSLC. Finally, we present a new GSLC-based subroutine for a state of the art general quantum circuit simulation algorithm by Bravyi et al. that allows for the usage of the faster CZ algorithms. We show that the GSLC formalism can give a speedup in practical simulation tasks by evaluating the complexity of simulating an algorithm with possible applications on near-term quantum hardware: the quantum approximate optimization algorithm.
The Gottesman-Knill theorem states that a Clifford circuit acting on stabilizer states can be simulated efficiently on a classical computer. Recently, this result has been generalized to cover inputs that are close to a coherent superposition of logarithmically many stabilizer states. The runtime of the classical simulation is governed by the stabilizer extent , which roughly measures how many stabilizer states are needed to approximate the state. An important open problem is to decide whether the extent is multiplicative under tensor products. An affirmative answer would yield an efficient algorithm for computing the extent of product inputs, while a negative result implies the existence of more efficient classical algorithms for simulating largescale quantum circuits. Here, we answer this question in the negative. Our result follows from very general properties of the set of stabilizer states, such as having a size that scales subexponentially in the dimension, and can thus be readily adapted to similar constructions for other resource theories.