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]