Simulation of quantum circuits by low-rank stabilizer decompositions

作者：Sergey Bravyi, Dan E. Browne, Padraic Calpin, Earl T. Campbell, David Gosset, Mark Howard · 发表于：White Rose Research Online (University of Leeds, The University of Sheffield, University of York) · 年份：2019 · 被引用次数：246 · 研究领域：Quantum Computing Algorithms and Architecture、Quantum Information and Cryptography、Quantum-Dot Cellular Automata

Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of \ns\nt\na\nb\ni\nl\ni\nz\ne\nr\n \nrank\n, which for a pure state \nψ\n is defined to be the smallest integer \nχ\n such that \nψ\n is a superposition of \nχ\n stabilizer states. Here we develop a comprehensive mathematical theory of the stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of \nχ\n∼\n10\n6\n stabilizer states and sample from the full \nn\n-bit output distribution, improving on previous simulations which used \n∼\n10\n3\n stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 \nT\n gates or 16 CCZ gates; these s...