Hybrid Techniques for Simulating Quantum Circuits using the Heisenberg Representation.

Quantum-circuit Simulation;Stabilizer-based Simulation of Generic Quantum Circuits;Stabilizer Frames;Multiframes and P-blocked Multiframes;Pauli Decision Diagrams and Matrix Product Multivalued Decision Diagrams;Metric and Computational Geometry of Stabilizer States;Heisenberg Representation for Quantum Computers;Computer Science;Engineering;Computer Science and Engineering

Garcia-Ramirez, Hector J.Shi, Yaoyun ;

University of Michigan

关键词: Quantum-circuit Simulation;    Stabilizer-based Simulation of Generic Quantum Circuits;    Stabilizer Frames;    Multiframes and P-blocked Multiframes;    Pauli Decision Diagrams and Matrix Product Multivalued Decision Diagrams;    Metric and Computational Geometry of Stabilizer States;    Heisenberg Representation for Quantum Computers;    Computer Science;    Engineering;    Computer Science and Engineering;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/107198/hjgarcia_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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 byone-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 smallnumber 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 ourtechnique, 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 resultsindicate that our stabilizer-based technique empirically outperforms QuIDDPro in allcases. While previous structure-aware simulations of quantum circuits were difficult to parallellize, we demonstrate a parallel version of Quipu that achieves a nontrivial speedup.