On Certified Randomness from Fourier Sampling or Random Circuit Sampling
Summarize this article with:
AbstractCertified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.► BibTeX data@article{Bassirian2026certifiedrandomness, doi = {10.22331/q-2026-02-10-2002}, url = {https://doi.org/10.22331/q-2026-02-10-2002}, title = {On {C}ertified {R}andomness from {F}ourier {S}ampling or {R}andom {C}ircuit {S}ampling}, author = {Bassirian, Roozbeh and Bouland, Adam and Fefferman, Bill and Gunn, Sam and Tal, Avishay}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2002}, month = feb, year = {2026} }► References [1] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory Comput., 9:143–252, 2013. doi:10.4086/toc.2013.v009a004. https://doi.org/10.4086/toc.2013.v009a004 [2] S. Aaronson and A. Ambainis. The need for structure in quantum speedups. Theory Comput., 10:133–166, 2014. doi:10.4086/TOC.2014.V010A006. https://doi.org/10.4086/TOC.2014.V010A006 [3] S. Aaronson and A. Arkhipov. Bosonsampling is far from uniform. Quantum Inf. Comput., 14(15-16):1383–1423, 2014. doi:10.26421/QIC14.15-16-7. https://doi.org/10.26421/QIC14.15-16-7 [4] S. Aaronson and A. Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM J. Comput., 47(3):982–1038, 2018. doi:10.1137/15M1050902. https://doi.org/10.1137/15M1050902 [5] F. Arute, K. Arya, R. Babbush, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019. doi:10.1038/s41586-019-1666-5. https://doi.org/10.1038/s41586-019-1666-5 [6] S. Aaronson. BQP and the polynomial hierarchy. In L. J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 141–150. ACM, 2010. doi:10.1145/1806689.1806711. https://doi.org/10.1145/1806689.1806711 [7] S. Aaronson. Certified randomness from quantum supremacy. Talk at CRYPTO 2018, October 2018. [8] S. Aaronson. Quantum supremacy and its applications. Talk at the Simons Institute for the Theory of Computing, June 2018. [9] S. Aaronson. On entropy from random circuit sampling. Talk at the Simons Institute for the Theory of Computing, May 2020. [10] S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy experiments. In R. O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 22:1–22:67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.22. https://doi.org/10.4230/LIPIcs.CCC.2017.22 [11] S. Aaronson and S. Gunn. On the classical hardness of spoofing linear cross-entropy benchmarking. Theory Comput., 16:1–8, 2020. doi:10.4086/TOC.2020.V016A011. https://doi.org/10.4086/TOC.2020.V016A011 [12] S. Aaronson and S. Hung. Certified randomness from quantum supremacy. In B. Saha and R. A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 933–944. ACM, 2023. doi:10.1145/3564246.3585145. https://doi.org/10.1145/3564246.3585145 [13] A. Acín and L. Masanes. Certified randomness in quantum physics. Nature, 540(7632):213–219, 2016. doi:10.1038/nature20119. https://doi.org/10.1038/nature20119 [14] C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. doi:10.1137/S0097539796300933. https://doi.org/10.1137/S0097539796300933 [15] Z. Brakerski, P. F. Christiano, U. Mahadev, U. V. Vazirani, and T. Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. J. ACM, 68(5):31:1–31:47, 2021. doi:10.1145/3441309. https://doi.org/10.1145/3441309 [16] A. Bouland, B. Fefferman, Z. Landau, and Y. Liu. Noise and the frontier of quantum supremacy. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1308–1317. IEEE, 2021. doi:10.1109/FOCS52979.2021.00127. https://doi.org/10.1109/FOCS52979.2021.00127 [17] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159–163, 2019. doi:10.1038/s41567-018-0318-2. https://doi.org/10.1038/s41567-018-0318-2 [18] R. B. Boppana, J. Håstad, and S. Zachos. Does co-NP have short interactive proofs? Inf. Process. Lett., 25(2):127–132, 1987. doi:10.1016/0020-0190(87)90232-8. https://doi.org/10.1016/0020-0190(87)90232-8 [19] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, et al. Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, 2018. doi:10.1038/s41567-018-0124-x. https://doi.org/10.1038/s41567-018-0124-x [20] 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:459–472, 2010. doi:10.1098/rspa.2010.0301. https://doi.org/10.1098/rspa.2010.0301 [21] Z. Brakerski, V. Koppula, U. V. Vazirani, and T. Vidick. Simpler proofs of quantumness. In S. T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, Riga, Latvia, June 9-12, 2020, volume 158 of LIPIcs, pages 8:1–8:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.TQC.2020.8. https://doi.org/10.4230/LIPICS.TQC.2020.8 [22] M. J. Bremner, A. Montanaro, and D. J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117(8):080501, 2016. doi:10.1103/PhysRevLett.117.080501. https://doi.org/10.1103/PhysRevLett.117.080501 [23] E. Bernstein and U. V. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. doi:10.1137/S0097539796300921. https://doi.org/10.1137/S0097539796300921 [24] N. Chia, K. Chung, and T. Yamakawa. Classical verification of quantum computations with efficient verifier. In R. Pass and K. Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III, volume 12552 of Lecture Notes in Computer Science, pages 181–206. Springer, 2020. doi:10.1007/978-3-030-64381-2_7. https://doi.org/10.1007/978-3-030-64381-2_7 [25] E. Chattopadhyay, P. Hatami, K. Hosseini, and S. Lovett. Pseudorandom generators from polarizing random walks. Theory Comput., 15:1–26, 2019. doi:10.4086/toc.2019.v015a010. https://doi.org/10.4086/toc.2019.v015a010 [26] E. Chattopadhyay, P. Hatami, S. Lovett, and A. Tal. Pseudorandom generators from the second fourier level and applications to AC0 with parity gates. In A. Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 22:1–22:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.22. https://doi.org/10.4230/LIPIcs.ITCS.2019.22 [27] M. Coudron, J. Stark, and T. Vidick. Trading locality for time: Certifiable randomness from low-depth circuits. Communications in Mathematical Physics, 382(1):49–86, Feb. 2021. doi:10.1007/s00220-021-03963-w. https://doi.org/10.1007/s00220-021-03963-w [28] B. Fefferman, R. Shaltiel, C. Umans, and E. Viola. On beating the hybrid argument. Theory Comput., 9:809–843, 2013. doi:10.4086/toc.2013.v009a026. https://doi.org/10.4086/toc.2013.v009a026 [29] B. Fefferman and C. Umans. On the power of quantum fourier sampling. In A. Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, Berlin, Germany, September 27-29, 2016, volume 61 of LIPIcs, pages 1:1–1:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.TQC.2016.1. https://doi.org/10.4230/LIPICS.TQC.2016.1 [30] E. Gat and S. Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. Electron. Colloquium Comput. Complex., page 136, 2011. URL https://eccc.weizmann.ac.il/report/2011/136. https://eccc.weizmann.ac.il/report/2011/136 [31] O. Goldreich, S. Goldwasser, and D. Ron. On the possibilities and limitations of pseudodeterministic algorithms. In R. D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 127–138. ACM, 2013. doi:10.1145/2422436.2422453. https://doi.org/10.1145/2422436.2422453 [32] S. Goldwasser, R. Impagliazzo, T. Pitassi, and R. Santhanam. On the pseudo-deterministic query complexity of NP search problems. In V. Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 36:1–36:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CCC.2021.36. https://doi.org/10.4230/LIPIcs.CCC.2021.36 [33] X. Gao, M. Kalinowski, C.-N. Chou, et al. Limitations of linear cross-entropy as a measure for quantum advantage. PRX Quantum, 5:010334, Feb 2024. doi:10.1103/PRXQuantum.5.010334. https://doi.org/10.1103/PRXQuantum.5.010334 [34] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219, 1996. doi:10.1145/237814.237866. https://doi.org/10.1145/237814.237866 [35] V. Guruswami, C. Umans, and S. P. Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. J. ACM, 56(4):20:1–20:34, 2009. doi:10.1145/1538902.1538904. https://doi.org/10.1145/1538902.1538904 [36] J. Håstad. Computational limitations for small depth circuits. PhD thesis, Massachusetts Institute of Technology, 1986. [37] S. Hirahara and F. L. Gall. Test of quantumness with small-depth quantum circuits. In F. Bonchi and S. J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 59:1–59:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.MFCS.2021.59. https://doi.org/10.4230/LIPIcs.MFCS.2021.59 [38] D. Hangleiter, M. Kliesch, J. Eisert, and C. Gogolin. Sample complexity of device-independently certified “quantum supremacy”.
Physical Review Letters, 122(21), May 2019. doi:10.1103/physrevlett.122.210502. https://doi.org/10.1103/physrevlett.122.210502 [39] L. Isserlis. On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables. Biometrika, 12(1/2):134–139, 1918. doi:10.2307/2331932. https://doi.org/10.2307/2331932 [40] G. D. Kahanamoku-Meyer, S. Choi, U. V. Vazirani, and N. Y. Yao. Classically-verifiable quantum advantage from a computational bell test. CoRR, abs/2104.00687, 2021. arXiv:2104.00687, doi:10.1038/s41567-022-01643-7. https://doi.org/10.1038/s41567-022-01643-7 arXiv:2104.00687 [41] H. Kobayashi, F. L. Gall, and H. Nishimura. Generalized quantum arthur-merlin games. SIAM J. Comput., 48(3):865–902, 2019. doi:10.1137/17M1160173. https://doi.org/10.1137/17M1160173 [42] Y. Kondo, R. Mori, and R. Movassagh. Quantum supremacy and hardness of estimating output probabilities of quantum circuits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1296–1307. IEEE, 2021. doi:10.1109/FOCS52979.2021.00126. https://doi.org/10.1109/FOCS52979.2021.00126 [43] H. Krovi. Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent. CoRR, abs/2206.05642, 2022. arXiv:2206.05642, doi:10.48550/ARXIV.2206.05642. https://doi.org/10.48550/ARXIV.2206.05642 arXiv:2206.05642 [44] Z. Liu and A. Gheorghiu. Depth-efficient proofs of quantumness. Quantum, 6:807, Sept. 2022. doi:10.22331/q-2022-09-19-807. https://doi.org/10.22331/q-2022-09-19-807 [45] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):1302 – 1338, 2000. doi:10.1214/aos/1015957395. https://doi.org/10.1214/aos/1015957395 [46] R. Movassagh. Cayley path and quantum computational supremacy: A proof of average-case #p-hardness of random circuit sampling with quantified robustness. CoRR, abs/1909.06210, 2019. arXiv:1909.06210, doi:10.48550/arXiv.1909.06210. https://doi.org/10.48550/arXiv.1909.06210 arXiv:1909.06210 [47] S. Pironio, A. Acín, S. Massar, et al. Random numbers certified by bell’s theorem. Nature, 464(7291):1021–1024, Apr 2010. doi:10.1038/nature09008. https://doi.org/10.1038/nature09008 [48] C. E. Porter and R. G. Thomas. Fluctuations of nuclear reaction widths. Phys. Rev., 104:483–491, Oct 1956. doi:10.1103/PhysRev.104.483. https://doi.org/10.1103/PhysRev.104.483 [49] R. Raz and A. Tal. Oracle separation of BQP and PH. In M. Charikar and E. Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 13–23. ACM, 2019. doi:10.1145/3313276.3316315. https://doi.org/10.1145/3313276.3316315 [50] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. doi:10.1137/S0097539795293172. https://doi.org/10.1137/S0097539795293172 [51] A. Tal. Tight bounds on the Fourier spectrum of AC0. In R. O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 15:1–15:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.15. https://doi.org/10.4230/LIPIcs.CCC.2017.15 [52] B. M. Terhal and D. P. DiVincenzo.
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games. Quant. Inf. Comput., 4(2):134–145, 2004. arXiv:quant-ph/0205133, doi:10.26421/QIC4.2-5. https://doi.org/10.26421/QIC4.2-5 arXiv:quant-ph/0205133 [53] E. Viola. On approximate majority and probabilistic time. In 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA, pages 155–168. IEEE Computer Society, 2007. doi:10.1109/CCC.2007.16. https://doi.org/10.1109/CCC.2007.16 [54] G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. SIAM J. Comput., 46(1):429–455, 2017. doi:10.1137/151002526. https://doi.org/10.1137/151002526 [55] X. Wu. A stochastic calculus approach to the oracle separation of $\mathsf{BQP}$ and $\mathsf{PH}$. Theory of Computing, 18(17):1–11, 2022. doi:10.4086/toc.2022.v018a017. https://doi.org/10.4086/toc.2022.v018a017 [56] T. Yamakawa and M. Zhandry. Verifiable quantum advantage without structure. J. ACM, 71(3):20, 2024. doi:10.1145/3658665. https://doi.org/10.1145/3658665 [57] Q. Zhu, S. Cao, F. Chen, et al. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. Science Bulletin, 67(3):240–245, 2022. doi:https://doi.org/10.1016/j.scib.2021.10.017. https://doi.org/10.1016/j.scib.2021.10.017 [58] H.-S. Zhong, Y.-H. Deng, J. Qin, et al. Phase-programmable gaussian boson sampling using stimulated squeezed light. Phys. Rev. Lett., 127:180502, Oct 2021. doi:10.1103/PhysRevLett.127.180502. https://doi.org/10.1103/PhysRevLett.127.180502 [59] H.-S. Zhong, H. Wang, Y.-H. Deng, et al. Quantum computational advantage using photons. Science, 370(6523):1460–1463, Dec 2020. doi:10.1126/science.abe8770. https://doi.org/10.1126/science.abe8770Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-10 10:03:07: Could not fetch cited-by data for 10.22331/q-2026-02-10-2002 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-10 10:03:07: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractCertified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.► BibTeX data@article{Bassirian2026certifiedrandomness, doi = {10.22331/q-2026-02-10-2002}, url = {https://doi.org/10.22331/q-2026-02-10-2002}, title = {On {C}ertified {R}andomness from {F}ourier {S}ampling or {R}andom {C}ircuit {S}ampling}, author = {Bassirian, Roozbeh and Bouland, Adam and Fefferman, Bill and Gunn, Sam and Tal, Avishay}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2002}, month = feb, year = {2026} }► References [1] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory Comput., 9:143–252, 2013. doi:10.4086/toc.2013.v009a004. https://doi.org/10.4086/toc.2013.v009a004 [2] S. Aaronson and A. Ambainis. The need for structure in quantum speedups. Theory Comput., 10:133–166, 2014. doi:10.4086/TOC.2014.V010A006. https://doi.org/10.4086/TOC.2014.V010A006 [3] S. Aaronson and A. Arkhipov. Bosonsampling is far from uniform. Quantum Inf. Comput., 14(15-16):1383–1423, 2014. doi:10.26421/QIC14.15-16-7. https://doi.org/10.26421/QIC14.15-16-7 [4] S. Aaronson and A. Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM J. Comput., 47(3):982–1038, 2018. doi:10.1137/15M1050902. https://doi.org/10.1137/15M1050902 [5] F. Arute, K. Arya, R. Babbush, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019. doi:10.1038/s41586-019-1666-5. https://doi.org/10.1038/s41586-019-1666-5 [6] S. Aaronson. BQP and the polynomial hierarchy. In L. J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 141–150. ACM, 2010. doi:10.1145/1806689.1806711. https://doi.org/10.1145/1806689.1806711 [7] S. Aaronson. Certified randomness from quantum supremacy. Talk at CRYPTO 2018, October 2018. [8] S. Aaronson. Quantum supremacy and its applications. Talk at the Simons Institute for the Theory of Computing, June 2018. [9] S. Aaronson. On entropy from random circuit sampling. Talk at the Simons Institute for the Theory of Computing, May 2020. [10] S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy experiments. In R. O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 22:1–22:67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.22. https://doi.org/10.4230/LIPIcs.CCC.2017.22 [11] S. Aaronson and S. Gunn. On the classical hardness of spoofing linear cross-entropy benchmarking. Theory Comput., 16:1–8, 2020. doi:10.4086/TOC.2020.V016A011. https://doi.org/10.4086/TOC.2020.V016A011 [12] S. Aaronson and S. Hung. Certified randomness from quantum supremacy. In B. Saha and R. A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 933–944. ACM, 2023. doi:10.1145/3564246.3585145. https://doi.org/10.1145/3564246.3585145 [13] A. Acín and L. Masanes. Certified randomness in quantum physics. Nature, 540(7632):213–219, 2016. doi:10.1038/nature20119. https://doi.org/10.1038/nature20119 [14] C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. doi:10.1137/S0097539796300933. https://doi.org/10.1137/S0097539796300933 [15] Z. Brakerski, P. F. Christiano, U. Mahadev, U. V. Vazirani, and T. Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. J. ACM, 68(5):31:1–31:47, 2021. doi:10.1145/3441309. https://doi.org/10.1145/3441309 [16] A. Bouland, B. Fefferman, Z. Landau, and Y. Liu. Noise and the frontier of quantum supremacy. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1308–1317. IEEE, 2021. doi:10.1109/FOCS52979.2021.00127. https://doi.org/10.1109/FOCS52979.2021.00127 [17] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159–163, 2019. doi:10.1038/s41567-018-0318-2. https://doi.org/10.1038/s41567-018-0318-2 [18] R. B. Boppana, J. Håstad, and S. Zachos. Does co-NP have short interactive proofs? Inf. Process. Lett., 25(2):127–132, 1987. doi:10.1016/0020-0190(87)90232-8. https://doi.org/10.1016/0020-0190(87)90232-8 [19] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, et al. Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6):595–600, 2018. doi:10.1038/s41567-018-0124-x. https://doi.org/10.1038/s41567-018-0124-x [20] 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:459–472, 2010. doi:10.1098/rspa.2010.0301. https://doi.org/10.1098/rspa.2010.0301 [21] Z. Brakerski, V. Koppula, U. V. Vazirani, and T. Vidick. Simpler proofs of quantumness. In S. T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, Riga, Latvia, June 9-12, 2020, volume 158 of LIPIcs, pages 8:1–8:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.TQC.2020.8. https://doi.org/10.4230/LIPICS.TQC.2020.8 [22] M. J. Bremner, A. Montanaro, and D. J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117(8):080501, 2016. doi:10.1103/PhysRevLett.117.080501. https://doi.org/10.1103/PhysRevLett.117.080501 [23] E. Bernstein and U. V. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. doi:10.1137/S0097539796300921. https://doi.org/10.1137/S0097539796300921 [24] N. Chia, K. Chung, and T. Yamakawa. Classical verification of quantum computations with efficient verifier. In R. Pass and K. Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III, volume 12552 of Lecture Notes in Computer Science, pages 181–206. Springer, 2020. doi:10.1007/978-3-030-64381-2_7. https://doi.org/10.1007/978-3-030-64381-2_7 [25] E. Chattopadhyay, P. Hatami, K. Hosseini, and S. Lovett. Pseudorandom generators from polarizing random walks. Theory Comput., 15:1–26, 2019. doi:10.4086/toc.2019.v015a010. https://doi.org/10.4086/toc.2019.v015a010 [26] E. Chattopadhyay, P. Hatami, S. Lovett, and A. Tal. Pseudorandom generators from the second fourier level and applications to AC0 with parity gates. In A. Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 22:1–22:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.22. https://doi.org/10.4230/LIPIcs.ITCS.2019.22 [27] M. Coudron, J. Stark, and T. Vidick. Trading locality for time: Certifiable randomness from low-depth circuits. Communications in Mathematical Physics, 382(1):49–86, Feb. 2021. doi:10.1007/s00220-021-03963-w. https://doi.org/10.1007/s00220-021-03963-w [28] B. Fefferman, R. Shaltiel, C. Umans, and E. Viola. On beating the hybrid argument. Theory Comput., 9:809–843, 2013. doi:10.4086/toc.2013.v009a026. https://doi.org/10.4086/toc.2013.v009a026 [29] B. Fefferman and C. Umans. On the power of quantum fourier sampling. In A. Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, Berlin, Germany, September 27-29, 2016, volume 61 of LIPIcs, pages 1:1–1:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.TQC.2016.1. https://doi.org/10.4230/LIPICS.TQC.2016.1 [30] E. Gat and S. Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. Electron. Colloquium Comput. Complex., page 136, 2011. URL https://eccc.weizmann.ac.il/report/2011/136. https://eccc.weizmann.ac.il/report/2011/136 [31] O. Goldreich, S. Goldwasser, and D. Ron. On the possibilities and limitations of pseudodeterministic algorithms. In R. D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 127–138. ACM, 2013. doi:10.1145/2422436.2422453. https://doi.org/10.1145/2422436.2422453 [32] S. Goldwasser, R. Impagliazzo, T. Pitassi, and R. Santhanam. On the pseudo-deterministic query complexity of NP search problems. In V. Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 36:1–36:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CCC.2021.36. https://doi.org/10.4230/LIPIcs.CCC.2021.36 [33] X. Gao, M. Kalinowski, C.-N. Chou, et al. Limitations of linear cross-entropy as a measure for quantum advantage. PRX Quantum, 5:010334, Feb 2024. doi:10.1103/PRXQuantum.5.010334. https://doi.org/10.1103/PRXQuantum.5.010334 [34] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219, 1996. doi:10.1145/237814.237866. https://doi.org/10.1145/237814.237866 [35] V. Guruswami, C. Umans, and S. P. Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. J. ACM, 56(4):20:1–20:34, 2009. doi:10.1145/1538902.1538904. https://doi.org/10.1145/1538902.1538904 [36] J. Håstad. Computational limitations for small depth circuits. PhD thesis, Massachusetts Institute of Technology, 1986. [37] S. Hirahara and F. L. Gall. Test of quantumness with small-depth quantum circuits. In F. Bonchi and S. J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 59:1–59:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.MFCS.2021.59. https://doi.org/10.4230/LIPIcs.MFCS.2021.59 [38] D. Hangleiter, M. Kliesch, J. Eisert, and C. Gogolin. Sample complexity of device-independently certified “quantum supremacy”.
Physical Review Letters, 122(21), May 2019. doi:10.1103/physrevlett.122.210502. https://doi.org/10.1103/physrevlett.122.210502 [39] L. Isserlis. On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables. Biometrika, 12(1/2):134–139, 1918. doi:10.2307/2331932. https://doi.org/10.2307/2331932 [40] G. D. Kahanamoku-Meyer, S. Choi, U. V. Vazirani, and N. Y. Yao. Classically-verifiable quantum advantage from a computational bell test. CoRR, abs/2104.00687, 2021. arXiv:2104.00687, doi:10.1038/s41567-022-01643-7. https://doi.org/10.1038/s41567-022-01643-7 arXiv:2104.00687 [41] H. Kobayashi, F. L. Gall, and H. Nishimura. Generalized quantum arthur-merlin games. SIAM J. Comput., 48(3):865–902, 2019. doi:10.1137/17M1160173. https://doi.org/10.1137/17M1160173 [42] Y. Kondo, R. Mori, and R. Movassagh. Quantum supremacy and hardness of estimating output probabilities of quantum circuits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1296–1307. IEEE, 2021. doi:10.1109/FOCS52979.2021.00126. https://doi.org/10.1109/FOCS52979.2021.00126 [43] H. Krovi. Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent. CoRR, abs/2206.05642, 2022. arXiv:2206.05642, doi:10.48550/ARXIV.2206.05642. https://doi.org/10.48550/ARXIV.2206.05642 arXiv:2206.05642 [44] Z. Liu and A. Gheorghiu. Depth-efficient proofs of quantumness. Quantum, 6:807, Sept. 2022. doi:10.22331/q-2022-09-19-807. https://doi.org/10.22331/q-2022-09-19-807 [45] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):1302 – 1338, 2000. doi:10.1214/aos/1015957395. https://doi.org/10.1214/aos/1015957395 [46] R. Movassagh. Cayley path and quantum computational supremacy: A proof of average-case #p-hardness of random circuit sampling with quantified robustness. CoRR, abs/1909.06210, 2019. arXiv:1909.06210, doi:10.48550/arXiv.1909.06210. https://doi.org/10.48550/arXiv.1909.06210 arXiv:1909.06210 [47] S. Pironio, A. Acín, S. Massar, et al. Random numbers certified by bell’s theorem. Nature, 464(7291):1021–1024, Apr 2010. doi:10.1038/nature09008. https://doi.org/10.1038/nature09008 [48] C. E. Porter and R. G. Thomas. Fluctuations of nuclear reaction widths. Phys. Rev., 104:483–491, Oct 1956. doi:10.1103/PhysRev.104.483. https://doi.org/10.1103/PhysRev.104.483 [49] R. Raz and A. Tal. Oracle separation of BQP and PH. In M. Charikar and E. Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 13–23. ACM, 2019. doi:10.1145/3313276.3316315. https://doi.org/10.1145/3313276.3316315 [50] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. doi:10.1137/S0097539795293172. https://doi.org/10.1137/S0097539795293172 [51] A. Tal. Tight bounds on the Fourier spectrum of AC0. In R. O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 15:1–15:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.15. https://doi.org/10.4230/LIPIcs.CCC.2017.15 [52] B. M. Terhal and D. P. DiVincenzo.
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games. Quant. Inf. Comput., 4(2):134–145, 2004. arXiv:quant-ph/0205133, doi:10.26421/QIC4.2-5. https://doi.org/10.26421/QIC4.2-5 arXiv:quant-ph/0205133 [53] E. Viola. On approximate majority and probabilistic time. In 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA, pages 155–168. IEEE Computer Society, 2007. doi:10.1109/CCC.2007.16. https://doi.org/10.1109/CCC.2007.16 [54] G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. SIAM J. Comput., 46(1):429–455, 2017. doi:10.1137/151002526. https://doi.org/10.1137/151002526 [55] X. Wu. A stochastic calculus approach to the oracle separation of $\mathsf{BQP}$ and $\mathsf{PH}$. Theory of Computing, 18(17):1–11, 2022. doi:10.4086/toc.2022.v018a017. https://doi.org/10.4086/toc.2022.v018a017 [56] T. Yamakawa and M. Zhandry. Verifiable quantum advantage without structure. J. ACM, 71(3):20, 2024. doi:10.1145/3658665. https://doi.org/10.1145/3658665 [57] Q. Zhu, S. Cao, F. Chen, et al. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. Science Bulletin, 67(3):240–245, 2022. doi:https://doi.org/10.1016/j.scib.2021.10.017. https://doi.org/10.1016/j.scib.2021.10.017 [58] H.-S. Zhong, Y.-H. Deng, J. Qin, et al. Phase-programmable gaussian boson sampling using stimulated squeezed light. Phys. Rev. Lett., 127:180502, Oct 2021. doi:10.1103/PhysRevLett.127.180502. https://doi.org/10.1103/PhysRevLett.127.180502 [59] H.-S. Zhong, H. Wang, Y.-H. Deng, et al. Quantum computational advantage using photons. Science, 370(6523):1460–1463, Dec 2020. doi:10.1126/science.abe8770. https://doi.org/10.1126/science.abe8770Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-10 10:03:07: Could not fetch cited-by data for 10.22331/q-2026-02-10-2002 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-10 10:03:07: No response from ADS or unable to decode the received json data when getting the list of citing works.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.