A brief history of quantum vs classical computational advantage

Ryan LaRose

doi:10.22331/q-2026-09-01-2198

A brief history of quantum vs classical computational advantage

Ryan LaRose

Department of Computational Mathematics, Science, and Engineering, Michigan State University, East Lansing, MI 48823, USA
Department of Electrical and Computer Engineering, Michigan State University, East Lansing, MI 48823, USA
Department of Physics and Astronomy, Michigan State University, East Lansing, MI 48823, USA
Center for Quantum Computing, Science, and Engineering, Michigan State University, East Lansing, MI 48823, USA

Published:	2026-09-01, volume 10, page 2198
Editor:	Philipp Schindler
Eprint:	arXiv:2412.14703v3
Doi:	https://doi.org/10.22331/q-2026-09-01-2198
Citation:	Quantum 10, 2198 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

In this review article we summarize all experiments claiming quantum computational advantage to date. Our review highlights challenges, loopholes, and refutations appearing in subsequent work to provide a complete picture of the current statuses of these experiments. In addition, we also discuss theoretical computational advantage in example problems such as approximate optimization and recommendation systems. Finally, we review recent experiments in quantum error correction --- the biggest frontier to reach experimental quantum advantage in Shor's algorithm.

► BibTeX data

@article{LaRose2026briefhistoryof,
  doi = {10.22331/q-2026-09-01-2198},
  url = {https://doi.org/10.22331/q-2026-09-01-2198},
  title = {A brief history of quantum vs classical computational advantage},
  author = {LaRose, Ryan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2198},
  month = sep,
  year = {2026}
}

► References

[1] John Preskill. Quantum computing and the entanglement frontier. arXiv, (arXiv:1203.5813), November 2012. 10.48550/arXiv.1203.5813. URL http://arxiv.org/abs/1203.5813. arXiv:1203.5813 [cond-mat, physics:quant-ph].
https://doi.org/10.48550/arXiv.1203.5813
arXiv:1203.5813

[2] John Preskill. Why I called it ‘quantum supremacy’, October 2019. URL https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/.
https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/

[3] Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum, 2 (1): 010103, March 2021. 10.1103/PRXQuantum.2.010103.
https://doi.org/10.1103/PRXQuantum.2.010103

[4] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, October 1997. ISSN 0097-5397, 1095-7111. 10.1137/S0097539795293172. arXiv: quant-ph/9508027.
https://doi.org/10.1137/S0097539795293172
arXiv:quant-ph/9508027

[5] Frank Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (77797779): 505–510, October 2019. ISSN 1476-4687. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5

[6] Xian-He Zhao, Han-Sen Zhong, Feng Pan, Zi-Han Chen, Rong Fu, Zhongling Su, Xiaotong Xie, Chaoxing Zhao, Pan Zhang, Wanli Ouyang, Chao-Yang Lu, Jian-Wei Pan, and Ming-Cheng Chen. Leapfrogging sycamore: Harnessing 1432 gpus for 7$\times$ faster quantum random circuit sampling. (arXiv:2406.18889), June 2024. 10.48550/arXiv.2406.18889. URL http://arxiv.org/abs/2406.18889. arXiv:2406.18889 [quant-ph].
https://doi.org/10.48550/arXiv.2406.18889
arXiv:2406.18889

[7] Han-Sen Zhong et al. Quantum computational advantage using photons. Science, 370 (6523): 1460–1463, December 2020. 10.1126/science.abe8770.
https://doi.org/10.1126/science.abe8770

[8] Changhun Oh, Minzhao Liu, Yuri Alexeev, Bill Fefferman, and Liang Jiang. Classical algorithm for simulating experimental gaussian boson sampling. Nature Physics, 20 (9): 1461–1468, September 2024. ISSN 1745-2481. 10.1038/s41567-024-02535-8.
https://doi.org/10.1038/s41567-024-02535-8

[9] Yulin Wu et al. Strong quantum computational advantage using a superconducting quantum processor. Physical Review Letters, 127 (18): 180501, October 2021. ISSN 0031-9007, 1079-7114. 10.1103/PhysRevLett.127.180501. arXiv:2106.14734 [quant-ph].
https://doi.org/10.1103/PhysRevLett.127.180501
arXiv:2106.14734

[10] Gleb Kalachev, Pavel Panteleev, PengFei Zhou, and Man-Hong Yung. Classical sampling of random quantum circuits with bounded fidelity. arXiv, (arXiv:2112.15083), December 2021. 10.48550/arXiv.2112.15083. URL http://arxiv.org/abs/2112.15083. arXiv:2112.15083.
https://doi.org/10.48550/arXiv.2112.15083
arXiv:2112.15083

[11] A. Morvan et al. Phase transitions in random circuit sampling. Nature, 634 (8033): 328–333, October 2024. ISSN 1476-4687. 10.1038/s41586-024-07998-6.
https://doi.org/10.1038/s41586-024-07998-6

[12] Han-Sen Zhong et al. Phase-programmable gaussian boson sampling using stimulated squeezed light. Physical Review Letters, 127 (18): 180502, October 2021. 10.1103/PhysRevLett.127.180502.
https://doi.org/10.1103/PhysRevLett.127.180502

[13] Qingling Zhu et al. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. Science Bulletin, 67 (3): 240–245, February 2022. ISSN 2095-9273. 10.1016/j.scib.2021.10.017.
https://doi.org/10.1016/j.scib.2021.10.017

[14] Xin Liu, Chu Guo, Yong Liu, Yuling Yang, Jiawei Song, Jie Gao, Zhen Wang, Wenzhao Wu, Dajia Peng, Pengpeng Zhao, Fang Li, He-Liang Huang, Haohuan Fu, and Dexun Chen. Redefining the quantum supremacy baseline with a new generation sunway supercomputer. (arXiv:2111.01066), November 2021a. 10.48550/arXiv.2111.01066. URL http://arxiv.org/abs/2111.01066. arXiv:2111.01066.
https://doi.org/10.48550/arXiv.2111.01066
arXiv:2111.01066

[15] Lars S. Madsen et al. Quantum computational advantage with a programmable photonic processor. Nature, 606 (79127912): 75–81, June 2022. ISSN 1476-4687. 10.1038/s41586-022-04725-x.
https://doi.org/10.1038/s41586-022-04725-x

[16] Yu-Hao Deng, Yi-Chao Gu, Hua-Liang Liu, Si-Qiu Gong, Hao Su, Zhi-Jiong Zhang, Hao-Yang Tang, Meng-Hao Jia, Jia-Min Xu, Ming-Cheng Chen, Jian Qin, Li-Chao Peng, Jiarong Yan, Yi Hu, Jia Huang, Hao Li, Yuxuan Li, Yaojian Chen, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Li Li, Han-Sen Zhong, Hui Wang, Nai-Le Liu, Jelmer J. Renema, Chao-Yang Lu, and Jian-Wei Pan. Gaussian boson sampling with pseudo-photon-number-resolving detectors and quantum computational advantage. Physical Review Letters, 131 (15): 150601, October 2023. 10.1103/PhysRevLett.131.150601.
https://doi.org/10.1103/PhysRevLett.131.150601

[17] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. Evidence for the utility of quantum computing before fault tolerance. Nature, 618 (79657965): 500–505, June 2023. ISSN 1476-4687. 10.1038/s41586-023-06096-3.
https://doi.org/10.1038/s41586-023-06096-3

[18] Joseph Tindall, Matt Fishman, Miles Stoudenmire, and Dries Sels. Efficient tensor network simulation of IBM’s eagle kicked ising experiment. (arXiv:2306.14887), August 2023. 10.48550/arXiv.2306.14887. URL http://arxiv.org/abs/2306.14887. arXiv:2306.14887 [quant-ph].
https://doi.org/10.48550/arXiv.2306.14887
arXiv:2306.14887

[19] Emanuele G. Dalla Torre and Mor M. Roses. Dissipative mean-field theory of ibm utility experiment. (arXiv:2308.01339), August 2023. 10.48550/arXiv.2308.01339. URL http://arxiv.org/abs/2308.01339. arXiv:2308.01339 [quant-ph].
https://doi.org/10.48550/arXiv.2308.01339
arXiv:2308.01339

[20] Hai-Jun Liao, Kang Wang, Zong-Sheng Zhou, Pan Zhang, and Tao Xiang. Simulation of ibm’s kicked ising experiment with projected entangled pair operator. (arXiv:2308.03082), August 2023a. 10.48550/arXiv.2308.03082. URL http://arxiv.org/abs/2308.03082. arXiv:2308.03082 [cond-mat, physics:quant-ph].
https://doi.org/10.48550/arXiv.2308.03082
arXiv:2308.03082

[21] Sajant Anand, Kristan Temme, Abhinav Kandala, and Michael Zaletel. Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime. (arXiv:2306.17839), June 2023. 10.48550/arXiv.2306.17839. URL http://arxiv.org/abs/2306.17839. arXiv:2306.17839 [quant-ph].
https://doi.org/10.48550/arXiv.2306.17839
arXiv:2306.17839

[22] Tomislav Begušić, Johnnie Gray, and Garnet Kin-Lic Chan. Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance. Science Advances, 10 (3): eadk4321, January 2024a. ISSN 2375-2548. 10.1126/sciadv.adk4321. arXiv:2308.05077 [quant-ph].
https://doi.org/10.1126/sciadv.adk4321
arXiv:2308.05077

[23] Andrew D. King et al. Computational supremacy in quantum simulation. (arXiv:2403.00910), March 2024. 10.48550/arXiv.2403.00910. URL http://arxiv.org/abs/2403.00910. arXiv:2403.00910 [cond-mat, physics:quant-ph].
https://doi.org/10.48550/arXiv.2403.00910
arXiv:2403.00910

[24] Xun Gao and Luming Duan. Efficient classical simulation of noisy quantum computation. (arXiv:1810.03176), October 2018. 10.48550/arXiv.1810.03176. URL http://arxiv.org/abs/1810.03176. arXiv:1810.03176 [quant-ph].
https://doi.org/10.48550/arXiv.1810.03176
arXiv:1810.03176

[25] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, page 945–957, June 2023. 10.1145/3564246.3585234. URL http://arxiv.org/abs/2211.03999.
https://doi.org/10.1145/3564246.3585234
arXiv:2211.03999

[26] Thomas Schuster, Chao Yin, Xun Gao, and Norman Y. Yao. A polynomial-time classical algorithm for noisy quantum circuits. (arXiv:2407.12768), October 2024. 10.48550/arXiv.2407.12768. URL http://arxiv.org/abs/2407.12768. arXiv:2407.12768 [quant-ph].
https://doi.org/10.48550/arXiv.2407.12768
arXiv:2407.12768

[27] Jon Nelson, Joel Rajakumar, Dominik Hangleiter, and Michael J. Gullans. Polynomial-time classical simulation of noisy circuits with naturally fault-tolerant gates. (arXiv:2411.02535), December 2024. 10.48550/arXiv.2411.02535. URL http://arxiv.org/abs/2411.02535. arXiv:2411.02535 [quant-ph].
https://doi.org/10.48550/arXiv.2411.02535
arXiv:2411.02535

[28] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão. Random quantum circuits transform local noise into global white noise. (arXiv:2111.14907), November 2021. 10.48550/arXiv.2111.14907. URL http://arxiv.org/abs/2111.14907. arXiv:2111.14907 [quant-ph].
https://doi.org/10.48550/arXiv.2111.14907
arXiv:2111.14907

[29] Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. Effect of non-unital noise on random circuit sampling. (arXiv:2306.16659), June 2023. 10.48550/arXiv.2306.16659. URL http://arxiv.org/abs/2306.16659. arXiv:2306.16659 [quant-ph].
https://doi.org/10.48550/arXiv.2306.16659
arXiv:2306.16659

[30] Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck França, and Yihui Quek. Noise-induced shallow circuits and absence of barren plateaus. (arXiv:2403.13927), October 2024. 10.48550/arXiv.2403.13927. URL http://arxiv.org/abs/2403.13927. arXiv:2403.13927 [quant-ph].
https://doi.org/10.48550/arXiv.2403.13927
arXiv:2403.13927

[31] P. Singkanipa and D. A. Lidar. Beyond unital noise in variational quantum algorithms: noise-induced barren plateaus and limit sets. Quantum, 9: 1617, January 2025. ISSN 2521-327X. 10.22331/q-2025-01-30-1617. arXiv:2402.08721 [quant-ph].
https://doi.org/10.22331/q-2025-01-30-1617
arXiv:2402.08721

[32] Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph, M. Cerezo, Zoë Holmes, and Hsin-Yuan Huang. Classically estimating observables of noiseless quantum circuits. Physical Review Letters, 135 (17): 170602, October 2025a. ISSN 0031-9007, 1079-7114. 10.1103/lh6x-7rc3. arXiv:2409.01706 [quant-ph].
https://doi.org/10.1103/lh6x-7rc3
arXiv:2409.01706

[33] Armando Angrisani, Antonio A. Mele, Manuel S. Rudolph, M. Cerezo, and Zoë Holmes. Simulating quantum circuits with arbitrary local noise using pauli propagation. (arXiv:2501.13101), May 2025b. 10.48550/arXiv.2501.13101. URL http://arxiv.org/abs/2501.13101. arXiv:2501.13101 [quant-ph].
https://doi.org/10.48550/arXiv.2501.13101
arXiv:2501.13101

[34] Scott Aaronson and Yuxuan Zhang. On verifiable quantum advantage with peaked circuit sampling. (arXiv:2404.14493), May 2024. 10.48550/arXiv.2404.14493. URL http://arxiv.org/abs/2404.14493. arXiv:2404.14493 [quant-ph].
https://doi.org/10.48550/arXiv.2404.14493
arXiv:2404.14493

[35] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão. Random quantum circuits anti-concentrate in log depth. PRX Quantum, 3 (1): 010333, March 2022. ISSN 2691-3399. 10.1103/PRXQuantum.3.010333. arXiv:2011.12277 [quant-ph].
https://doi.org/10.1103/PRXQuantum.3.010333
arXiv:2011.12277

[36] Daniel Belkin, James Allen, Soumik Ghosh, Christopher Kang, Sophia Lin, James Sud, Fred Chong, Bill Fefferman, and Bryan K. Clark. Approximate t-designs in generic circuit architectures. (arXiv:2310.19783), May 2024. 10.48550/arXiv.2310.19783. URL http://arxiv.org/abs/2310.19783. arXiv:2310.19783 [quant-ph].
https://doi.org/10.48550/arXiv.2310.19783
arXiv:2310.19783

[37] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth. (arXiv:2407.07754), January 2025. 10.48550/arXiv.2407.07754. URL http://arxiv.org/abs/2407.07754. arXiv:2407.07754 [quant-ph].
https://doi.org/10.48550/arXiv.2407.07754
arXiv:2407.07754

[38] Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V. Gorshkov, Bill Fefferman, and Michael J. Gullans. Tight bounds on the convergence of noisy random circuits to the uniform distribution. PRX Quantum, 3 (4): 040329, December 2022a. ISSN 2691-3399. 10.1103/PRXQuantum.3.040329. arXiv:2112.00716 [quant-ph].
https://doi.org/10.1103/PRXQuantum.3.040329
arXiv:2112.00716

[39] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters, 117 (8): 080501, August 2016. 10.1103/PhysRevLett.117.080501.
https://doi.org/10.1103/PhysRevLett.117.080501

[40] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1: 8, April 2017. ISSN 2521-327X. 10.22331/q-2017-04-25-8. arXiv:1610.01808 [quant-ph].
https://doi.org/10.22331/q-2017-04-25-8
arXiv:1610.01808

[41] Michael J. Bremner, Richard Jozsa, and Dan 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 (2126): 459–472, February 2011. ISSN 1364-5021, 1471-2946. 10.1098/rspa.2010.0301. arXiv:1005.1407 [quant-ph].
https://doi.org/10.1098/rspa.2010.0301
arXiv:1005.1407

[42] Richard Jozsa, Soumik Ghosh, and Sergii Strelchuk. Iqp computations with intermediate measurements. (arXiv:2408.10093), July 2025. 10.48550/arXiv.2408.10093. URL http://arxiv.org/abs/2408.10093. arXiv:2408.10093 [quant-ph].
https://doi.org/10.48550/arXiv.2408.10093
arXiv:2408.10093

[43] Joel Rajakumar, James D. Watson, and Yi-Kai Liu. Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth. January 2025. 10.1137/1.9781611978322.30. URL http://arxiv.org/abs/2403.14607. arXiv:2403.14607 [quant-ph].
https://doi.org/10.1137/1.9781611978322.30
arXiv:2403.14607

[44] Julien Codsi and John van de Wetering. Classically simulating quantum supremacy iqp circuits through a random graph approach. Physical Review A, 111 (1): 012422, January 2025. ISSN 2469-9926, 2469-9934. 10.1103/PhysRevA.111.012422. arXiv:2212.08609 [quant-ph].
https://doi.org/10.1103/PhysRevA.111.012422
arXiv:2212.08609

[45] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin. Logical quantum processor based on reconfigurable atom arrays. Nature, 626 (7997): 58–65, February 2024a. ISSN 1476-4687. 10.1038/s41586-023-06927-3.
https://doi.org/10.1038/s41586-023-06927-3

[46] Juan Bermejo-Vega. Architectures for quantum simulation showing a quantum speedup. Physical Review X, 8 (2), 2018. 10.1103/PhysRevX.8.021010.
https://doi.org/10.1103/PhysRevX.8.021010

[47] Jonas Haferkamp, Dominik Hangleiter, Adam Bouland, Bill Fefferman, Jens Eisert, and Juani Bermejo-Vega. Closing gaps of a quantum advantage with short-time hamiltonian dynamics. Physical Review Letters, 125 (25): 250501, December 2020. ISSN 0031-9007, 1079-7114. 10.1103/PhysRevLett.125.250501. arXiv:1908.08069 [quant-ph].
https://doi.org/10.1103/PhysRevLett.125.250501
arXiv:1908.08069

[48] Joel Rajakumar and James D. Watson. Gibbs sampling gives quantum advantage at constant temperatures with o(1)-local hamiltonians. (arXiv:2408.01516), October 2024. 10.48550/arXiv.2408.01516. URL http://arxiv.org/abs/2408.01516. arXiv:2408.01516 [quant-ph].
https://doi.org/10.48550/arXiv.2408.01516
arXiv:2408.01516

[49] Thiago Bergamaschi, Chi-Fang Chen, and Yunchao Liu. Quantum computational advantage with constant-temperature gibbs sampling. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), page 1063–1085, October 2024. 10.1109/FOCS61266.2024.00071. URL http://arxiv.org/abs/2404.14639. arXiv:2404.14639 [quant-ph].
https://doi.org/10.1109/FOCS61266.2024.00071
arXiv:2404.14639

