Classical Simulability of Quantum Circuits with Shallow Magic Depth

A. Ehrenfeucht and M. Karpinski, The computational complexity of (XOR, AND) counting problems (International Computer Science Inst., 1990)

1990

Earlier work this paper cites.

D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439

1992

Earlier work this paper cites.

P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings 35th annual symposium on foundations of computer science (Ieee, 1994) pp. 124–134

1994

Earlier work this paper cites.

S. A. Fenner, L. J. Fortnow, and S. A. Kurtz, Gap-definable counting classes, Journal of Computer and System Sciences 48

1994

Earlier work this paper cites.

A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem, arXiv preprint quant-ph/9511026 (1995)

1995

Earlier work this paper cites.

D. R. Simon, On the power of quantum computation, SIAM journal on computing 26

1997

Earlier work this paper cites.

D. Gottesman, Stabilizer codes and quantum error correction (California Institute of Technology, 1997)

1997

Earlier work this paper cites.

A. Y. Kitaev, Quantum error correction with imperfect gates, in Quantum communication, computing, and measurement (Springer, 1997) pp. 181–188

1997

Earlier work this paper cites.

D. Gottesman, The heisenberg representation of quantum computers, arXiv preprint quant-ph/9807006 (1998)

1998

Earlier work this paper cites.

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41

1999

Earlier work this paper cites.

D. Gottesman and I. L. Chuang, Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations, Nature 402

1999

Earlier work this paper cites.

J. Dehaene and B. De Moor, Clifford group, stabilizer states, and linear and quadratic operations over gf (2), Physical Review A 68

2003

Earlier work this paper cites.

N. Schuch and J. Siewert, Programmable networks for quantum algorithms, Physical review letters 91

2003

Earlier work this paper cites.

R. Raussendorf, D. E. Browne, and H. J. Briegel, Measurement-based quantum computation on cluster states, Physical review A 68

2003

Earlier work this paper cites.

S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A—Atomic, Molecular, and Optical Physics 70

2004

Earlier work this paper cites.

E. Knill, Fault-tolerant postselected quantum computation: Schemes, arXiv preprint quant-ph/0402171 (2004)

2004

Earlier work this paper cites.

Y. Shi, Quantum and classical tradeoffs, Theoretical computer science 344

2005

Earlier work this paper cites.

S. Bravyi and A. Kitaev, Universal quantum computation with ideal clifford gates and noisy ancillas, Physical Review A—Atomic, Molecular, and Optical Physics 71

2005

Earlier work this paper cites.

S. Aaronson, Quantum computing, postselection, and probabilistic polynomial-time, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461

2005

Earlier work this paper cites.

E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland, Randomized benchmarking of quantum gates, Physical Review A—Atomic, Molecular, and Optical Physics 77

2008

Earlier work this paper cites.

D. Shepherd and M. J. Bremner, Temporally unstructured quantum computation, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465

2009

Cited alongside, same era.

S. Aaronson and A. Arkhipov, The computational complexity of linear optics, in Proceedings of the forty-third annual ACM symposium on Theory of computing (2011) pp. 333–342

2011

Cited alongside, same era.

M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467

2011

Cited alongside, same era.

H. J. Garcia, I. L. Markov, and A. W. Cross, Efficient inner-product algorithm for stabilizer states, arXiv preprint arXiv:1210.6646 (2012)

Original

2012

Cited alongside, same era.

M.-H. Yung and B. Cheng, Anti-forging quantum data: Cryptographic verification of quantum computational power, arXiv preprint arXiv:2005.01510 (2020)

Original

2020

Later among the works it cites.

H. Qassim, H. Pashayan, and D. Gosset, Improved upper bounds on the stabilizer rank of magic states, Quantum 5

2021

Later among the works it cites.

C. Gidney and N. C. Jones, A cccz gate performed with 6 t gates, arXiv preprint arXiv:2106.11513 (2021)

Original

2021

Later among the works it cites.

A. J. Daley, I. Bloch, C. Kokail, S. Flannigan, N. Pearson, M. Troyer, and P. Zoller, Practical quantum advantage in quantum simulation, Nature 607

2022

Later among the works it cites.

S. Bravyi, D. Gosset, and Y. Liu, How to simulate quantum measurement without computing marginals, Physical Review Letters 128