In this paper, we improve the layered implementation of arbitrary stabilizer circuits introduced by Aaronson and Gottesman in Phys. Rev. A 70 (052328), 2004: to implement a general stabilizer circuit, we reduce their 11-stage computation -H-C-P-C-P-C-H-P-C-P-Cover the gate set consisting of Hadamard, controlled-NOT, and phase gates, into a 7-stage computation of the form -C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the -C- stages: not only the use of -CZ- stages allows a shorter layered expression, but -CZ- stages are simpler and appear to be easier to implement compared to the -C- stages. Based on this decomposition, we develop a two-qubit gate depth(14n-4) implementation of stabilizer circuits over the gate library {H, P, CNOT}, executable in the Linear Nearest Neighbor (LNN) architecture, improving best previously known depth25n circuit, also executable in the LNN architecture. Our constructions rely on Bruhat decomposition of the symplectic group and on folding arbitrarily long sequences of the form (-P-C-)minto a three-stage computation -P-CZ-C-. Our results include the reduction of the 11-stage decomposition -H-C-P-C-PC-H-P-C-P-Cinto a 9-stage decomposition of the form -C-P-C-PH-C-P-C-P-. This reduction is based on the Bruhat decomposition of the symplectic group. This result also implies a new normal form for stabilizer circuits. We show that a circuit in this normal form is optimal in the number of Hadamard gates used. We also show that the normal form has an asymptotically optimal number of parameters.
In this paper, we improve the layered implementation of arbitrary stabilizer circuits introduced by Aaronson and Gottesman in Phys. Rev. A 70 (052328), 2004: to implement a general stabilizer circuit, we reduce their 11-stage computation -H-C-P-C-P-C-H-P-C-P-Cover the gate set consisting of Hadamard, controlled-NOT, and phase gates, into a 7-stage computation of the form -C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the -C- stages: not only the use of -CZ- stages allows a shorter layered expression, but -CZ- stages are simpler and appear to be easier to implement compared to the -C- stages. Based on this decomposition, we develop a two-qubit gate depth(14n-4) implementation of stabilizer circuits over the gate library {H, P, CNOT}, executable in the Linear Nearest Neighbor (LNN) architecture, improving best previously known depth25n circuit, also executable in the LNN architecture. Our constructions rely on Bruhat decomposition of the symplectic group and on folding arbitrarily long sequences of the form (-P-C-)minto a three-stage computation -P-CZ-C-. Our results include the reduction of the 11-stage decomposition -H-C-P-C-PC-H-P-C-P-Cinto a 9-stage decomposition of the form -C-P-C-PH-C-P-C-P-. This reduction is based on the Bruhat decomposition of the symplectic group. This result also implies a new normal form for stabilizer circuits. We show that a circuit in this normal form is optimal in the number of Hadamard gates used. We also show that the normal form has an asymptotically optimal number of parameters.
In this paper we improve the layered implementation of arbitrary stabilizer circuits introduced by Aaronson and Gottesman in {\it Phys. Rev. A 70(052328)}, 2004. In particular, we reduce their 11-stage computation -H-C-P-C-P-C-H-P-C-P-C- into an 8-stage computation of the form -H-C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the -C- stages: not only the use of -CZ- stages allows a shorter layered expression, but -CZ- stages are simpler and appear to be easier to implement compared to the -C- stages. Relying on the 8-stage decomposition we develop a two-qubit depth-(14n−4) implementation of stabilizer circuits over the gate library {P,H,CNOT}, executable in the LNN architecture, improving best previously known depth-25n circuit, also executable in the LNN architecture. Our constructions rely on folding arbitrarily long sequences (-P-C-)m into a 3-stage computation -P-CZ-C-, as well as efficient implementation of the -CZ- stage circuits.
We start by studying the subgroup structures underlying stabilizer circuits. Then we apply our results to provide two normal forms for stabilizer circuits. These forms are computed by induction using simple conjugation rules in the Clifford group and our algorithms do not rely on a special decomposition in the symplectic group. The first normal form has shape CX-CZ-P-Z-X-H-CZ-P-H, where CX (resp. CZ) denotes a layer of CNOT (resp. controlled-Z) gates, P a layer of phase gates, X (resp. Z) a layer of Pauli-X (resp. Pauli-Z) gates. Then we replace most of the controlled-Z gates by CNOT gates to obtain a second normal form of type P-CX-CZ-CX-Z-X-H-CZ-CX-P-H. In this second form, both controlled-Z layers have depth 1 and together contain therefore at most n controlled-Z gates. We also consider normal forms for stabilizer states and graph states. Finally we carry out a few tests on classical and quantum computers in order to show experimentally the utility of these normal forms to reduce the gate count of a stabilizer circuit.
We start by studying the subgroup structures underlying stabilizer circuits and we use our results to propose a new normal form for stabilizer circuits. This normal form is computed by induction using simple conjugation rules in the Clifford group. It has shape CX-CZ-P-H-CZ-P-H, where CX (resp. CZ) denotes a layer of $\cnot$ (resp. $\cz$) gates, P a layer of phase gates and H a layer of Hadamard gates. Then we consider a normal form for stabilizer states and we show how to reduce the two-qubit gate count in circuits implementing graph states. Finally we carry out a few numerical tests on classical and quantum computers in order to show the practical utility of our methods. All the algorithms described in the paper are implemented in the C language as a Linux command available on GitHub.
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.
Large-scale quantum computation is likely to require massive quantum error correction (QEC). QEC codes and circuits are described via the stabilizer formalism, which represents stabilizer states by keeping track of the operators that preserve them. Such states are obtained by stabilizer circuits (consisting of CNOT, Hadamard and Phase gates) and can be represented compactly on conventional computers using O(n2) bits, where n is the number of qubits. As an additional application, the work by Aaronson and Gottesman suggests the use of superpositions of stabilizer states to represent arbitrary quantum states. To aid in such applications and improve our understanding of stabilizer states, we characterize and count nearest-neighbor stabilizer states, quantify the distribution of angles between pairs of stabilizer states, study succinct stabilizer superpositions and stabilizer bivectors, explore the approximation of non-stabilizer states by single stabilizer states and short linear combinations of stabilizer states, develop an improved inner-product computation for stabilizer states via synthesis of compact canonical stabilizer circuits, propose an orthogonalization procedure for stabilizer states, and evaluate several of these algorithms empirically.
The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.