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.
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.
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 group-theory techniques and insights from quantum physics. Realistic circuits enriched with quantum error-correcting codes and fault-tolerant procedures are dominated by stabilizer subcircuits and contain a relatively small number of non-Clifford components. Therefore, we develop new data structures and algorithms that facilitate parallel simulation of such circuits. Stabilizer frames offer more compact storage than previous approaches but require more sophisticated bookkeeping. Our implementation, called Quipu, simulates certain quantum arithmetic circuits (e.g., reversible ripple-carry adders) in polynomial time and space for equal superpositions of n-qubits. 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 Fourier transform and quantum fault-tolerant circuits using Quipu, and the results demonstrate that our stabilizer-based technique empirically outperforms QuIDDPro in all cases. While previous high-performance, structure-aware simulations of quantum circuits were difficult to parallellize, we demonstrate that Quipu can be parallelized with a nontrivial computational speedup.
As quantum information processing gains traction, its simulation becomes increasingly significant for engineering purposes - evaluation, testing and optimization - as well as for theoretical research. Generic quantum-circuit simulation appears intractable for conventional computers. However, Gottesman and Knill identified an important subclass, called stabilizer circuits, which can be simulated efficiently using group-theory techniques. Practical circuits enriched with quantum error-correcting codes and fault-tolerant procedures are dominated by stabilizer subcircuits and contain a relatively small number of non-stabilizer components. Therefore, we develop new group-theory data structures and algorithms to simulate such circuits. Stabilizer frames offer more compact storage than previous approaches but requires more sophisticated bookkeeping. Our implementation, called Quipu, simulates certain quantum arithmetic circuits (e.g., ripple-carry adders) in polynomial time and space for equal superpositions of n-qubits. On such instances, known linear-algebraic simulation techniques, such as the (state-of-the-art) BDD-based simulator QuIDDPro, take exponential time. We simulate various quantum Fourier transform and quantum fault-tolerant circuits with Quipu, and the results demonstrate that our stabilizer-based technique outperforms QuIDDPro in all cases.
Quantum-mechanical phenomena are playing an increasing role in information processing as transistor sizes approach the nanometer level, while the securest forms of communication rely on quantum data encoding. When they involve a finite number of basis states, these phenomena can be modeled as quantum circuits, the quantum analogue of conventional or classical logic circuits. Simulation of quantum circuits can therefore be used as a tool to evaluate issues in the design of quantum information processors. Unfortunately, simulating such phenomena efficiently is exceedingly difficult. The matrices representing quantum operators (gates) and vectors modeling quantum states grow exponentially with the number of quantum bits. The information represented by quantum states and operators often exhibits structure that can be exploited when simulating certain classes of quantum circuits. We study the development of simulation methods that run on classical computers and take advantage of such repetitions and redundancies. In particular, we define a new data structure for simulating quantum circuits called the quantum information decision diagram (QuIDD). A QuIDD is a compressed graph representation of a vector or matrix and permits computations to be performed directly on the compressed data. We develop a comprehensive set of algorithms for operating on QuIDDs in both the state-vector and density-matrix formats, and evaluate their complexity. These algorithms have been implemented in a general-purpose simulator program for quantum-mechanical applications called QuIDDPro. Through extensive experiments conducted on representative quantum simulation applications, including Grover's search algorithm, error characterization, and reversible circuits, we demonstrate that QuIDDPro is faster than other existing quantum-mechanical simulators such as the National Institute of Standards and Technology's QCSim program, and is far more memory-efficient. Using QuIDDPro, we explore the advantages of quantum computation over classical computation, simulate quantum errors and error correction, and study the impact of numerical precision on the fidelity of simulations. We also develop several novel algorithms for testing quantum circuit equivalence and compare them empirically. The QuIDDPro software is equipped with a user-friendly interface and is distributed with numerous example scripts. It has been used as a laboratory supplement for quantum computing courses at several universities.
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.
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 only) and can be represented compactly on conventional computers using Omega(n^2) bits, where n is the number of qubits. Although techniques for the efficient simulation of stabilizer circuits have been studied extensively, techniques for efficient manipulation of stabilizer states are not currently available. To this end, we design new algorithms for: (i) obtaining canonical generators for stabilizer states, (ii) obtaining canonical stabilizer circuits, and (iii) computing the inner product between stabilizer states. Our inner-product algorithm takes O(n^3) time in general, but observes quadratic behavior for many practical instances relevant to QECC (e.g., GHZ states). We prove that each n-qubit stabilizer state has exactly 4(2^n - 1) nearest-neighbor stabilizer states, and verify this claim experimentally using our algorithms. We design techniques for representing arbitrary quantum states using stabilizer frames and generalize our algorithms to compute the inner product between two such frames.