[50] Jordan S. Cotler, Daniel K. Mark, Hsin-Yuan Huang, Felipe Hernandez, Joonhee Choi, Adam L. Shaw, Manuel Endres, and Soonwon Choi. Emergent quantum state designs from individual many-body wavefunctions. PRX Quantum, 4 (1): 010311, January 2023. ISSN 2691-3399. 10.1103/PRXQuantum.4.010311. arXiv:2103.03536 [quant-ph].
https://doi.org/10.1103/PRXQuantum.4.010311
arXiv:2103.03536

[51] Joonhee Choi, Adam L. Shaw, Ivaylo S. Madjarov, Xin Xie, Ran Finkelstein, Jacob P. Covey, Jordan S. Cotler, Daniel K. Mark, Hsin-Yuan Huang, Anant Kale, Hannes Pichler, Fernando G. S. L. Brandão, Soonwon Choi, and Manuel Endres. Preparing random states and benchmarking with many-body quantum chaos. Nature, 613 (7944): 468–473, January 2023. ISSN 0028-0836, 1476-4687. 10.1038/s41586-022-05442-1. arXiv:2103.03535 [quant-ph].
https://doi.org/10.1038/s41586-022-05442-1
arXiv:2103.03535

[52] Guifré Vidal. Efficient classical simulation of slightly entangled quantum computations. Physical Review Letters, 91 (14): 147902, October 2003. 10.1103/PhysRevLett.91.147902.
https://doi.org/10.1103/PhysRevLett.91.147902

