On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking

by Scott Aaronson and Sam Gunn

Theory of Computing, Volume 16(11), pp. 1-8, 2020

Bibliography with links to cited articles

[1]   Scott Aaronson and Alex Arkhipov: The computational complexity of linear optics. Theory of Computing, 9(4):143–252, 2013. Preliminary version in STOC’11. [doi:10.4086/toc.2013.v009a004]

[2]   Scott Aaronson and Lijie Chen: Complexity-theoretic foundations of quantum supremacy experiments. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 22:1–22:67, 2017. [doi:10.4230/LIPIcs.CCC.2017.22, arXiv:1612.05903]

[3]   Frank Arute et al.: Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019. [doi:10.1038/s41586-019-1666-5]

[4]   Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven: Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, 2018. [doi:10.1038/s41567-018-0124-x]

[5]   Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani: On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159–163, 2019. Preliminary version in ITCS’19. [doi:10.1038/s41567-018-0318-2]

[6]   Michael Bremner, Richard Jozsa, and Dan Shepherd: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Royal Soc. London Ser. A, 467(2126):459–472, 2011. [arXiv:1005.1407]

[7]   Johnnie Gray and Stefanos Kourtis: Hyper-optimized tensor network contraction, 2020. [arXiv:2002.01935]

[8]   Aram Harrow and Saeed Mehraban: Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates. 2018. [arXiv:1809.06957]

[9]   Cupjin Huang, Michael Newman, and Mario Szegedy: Explicit lower bounds on strong quantum simulation. CoRR, 2018. [arXiv:1804.10368]

[10]   John Napp, Rolando L. La Placa, Alexander M. Dalzell, Fernando G. S. L. Brandao, and Aram W. Harrow: Efficient classical simulation of random shallow 2D quantum circuits. 2019. [arXiv:2001.00021]

[11]   Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff: Leveraging secondary storage to simulate deep 54-qubit Sycamore circuits. 2019. [arXiv:1910.09534]

[12]   Yiqing Zhou, E. Miles Stoudenmire, and Xavier Waintal: What limits the simulation of quantum computers?, 2020. [arXiv:2002.07730]