Bravyi, S;
Browne, D;
Calpin, P;
Campbell, E;
Gosset, D;
Howard, M;
(2019)
Simulation of quantum circuits by ow-rank sotabilizer decompositions.
Quantum
, 3
, Article 181. 10.22331/q-2019-09-02-181.
Preview |
Text
q-2019-09-02-181.pdf - Published Version Download (3MB) | Preview |
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 stabilizer 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 χ ∼ 106 stabilizer states and sample from the full n-bit output distribution, improving on previous simulations which used ∼ 103 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.
| Type: | Article |
|---|---|
| Title: | Simulation of quantum circuits by ow-rank sotabilizer decompositions |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.22331/q-2019-09-02-181 |
| Publisher version: | https://doi.org/10.22331/q-2019-09-02-181 |
| Language: | English |
| Additional information: | Published under CC-BY 4.0. http://creativecommons.org/licenses/by/4.0/ |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Physics and Astronomy |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10091572 |
Archive Staff Only
 |
View Item |