[53] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, November 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328

[54] Sergey Bravyi, David Gosset, and Yinchen Liu. Classical simulation of peaked shallow quantum circuits. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 561–572, New York, NY, USA, June 2024. Association for Computing Machinery. ISBN 9798400703836. 10.1145/3618260.3649638. URL https://doi.org/10.1145/3618260.3649638.
https://doi.org/10.1145/3618260.3649638

[55] Charles Neill. A path towards quantum supremacy with superconducting qubits. PhD thesis, UC Santa Barbara, 2017. URL https://escholarship.org/uc/item/62s5k712.
https://escholarship.org/uc/item/62s5k712

[56] Aram W. Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (76717671): 203–209, September 2017. ISSN 1476-4687. 10.1038/nature23458.
https://doi.org/10.1038/nature23458

[57] 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, April 2018. 10.1126/science.aao4309.
https://doi.org/10.1126/science.aao4309

[58] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15 (22): 159–163, February 2019. ISSN 1745-2481. 10.1038/s41567-018-0318-2.
https://doi.org/10.1038/s41567-018-0318-2

[59] Igor L. Markov, Aneeqa Fatima, Sergei V. Isakov, and Sergio Boixo. Quantum supremacy is both closer and farther than it appears. (arXiv:1807.10749), September 2018. 10.48550/arXiv.1807.10749. URL http://arxiv.org/abs/1807.10749. arXiv:1807.10749.
https://doi.org/10.48550/arXiv.1807.10749
arXiv:1807.10749

[60] Brayden Ware, Abhinav Deshpande, Dominik Hangleiter, Pradeep Niroula, Bill Fefferman, Alexey V. Gorshkov, and Michael J. Gullans. A sharp phase transition in linear cross-entropy benchmarking. (arXiv:2305.04954), May 2023. 10.48550/arXiv.2305.04954. URL http://arxiv.org/abs/2305.04954. arXiv:2305.04954 [quant-ph].
https://doi.org/10.48550/arXiv.2305.04954
arXiv:2305.04954

[61] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, and Avishay Tal. On certified randomness from quantum advantage experiments. (arXiv:2111.14846), November 2021. 10.48550/arXiv.2111.14846. URL http://arxiv.org/abs/2111.14846. arXiv:2111.14846 [quant-ph].
https://doi.org/10.48550/arXiv.2111.14846
arXiv:2111.14846

[62] Scott Aaronson and Shih-Han Hung. Certified randomness from quantum supremacy. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 933–944, New York, NY, USA, June 2023. Association for Computing Machinery. ISBN 978-1-4503-9913-5. 10.1145/3564246.3585145. URL https://dl.acm.org/doi/10.1145/3564246.3585145.
https://doi.org/10.1145/3564246.3585145

[63] David Deutsch and Roger Penrose. Quantum theory, the church–turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400 (1818): 97–117, January 1985. 10.1098/rspa.1985.0070.
https://doi.org/10.1098/rspa.1985.0070

[64] Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff. Leveraging secondary storage to simulate deep 54-qubit sycamore circuits. (arXiv:1910.09534), October 2019. 10.48550/arXiv.1910.09534. URL http://arxiv.org/abs/1910.09534. arXiv:1910.09534 [quant-ph].
https://doi.org/10.48550/arXiv.1910.09534
arXiv:1910.09534

[65] IBM casts doubt on Google’s claims of quantum supremacy. https://www.science.org/content/article/ ibm-casts-doubt-googles-claims-quantum-supremacy, October 2019. URL https://www.science.org/content/article/ibm-casts-doubt-googles-claims-quantum-supremacy.
https://www.science.org/content/article/ibm-casts-doubt-googles-claims-quantum-supremacy

[66] Internet archive of ``Quantum supremacy using a programmable superconducting quantum processor'''. https://ia601007.us.archive.org/12/items/427430775 quantumsupremacyusingaprogrammablesuperconductingprocessor/ 427430775-Quantum-Supremacy-Using-a-Programmable-Superconducting-Processor.pdf.
https://ia601007.us.archive.org/12/items/427430775quantumsupremacyusingaprogrammablesuperconductingprocessor/427430775-Quantum-Supremacy-Using-a-Programmable-Superconducting-Processor.pdf

[67] Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W. Draeger, Eric T. Holland, and Robert Wisnieff. Pareto-efficient quantum circuit simulation using tensor contraction deferral. (arXiv:1710.05867), August 2020. 10.48550/arXiv.1710.05867. URL http://arxiv.org/abs/1710.05867. arXiv:1710.05867 [quant-ph].
https://doi.org/10.48550/arXiv.1710.05867
arXiv:1710.05867

[68] Johnnie Gray and Stefanos Kourtis. Hyper-optimized tensor network contraction. Quantum, 5: 410, March 2021. 10.22331/q-2021-03-15-410.
https://doi.org/10.22331/q-2021-03-15-410

[69] Igor L. Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing, 38 (3): 963–981, January 2008. ISSN 0097-5397. 10.1137/050644756.
https://doi.org/10.1137/050644756

[70] Yiqing Zhou, E. Miles Stoudenmire, and Xavier Waintal. What limits the simulation of quantum computers? Physical Review X, 10 (4): 041038, November 2020. 10.1103/PhysRevX.10.041038.
https://doi.org/10.1103/PhysRevX.10.041038

[71] 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. (arXiv:2005.06787), May 2020. 10.48550/arXiv.2005.06787. URL http://arxiv.org/abs/2005.06787. arXiv:2005.06787.
https://doi.org/10.48550/arXiv.2005.06787
arXiv:2005.06787

[72] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. (arXiv:1805.01450), May 2018. 10.48550/arXiv.1805.01450. URL http://arxiv.org/abs/1805.01450. arXiv:1805.01450.
https://doi.org/10.48550/arXiv.1805.01450
arXiv:1805.01450

[73] Benjamin Villalonga, Sergio Boixo, Bron Nelson, Christopher Henze, Eleanor Rieffel, Rupak Biswas, and Salvatore Mandrà. A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware. npj Quantum Information, 5 (1): 1–16, October 2019. ISSN 2056-6387. 10.1038/s41534-019-0196-1.
https://doi.org/10.1038/s41534-019-0196-1

[74] Feng Pan and Pan Zhang. Simulating the sycamore quantum supremacy circuits. (arXiv:2103.03074), March 2021. 10.48550/arXiv.2103.03074. URL http://arxiv.org/abs/2103.03074. arXiv:2103.03074.
https://doi.org/10.48550/arXiv.2103.03074
arXiv:2103.03074

[75] Yong, Liu, Xin, Liu, Fang, Li, Haohuan Fu, Yuling Yang, Jiawei Song, Pengpeng Zhao, Zhen Wang, Dajia Peng, Huarong Chen, Chu Guo, Heliang Huang, Wenzhao Wu, and Dexun Chen. Closing the “quantum supremacy” gap: Achieving real-time simulation of a random quantum circuit using a new sunway supercomputer. (arXiv:2110.14502), November 2021. 10.48550/arXiv.2110.14502. URL http://arxiv.org/abs/2110.14502. arXiv:2110.14502.
https://doi.org/10.48550/arXiv.2110.14502
arXiv:2110.14502

[76] Chu Guo, Yong Liu, Min Xiong, Shichuan Xue, Xiang Fu, Anqi Huang, Xiaogang Qiang, Ping Xu, Junhua Liu, Shenggen Zheng, He-Liang Huang, Mingtang Deng, Dario Poletti, Wan-Su Bao, and Junjie Wu. General-purpose quantum circuit simulator with projected entangled-pair states and the quantum supremacy frontier. Physical Review Letters, 123 (19): 190501, November 2019. 10.1103/PhysRevLett.123.190501.
https://doi.org/10.1103/PhysRevLett.123.190501

[77] Feng Pan, Keyang Chen, and Pan Zhang. Solving the sampling problem of the sycamore quantum circuits. (arXiv:2111.03011), August 2022. 10.48550/arXiv.2111.03011. URL http://arxiv.org/abs/2111.03011. arXiv:2111.03011.
https://doi.org/10.48550/arXiv.2111.03011
arXiv:2111.03011

[78] Feng Pan. Solve sycamore. https://github.com/Fanerst/solve_sycamore, August 2023.
https://github.com/Fanerst/solve_sycamore

[79] Boaz Barak, Chi-Ning Chou, and Xun Gao. Spoofing linear cross-entropy benchmarking in shallow quantum circuits. (arXiv:2005.02421), May 2020. 10.48550/arXiv.2005.02421. URL http://arxiv.org/abs/2005.02421. arXiv:2005.02421.
https://doi.org/10.48550/arXiv.2005.02421
arXiv:2005.02421

[80] 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. PRX Quantum, 5 (1): 010334, February 2024. 10.1103/PRXQuantum.5.010334.
https://doi.org/10.1103/PRXQuantum.5.010334

[81] Gregory Bentsen, Bill Fefferman, Soumik Ghosh, Michael J. Gullans, and Yinchen Liu. On the complexity of sampling from shallow brownian circuits. (arXiv:2411.04169), November 2024. 10.48550/arXiv.2411.04169. URL http://arxiv.org/abs/2411.04169. arXiv:2411.04169 [quant-ph].
https://doi.org/10.48550/arXiv.2411.04169
arXiv:2411.04169

[82] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, STOC ’11, page 333–342, New York, NY, USA, June 2011. Association for Computing Machinery. ISBN 978-1-4503-0691-1. 10.1145/1993636.1993682. URL https://dl.acm.org/doi/10.1145/1993636.1993682.
https://doi.org/10.1145/1993636.1993682

[83] Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51 (4): 671–697, July 2004. ISSN 0004-5411. 10.1145/1008731.1008738.
https://doi.org/10.1145/1008731.1008738

[84] Alex Neville, Chris Sparrow, Raphaël Clifford, Eric Johnston, Patrick M. Birchall, Ashley Montanaro, and Anthony Laing. Classical boson sampling algorithms with superior performance to near-term experiments. Nature Physics, 13 (12): 1153–1157, December 2017. ISSN 1745-2481. 10.1038/nphys4270.
https://doi.org/10.1038/nphys4270

[85] E. Knill, R. Laflamme, and G. J. Milburn. A scheme for efficient quantum computation with linear optics. Nature, 409 (6816): 46–52, January 2001a. ISSN 1476-4687. 10.1038/35051009.
https://doi.org/10.1038/35051009

[86] Craig S. Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex. Gaussian boson sampling. Physical Review Letters, 119 (17): 170501, October 2017. 10.1103/PhysRevLett.119.170501.
https://doi.org/10.1103/PhysRevLett.119.170501

[87] Nicolás Quesada, Juan Miguel Arrazola, and Nathan Killoran. Gaussian boson sampling using threshold detectors. Physical Review A, 98 (6): 062322, December 2018. 10.1103/PhysRevA.98.062322.
https://doi.org/10.1103/PhysRevA.98.062322

[88] Max Tillmann, Borivoje Dakić, René Heilmann, Stefan Nolte, Alexander Szameit, and Philip Walther. Experimental boson sampling. Nature Photonics, 7 (7): 540–544, July 2013. ISSN 1749-4893. 10.1038/nphoton.2013.102.
https://doi.org/10.1038/nphoton.2013.102

[89] Justin B. Spring, Benjamin J. Metcalf, Peter C. Humphreys, W. Steven Kolthammer, Xian-Min Jin, Marco Barbieri, Animesh Datta, Nicholas Thomas-Peter, Nathan K. Langford, Dmytro Kundys, James C. Gates, Brian J. Smith, Peter G. R. Smith, and Ian A. Walmsley. Boson sampling on a photonic chip. Science, 339 (6121): 798–801, February 2013. 10.1126/science.1231692.
https://doi.org/10.1126/science.1231692

[90] 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, August 2014. ISSN 1749-4893. 10.1038/nphoton.2014.135.
https://doi.org/10.1038/nphoton.2014.135

[91] J. C. Loredo, M. A. Broome, P. Hilaire, O. Gazzano, I. Sagnes, A. Lemaitre, M. P. Almeida, P. Senellart, and A. G. White. Boson sampling with single-photon fock states from a bright solid-state source. Physical Review Letters, 118 (13): 130503, March 2017. 10.1103/PhysRevLett.118.130503.
https://doi.org/10.1103/PhysRevLett.118.130503

[92] Andrea Crespi, Roberto Osellame, Roberta Ramponi, Daniel J. Brod, Ernesto F. Galvão, Nicolò Spagnolo, Chiara Vitelli, Enrico Maiorino, Paolo Mataloni, and Fabio Sciarrino. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nature Photonics, 7 (7): 545–549, July 2013. ISSN 1749-4893. 10.1038/nphoton.2013.112.
https://doi.org/10.1038/nphoton.2013.112

[93] Jacques Carolan, Jasmin D. A. Meinecke, Peter J. Shadbolt, Nicholas J. Russell, Nur Ismail, Kerstin Wörhoff, Terry Rudolph, Mark G. Thompson, Jeremy L. O’Brien, Jonathan C. F. Matthews, and Anthony Laing. On the experimental verification of quantum complexity in linear optics. Nature Photonics, 8 (8): 621–626, August 2014. ISSN 1749-4893. 10.1038/nphoton.2014.152.
https://doi.org/10.1038/nphoton.2014.152

[94] Jacques Carolan, Christopher Harrold, Chris Sparrow, Enrique Martín-López, Nicholas J. Russell, Joshua W. Silverstone, Peter J. Shadbolt, Nobuyuki Matsuda, Manabu Oguma, Mikitaka Itoh, Graham D. Marshall, Mark G. Thompson, Jonathan C. F. Matthews, Toshikazu Hashimoto, Jeremy L. O’Brien, and Anthony Laing. Universal linear optics. Science, 349 (6249): 711–716, August 2015. 10.1126/science.aab3642.
https://doi.org/10.1126/science.aab3642

[95] Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari, Justin Dove, Scott Aaronson, Timothy C. Ralph, and Andrew G. White. Photonic boson sampling in a tunable circuit. Science, 339 (6121): 794–798, February 2013. 10.1126/science.1231440.
https://doi.org/10.1126/science.1231440

[96] Marco Bentivegna, Nicolò Spagnolo, Chiara Vitelli, Fulvio Flamini, Niko Viggianiello, Ludovico Latmiral, Paolo Mataloni, Daniel J. Brod, Ernesto F. Galvão, Andrea Crespi, Roberta Ramponi, Roberto Osellame, and Fabio Sciarrino. Experimental scattershot boson sampling. Science Advances, 1 (3): e1400255, April 2015. 10.1126/sciadv.1400255.
https://doi.org/10.1126/sciadv.1400255

[97] Hui Wang, Jian Qin, Xing Ding, Ming-Cheng Chen, Si Chen, Xiang You, Yu-Ming He, Xiao Jiang, Z. Wang, L. You, J. J. Renema, Sven Hoefling, Chao-Yang Lu, and Jian-Wei Pan. Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces. Physical Review Letters, 123 (25): 250503, December 2019. ISSN 0031-9007, 1079-7114. 10.1103/PhysRevLett.123.250503. arXiv:1910.09930 [quant-ph].
https://doi.org/10.1103/PhysRevLett.123.250503
arXiv:1910.09930

[98] Peter Clifford and Raphaël Clifford. The Classical Complexity of Boson Sampling, page 146–155. Proceedings. Society for Industrial and Applied Mathematics, January 2018. 10.1137/1.9781611975031.10. URL https://epubs.siam.org/doi/10.1137/1.9781611975031.10.
https://doi.org/10.1137/1.9781611975031.10

[99] Peter Clifford and Raphaël Clifford. Bosonsampling: Classical boson sampling. https://cran.r-project.org/web/packages/BosonSampling/index.html, October 2017.
https://cran.r-project.org/web/packages/BosonSampling/index.html

[100] Junjie Wu, Yong Liu, Baida Zhang, Xianmin Jin, Yang Wang, Huiquan Wang, and Xuejun Yang. A benchmark test of boson sampling on tianhe-2 supercomputer. National Science Review, 5 (5): 715–720, September 2018. ISSN 2095-5138. 10.1093/nsr/nwy079.
https://doi.org/10.1093/nsr/nwy079

[101] Herbert John Ryser. Combinatorial Mathematics. American Mathematical Soc., December 1963. ISBN 978-1-61444-014-7. 10.5948/UPO9781614440147.
https://doi.org/10.5948/UPO9781614440147

[102] K. Balasubramanian. Combinatorics and diagonals of matrices. Thesis, Indian Statistical Institute,Calcutta, December 1980. URL http://localhost:8080/xmlui/handle/10263/3603. Accepted: 2012-04-29T18:32:22Z.
http://localhost:8080/xmlui/handle/10263/3603

[103] Eric Bax. Finite-difference algorithms for counting problems. phd, California Institute of Technology, 1998. URL https://resolver.caltech.edu/CaltechETD:etd-01182008-113319.
https://resolver.caltech.edu/CaltechETD:etd-01182008-113319

[104] Andreas Björklund, Brajesh Gupt, and Nicolás Quesada. A faster hafnian formula for complex matrices and its benchmarking on a supercomputer. ACM J. Exp. Algorithmics, 24: 1.11:1–1.11:17, June 2019. ISSN 1084-6654. 10.1145/3325111.
https://doi.org/10.1145/3325111

[105] Brajesh Gupt, Juan Miguel Arrazola, Nicolás Quesada, and Thomas R. Bromley. Classical benchmarking of gaussian boson sampling on the titan supercomputer. Quantum Information Processing, 19 (8): 249, July 2020. ISSN 1573-1332. 10.1007/s11128-020-02713-6.
https://doi.org/10.1007/s11128-020-02713-6

[106] 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): 100502, March 2020. 10.1103/PhysRevLett.124.100502.
https://doi.org/10.1103/PhysRevLett.124.100502

[107] Bujiao Wu, Bin Cheng, Fei Jia, Jialin Zhang, Man-Hong Yung, and Xiaoming Sun. Speedup in classical simulation of gaussian boson sampling. Science Bulletin, 65 (10): 832–841, May 2020. ISSN 2095-9273. 10.1016/j.scib.2020.02.012.
https://doi.org/10.1016/j.scib.2020.02.012

[108] Yuxuan Li, Lin Gan, Mingcheng Chen, Yaojian Chen, Haitian Lu, Chaoyang Lu, Jianwei Pan, Haohuan Fu, and Guangwen Yang. Benchmarking 50-photon gaussian boson sampling on the sunway taihulight. IEEE Transactions on Parallel and Distributed Systems, 33 (6): 1357–1372, June 2022. ISSN 1558-2183. 10.1109/TPDS.2021.3111185.
https://doi.org/10.1109/TPDS.2021.3111185

[109] Nicolas Quesada, Rahel S. Chadwick, Bryn A. Bell, Juan Miguel Arrazola, Trevor Vincent, Haoyu Qi, and Raul Garcia-Patron. Quadratic speed-up for simulating gaussian boson sampling. PRX Quantum, 3 (1): 010306, January 2022. 10.1103/PRXQuantum.3.010306.
https://doi.org/10.1103/PRXQuantum.3.010306

[110] Junheng Shi and Tim Byrnes. Effect of partial distinguishability on quantum supremacy in gaussian boson sampling. npj Quantum Information, 8 (1): 1–11, May 2022. ISSN 2056-6387. 10.1038/s41534-022-00557-9.
https://doi.org/10.1038/s41534-022-00557-9

[111] Jelmer J. Renema. Simulability of partially distinguishable superposition and gaussian boson sampling. Physical Review A, 101 (6): 063840, June 2020. 10.1103/PhysRevA.101.063840.
https://doi.org/10.1103/PhysRevA.101.063840

[112] Jacob F. F. Bulmer, Bryn A. Bell, Rachel S. Chadwick, Alex E. Jones, Diana Moise, Alessandro Rigazzi, Jan Thorbecke, Utz-Uwe Haus, Thomas Van Vaerenbergh, Raj B. Patel, Ian A. Walmsley, and Anthony Laing. The boundary for quantum advantage in gaussian boson sampling. Science Advances, 8 (4): eabl9236, January 2022. ISSN 2375-2548. 10.1126/sciadv.abl9236. arXiv:2108.01622 [quant-ph].
https://doi.org/10.1126/sciadv.abl9236
arXiv:2108.01622

[113] Ágoston Kaposi, Zoltán Kolarovszki, Tamás Kozsik, Zoltán Zimborás, and Péter Rakyta. Polynomial speedup in torontonian calculation by a scalable recursive algorithm. (arXiv:2109.04528), November 2022. 10.48550/arXiv.2109.04528. URL http://arxiv.org/abs/2109.04528. arXiv:2109.04528 [quant-ph].
https://doi.org/10.48550/arXiv.2109.04528
arXiv:2109.04528

[114] Nicolás Quesada and Juan Miguel Arrazola. Exact simulation of gaussian boson sampling in polynomial space and exponential time. Physical Review Research, 2 (2): 023005, April 2020. ISSN 2643-1564. 10.1103/PhysRevResearch.2.023005. arXiv:1908.08068 [quant-ph].
https://doi.org/10.1103/PhysRevResearch.2.023005
arXiv:1908.08068

[115] 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. (arXiv:2109.11525), February 2022. 10.48550/arXiv.2109.11525. URL http://arxiv.org/abs/2109.11525. arXiv:2109.11525 [quant-ph].
https://doi.org/10.48550/arXiv.2109.11525
arXiv:2109.11525

[116] Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, Dominik Hangleiter, Bill Fefferman, and Ish Dhand. Quantum computational advantage via high-dimensional gaussian boson sampling. Science Advances, 8 (1): eabi7894, January 2022b. 10.1126/sciadv.abi7894.
https://doi.org/10.1126/sciadv.abi7894

[117] Changhun Oh, Kyungjoo Noh, Bill Fefferman, and Liang Jiang. Classical simulation of lossy boson sampling using matrix product operators. Physical Review A, 104 (2): 022407, August 2021. 10.1103/PhysRevA.104.022407.
https://doi.org/10.1103/PhysRevA.104.022407

[118] Minzhao Liu, Changhun Oh, Junyu Liu, Liang Jiang, and Yuri Alexeev. Simulating lossy gaussian boson sampling with matrix-product operators. Physical Review A, 108 (5): 052604, November 2023. 10.1103/PhysRevA.108.052604.
https://doi.org/10.1103/PhysRevA.108.052604

[119] Gil Kalai and Guy Kindler. Gaussian noise sensitivity and bosonsampling. (arXiv:1409.3093), November 2014. 10.48550/arXiv.1409.3093. URL http://arxiv.org/abs/1409.3093. arXiv:1409.3093 [quant-ph].
https://doi.org/10.48550/arXiv.1409.3093
arXiv:1409.3093

[120] Joseph Tindall and Matthew Fishman. Gauging tensor networks with belief propagation. SciPost Physics, 15 (6): 222, December 2023. ISSN 2542-4653. 10.21468/SciPostPhys.15.6.222.
https://doi.org/10.21468/SciPostPhys.15.6.222

[121] K. Kechedzhi, S. V. Isakov, S. Mandrà, B. Villalonga, X. Mi, S. Boixo, and V. Smelyanskiy. Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments. (arXiv:2306.15970), January 2024. 10.48550/arXiv.2306.15970. URL http://arxiv.org/abs/2306.15970. arXiv:2306.15970.
https://doi.org/10.48550/arXiv.2306.15970
arXiv:2306.15970

[122] Tomislav Begušić and Garnet Kin-Lic Chan. Fast classical simulation of evidence for the utility of quantum computing before fault tolerance. (arXiv:2306.16372), June 2023. 10.48550/arXiv.2306.16372. URL http://arxiv.org/abs/2306.16372. arXiv:2306.16372.
https://doi.org/10.48550/arXiv.2306.16372
arXiv:2306.16372

[123] Tomislav Begušić, Kasra Hejazi, and Garnet Kin-Lic Chan. Simulating quantum circuit expectation values by clifford perturbation theory. (arXiv:2306.04797), July 2023. 10.48550/arXiv.2306.04797. URL http://arxiv.org/abs/2306.04797. arXiv:2306.04797.
https://doi.org/10.48550/arXiv.2306.04797
arXiv:2306.04797

[124] Tomislav Begušić, Johnnie Gray, and Garnet Kin-Lic Chan. Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance. Science Advances, 10 (3): eadk4321, January 2024b. 10.1126/sciadv.adk4321.
https://doi.org/10.1126/sciadv.adk4321

[125] Hai-Jun Liao, Kang Wang, Zong-Sheng Zhou, Pan Zhang, and Tao Xiang. Simulation of ibm’s kicked ising experiment with projected entangled pair operator. (arXiv:2308.03082), August 2023b. 10.48550/arXiv.2308.03082. URL http://arxiv.org/abs/2308.03082. arXiv:2308.03082.
https://doi.org/10.48550/arXiv.2308.03082
arXiv:2308.03082

[126] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. (arXiv:1411.4028), November 2014. 10.48550/arXiv.1411.4028. URL http://arxiv.org/abs/1411.4028. arXiv:1411.4028.
https://doi.org/10.48550/arXiv.1411.4028
arXiv:1411.4028

[127] Johan Håstad. On bounded occurrence constraint satisfaction. Information Processing Letters, 74 (1): 1–6, April 2000. ISSN 0020-0190. 10.1016/S0020-0190(00)00032-6.
https://doi.org/10.1016/S0020-0190(00)00032-6

[128] Johan Håstad. Some optimal inapproximability results. J. ACM, 48 (4): 798–859, July 2001. ISSN 0004-5411. 10.1145/502090.502098.
https://doi.org/10.1145/502090.502098

[129] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. (arXiv:1412.6062), June 2015. 10.48550/arXiv.1412.6062. URL http://arxiv.org/abs/1412.6062. arXiv:1412.6062.
https://doi.org/10.48550/arXiv.1412.6062
arXiv:1412.6062

[130] Scott Aaronson. Quantum computing news items (by reader request). https://scottaaronson.blog/?p=2155, January 2015.
https://scottaaronson.blog/?p=2155

[131] Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the random assignment on constraint satisfaction problems of bounded degree. (arXiv:1505.03424), August 2015. 10.48550/arXiv.1505.03424. URL http://arxiv.org/abs/1505.03424. arXiv:1505.03424.
https://doi.org/10.48550/arXiv.1505.03424
arXiv:1505.03424

[132] Ashley Montanaro and Leo Zhou. Quantum speedups in solving near-symmetric optimization problems by low-depth qaoa. (arXiv:2411.04979), November 2024. 10.48550/arXiv.2411.04979. URL http://arxiv.org/abs/2411.04979. arXiv:2411.04979.
https://doi.org/10.48550/arXiv.2411.04979
arXiv:2411.04979

[133] Zhang Jiang, Eleanor G. Rieffel, and Zhihui Wang. Near-optimal quantum circuit for grover’s unstructured search using a transverse field. Physical Review A, 95 (6): 062317, June 2017. 10.1103/PhysRevA.95.062317.
https://doi.org/10.1103/PhysRevA.95.062317

[134] Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79 (2): 325–328, July 1997. ISSN 0031-9007, 1079-7114. 10.1103/PhysRevLett.79.325. arXiv: quant-ph/9706033.
https://doi.org/10.1103/PhysRevLett.79.325
arXiv:quant-ph/9706033

[135] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26 (5): 1510–1523, October 1997. ISSN 0097-5397, 1095-7111. 10.1137/S0097539796300933. arXiv:quant-ph/9701001.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001

[136] E.M. Stoudenmire and Xavier Waintal. Opening the black box inside grover’s algorithm. Physical Review X, 14 (4), 2024. 10.1103/PhysRevX.14.041029.
https://doi.org/10.1103/PhysRevX.14.041029

[137] Scott Aaronson. Shtetl-optimized: The blog of scott aaronson. https://scottaaronson.blog/?p=7157, March 2023.
https://scottaaronson.blog/?p=7157

[138] Bikram Khanal, Javier Orduz, Pablo Rivas, and Erich Baker. Supercomputing leverages quantum machine learning and grover’s algorithm. The Journal of Supercomputing, 79 (6): 6918–6940, April 2023. ISSN 1573-0484. 10.1007/s11227-022-04923-4.
https://doi.org/10.1007/s11227-022-04923-4

[139] T. Muser, E. Zapusek, V. Belis, and F. Reiter. Provable advantages of kernel-based quantum learners and quantum preprocessing based on grover’s algorithm. Physical Review A, 110 (3): 032434, September 2024. 10.1103/PhysRevA.110.032434.
https://doi.org/10.1103/PhysRevA.110.032434

[140] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. (arXiv:1603.08675), September 2016. 10.48550/arXiv.1603.08675. URL http://arxiv.org/abs/1603.08675. arXiv:1603.08675.
https://doi.org/10.48550/arXiv.1603.08675
arXiv:1603.08675

[141] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. (arXiv:1807.04271), May 2019. 10.48550/arXiv.1807.04271. URL http://arxiv.org/abs/1807.04271. arXiv:1807.04271.
https://doi.org/10.48550/arXiv.1807.04271
arXiv:1807.04271

[142] Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. ACM, 51 (6): 1025–1041, November 2004. ISSN 0004-5411. 10.1145/1039488.1039494.
https://doi.org/10.1145/1039488.1039494

[143] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. Quantum-inspired algorithms in practice. (arXiv:1905.10415), August 2020. 10.48550/arXiv.1905.10415. URL http://arxiv.org/abs/1905.10415. arXiv:1905.10415.
https://doi.org/10.48550/arXiv.1905.10415
arXiv:1905.10415

[144] Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. (arXiv:1811.04852), November 2018. 10.48550/arXiv.1811.04852. URL http://arxiv.org/abs/1811.04852. arXiv:1811.04852.
https://doi.org/10.48550/arXiv.1811.04852
arXiv:1811.04852

[145] András Gilyén, Zhao Song, and Ewin Tang. An improved quantum-inspired algorithm for linear regression. Quantum, 6: 754, June 2022. 10.22331/q-2022-06-30-754.
https://doi.org/10.22331/q-2022-06-30-754

[146] Ewin Tang. Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions. Physical Review Letters, 127 (6): 060503, August 2021. 10.1103/PhysRevLett.127.060503.
https://doi.org/10.1103/PhysRevLett.127.060503

[147] Jordan Cotler, Hsin-Yuan Huang, and Jarrod R. McClean. Revisiting dequantization and quantum advantage in learning tasks. (arXiv:2112.00811), December 2021. 10.48550/arXiv.2112.00811. URL http://arxiv.org/abs/2112.00811. arXiv:2112.00811 [quant-ph].
https://doi.org/10.48550/arXiv.2112.00811
arXiv:2112.00811

[148] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549 (7671): 195–202, September 2017. ISSN 1476-4687. 10.1038/nature23474.
https://doi.org/10.1038/nature23474

[149] M. Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J. Coles. Challenges and opportunities in quantum machine learning. Nature Computational Science, 2 (9): 567–576, September 2022. ISSN 2662-8457. 10.1038/s43588-022-00311-3.
https://doi.org/10.1038/s43588-022-00311-3

[150] Gian Gentinetta, Arne Thomsen, David Sutter, and Stefan Woerner. The complexity of quantum support vector machines. Quantum, 8: 1225, January 2024. 10.22331/q-2024-01-11-1225.
https://doi.org/10.22331/q-2024-01-11-1225

[151] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 17 (9): 1013–1017, September 2021b. ISSN 1745-2481. 10.1038/s41567-021-01287-z.
https://doi.org/10.1038/s41567-021-01287-z

[152] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6–7): 467–488, June 1982. ISSN 0020-7748, 1572-9575. 10.1007/BF02650179.
https://doi.org/10.1007/BF02650179

[153] A. Yu Kitaev. Quantum measurements and the abelian stabilizer problem. (arXiv:quant-ph/9511026), November 1995. 10.48550/arXiv.quant-ph/9511026. URL http://arxiv.org/abs/quant-ph/9511026. arXiv:quant-ph/9511026.
https://doi.org/10.48550/arXiv.quant-ph/9511026
arXiv:quant-ph/9511026

[154] Lin Lin. Lecture notes on quantum algorithms for scientific computation. (arXiv:2201.08309), January 2022. 10.48550/arXiv.2201.08309. URL http://arxiv.org/abs/2201.08309. arXiv:2201.08309 [quant-ph].
https://doi.org/10.48550/arXiv.2201.08309
arXiv:2201.08309

[155] Lin Lin and Yu Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3 (1): 010318, February 2022. 10.1103/PRXQuantum.3.010318.
https://doi.org/10.1103/PRXQuantum.3.010318

[156] Laura Clinton, Toby S. Cubitt, Raul Garcia-Patron, Ashley Montanaro, Stasja Stanisic, and Maarten Stroeks. Quantum phase estimation without controlled unitaries. (arXiv:2410.21517), October 2024. 10.48550/arXiv.2410.21517. URL http://arxiv.org/abs/2410.21517. arXiv:2410.21517 [quant-ph].
https://doi.org/10.48550/arXiv.2410.21517
arXiv:2410.21517

[157] Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, and Garnet Kin-Lic Chan. Nature Communications, (1): 1952, April 2023. 10.1038/s41467-023-37587-6.
https://doi.org/10.1038/s41467-023-37587-6

[158] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nature Reviews Physics, 3 (9): 625–644, September 2021. ISSN 2522-5820. 10.1038/s42254-021-00348-9.
https://doi.org/10.1038/s42254-021-00348-9

[159] Nobuyuki Yoshioka, Mirko Amico, William Kirby, Petar Jurcevic, Arkopal Dutt, Bryce Fuller, Shelly Garion, Holger Haas, Ikko Hamamura, Alexander Ivrii, Ritajit Majumdar, Zlatko Minev, Mario Motta, Bibek Pokharel, Pedro Rivero, Kunal Sharma, Christopher J. Wood, Ali Javadi-Abhari, and Antonio Mezzacapo. Diagonalization of large many-body hamiltonians on a quantum processor. Nature Communications, 16 (1): 5014, June 2025. ISSN 2041-1723. 10.1038/s41467-025-59716-z. arXiv:2407.14431 [quant-ph].
https://doi.org/10.1038/s41467-025-59716-z
arXiv:2407.14431

[160] Samuele Piccinelli, Alberto Baiardi, Max Rossmannek, Almudena Carrera Vazquez, Francesco Tacchino, Stefano Mensa, Edoardo Altamura, Ali Alavi, Mario Motta, Javier Robledo-Moreno, William Kirby, Kunal Sharma, Antonio Mezzacapo, and Ivano Tavernelli. Quantum chemistry with provable convergence via randomized sample-based quantum diagonalization. (arXiv:2508.02578), August 2025. 10.48550/arXiv.2508.02578. URL http://arxiv.org/abs/2508.02578. arXiv:2508.02578 [quant-ph].
https://doi.org/10.48550/arXiv.2508.02578
arXiv:2508.02578

[161] Martín Larocca, Supanut Thanasilp, Samson Wang, Kunal Sharma, Jacob Biamonte, Patrick J. Coles, Lukasz Cincio, Jarrod R. McClean, Zoë Holmes, and M. Cerezo. Barren plateaus in variational quantum computing. Nature Reviews Physics, 7 (4): 174–189, April 2025. ISSN 2522-5820. 10.1038/s42254-025-00813-9.
https://doi.org/10.1038/s42254-025-00813-9

[162] Craig Gidney and Martin Ekerå. How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits. Quantum, 5: 433, April 2021. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[163] Élie Gouzien and Nicolas Sangouard. Factoring 2048-bit rsa integers in 177 days with 13 436 qubits and a multimode memory. Physical Review Letters, 127 (14): 140503, September 2021. 10.1103/PhysRevLett.127.140503.
https://doi.org/10.1103/PhysRevLett.127.140503

[164] Timothy Proctor, Kevin Young, Andrew D. Baczewski, and Robin Blume-Kohout. Benchmarking quantum computers. Nature Reviews Physics, 7 (2): 105–118, February 2025. ISSN 2522-5820. 10.1038/s42254-024-00796-z.
https://doi.org/10.1038/s42254-024-00796-z

[165] Oded Regev. An efficient quantum factoring algorithm. (arXiv:2308.06572), January 2024. 10.48550/arXiv.2308.06572. URL http://arxiv.org/abs/2308.06572. arXiv:2308.06572 [quant-ph].
https://doi.org/10.48550/arXiv.2308.06572
arXiv:2308.06572

[166] D. G. Cory, M. Price, W. Maas, E. Knill, R. Laflamme, W. H. Zurek, T. F. Havel, and S. S. Somaroo. Experimental quantum error correction. Physical Review Letters, 81: 2152, 1998. 10.1103/PhysRevLett.81.2152.
https://doi.org/10.1103/PhysRevLett.81.2152

[167] J. Chiaverini, D. Leibfried, T. Schaetz, M. D. Barrett, R. B. Blakestad, J. Britton, W. M. Itano, J. D. Jost, E. Knill, C. Langer, R. Ozeri, and D. J. Wineland. Realization of quantum error correction. Nature, 432 (7017): 602–605, December 2004. ISSN 1476-4687. 10.1038/nature03074.
https://doi.org/10.1038/nature03074

[168] T. B. Pittman, B. C. Jacobs, and J. D. Franson. Demonstration of quantum error correction using linear optics. Physical Review A, 71 (5): 052332, May 2005. ISSN 1050-2947, 1094-1622. 10.1103/PhysRevA.71.052332. arXiv:quant-ph/0502042.
https://doi.org/10.1103/PhysRevA.71.052332
arXiv:quant-ph/0502042

[169] E. Knill, R. Laflamme, R. Martinez, and C. Negrevergne. Benchmarking quantum computers: the five-qubit error correcting code. Physical Review Letters, 86: 5811, 2001b. 10.1103/PhysRevLett.86.5811.
https://doi.org/10.1103/PhysRevLett.86.5811

[170] P. Schindler, J. T. Barreiro, T. Monz, V. Nebendahl, D. Nigg, M. Chwalla, M. Hennrich, and R. Blatt. Experimental repetitive quantum error correction. Science, 332: 1059, 2011. 10.1126/science.1203329.
https://doi.org/10.1126/science.1203329

[171] O. Moussa, J. Baugh, C. A. Ryan, and R. Laflamme. Demonstration of sufficient control for two rounds of quantum error correction in a solid-state ensemble quantum information processor. Physical Review Letters, 107: 160501, 2011. 10.1103/PhysRevLett.107.160501.
https://doi.org/10.1103/PhysRevLett.107.160501

[172] J. Zhang, T. Laflamme, and D. Cory. Experimental implementation of encoded logical qubits in a 3-qubit decoherence-free subspace. Physical Review A, 82: 022304, 2011. 10.1103/PhysRevLett.109.100503.
https://doi.org/10.1103/PhysRevLett.109.100503

[173] M. D. Reed, L. DiCarlo, S. E. Nigg, L. Sun, L. Frunzio, S. M. Girvin, and R. J. Schoelkopf. Realization of three-qubit quantum error correction with superconducting circuits. Nature, 482: 382, 2012. 10.1038/nature10786.
https://doi.org/10.1038/nature10786

[174] J. Zhang, R. Laflamme, and D. G. Cory. Experimental quantum error correction with large block codes. Physical Review Letters, 108: 110501, 2012. 10.1103/PhysRevLett.81.2152.
https://doi.org/10.1103/PhysRevLett.81.2152

[175] B. A. Bell, D. A. Herrera-Martí, M. S. Tame, D. Markham, W. J. Wadsworth, and J. G. Rarity. Experimental demonstration of a graph state quantum error-correction code. Nature Communications, 5: 5480, 2014. 10.1038/ncomms4658.
https://doi.org/10.1038/ncomms4658

[176] J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, I. C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and J. M. Martinis. State preservation by repetitive error detection in a superconducting quantum circuit. Nature, 519: 66, 2015. 10.1038/nature14270.
https://doi.org/10.1038/nature14270

[177] D. Nigg, M. Müller, E. A. Martinez, P. Schindler, M. Hennrich, T. Monz, M. A. Martin-Delgado, and R. Blatt. Quantum computations on a topologically encoded qubit. Science, 345: 302, 2014. 10.1126/science.1253742.
https://doi.org/10.1126/science.1253742

[178] G. Waldherr, Y. Wang, S. Zaiser, M. Jamali, T. Schulte-Herbrüggen, H. Abe, T. Ohshima, J. Isoya, J. F. Du, P. Neumann, and J. Wrachtrup. Quantum error correction in a solid-state hybrid spin register. Nature, 506: 204, 2014. 10.1038/nature12919.
https://doi.org/10.1038/nature12919

[179] Diego Riste, Stefano Poletto, M-Z Huang, Alessandro Bruno, Visa Vesterinen, O-P Saira, and Leonardo DiCarlo. Detecting bit-flip errors in a logical qubit using stabilizer measurements. Nature communications, 6 (1): 1–6, 2015. 10.1038/ncomms7983.
https://doi.org/10.1038/ncomms7983

[180] Antonio D Córcoles, Easwar Magesan, Srikanth J Srinivasan, Andrew W Cross, Matthias Steffen, Jay M Gambetta, and Jerry M Chow. Demonstration of a quantum error detection code using a square lattice of four superconducting qubits. Nature communications, 6 (1): 1–10, 2015. 10.1038/ncomms7979.
https://doi.org/10.1038/ncomms7979

[181] Julia Cramer, Norbert Kalb, M Adriaan Rol, Bas Hensen, Machiel S Blok, Matthew Markham, Daniel J Twitchen, Ronald Hanson, and Tim H Taminiau. Repeated quantum error correction on a continuously encoded qubit by real-time feedback. Nature communications, 7 (1): 1–7, 2016. 10.1038/ncomms11526.
https://doi.org/10.1038/ncomms11526

[182] Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang, et al. Extending the lifetime of a quantum bit with error correction in superconducting circuits. Nature, 536 (7617): 441–445, 2016. 10.1038/nature18949.
https://doi.org/10.1038/nature18949

[183] Maika Takita, Andrew W Cross, AD Córcoles, Jerry M Chow, and Jay M Gambetta. Experimental demonstration of fault-tolerant state preparation with superconducting qubits. Physical review letters, 119 (18): 180501, 2017. 10.1103/PhysRevLett.119.180501.
https://doi.org/10.1103/PhysRevLett.119.180501

[184] Norbert M Linke, Mauricio Gutierrez, Kevin A Landsman, Caroline Figgatt, Shantanu Debnath, Kenneth R Brown, and Christopher Monroe. Fault-tolerant quantum error detection. Science advances, 3 (10): e1701074, 2017. 10.1126/sciadv.1701074.
https://doi.org/10.1126/sciadv.1701074

[185] Reinier W. Heeres, Philip Reinhold, Nissim Ofek, Luigi Frunzio, Liang Jiang, Michel H. Devoret, and Robert J. Schoelkopf. Implementing a universal gate set on a logical qubit encoded in an oscillator. Nature Communications, 8 (1): 94, July 2017. ISSN 2041-1723. 10.1038/s41467-017-00045-1.
https://doi.org/10.1038/s41467-017-00045-1

[186] James R Wootton and Daniel Loss. Repetition code of 15 qubits. Physical Review A, 97 (5): 052313, 2018. 10.1103/PhysRevA.97.052313.
https://doi.org/10.1103/PhysRevA.97.052313

[187] Christian Kraglund Andersen, Ants Remm, Stefania Lazar, Sebastian Krinner, Johannes Heinsoo, Jean-Claude Besse, Mihai Gabureac, Andreas Wallraff, and Christopher Eichler. Entanglement stabilization using ancilla-based parity detection and real-time feedback in superconducting circuits. npj Quantum Information, 5 (1): 1–7, 2019. 10.1038/s41534-019-0185-4.
https://doi.org/10.1038/s41534-019-0185-4

[188] Ming Gong, Xiao Yuan, Shiyu Wang, Yulin Wu, Youwei Zhao, Chen Zha, Shaowei Li, Zhen Zhang, Qi Zhao, Yunchao Liu, et al. Experimental verification of five-qubit quantum error correction with superconducting qubits. arXiv preprint arXiv:1907.04507, 2019. 10.1093/nsr/nwab011.
https://doi.org/10.1093/nsr/nwab011
arXiv:1907.04507

[189] Ling Hu, Yuwei Ma, Weizhou Cai, Xianghao Mu, Yuan Xu, Weiting Wang, Yukai Wu, Haiyan Wang, YP Song, C-L Zou, et al. Quantum error correction and universal gate set operation on a binomial bosonic logical qubit. Nature Physics, 15 (5): 503–508, 2019. 10.1038/s41567-018-0414-3.
https://doi.org/10.1038/s41567-018-0414-3

[190] Robin Harper and Steven T. Flammia. Fault-tolerant logical gates in the ibm quantum experience. Physical Review Letters, 122 (8): 080504, February 2019. 10.1103/PhysRevLett.122.080504.
https://doi.org/10.1103/PhysRevLett.122.080504

[191] James R. Wootton. Benchmarking near-term devices with quantum error correction. Quantum Science and Technology, 5 (4): 044004, October 2020. ISSN 2058-9565. 10.1088/2058-9565/aba038. arXiv:2004.11037 [quant-ph].
https://doi.org/10.1088/2058-9565/aba038
arXiv:2004.11037

[192] Christian Kraglund Andersen, Ants Remm, Stefania Lazar, Sebastian Krinner, Nathan Lacroix, Graham J Norris, Mihai Gabureac, Christopher Eichler, and Andreas Wallraff. Repeated quantum error detection in a surface code. Nature Physics, 16: 875–880, 2020. 10.1038/s41567-020-0920-y.
https://doi.org/10.1038/s41567-020-0920-y

[193] Laird Egan, Dripto M. Debroy, Crystal Noel, Andrew Risinger, Daiwei Zhu, Debopriyo Biswas, Michael Newman, Muyuan Li, Kenneth R. Brown, Marko Cetina, and Christopher Monroe. Fault-tolerant control of an error-corrected qubit. Nature, 598 (7880): 281–286, October 2021. ISSN 1476-4687. 10.1038/s41586-021-03928-y.
https://doi.org/10.1038/s41586-021-03928-y

[194] Yi-Han Luo, Ming-Cheng Chen, Manuel Erhard, Han-Sen Zhong, Dian Wu, Hao-Yang Tang, Qi Zhao, Xi-Lin Wang, Keisuke Fujii, Li Li, et al. Quantum teleportation of physical qubits into logical code-spaces. arXiv preprint arXiv:2009.06242, 2020. 10.1073/pnas.2026250118.
https://doi.org/10.1073/pnas.2026250118
arXiv:2009.06242

[195] P Campagne-Ibarcq, A Eickbusch, S Touzard, E Zalys-Geller, NE Frattini, VV Sivak, P Reinhold, S Puri, S Shankar, RJ Schoelkopf, et al. Quantum error correction of a qubit encoded in grid states of an oscillator. Nature, 584 (7821): 368–372, 2020. 10.1038/s41586-020-2603-3.
https://doi.org/10.1038/s41586-020-2603-3

[196] Zijun Chen et al. Exponential suppression of bit or phase errors with cyclic error correction. Nature, 595 (78677867): 383–387, July 2021. ISSN 1476-4687. 10.1038/s41586-021-03588-y.
https://doi.org/10.1038/s41586-021-03588-y

[197] C. Ryan-Anderson et al. Realization of real-time fault-tolerant quantum error correction. Physical Review X, 11 (4): 041058, December 2021. 10.1103/PhysRevX.11.041058.
https://doi.org/10.1103/PhysRevX.11.041058

[198] Sebastian Krinner, Nathan Lacroix, Ants Remm, Agustin Di Paolo, Elie Genois, Catherine Leroux, Christoph Hellings, Stefania Lazar, Francois Swiadek, Johannes Herrmann, Graham J. Norris, Christian Kraglund Andersen, Markus Müller, Alexandre Blais, Christopher Eichler, and Andreas Wallraff. Realizing repeated quantum error correction in a distance-three surface code. 605: 669–674, May 2022. ISSN 1476-4687. 10.1038/s41586-022-04566-8.
https://doi.org/10.1038/s41586-022-04566-8

[199] M. H. Abobeih, Y. Wang, J. Randall, S. J. H. Loenen, C. E. Bradley, M. Markham, D. J. Twitchen, B. M. Terhal, and T. H. Taminiau. Fault-tolerant operation of a logical qubit in a diamond quantum processor. Nature, 606 (7916): 884–889, June 2022. ISSN 1476-4687. 10.1038/s41586-022-04819-6.
https://doi.org/10.1038/s41586-022-04819-6

[200] Youwei Zhao, Yangsen Ye, He-Liang Huang, Yiming Zhang, Dachao Wu, Huijie Guan, Qingling Zhu, Zuolin Wei, Tan He, Sirui Cao, Fusheng Chen, Tung-Hsun Chung, Hui Deng, Daojin Fan, Ming Gong, Cheng Guo, Shaojun Guo, Lianchen Han, Na Li, Shaowei Li, Yuan Li, Futian Liang, Jin Lin, Haoran Qian, Hao Rong, Hong Su, Lihua Sun, Shiyu Wang, Yulin Wu, Yu Xu, Chong Ying, Jiale Yu, Chen Zha, Kaili Zhang, Yong-Heng Huo, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. Realization of an error-correcting surface code with superconducting qubits. Physical Review Letters, 129 (3): 030501, July 2022. 10.1103/PhysRevLett.129.030501.
https://doi.org/10.1103/PhysRevLett.129.030501

[201] V. V. Sivak, A. Eickbusch, B. Royer, S. Singh, I. Tsioutsios, S. Ganjam, A. Miano, B. L. Brock, A. Z. Ding, L. Frunzio, S. M. Girvin, R. J. Schoelkopf, and M. H. Devoret. Real-time quantum error correction beyond break-even. Nature, 616 (7955): 50–55, April 2023. ISSN 1476-4687. 10.1038/s41586-023-05782-6.
https://doi.org/10.1038/s41586-023-05782-6

[202] Rajeev Acharya et al. Suppressing quantum errors by scaling a surface code logical qubit. Nature, 614 (7949): 676–681, February 2023. ISSN 1476-4687. 10.1038/s41586-022-05434-1.
https://doi.org/10.1038/s41586-022-05434-1

[203] A. Paetznick, M. P. da Silva, C. Ryan-Anderson, J. M. Bello-Rivas, J. P. Campora III, A. Chernoguzov, J. M. Dreiling, C. Foltz, F. Frachon, J. P. Gaebler, T. M. Gatterman, L. Grans-Samuelsson, D. Gresh, D. Hayes, N. Hewitt, C. Holliman, C. V. Horst, J. Johansen, D. Lucchetti, Y. Matsuoka, M. Mills, S. A. Moses, B. Neyenhuis, A. Paz, J. Pino, P. Siegfried, A. Sundaram, D. Tom, S. J. Wernli, M. Zanner, R. P. Stutz, and K. M. Svore. Demonstration of logical qubits and repeated error correction with better-than-physical error rates. (arXiv:2404.02280), November 2024. 10.48550/arXiv.2404.02280. URL http://arxiv.org/abs/2404.02280. arXiv:2404.02280 [quant-ph].
https://doi.org/10.48550/arXiv.2404.02280
arXiv:2404.02280

[204] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin. Logical quantum processor based on reconfigurable atom arrays. Nature, 626 (7997): 58–65, February 2024b. ISSN 1476-4687. 10.1038/s41586-023-06927-3.
https://doi.org/10.1038/s41586-023-06927-3

[205] Rajeev Acharya et al. Quantum error correction below the surface code threshold. Nature, page 1–3, December 2024. ISSN 1476-4687. 10.1038/s41586-024-08449-y.
https://doi.org/10.1038/s41586-024-08449-y

[206] Hartmut Neven. Meet willow, our state-of-the-art quantum chip. https://blog.google/technology/research/google-willow-quantum-chip/, December 2024.
https://blog.google/technology/research/google-willow-quantum-chip/

[207] Riddhi S. Gupta, Neereja Sundaresan, Thomas Alexander, Christopher J. Wood, Seth T. Merkel, Michael B. Healy, Marius Hillenbrand, Tomas Jochym-O’Connor, James R. Wootton, Theodore J. Yoder, Andrew W. Cross, Maika Takita, and Benjamin J. Brown. Encoding a magic state with beyond break-even fidelity. Nature, 625 (7994): 259–263, January 2024. ISSN 1476-4687. 10.1038/s41586-023-06846-3.
https://doi.org/10.1038/s41586-023-06846-3

[208] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. arXiv:1803.11173 [physics, physics:quant-ph], March 2018. 10.1038/s41467-018-07090-4. URL http://arxiv.org/abs/1803.11173. arXiv: 1803.11173.
https://doi.org/10.1038/s41467-018-07090-4
arXiv:1803.11173

[209] Hrant Gharibyan, Mohammed Zuhair Mullath, Nicholas E. Sherman, Vincent P. Su, Hayk Tepanyan, and Yuxuan Zhang. Heuristic quantum advantage with peaked circuits. (arXiv:2510.25838), October 2025. 10.48550/arXiv.2510.25838. URL http://arxiv.org/abs/2510.25838. arXiv:2510.25838 [quant-ph].
https://doi.org/10.48550/arXiv.2510.25838
arXiv:2510.25838

[210] Abhinav Deshpande, Bill Fefferman, Soumik Ghosh, Michael Gullans, and Dominik Hangleiter. Peaked quantum advantage using error correction. (arXiv:2510.05262), October 2025. 10.48550/arXiv.2510.05262. URL http://arxiv.org/abs/2510.05262. arXiv:2510.05262 [quant-ph].
https://doi.org/10.48550/arXiv.2510.05262
arXiv:2510.05262

Cited by

[1] Jens Eisert and John Preskill, "Mind the gaps: The fraught road to quantum advantage", arXiv:2510.19928, (2025).

[2] Laurin E. Fischer, "Enabling large-scale digital quantum simulations with superconducting qubits", arXiv:2602.04719, (2026).

[3] Sven Benjamin Kožić, Gianpaolo Torre, and Salvatore Marco Giampaolo, "Advancements in numerical methods for quantum resources", Journal of Statistical Mechanics: Theory and Experiment 2026 1, 014001 (2026).

[4] Tai-Ping Sun, Zhao-Yun Chen, Yun-Jie Wang, Cheng Xue, Huan-Yu Liu, Xi-Ning Zhuang, Xiao-Fan Xu, Yu-Chun Wu, and Guo-Ping Guo, "SparQSim: Simulating Scalable Quantum Algorithms via Sparse Quantum State Representations", arXiv:2503.15118, (2025).

[5] Pablo Bermejo, Benjamin Villalonga, Brayden Ware, Guifre Vidal, and Aaron Szasz, "Tensor Networks with Belief Propagation Cannot Feasibly Simulate Google's Quantum Echoes Experiment", arXiv:2604.15427, (2026).

[6] Jakub Czartowski and Rafał Bistroń, "Advantage framework for resource engines", Physical Review A 114 2, 022461 (2026).

[7] Matthew Duschenes, Roger G. Melko, Juan Carrasquilla, and Raymond Laflamme, "Distributions of noisy expectation values over sets of measurement operators", Physical Review A 114 2, 022434 (2026).

[8] Hrishikesh Belagali, Thomas Van Camp, R. Pradeep, Sourin Das, Namit Anand, and Ryan LaRose, "Efficient classical simulation of large-scale unitary cluster Jastrow circuits", arXiv:2607.21337, (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-09-15 19:37:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-09-15 19:37:45).

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.