Simulation of Quantum Circuits via Stabilizer Frames
Authors:
- Héctor J. GarcíaHGHéctor J. García
- Igor L. MarkovIMIgor L. Markov
Preprint
Abstract
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 parallelize, we demonstrate that Quipu can be parallelized with a nontrivial computational speedup.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Optimized Quantum Gate Library for Various Physical Machine DescriptionsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2013
- Fast equivalence-checking for quantum circuits2010
- Randomized benchmarking of quantum gatesPhysical Review A, 2008
- Massively parallel quantum computer simulatorComputer Physics Communications, 2007
- A layered software architecture for quantum computing design toolsComputer, 2006
- Entanglement on mixed stabilizer states: normal forms and reduction proceduresNew Journal of Physics, 2005
- Improved simulation of stabilizer circuitsPhysical Review A, 2004
- A practical architecture for reliable quantum computersComputer, 2002
- Fault-Tolerant Error Correction with Efficient Quantum CodesPhysical Review Letters, 1996
- Approximate quantum Fourier transform and decoherencePhysical Review A, 1996