Quantum supremacy and hardness of estimating output probabilities of quantum circuits

L. Stockmeyer, “On approximation algorithms for # ​ 𝖯 \#\mathsf{P} ,” SIAM Journal on Computing , vol. 14, no. 4, pp. 849–861, 1985

1985

Earlier work this paper cites.

R. P. Feynman, “Quantum mechanical computers,” Foundations of physics , vol. 16, no. 6, pp. 507–531, 1986

1986

Earlier work this paper cites.

L. R. Welch and E. R. Berlekamp, “Error correction for algebraic block codes,” Dec. 30 1986, uS Patent 4 633 470

1986

Earlier work this paper cites.

R. Paturi, “On the degree of polynomials that approximate symmetric boolean functions (preliminary version),” in Proceedings of the twenty-fourth annual ACM symposium on Theory of computing . ACM, 1992, pp. 468–474

1992

Earlier work this paper cites.

L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , 1996, pp. 212–219

1996

Earlier work this paper cites.

D. R. Simon, “On the power of quantum computation,” SIAM journal on computing , vol. 26, no. 5, pp. 1474–1483, 1997

1997

Earlier work this paper cites.

S. Fenner, F. Green, S. Homer, and R. Pruim, “Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy,” arXiv preprint quant-ph/9812056 , 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 , vol. 41, no. 2, pp. 303–332, 1999

1999

Earlier work this paper cites.

B. M. Terhal and D. P. DiVincenzo, “Adaptive quantum computation, constant depth quantum circuits and Arthur–Merlin games,” Quant. Inf. Comp. , vol. 4, no. 2, pp. 134–145, 2004

2004

Earlier work this paper cites.

E. A. Rakhmanov, “Bounds for polynomials with a unit discrete norm,” Annals of mathematics , pp. 55–88, 2007

2007

Earlier work this paper cites.

S. Arora and B. Barak, Computational Complexity: A Modern Approach , 1st ed. USA: Cambridge University Press, 2009

2009

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,” in Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences , vol. 467, no. 2126. The Royal Society, 2011, pp. 459–472

2011

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 . ACM, 2011, pp. 333–342

2011

Cited alongside, same era.

M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Average-case complexity versus approximate simulation of commuting quantum computations,” Physical review letters , vol. 117, no. 8, p. 080501, 2016

2016

Cited alongside, same era.

A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, “On the complexity and verification of quantum random circuit sampling,” Nature Physics , vol. 15, no. 2, p. 159, 2019

2019

Later among the works it cites.

S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, “Simulation of quantum circuits by low-rank stabilizer decompositions,” Quantum , vol. 3, p. 181, 2019

2019

Later among the works it cites.

J. Napp, R. L. La Placa, A. M. Dalzell, F. G. Brandao, and A. W. Harrow, “Efficient classical simulation of random shallow 2D quantum circuits,” arXiv preprint arXiv:2001.00021 , 2020

Original

2020

Later among the works it cites.

C. Huang, F. Zhang, M. Newman, J. Cai, X. Gao, Z. Tian, J. Wu, H. Xu, H. Yu, B. Yuan et al. , “Classical simulation of quantum supremacy circuits,” arXiv preprint arXiv:2005.06787 , 2020

Original

2020

Later among the works it cites.