{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T02:22:50Z","timestamp":1773109370356,"version":"3.50.1"},"reference-count":68,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T00:00:00Z","timestamp":1746403200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"German Federal Ministry of Education and Research","award":["13N16066"],"award-info":[{"award-number":["13N16066"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"For random quantum circuits on n<\/mml:mi><\/mml:math> qubits of depth &#x0398;<\/mml:mi>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math> with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method \\cite{Aharonov2023_paulipaths} . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates &#x2013;<\/mml:mtext><\/mml:math> going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit.<\/jats:p>","DOI":"10.22331\/q-2025-05-05-1730","type":"journal-article","created":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T11:41:31Z","timestamp":1746445291000},"page":"1730","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":7,"title":["Pauli path simulations of noisy quantum circuits beyond average case"],"prefix":"10.22331","volume":"9","author":[{"given":"Guillermo","family":"Gonz\u00e1lez-Garc\u00eda","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany"},{"name":"Munich Center for Quantum Science and Technology (MCQST), Schellingstr. 4, D-80799 Munich, Germany"}]},{"given":"J. Ignacio","family":"Cirac","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany"},{"name":"Munich Center for Quantum Science and Technology (MCQST), Schellingstr. 4, D-80799 Munich, Germany"}]},{"given":"Rahul","family":"Trivedi","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany"},{"name":"Deparment of Electrical and Computer Engineering, University of Washington, Seattle, Washington 98195, USA"}]}],"member":"9598","published-online":{"date-parts":[[2025,5,5]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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. STOC \u201923. ACM (2023).","DOI":"10.1145\/3564246.3585234"},{"key":"1","doi-asserted-by":"publisher","unstructured":"I. M. Georgescu, S. Ashhab, and Franco Nori. ``Quantum simulation''. Rev. Mod. Phys. 86, 153\u2013185 (2014).","DOI":"10.1103\/RevModPhys.86.153"},{"key":"2","doi-asserted-by":"publisher","unstructured":"P.W. Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th Annual Symposium on Foundations of Computer Science. Pages 124\u2013134. (1994).","DOI":"10.1109\/SFCS.1994.365700"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM J. Comput. 26, 1484\u20131509 (1997).","DOI":"10.1137\/S0097539795293172"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Andrew W Cross, Jay M Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J Yoder. ``High-threshold and low-overhead fault-tolerant quantum memory''. Nature 627, 778\u2013782 (2024).","DOI":"10.1038\/s41586-024-07107-7"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Google Quantum AI. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676\u2013681 (2023).","DOI":"10.1038\/s41586-022-05434-1"},{"key":"6","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. ``The complexity of nisq''. Nat. Commun. 14, 6001 (2023).","DOI":"10.1038\/s41467-023-41217-6"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. ``Variational quantum algorithms''. Nat. Rev. Phys. 3, 625\u2013644 (2021).","DOI":"10.1038\/s42254-021-00348-9"},{"key":"9","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Al\u00e1n Aspuru-Guzik, and Jeremy L O\u2019brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nat. Commun. 5, 1\u20137 (2014).","DOI":"10.1038\/ncomms5213"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. ``Cost function dependent barren plateaus in shallow parametrized quantum circuits''. Nat. Commun. 12, 1\u201312 (2021).","DOI":"10.1038\/s41467-021-21728-w"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Tobias Haug, Kishor Bharti, and M.S. Kim. ``Capacity and quantum geometry of parametrized quantum circuits''. PRX Quantum 2, 040309 (2021).","DOI":"10.1103\/PRXQuantum.2.040309"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Kouhei Nakaji and Naoki Yamamoto. ``Expressibility of the alternating layered ansatz for quantum computation''. Quantum 5, 434 (2021).","DOI":"10.22331\/q-2021-04-19-434"},{"key":"14","doi-asserted-by":"publisher","unstructured":"V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte. ``Reachability deficits in quantum approximate optimization''. Phys. Rev. Lett. 124, 090504 (2020).","DOI":"10.1103\/PhysRevLett.124.090504"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Daniel Stilck Fran\u00e7a and Raul Garcia-Patron. ``Limitations of optimization algorithms on noisy quantum devices''. Nat. Phys. 17, 1221\u20131227 (2021).","DOI":"10.1038\/s41567-021-01356-3"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Giacomo De Palma, Milad Marvian, Cambyse Rouz\u00e9, and Daniel Stilck Fran\u00e7a. ``Limitations of variational quantum algorithms: A quantum optimal transport approach''. PRX Quantum 4, 010309 (2023).","DOI":"10.1103\/PRXQuantum.4.010309"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Guillermo Gonz\u00e1lez-Garc\u00eda, Rahul Trivedi, and J. Ignacio Cirac. ``Error propagation in nisq devices for solving classical optimization problems''. PRX Quantum 3, 040326 (2022).","DOI":"10.1103\/PRXQuantum.3.040326"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando Brandao, David Buell, Brian Burkett, Yu Chen, Jimmy Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Michael Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew Harrigan, Michael Hartmann, Alan Ho, Markus Rudolf Hoffmann, Trent Huang, Travis Humble, Sergei Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, Dave Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandr\u00e0, Jarrod Ryan McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin Jeffery Sung, Matt Trevithick, Amit Vainsencher, Benjamin Villalonga, Ted White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John Martinis. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505\u2013510 (2019).","DOI":"10.1038\/s41586-019-1666-5"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. ``Strong quantum computational advantage using a superconducting quantum processor''. Phys. Rev. Lett. 127, 180501 (2021).","DOI":"10.1103\/PhysRevLett.127.180501"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. ``Evidence for the utility of quantum computing before fault tolerance''. Nature 618, 500\u2013505 (2023).","DOI":"10.1038\/s41586-023-06096-3"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Joseph Tindall, Matthew Fishman, E. Miles Stoudenmire, and Dries Sels. ``Efficient tensor network simulation of ibm's eagle kicked ising experiment''. PRX Quantum 5, 010308 (2024).","DOI":"10.1103\/PRXQuantum.5.010308"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Kostyantyn Kechedzhi, SV Isakov, Salvatore Mandr\u00e0, Benjamin Villalonga, Xiao Mi, Sergio Boixo, and V Smelyanskiy. ``Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments''. Future Gener. Comput. Syst. 153, 431\u2013441 (2024).","DOI":"10.1016\/j.future.2023.12.002"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Yuguo Shao, Fuchuan Wei, Song Cheng, and Zhengwei Liu. ``Simulating noisy variational quantum algorithms: A polynomial approach''. Phys. Rev. Lett. 133, 120603 (2024).","DOI":"10.1103\/PhysRevLett.133.120603"},{"key":"24","unstructured":"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'' (2023). arXiv:2308.03082."},{"key":"25","unstructured":"Enrico Fontana, Manuel S Rudolph, Ross Duncan, Ivan Rungger, and Cristina C\u0131\u0302rstoiu. ``Classical simulations of noisy variational quantum circuits'' (2023). arXiv:2306.05400."},{"key":"26","unstructured":"Manuel S Rudolph, Enrico Fontana, Zo\u00eb Holmes, and Lukasz Cincio. ``Classical surrogate simulation of quantum systems with lowesa'' (2023). arXiv:2308.09109."},{"key":"27","unstructured":"Sajant Anand, Kristan Temme, Abhinav Kandala, and Michael Zaletel. ``Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime'' (2023). arXiv:2306.17839."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Nikita A. Nemkov, Evgeniy O. Kiktenko, and Aleksey K. Fedorov. ``Fourier expansion in variational quantum algorithms''. Phys. Rev. A 108 (2023).","DOI":"10.1103\/physreva.108.032406"},{"key":"29","unstructured":"Xun Gao and Luming Duan. ``Efficient classical simulation of noisy quantum computation'' (2018). arXiv:1810.03176."},{"key":"30","doi-asserted-by":"publisher","unstructured":"Joel Rajakumar, James D Watson, and Yi-Kai Liu. ``Polynomial-time classical simulation of noisy iqp circuits with constant depth''. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1037\u20131056. SIAM (2025).","DOI":"10.1137\/1.9781611978322.30"},{"key":"31","unstructured":"Andrew Tanggara, Mile Gu, and Kishor Bharti. ``Classically spoofing system linear cross entropy score benchmarking'' (2024). arXiv:2405.00789."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Curt von Keyserlingk, Frank Pollmann, and Tibor Rakovszky. ``Operator backflow and the classical simulation of quantum transport''. Phys. Rev. B 105, 245101 (2022).","DOI":"10.1103\/PhysRevB.105.245101"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Tibor Rakovszky, C. W. von Keyserlingk, and Frank Pollmann. ``Dissipation-assisted operator evolution method for capturing hydrodynamic transport''. Phys. Rev. B 105, 075131 (2022).","DOI":"10.1103\/PhysRevB.105.075131"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brand\u00e3o. ``Random quantum circuits anticoncentrate in log depth''. PRX Quantum 3, 010333 (2022).","DOI":"10.1103\/PRXQuantum.3.010333"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. ``On the complexity and verification of quantum random circuit sampling''. Nat. Phys. 15, 159\u2013163 (2019).","DOI":"10.1038\/s41567-018-0318-2"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. ``Quantum computational advantage via 60-qubit 24-cycle random circuit sampling''. Sci. Bull. 67, 240\u2013245 (2022).","DOI":"10.1016\/j.scib.2021.10.017"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, and Robin Kothari. ``Hamiltonian simulation with nearly optimal dependence on all parameters''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 792\u2013809. (2015).","DOI":"10.1109\/FOCS.2015.54"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. ``Theory of trotter error with commutator scaling''. Phys. Rev. X 11, 011020 (2021).","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Roland C. Farrell, Marc Illa, Anthony N. Ciavarella, and Martin J. Savage. ``Quantum simulations of hadron dynamics in the schwinger model using 112 qubits''. Phys. Rev. D 109, 114510 (2024).","DOI":"10.1103\/PhysRevD.109.114510"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Fergus Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann, and Andrew G Green. ``Parallel quantum simulation of large systems on small nisq computers''. npj Quantum Inf. 7, 79 (2021).","DOI":"10.1038\/s41534-021-00420-3"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Refik Mansuroglu, Timo Eckstein, Ludwig N\u00fctzel, Samuel A Wilkinson, and Michael J Hartmann. ``Variational hamiltonian simulation for translational invariant systems via classical pre-processing''. Quantum Sci. and Technol. 8, 025006 (2023).","DOI":"10.1088\/2058-9565\/acb1d0"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Kazunobu Maruyoshi, Takuya Okuda, Juan W Pedersen, Ryo Suzuki, Masahito Yamazaki, and Yutaka Yoshida. ``Conserved charges in the quantum simulation of integrable spin chains''. J. Phys. A: Math. Theor. 56, 165301 (2023).","DOI":"10.1088\/1751-8121\/acc369"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Matthieu Vanicat, Lenart Zadnik, and Toma\u017eProsen. ``Integrable trotterization: Local conservation laws and boundary driving''. Phys. Rev. Lett. 121, 030606 (2018).","DOI":"10.1103\/PhysRevLett.121.030606"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Roland C. Farrell, Marc Illa, Anthony N. Ciavarella, and Martin J. Savage. ``Scalable circuits for preparing ground states on digital quantum computers: The schwinger model vacuum on 100 qubits''. PRX Quantum 5, 020315 (2024).","DOI":"10.1103\/PRXQuantum.5.020315"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan. ``Low-depth quantum simulation of materials''. Phys. Rev. X 8, 011044 (2018).","DOI":"10.1103\/PhysRevX.8.011044"},{"key":"46","doi-asserted-by":"publisher","unstructured":"C. W. von Keyserlingk, Tibor Rakovszky, Frank Pollmann, and S. L. Sondhi. ``Operator hydrodynamics, otocs, and entanglement growth in systems without conservation laws''. Phys. Rev. X 8, 021013 (2018).","DOI":"10.1103\/PhysRevX.8.021013"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Sattwik Deb Mishra, Miguel Fr\u00edas-P\u00e9rez, and Rahul Trivedi. ``Classically computing performance bounds on depolarized quantum circuits''. PRX Quantum 5, 020317 (2024).","DOI":"10.1103\/PRXQuantum.5.020317"},{"key":"48","unstructured":"Benjamin F Schiffer, Adrian Franco Rubio, Rahul Trivedi, and J Ignacio Cirac. ``The quantum adiabatic algorithm suppresses the proliferation of errors'' (2024). arXiv:2404.15397."},{"key":"49","unstructured":"Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan. ``Limitations of noisy reversible computation'' (1996). arXiv:9611028."},{"key":"50","unstructured":"Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck Fran\u00e7a, and Yihui Quek. ``Noise-induced shallow circuits and absence of barren plateaus'' (2024). arXiv:2403.13927."},{"key":"51","doi-asserted-by":"publisher","unstructured":"Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. ``Effect of nonunital noise on random-circuit sampling''. PRX Quantum 5, 030317 (2024).","DOI":"10.1103\/PRXQuantum.5.030317"},{"key":"52","unstructured":"Daniel Gottesman. ``The heisenberg representation of quantum computers'' (1998). arXiv:9807006."},{"key":"53","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by clifford gates''. Phys. Rev. Lett. 116, 250501 (2016).","DOI":"10.1103\/PhysRevLett.116.250501"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, and Falk Unger. ``New limits on fault-tolerant quantum computation''. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). Pages 411\u2013419. IEEE (2006).","DOI":"10.1109\/FOCS.2006.50"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer. ``Simulation of qubit quantum circuits via pauli propagation''. Phys. Rev. A 99, 062337 (2019).","DOI":"10.1103\/PhysRevA.99.062337"},{"key":"57","unstructured":"Michael A Nielsen and Isaac L Chuang. ``Quantum computation and quantum information''. Cambridge university press. (2010). url: https:\/\/www.cambridge.org\/highereducation\/books\/quantum-computation-and-quantum-information\/01E10196D0A682A6AEFFEA52D53BE9AE."},{"key":"58","doi-asserted-by":"publisher","unstructured":"Prakash Murali, Norbert Matthias Linke, Margaret Martonosi, Ali Javadi Abhari, Nhung Hong Nguyen, and Cinthia Huerta Alderete. ``Full-stack, real-system quantum computer studies: Architectural comparisons and design insights''. In Proceedings of the 46th International Symposium on Computer Architecture. Pages 527\u2013540. (2019).","DOI":"10.48550\/arXiv.1905.11349"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error rate''. SIAM J. Comput. 38, 1207\u20131282 (2008).","DOI":"10.1137\/S0097539799359385"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. ``A review on quantum approximate optimization algorithm and its variants''. Phys. Rep. 1068, 1\u201366 (2024).","DOI":"10.1016\/j.physrep.2024.03.002"},{"key":"61","doi-asserted-by":"publisher","unstructured":"Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou. ``Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer''. Phys. Rev. Res. 4, 033029 (2022).","DOI":"10.1103\/PhysRevResearch.4.033029"},{"key":"62","doi-asserted-by":"publisher","unstructured":"Nikhil Bansal, Sergey Bravyi, and Barbara M. Terhal. ``Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs''. Quantum Info. Comput. 9, 701\u2013720 (2009).","DOI":"10.26421\/qic9.7-8-12"},{"key":"63","doi-asserted-by":"crossref","unstructured":"Q.I. Rahman and G. Schmeisser. ``Analytic theory of polynomials''. London Mathematical Society monographs. Clarendon Press. (2002). url: https:\/\/books.google.de\/books?id=FzFEEVO3PXYC.","DOI":"10.1093\/oso\/9780198534938.001.0001"},{"key":"64","doi-asserted-by":"publisher","unstructured":"Adam Nahum, Sagar Vijay, and Jeongwan Haah. ``Operator spreading in random unitary circuits''. Phys. Rev. X 8, 021014 (2018).","DOI":"10.1103\/PhysRevX.8.021014"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nat. Phys. 17, 332\u2013336 (2021).","DOI":"10.1038\/s41567-020-01105-y"},{"key":"66","unstructured":"Thomas Schuster, Chao Yin, Xun Gao, and Norman Y Yao. ``A polynomial-time classical algorithm for noisy quantum circuits'' (2024). arXiv:2407.12768."},{"key":"67","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. ``Introduction to algorithms''. MIT press. (2022). url: https:\/\/mitpress.mit.edu\/9780262046305\/introduction-to-algorithms."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-05-05-1730\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T11:41:35Z","timestamp":1746445295000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-05-05-1730\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,5]]},"references-count":68,"URL":"https:\/\/doi.org\/10.22331\/q-2025-05-05-1730","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,5]]},"article-number":"1730"}}