Simulation of quantum circuits by low-rank stabilizer decompositions

View/ Open
Date
2019-09-02Author
Bravyi, Sergey
Browne, Dan
Calpin, Padraic
Campbell, Earl
Gosset, David
Howard, Mark
Metadata
Show full item recordUsage
This item's downloads: 174 (view details)
Cited 15 times in Scopus (view citations)
Recommended Citation
Bravyi, Sergey, Browne, Dan, Calpin, Padraic, Campbell, Earl, Gosset, David, & Howard, Mark. (2019). Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum, 3(181). doi: https://doi.org/10.22331/q-2019-09-02-181
Published Version
Abstract
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
s
t
a
b
i
l
i
z
e
r
rank
, which for a pure state
ψ
is defined to be the smallest integer
χ
such that
ψ
is a superposition of
χ
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
χ
∼
10
6
stabilizer states and sample from the full
n
-bit output distribution, improving on previous simulations which used
∼
10
3
stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64
T
gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.
Collections
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. Please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.
The following license files are associated with this item: