Pauli path simulations of noisy quantum circuits beyond average case
1Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany
2Munich Center for Quantum Science and Technology (MCQST), Schellingstr. 4, D-80799 Munich, Germany
3Deparment of Electrical and Computer Engineering, University of Washington, Seattle, Washington 98195, USA
| Published: | 2025-05-05, volume 9, page 1730 |
| Editor: | Dax Enshan Koh |
| Eprint: | arXiv:2407.16068v2 |
| Doi: | https://doi.org/10.22331/q-2025-05-05-1730 |
| Citation: | Quantum 9, 1730 (2025). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
For random quantum circuits on $n$ qubits of depth $\Theta(\log n)$ with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method [1] . 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 $\unicode{x2013}$ 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.
Featured image: Graphical representation of the Pauli path method. The operator $O$ is evolved under Heisenberg evolution, expressing it in the Pauli basis after each layer. The process can be depicted as a tree: first $U_d$ is applied, and $U_d^{\dagger}OU_d$ can be written as a linear combination of Pauli strings, denoted as $s_{d-1}$ in the figure. Then, each of the $s_{d-1}$ will be evolved according to $U_{d-1}$, which will yield a superposition of different $s_{d-2}$. The process is then repeated until all the layers have been applied. We refer to a single branch of this tree as a Pauli path $s$, and it corresponds to a specific configuration of Pauli strings, $s=(s_d,s_{d-1},..,s_0)$. The sum over all possible Pauli paths yields the exact Heisenberg evolution of the operator $O$.
Popular summary
We first analyze the interplay between noise and quantum magic, which is a quantum resource that is known to be necessary to achieve exponential quantum speed-ups. We find that, if noise is introduced at a faster rate than quantum magic, the noisy quantum circuit can be simulated classically using Pauli path algorithms. This result illustrates the existence of a “competition” between noise and the quantum magic in the system: if the noise “outcompetes” the quantum magic, the noisy circuit behaves in a more classical way, which implies classical simulability. As a consequence of our result, we show how this result limits the potential for exponential quantum speed-ups of certain classes of variational quantum algorithms. Furthermore, we also make explicit the limitations of the Pauli-path algorithms by providing a simple noisy quantum circuit for which the classical simulation fails even though it is known to succeed typically for quantum circuits.
► BibTeX data
► References
[1] 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 ’23. ACM (2023).
https://doi.org/10.1145/3564246.3585234
[2] I. M. Georgescu, S. Ashhab, and Franco Nori. ``Quantum simulation''. Rev. Mod. Phys. 86, 153–185 (2014).
https://doi.org/10.1103/RevModPhys.86.153
[3] P.W. Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th Annual Symposium on Foundations of Computer Science. Pages 124–134. (1994).
https://doi.org/10.1109/SFCS.1994.365700
[4] Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM J. Comput. 26, 1484–1509 (1997).
https://doi.org/10.1137/S0097539795293172
[5] 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–782 (2024).
https://doi.org/10.1038/s41586-024-07107-7
[6] Google Quantum AI. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676–681 (2023).
https://doi.org/10.1038/s41586-022-05434-1
[7] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[8] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. ``The complexity of nisq''. Nat. Commun. 14, 6001 (2023).
https://doi.org/10.1038/s41467-023-41217-6
[9] 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–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9
[10] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028
[11] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nat. Commun. 5, 1–7 (2014).
https://doi.org/10.1038/ncomms5213
[12] 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–12 (2021).
https://doi.org/10.1038/s41467-021-21728-w
[13] Tobias Haug, Kishor Bharti, and M.S. Kim. ``Capacity and quantum geometry of parametrized quantum circuits''. PRX Quantum 2, 040309 (2021).
https://doi.org/10.1103/PRXQuantum.2.040309
[14] Kouhei Nakaji and Naoki Yamamoto. ``Expressibility of the alternating layered ansatz for quantum computation''. Quantum 5, 434 (2021).
https://doi.org/10.22331/q-2021-04-19-434
[15] V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte. ``Reachability deficits in quantum approximate optimization''. Phys. Rev. Lett. 124, 090504 (2020).
https://doi.org/10.1103/PhysRevLett.124.090504
[16] Daniel Stilck França and Raul Garcia-Patron. ``Limitations of optimization algorithms on noisy quantum devices''. Nat. Phys. 17, 1221–1227 (2021).
https://doi.org/10.1038/s41567-021-01356-3
[17] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França. ``Limitations of variational quantum algorithms: A quantum optimal transport approach''. PRX Quantum 4, 010309 (2023).
https://doi.org/10.1103/PRXQuantum.4.010309
[18] Guillermo González-García, Rahul Trivedi, and J. Ignacio Cirac. ``Error propagation in nisq devices for solving classical optimization problems''. PRX Quantum 3, 040326 (2022).
https://doi.org/10.1103/PRXQuantum.3.040326
[19] 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à, 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–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
[20] 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).
https://doi.org/10.1103/PhysRevLett.127.180501
[21] 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–505 (2023).
https://doi.org/10.1038/s41586-023-06096-3
[22] 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).
https://doi.org/10.1103/PRXQuantum.5.010308
[23] Kostyantyn Kechedzhi, SV Isakov, Salvatore Mandrà, 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–441 (2024).
https://doi.org/10.1016/j.future.2023.12.002
[24] Yuguo Shao, Fuchuan Wei, Song Cheng, and Zhengwei Liu. ``Simulating noisy variational quantum algorithms: A polynomial approach''. Phys. Rev. Lett. 133, 120603 (2024).
https://doi.org/10.1103/PhysRevLett.133.120603
[25] 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.
arXiv:2308.03082
[26] Enrico Fontana, Manuel S Rudolph, Ross Duncan, Ivan Rungger, and Cristina Cı̂rstoiu. ``Classical simulations of noisy variational quantum circuits'' (2023). arXiv:2306.05400.
arXiv:2306.05400
[27] Manuel S Rudolph, Enrico Fontana, Zoë Holmes, and Lukasz Cincio. ``Classical surrogate simulation of quantum systems with lowesa'' (2023). arXiv:2308.09109.
arXiv:2308.09109
[28] Sajant Anand, Kristan Temme, Abhinav Kandala, and Michael Zaletel. ``Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime'' (2023). arXiv:2306.17839.
arXiv:2306.17839
[29] Nikita A. Nemkov, Evgeniy O. Kiktenko, and Aleksey K. Fedorov. ``Fourier expansion in variational quantum algorithms''. Phys. Rev. A 108 (2023).
https://doi.org/10.1103/physreva.108.032406
[30] Xun Gao and Luming Duan. ``Efficient classical simulation of noisy quantum computation'' (2018). arXiv:1810.03176.
arXiv:1810.03176
[31] 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–1056. SIAM (2025).
https://doi.org/10.1137/1.9781611978322.30
[32] Andrew Tanggara, Mile Gu, and Kishor Bharti. ``Classically spoofing system linear cross entropy score benchmarking'' (2024). arXiv:2405.00789.
arXiv:2405.00789
[33] Curt von Keyserlingk, Frank Pollmann, and Tibor Rakovszky. ``Operator backflow and the classical simulation of quantum transport''. Phys. Rev. B 105, 245101 (2022).
https://doi.org/10.1103/PhysRevB.105.245101
[34] Tibor Rakovszky, C. W. von Keyserlingk, and Frank Pollmann. ``Dissipation-assisted operator evolution method for capturing hydrodynamic transport''. Phys. Rev. B 105, 075131 (2022).
https://doi.org/10.1103/PhysRevB.105.075131
[35] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão. ``Random quantum circuits anticoncentrate in log depth''. PRX Quantum 3, 010333 (2022).
https://doi.org/10.1103/PRXQuantum.3.010333
[36] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. ``On the complexity and verification of quantum random circuit sampling''. Nat. Phys. 15, 159–163 (2019).
https://doi.org/10.1038/s41567-018-0318-2
[37] 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–245 (2022).
https://doi.org/10.1016/j.scib.2021.10.017
[38] 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–809. (2015).
https://doi.org/10.1109/FOCS.2015.54
[39] 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).
https://doi.org/10.1103/PhysRevX.11.011020
[40] 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).
https://doi.org/10.1103/PhysRevD.109.114510
[41] 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).
https://doi.org/10.1038/s41534-021-00420-3
[42] Refik Mansuroglu, Timo Eckstein, Ludwig Nützel, 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).
https://doi.org/10.1088/2058-9565/acb1d0
[43] 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).
https://doi.org/10.1088/1751-8121/acc369
[44] Matthieu Vanicat, Lenart Zadnik, and TomažProsen. ``Integrable trotterization: Local conservation laws and boundary driving''. Phys. Rev. Lett. 121, 030606 (2018).
https://doi.org/10.1103/PhysRevLett.121.030606
[45] 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).
https://doi.org/10.1103/PRXQuantum.5.020315
[46] 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).
https://doi.org/10.1103/PhysRevX.8.011044
[47] 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).
https://doi.org/10.1103/PhysRevX.8.021013
[48] Sattwik Deb Mishra, Miguel Frías-Pérez, and Rahul Trivedi. ``Classically computing performance bounds on depolarized quantum circuits''. PRX Quantum 5, 020317 (2024).
https://doi.org/10.1103/PRXQuantum.5.020317
[49] 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.
arXiv:2404.15397
[50] Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan. ``Limitations of noisy reversible computation'' (1996). arXiv:9611028.
arXiv:quant-ph/9611028
[51] 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'' (2024). arXiv:2403.13927.
arXiv:2403.13927
[52] Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. ``Effect of nonunital noise on random-circuit sampling''. PRX Quantum 5, 030317 (2024).
https://doi.org/10.1103/PRXQuantum.5.030317
[53] Daniel Gottesman. ``The heisenberg representation of quantum computers'' (1998). arXiv:9807006.
arXiv:quant-ph/9807006
[54] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328
[55] Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by clifford gates''. Phys. Rev. Lett. 116, 250501 (2016).
https://doi.org/10.1103/PhysRevLett.116.250501
[56] 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–419. IEEE (2006).
https://doi.org/10.1109/FOCS.2006.50
[57] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer. ``Simulation of qubit quantum circuits via pauli propagation''. Phys. Rev. A 99, 062337 (2019).
https://doi.org/10.1103/PhysRevA.99.062337
[58] 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.
https://www.cambridge.org/highereducation/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE
[59] 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–540. (2019).
https://doi.org/10.48550/arXiv.1905.11349
[60] Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error rate''. SIAM J. Comput. 38, 1207–1282 (2008).
https://doi.org/10.1137/S0097539799359385
[61] 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–66 (2024).
https://doi.org/10.1016/j.physrep.2024.03.002
[62] 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).
https://doi.org/10.1103/PhysRevResearch.4.033029
[63] 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–720 (2009).
https://doi.org/10.26421/qic9.7-8-12
[64] 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.
https://books.google.de/books?id=FzFEEVO3PXYC
[65] Adam Nahum, Sagar Vijay, and Jeongwan Haah. ``Operator spreading in random unitary circuits''. Phys. Rev. X 8, 021014 (2018).
https://doi.org/10.1103/PhysRevX.8.021014
[66] 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–336 (2021).
https://doi.org/10.1038/s41567-020-01105-y
[67] Thomas Schuster, Chao Yin, Xun Gao, and Norman Y Yao. ``A polynomial-time classical algorithm for noisy quantum circuits'' (2024). arXiv:2407.12768.
arXiv:2407.12768
[68] 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.
https://mitpress.mit.edu/9780262046305/introduction-to-algorithms
Cited by
[1] Zong-Yuan Ge, Lian-Ao Wu, and Zhao-Ming Wang, "Enhanced algorithmic perfect state transfer on IBM quantum computers", Quantum Science and Technology 11 2, 025005 (2026).
[2] Gleb Kalachev, Pavel Mosharev, Zuoheng Zou, Pavel Panteleev, and Man-Hong Yung, "Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits", Quantum 10, 2173 (2026).
[3] 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 (2025).
[4] Zihan Cheng, Eric Huang, Vedika Khemani, Michael J. Gullans, and Matteo Ippoliti, "Emergent Unitary Designs for Encoded Qubits from Coherent Errors and Syndrome Measurements", PRX Quantum 6 3, 030333 (2025).
[5] Guillermo González-García, Alexey V. Gorshkov, J. Ignacio Cirac, and Rahul Trivedi, "Dynamical Complexity of Non-Gaussian Many-Body Systems with Dissipation", Physical Review Letters 135 19, 190401 (2025).
[6] Ewan McCulloch, J. Alexander Jacoby, Curt von Keyserlingk, and Sarang Gopalakrishnan, "Subexponential Decay of Local Correlations from Diffusion-Limited Dephasing", Physical Review Letters 136 19, 190403 (2026).
[7] Zong-Liang Li and Shi-Xin Zhang, "Dual role of low-weight Pauli propagation: A flawed simulator but a powerful initializer for variational quantum algorithms", Physical Review Research 8 1, 013266 (2026).
[8] Yuri Alexeev, Marwa H. Farag, Taylor L. Patti, Mark E. Wolf, Natalia Ares, Alán Aspuru-Guzik, Simon C. Benjamin, Zhenyu Cai, Shuxiang Cao, Christopher Chamberland, Zohim Chandani, Federico Fedele, Ikko Hamamura, Nicholas Harrigan, Jin-Sung Kim, Elica Kyoseva, Justin G. Lietz, Tom Lubowe, Alexander McCaskey, Roger G. Melko, Kouhei Nakaji, Alberto Peruzzo, Pooja Rao, Bruno Schmitt, Sam Stanwyck, Norm M. Tubman, Hanrui Wang, and Timothy Costa, "Artificial intelligence for quantum computing", Nature Communications 16 1, 10829 (2025).
[9] Shuo Liu, Shao-Kai Jian, and Shi-Xin Zhang, "Noisy monitored quantum circuits", Journal of Physics: Condensed Matter 38 20, 203001 (2026).
[10] Armando Angrisani, Antonio A. Mele, Manuel S. Rudolph, M. Cerezo, and Zoë Holmes, "Simulating Quantum Circuits with Arbitrary Local Noise Using Pauli Propagation", PRX Quantum 7 2, 020313 (2026).
[11] Victor Martinez, Armando Angrisani, Ekaterina Pankovets, Omar Fawzi, and Daniel Stilck França, "Efficient Simulation of Parametrized Quantum Circuits under Nonunital Noise through Pauli Backpropagation", Physical Review Letters 134 25, 250602 (2025).
[12] Sacha Lerch, Ricard Puig, Manuel S. Rudolph, Armando Angrisani, Tyson Jones, M. Cerezo, Supanut Thanasilp, and Zoë Holmes, "Efficient Quantum-Enhanced Classical Simulation for Patches of Quantum Landscapes", PRX Quantum 7 2, 020359 (2026).
[13] Aaron Miller, Joachim Favre, Zoë Holmes, Özlem Salehi, Rahul Chakraborty, Anton Nykänen, Zoltán Zimborás, Adam Glos, and Guillermo García-Pérez, "Simulation of Fermionic circuits using Majorana Propagation", arXiv:2503.18939, (2025).
[14] Armando Angrisani and Elham Kashefi, "Quantum Differential Privacy in the Local Model", IEEE Transactions on Information Theory 71 5, 3675 (2025).
[15] Cristina Cirstoiu, "A Fourier analysis framework for approximate classical simulations of quantum circuits", arXiv:2410.13856, (2024).
[16] Jon Nelson, Joel Rajakumar, Dominik Hangleiter, and Michael J. Gullans, "Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates", arXiv:2411.02535, (2024).
[17] Ashe Miller, Corey Ostrove, Jordan Hines, Robin Blume-Kohout, Kevin Young, and Timothy Proctor, "Efficient simulation of Clifford circuits with small Markovian errors", arXiv:2504.15128, (2025).
[18] Jon Nelson, Joel Rajakumar, and Michael J. Gullans, "Limitations of Noisy Geometrically Local Quantum Circuits", arXiv:2510.06346, (2025).
[19] Varun Upreti, Ulysse Chabaud, Zoë Holmes, and Armando Angrisani, "When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits", arXiv:2510.07264, (2025).
[20] Jue Xu, Chu Zhao, Xiangran Zhang, Shuchen Zhu, and Qi Zhao, "Classical Simulation of Noiseless Quantum Dynamics without Randomness", arXiv:2601.15770, (2026).
[21] Yanting Teng, Su Yeon Chang, Manuel S. Rudolph, and Zoë Holmes, "Leveraging Symmetry Merging in Pauli Propagation", arXiv:2512.12094, (2025).
[22] Manuel S. Rudolph, Armando Angrisani, Andrew Wright, Iwo Sanderski, Ricard Puig, and Zoë Holmes, "Thermal State Simulation with Pauli and Majorana Propagation", arXiv:2602.04878, (2026).
[23] Shravan Shravan, Mohsin Raza, and Ariel Shlosberg, "Efficient simulation of noisy IQP circuits with amplitude-damping noise", arXiv:2604.05036, (2026).
[24] Shao-Hen Chiew, Armando Angrisani, Zoë Holmes, and Giuseppe Carleo, "Quantum simulation in the Heisenberg picture via vectorization", arXiv:2602.20154, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 00:07:21) and SAO/NASA ADS (last updated successfully 2026-08-09 00:07:29). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.