We present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a classical distribution on a quantum device that is supposed to demonstrate a quantum advantage. The other player, the skeptical Alice, is then allowed to propose mock distributions supposed to reproduce Bob's device's statistics. He then needs to provide witness functions to prove that Alice's proposed mock distributions cannot properly approximate his device. Within this framework, we establish three results. First, for random quantum circuits, Bob being able to efficiently distinguish his distribution from Alice's implies efficient approximate simulation of the distribution. Secondly, finding a polynomial time function to distinguish the output of random circuits from the uniform distribution can also spoof the heavy output generation problem in polynomial time. This pinpoints that exponential resources may be unavoidable for even the most basic verification tasks in the setting of random quantum circuits. Beyond this setting, by employing strong data processing inequalities, our framework allows us to analyse the effect of noise on classical simulability and verification of more general near-term quantum advantage proposals.
The easiest way to establish quantum advantage would be to solve a well-established hard computational problem, such as factoring large numbers or simulating large-sized molecules. Unfortunately, although well-known quantum algorithms provide speedups for these problems, their implementation is likely beyond the power of the devices that will be available in the following years.
Thus, the community focused on quantum advantage proposals based on sampling from the outcomes of random quantum circuits. This is because current quantum devices can sample from (noisy) circuits, and there is strong complexity-theoretic evidence that this is a challenging task for classical computers.
Unfortunately, this random circuit sampling is not known to have practical applications. Furthermore, it is not known how to certify that the quantum device is indeed sampling from a distribution close to the target one in some metric without employing exponential classical computational time. In fact, it is not even known how to efficiently distinguish the output of a random quantum circuit from a fair coin toss.
In this work, we show that the lack of efficient ways to distinguish the outputs of quantum circuits is intimately related to the hardness of their simulation. We exploit a framework where most of the existing approaches to certify quantum advantage can be understood as a game between an agent that wishes to convince the community to have reached quantum advantage (Bob), and a skeptical member (Alice).
In this game, Alice is allowed to propose an alternative hypothesis to what Bob's device is doing, say just sampling from fair coins. It is then Bob's job to propose an (efficient) test refuting Alice's hypothesis by pointing out that Alice cannot reproduce specific statistics of his distribution. Alice and Bob then play an interactive game of new proposal and refutation test proposals until one of the two players can not propose a new distribution (Alice) or a novel test (Bob) and concedes defeat.
Our main result is that Bob can never win this game in the setting of random quantum circuits using efficiently computable test functions. The reason is that the existence of an efficient way of distinguishing his distributions from Alice's would also allow Alice to simulate Bob's device efficiently. As it is not believed that the outputs of random quantum circuits can be simulated efficiently classically, our results indicate that for such problems, efficient verification strategies are not possible. In addition, we show that even the existence of an efficient test that distinguishes the output from perfectly random coins seems unlikely, as it is in direct contradiction with a recent complexity theory conjecture.
 Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Research in Optical Sciences. OSA, 2014a. 10.1364/qim.2014.qth1a.2.
 Scott Aaronson and Alex Arkhipov. Boson sampling is far from uniform. Quantum Info. Comput., 14 (15–16): 1383–1423, November 2014b. ISSN 1533-7146. https://doi.org/10.26421/qic14.15-16-7.
 Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32nd Computational Complexity Conference, 2017. ISBN 9783959770408. https://doi.org/10.48550/arXiv.1612.05903.
 Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5), Nov 2004. ISSN 1094-1622. 10.1103/physreva.70.052328.
 Scott Aaronson and Sam Gunn. On the classical hardness of spoofing linear cross-entropy benchmarking. Theory of Computing, 16 (11): 1–8, 2020. 10.4086/toc.2020.v016a011.
 Andris Ambainis and Joseph Emerson. Quantum t-designs: t-wise independence in the quantum world. In Twenty-Second Annual IEEE Conference on Computational Complexity 07). IEEE, jun 2007. 10.1109/ccc.2007.26.
 Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G S L Brandao, David A Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P Harrigan, Michael J Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S Humble, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C Platt, Chris Quintana, Eleanor G Rieffel, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Kevin J Sung, Matthew D Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. ISSN 1476-4687. 10.1038/s41586-019-1666-5.
 Salman Beigi, Nilanjana Datta, and Cambyse Rouzé. Quantum reverse hypercontractivity: Its tensorization and application to strong converses. Communications in Mathematical Physics, 376 (2): 753–794, may 2020. 10.1007/s00220-020-03750-z.
 Sergio Boixo, Troels F. Rønnow, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer. Evidence for quantum annealing with more than one hundred qubits. Nature Physics, 10 (3): 218–224, feb 2014. 10.1038/nphys2900.
 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, apr 2018. 10.1038/s41567-018-0124-x.
 Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15 (2): 159, 2019. https://doi.org/10.1038/s41567-018-0318-2.
 Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler Proofs of Quantumness. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-146-7. 10.4230/LIPIcs.TQC.2020.8.
 Michael J Bremner, Richard Jozsa, and Dan 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, volume 467, pages 459–472. The Royal Society, 2011. https://doi.org/10.1098/rspa.2010.0301.
 Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1: 8, apr 2017. 10.22331/q-2017-04-25-8.
 Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends® in Machine Learning, 8 (3-4): 231–357, 2015. ISSN 1935-8237. 10.1561/2200000050.
 Jacques Carolan, Jasmin D. A. Meinecke, Peter J. Shadbolt, Nicholas J. Russell, Nur Ismail, Kerstin Wörhoff, Terry Rudolph, Mark G. Thompson, Jeremy L. Brien, Jonathan C. F. Matthews, and Anthony Laing. On the experimental verification of quantum complexity in linear optics. Nature Photonics, 8 (8): 621–626, jul 2014. 10.1038/nphoton.2014.152.
 Kai-Min Chung, Yi Lee, Han-Hsuan Lin, and Xiaodi Wu. Constant-round Blind Classical Verification of Quantum Sampling. arXiv:2012.04848 [quant-ph], December 2020. arXiv: 2012.04848.
 Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A, 80 (1), jul 2009. 10.1103/physreva.80.012304.
 D.P. DiVincenzo, D.W. Leung, and B.M. Terhal. Quantum data hiding. IEEE Transactions on Information Theory, 48 (3): 580–598, Mar 2002. ISSN 0018-9448. 10.1109/18.985948.
 Daniel Stilck França and Raul Garcia-Patrón. Limitations of optimization algorithms on noisy quantum devices. Nature Physics, 17 (11): 1221–1227, oct 2021. 10.1038/s41567-021-01356-3.
 Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, and Soonwon Choi. Limitations of linear cross-entropy as a measure for quantum advantage, 2021. URL https://arxiv.org/abs/2112.01657.
 Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012.
 J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega. Closing gaps of a quantum advantage with short-time hamiltonian dynamics. Physical Review Letters, 125 (25): 250501, dec 2020. 10.1103/physrevlett.125.250501.
 Dominik Hangleiter, Juani Bermejo-Vega, Martin Schwarz, and Jens Eisert. Anticoncentration theorems for schemes showing a quantum speedup. Quantum, 2: 65, may 2018. 10.22331/q-2018-05-22-65.
 Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin. Sample complexity of device-independently certified ``quantum supremacy''. Phys. Rev. Lett., 122: 210502, May 2019. 10.1103/PhysRevLett.122.210502.
 Christoph Hirche, Cambyse Rouzé, and Daniel Stilck França. On contraction coefficients, partial orders and approximation of capacities for quantum channels, 2020. arXiv:2011.05949v1.
 Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen. Classical simulation of quantum supremacy circuits, 2020. arXiv:2005.06787.
 Michael J. Kastoryano and Kristan Temme. Quantum logarithmic sobolev inequalities and rapid mixing. Journal of Mathematical Physics, 54 (5): 052202, may 2013. 10.1063/1.4804995.
 S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220 (4598): 671–680, may 1983. 10.1126/science.220.4598.671.
 M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert. Dissipative quantum church-turing theorem. Physical Review Letters, 107 (12), sep 2011. 10.1103/physrevlett.107.120501.
 William Kretschmer. The Quantum Supremacy Tsirelson Inequality. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:13, Dagstuhl, Germany, 2021. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-177-1. 10.4230/LIPIcs.ITCS.2021.13.
 David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
 AP Lund, Michael J Bremner, and TC Ralph. Quantum sampling problems, Boson sampling and quantum supremacy. npj Quantum Information, 3 (1): 15, 2017. https://doi.org/10.1038/s41534-017-0018-2.
 Urmila Mahadev. Classical Verification of Quantum Computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259–267, Paris, October 2018. IEEE. ISBN 978-1-5386-4230-6. 10.1109/FOCS.2018.00033.
 Alexander Müller-Hermes, David Reeb, and Michael M. Wolf. Quantum subdivision capacities and continuous-time quantum coding. IEEE Transactions on Information Theory, 61 (1): 565–581, jan 2015. 10.1109/tit.2014.2366456.
 Alexander Müller-Hermes, Daniel Stilck França, and Michael M. Wolf. Relative entropy convergence for depolarizing channels. Journal of Mathematical Physics, 57 (2): 022202, feb 2016a. 10.1063/1.4939560.
 Alexander Müller-Hermes, Daniel Stilck França, and Michael M. Wolf. Entropy production of doubly stochastic quantum channels. Journal of Mathematical Physics, 57 (2): 022203, feb 2016b. 10.1063/1.4941136.
 C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen, Z. Chen, A. Fowler, B. Foxen, M. Giustina, R. Graff, E. Jeffrey, T. Huang, J. Kelly, P. Klimov, E. Lucero, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, H. Neven, and J. M. Martinis. A blueprint for demonstrating quantum supremacy with superconducting qubits. Science, 360 (6385): 195–199, apr 2018. 10.1126/science.aao4309.
 Feng Pan and Pan Zhang. Simulation of quantum circuits using the big-batch tensor network method. Physical Review Letters, 128 (3): 030501, jan 2022. 10.1103/physrevlett.128.030501.
 Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff. Leveraging secondary storage to simulate deep 54-qubit sycamore circuits, 2019. https://arxiv.org/abs/1910.09534.
 D. S. Phillips, M. Walschaers, J. J. Renema, I. A. Walmsley, N. Treps, and J. Sperling. Benchmarking of Gaussian boson sampling using two-point correlators. Physical Review A, 99 (2): 023836, February 2019. ISSN 2469-9926, 2469-9934. 10.1103/PhysRevA.99.023836.
 Haoyu Qi, Daniel J. Brod, Nicolás Quesada, and Raul Garcia-Patron. Regimes of classical simulability for noisy gaussian boson sampling. Physical Review Letters, 124 (10), mar 2020. 10.1103/physrevlett.124.100502.
 Nicolò Spagnolo, Chiara Vitelli, Marco Bentivegna, Daniel J. Brod, Andrea Crespi, Fulvio Flamini, Sandro Giacomini, Giorgio Milani, Roberta Ramponi, Paolo Mataloni, Roberto Osellame, Ernesto F. Galvão, and Fabio Sciarrino. Experimental validation of photonic boson sampling. Nature Photonics, 8 (8): 615–620, jun 2014. 10.1038/nphoton.2014.135.
 Koji Tsuda, Gunnar Rätsch, and Manfred K Warmuth. Matrix exponentiated gradient updates for on-line learning and bregman projection. J. Mach. Learn. Res., 6 (Jun): 995–1018, 2005.
 Benjamin Villalonga, Murphy Yuezhen Niu, Li Li, Hartmut Neven, John C. Platt, Vadim N. Smelyanskiy, and Sergio Boixo. Efficient approximation of experimental Gaussian boson sampling, 2021. arXiv:2109.11525v1.
 Lei Wang, Troels F. Rønnow, Sergio Boixo, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer. Comment on: "classical signature of quantum annealing", 2013. https://arxiv.org/abs/1305.5837.
 Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. Strong quantum computational advantage using a superconducting quantum processor. Physical Review Letters, 127 (18): 180501, oct 2021. 10.1103/physrevlett.127.180501.
 Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. Quantum computational advantage using photons. Science, 370 (6523): 1460–1463, December 2020. 10.1126/science.abe8770.
 Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. Science Bulletin, 67 (3): 240–245, feb 2022. 10.1016/j.scib.2021.10.017.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.