Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates.

By Sergey Bravyi, David Gosset. Physical Review Letters, 2016

399 citations recorded by the source corpus.

We present a new algorithm for classical simulation of quantum circuits over the Clifford+T gate set. The runtime of the algorithm is polynomial in the number of qubits and the number of Clifford gates in the circuit but exponential in the number of T gates. The exponential scaling is sufficiently mild that the algorithm can be used in practice to simulate medium-sized quantum circuits dominated by Clifford gates. The first demonstrations of fault-tolerant quantum circuits based on 2D topological codes are likely to be dominated by Clifford gates due to a high implementation cost associated with logical T gates. Thus our algorithm may serve as a verification tool for near-term quantum computers which cannot in practice be simulated by other means. To demonstrate the power of the new method, we performed a classical simulation of a hidden shift quantum algorithm with 40 qubits, a few hundred Clifford gates, and nearly 50 T gates.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/c3be3baafe708dab689fdfb917161fd8823d1054

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Suguru Endo
2. Simon C. Benjamin
3. Göran Wendin
4. Jarrod R. McClean
5. Ying Li
6. Ryan Babbush
7. Jay M. Gambetta
8. Patrick J. Coles

In Computational Theory and Mathematics

1. Göran Wendin
2. Andreas J. Winter
3. Zi-Wen Liu
4. Ashley Montanaro
5. Jarrod R. McClean
6. Sergey Bravyi
7. Ying Li
8. Dan E. Browne

Citations in the corpus

• Qulacs: a fast and versatile quantum circuit simulator for research purpose (2020, background): “[8] Sergey Bravyi and David Gosset, “Improved classical simulation of quantum circuits dominated by clifford gates,” Phys.”
• Many-Body Quantum Magic (2020, methodology): “[43] Sergey Bravyi and David Gosset, “Improved classical simulation of quantum circuits dominated by clifford gates,” Phys.”
• Quantum information processing with superconducting circuits: a review (2016, methodology): “However, the exponential scaling was sufficiently mild that it was possible to use the algorithm to simulate classically a medium­sized quantum circuit dominated by Clifford gates, namely a hidden­shift quantum algorithm with 40 qubits, a few hundred Clifford gates, and nearly 50 T gates [203].”
• Quantum circuits and low-degree polynomials over F2 (2016, background): “It was already shown by Aaronson and Gottesman that circuits on ` qubits containing k non-Clifford gates can be simulated in time 2O(k) poly(`) [2], and more recent work has improved the constant hidden in the O(k) term for circuits where the only non-Clifford gate is the T gate [9, 8].”
• Quantum computational supremacy (2017, background): “A non-trivial example of this is executing computations which are mostly or entirely comprised of Clifford gates, which are known to be efficiently classically simulable 5,10 despite displaying such quantum characteristics as allowing the creation of large-scale entanglement.”
• Simulation of quantum circuits by low-rank stabilizer decompositions (2018, methodology): “48m with certain polynomial prefactors [11].”
• The future of quantum computing with superconducting qubits (2022, background): “This is far beyond the limit of existing classical algorithms that can simulate Clifford+ T circuits with about 50 T -gates 84,85 .”
• Quantum error mitigation (2022, background): “This is well beyond the classically tractable regime of ∼ 50 T gates (Bravyi and Gosset, 2016).”