- Physical Review Journals
All JournalsPhysics Magazine

PRX Quantum

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Error Propagation in NISQ Devices for Solving Classical Optimization Problems

Guillermo González-García1,2,*,‡, Rahul Trivedi1,2,†,‡, and J. Ignacio Cirac1,2

  • 1Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, Garching 85748, Germany
  • 2Munich Center for Quantum Science and Technology (MCQST), Schellingstr. 4, Munich D-80799, Germany

  • *guillermo.gonzalez@mpq.mpg.de
  • †rahul.trivedi@mpq.mpg.de
  • ‡Both authors contributed equally.
PDF

PRX Quantum 3, 040326 – Published 5 December, 2022

DOI: https://doi.org/10.1103/PRXQuantum.3.040326

Abstract

We propose a random circuit model that attempts to capture the behavior of noisy intermediate-scale quantum devices when used for variationally solving classical optimization problems. Our model accounts for the propagation of arbitrary single-qubit errors through the circuit. We find that, even with a small noise rate, the quality of the obtained optima implies that a single-qubit error rate of 1/(nD) (where n is the number of qubits and D is the circuit depth) is needed for the possibility of a quantum advantage. We estimate that this translates to an error rate lower than 10−6 using the quantum approximate optimization algorithm for classical optimization problems with two-dimensional circuits.

View figure in article

Physics Subject Headings (PhySH)

Popular Summary

Recent experimental advances in quantum hardware have given us access to small, noisy quantum computers. However, it remains unclear whether they can outperform classical computers in problems of practical interest since the noise levels in these devices place serious limitations on what they can achieve. One of the proposed applications for these small devices is to use the entanglement structure of possible quantum states to solve classical optimization problems. In this work, we theoretically analyze the impact of noise on the quality of the solution obtained by these devices.

An indispensable ingredient that makes quantum computers powerful is quantum entanglement. However, quantum entanglement might also be a double-edged sword: while it is necessary to unlock the power of quantum computers, any mechanism to create entanglement in a quantum circuit also propagates errors through the circuit. Our model, based on random circuits, shows that in the presence of entanglement, an error in one qubit can spread rapidly to the others and possibly to an extent that quantum circuits could lose their advantage over known classical algorithms. The analysis in our work suggests that the propagation of errors should be taken into account when designing quantum algorithms, as it might guide us to design better circuits even with current hardware constraints.

Article Text

