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.
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.
A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as nω/2 < n1.19 which samples from the output distribution obtained by measuring all n qubits of a planar graph state in given Pauli bases. Here ω is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime.A key ingredient is a mapping which, given a tree decomposition of some graph G , produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise ntω−1 where t is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over F2 in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.
Abstract The standard stabilizer formalism provides a setting to show that quantum computations restricted to operations within the Clifford group are classically efficiently simulable: this is the content of the well-known Gottesman–Knill theorem. This work analyzes the mathematical structure behind this theorem to find possible generalizations and derivation of constraints required for constructing a non-trivial generalized Clifford group. We prove that if the closure of the stabilizing set is dense in the set of SU(d) transformations, then the associated Clifford group is trivial, consisting only of local gates and permutations of subsystems. This result demonstrates the close relationship between the density of the stabilizing set and the simplicity of the corresponding Clifford group. We apply the analysis to investigate stabilization with binary observables for qubits and find that the formalism is equivalent to the standard stabilization for a low number of qubits. Based on the observed patterns, we conjecture that a large class of generalized stabilizer states are equivalent to the standard ones. Our results provide better insights into the structure of Gottesman–Knill-type results, consequently allowing us to draw a sharper line between quantum and classical computation.
Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.
Quantum normalizer circuits were recently introduced as generalizations of Clifford circuits: a normalizer circuit over a finite Abelian group G is composed of the quantum Fourier transform (QFT) over G, together with gates which compute quadratic functions and automorphisms. In \cite{VDNest_12_QFTs} it was shown that every normalizer circuit can be simulated efficiently classically. This result provides a nontrivial example of a family of quantum circuits that cannot yield exponential speed-ups in spite of usage of the QFT, the latter being a central quantum algorithmic primitive. Here we extend the aforementioned result in several ways. Most importantly, we show that normalizer circuits supplemented with intermediate measurements can also be simulated efficiently classically, even when the computation proceeds adaptively. This yields a generalization of the Gottesman-Knill theorem (valid for n-qubit Clifford operations) to quantum circuits described by arbitrary finite Abelian groups. Moreover, our simulations are twofold: we present efficient classical algorithms to sample the measurement probability distribution of any adaptive-normalizer computation, as well as to compute the amplitudes of the state vector in every step of it. Finally we develop a generalization of the stabilizer formalism relative to arbitrary finite Abelian groups: for example we characterize how to update stabilizers under generalized Pauli measurements and provide a normal form of the amplitudes of generalized stabilizer states using quadratic functions and subgroup cosets.