References (52)

  1. Frank Arute, et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  2. Yulin Wu, et al., Strong Quantum Computational Advantage Using a Superconducting Quantum Processor, Phys. Rev. Lett. 127, 180501 (2021).
  3. Han-Sen Zhong, et al., Quantum computational advantage using photons, Science 370, 1460 (2020).
  4. John Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  5. Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, Noisy intermediate-scale quantum algorithms, Rev. Mod. Phys. 94, 015004 (2022).
  6. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser, Quantum computation by adiabatic evolution. arXiv preprint (2000), ArXiv:quant-ph/0001106.
  7. Tameem Albash and Daniel A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018).
  8. Google AI Quantum, Collaborators*†, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, et al., Hartree-fock on a superconducting qubit quantum computer, Science, 369, 1084 (2020).
  9. Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, and Lukasz Cincio, et al., Variational quantum algorithms, Nat. Rev. Phys. 3, 625 (2021).
  10. Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, and Sergio Boixo, et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys. 17, 332 (2021).
  11. Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms, New J. Phys. 18, 023023 (2016).
  12. Tyson Jones, Suguru Endo, Sam McArdle, Xiao Yuan, and Simon C. Benjamin, Variational quantum algorithms for discovering Hamiltonian spectra, Phys. Rev. A 99, 062304 (2019).
  13. 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 (2014).
  14. Dave Wecker, Matthew B. Hastings, and Matthias Troyer, Progress towards practical quantum variational algorithms, Phys. Rev. A 92, 042303 (2015).
  15. David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch, Filtering variational quantum algorithms for combinatorial optimization, Quantum Sci. Technol. 7, 015021 (2022).
  16. Tadashi Kadowaki and Hidetoshi Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E 58, 5355 (1998).
  17. Suguru Endo, Iori Kurata, and Yuya O. Nakagawa, Calculation of the Green’s function on near-term quantum computers, Phys. Rev. Res. 2, 033281 (2020).
  18. A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chem. Phys. Lett. 219, 343 (1994).
  19. Hongbin Liu, Guang Hao Low, Damian S. Steiger, Thomas Häner, Markus Reiher, and Matthias Troyer, Prospects of quantum computing for molecular sciences, Mater. Theory 6, 1 (2022).
  20. Andrew A. Houck, Hakan E. Türeci, and Jens Koch, On-chip quantum simulation with superconducting circuits, Nat. Phys. 8, 292 (2012).
  21. Matteo Ippoliti, Kostyantyn Kechedzhi, Roderich Moessner, S. L. Sondhi, and Vedika Khemani, Many-Body Physics in the NISQ Era: Quantum Programming a Discrete Time Crystal, PRX Quantum 2, 030346 (2021).
  22. Bernhard H. Korte, Jens Vygen, B. Korte, and J. Vygen, Combinatorial Optimization (Springer, Heidelberg, 2011), Vol. 1.
  23. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, A quantum approximate optimization algorithm. (2014), arXiv preprint ArXiv:1411.4028.
  24. Edward Farhi and Aram W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm. (2016), arXiv preprint ArXiv:1602.07674.
  25. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou, The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. (2019), arXiv preprint ArXiv:1910.08187.
  26. Gian Giacomo Guerreschi and Anne Y. Matsuura, Qaoa for max-cut requires hundreds of qubits for quantum speed-up, Sci. Rep. 9, 1 (2019).
  27. Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin, Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices, Phys. Rev. X 10, 021067 (2020).
  28. Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, Lucas T. Brady, Abhinav Deshpande, Fangli Liu, Stephen Jordan, Alexey V. Gorshkov, and Christopher Monroe, Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator, Proc. Nat. Acad. Sci. 117, 25396 (2020).
  29. 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 (2021).
  30. Tobias Haug, Kishor Bharti, and M. S. Kim, Capacity and Quantum Geometry of Parametrized Quantum Circuits, PRX Quantum 2, 040309 (2021).
  31. Kouhei Nakaji and Naoki Yamamoto, Expressibility of the alternating layered ansatz for quantum computation, Quantum 5, 434 (2021).
  32. V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte, Reachability Deficits in Quantum Approximate Optimization, Phys. Rev. Lett. 124, 090504 (2020).
  33. Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nat. Commun. 12, 1 (2021).
  34. Jeffrey Marshall, Filip Wudarski, Stuart Hadfield, and Tad Hogg, Characterizing local noise in QAOA circuits, IOP SciNotes 1, 025208 (2020).
  35. Cheng Xue, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo, Effects of quantum noise on quantum approximate optimization algorithm, Chin. Phys. Lett. 38, 030302 (2021).
  36. Daniel Stilck França and Raul Garcia-Patron, Limitations of optimization algorithms on noisy quantum devices, Nat. Phys. 17, 1221 (2021).
  37. Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan, Limitations of noisy reversible computation. (1996), arXiv preprint ArXiv:quant-ph/9611028.
  38. Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim, Quantum refrigerator. (2013), arXiv preprint ArXiv:1301.1995.
  39. Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu, in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), p. 1308. IEEE, 2022.
  40. Abhinav Deshpande, Bill Fefferman, Alexey V. Gorshkov, Michael J. Gullans, Pradeep Niroula, and Oles Shtanko, Tight bounds on the convergence of noisy random circuits to uniform. (2021), arXiv preprint ArXiv:2112.00716.
  41. Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, Random quantum circuits transform local noise into global white noise. (2021), arXiv preprint ArXiv:2111.14907.
  42. Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven, Characterizing quantum supremacy in near-term devices, Nat. Phys. 14, 595 (2018).
  43. Joseph Emerson, Robert Alicki, and Karol Życzkowski, Scalable noise estimation with random unitary operators, J. Opt. B: Quantum Semiclass. Opt. 7, S347 (2005).
  44. Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42, 1115 (1995).
  45. Paul Erdös, On some extremal problems in graph theory, Isr. J. Math. 3, 113 (1965).
  46. Eran Halperin, Dror Livnat, and Uri Zwick, Max cut in cubic graphs, J. Alg. 53, 169 (2004).
  47. F. Hadlock, Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput. 4, 221 (1975).
  48. It should be noted that a noiseless swap gate cannot propagate an error from one qubit to another, since it will just swap the error. Therefore, a more sophisticated model could account for this by distinguishing between the swap gates and other two-qubit gates, as well as adding other sources and types of noise. We still expect our scalings to hold in that case.
  49. Benjamin F. Schiffer, Jordi Tura, and J. Ignacio Cirac, Adiabatic spectroscopy and a variational quantum adiabatic algorithm. (2021), arXiv preprint ArXiv:2103.01226.
  50. Kazuoki Azuma, Weighted sums of certain dependent random variables, Tohoku Math. J. 19, 357 (1967).
  51. Gregory F. Lawler, Introduction to Stochastic Processes (Chapman and Hall/CRC, New York, 2018).
  52. Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc. 58, 13 (1963).

Outline

Information

PRX Quantum 3, 040326– Published 5 December, 2022
  • Received 13 April 2022
  • Accepted 13 October 2022
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation