- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review Applied

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Optimization via quantum preconditioning

Maxime Dupont*, Tina Oberoi†, and Bhuvanesh Sundar

  • *Contact author: mdupont@rigetti.com
  • †Current affiliation: University of Chicago, Chicago, Illinois, USA.
PDF

Phys. Rev. Applied 24, 044013 – Published 3 October, 2025

DOI: https://doi.org/10.1103/9prw-684p

Abstract

State-of-the-art classical optimization solvers set a high bar for quantum computers to deliver utility in this domain. Here, we introduce a quantum-preconditioning approach based on the quantum approximate optimization algorithm. This transforms the input problem into a more suitable form for a solver, with the level of preconditioning determined by the depth of the quantum circuit. We demonstrate that best-in-class classical heuristics such as simulated annealing and the Burer-Monteiro algorithm can converge more rapidly when given quantum-preconditioned input for various problems, including Sherrington-Kirkpatrick spin glasses, random 3-regular graph maximum-cut problems, and a real-world grid energy problem. Accounting for the additional time taken for preconditioning, the benefit offered by shallow circuits translates into a practical quantum-inspired advantage for random 3-regular graph maximum-cut problems through quantum circuit emulations. We investigate why quantum preconditioning makes the problem easier and test an experimental implementation on a superconducting device. We identify challenges and discuss the prospects for a hardware-based quantum advantage in optimization via quantum preconditioning.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (169)

  1. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity (Courier, North Chelmsford, 1998).
  2. B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms (Springer, Berlin Heidelberg New York, 2012), Vol. 2.
  3. G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. Lü, H. Wang, and Y. Wang, The unconstrained binary quadratic programming problem: A survey, J. Comb. Optim. 28, 58 (2014).
  4. C. H. Papadimitriou, in Encyclopedia of Computer Science (John Wiley and Sons Ltd., GBR, 2003), pp. 260–265.
  5. F. Barahona, On the computational complexity of Ising spin glass models, J. Phys. A Math. Theor. 15, 3241 (1982).
  6. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science 220, 671 (1983).
  7. K. Hukushima and K. Nemoto, Exchange Monte Carlo method and application to spin glass simulations, J. Phys. Soc. Japan 65, 1604 (1996).
  8. S. Burer, R. D. C. Monteiro, and Y. Zhang, Rank-two relaxation heuristics for max-cut and other binary quadratic programs, SIAM J. Optim. 12, 503 (2002).
  9. S. Burer and R. D. C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program. 95, 329 (2003).
  10. M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42, 1115 (1995).
  11. D. P. Williamson and D. B. Shmoys, The design of approximation algorithms (Cambridge University Press, 2011).
  12. I. Dunning, S. Gupta, and J. Silberholz, What works best when? A systematic evaluation of heuristics for max-cut and QUBO, INFORMS J. Comput. 30, 608 (2018).
  13. A. Steane, Quantum computing, Rep. Prog. Phys. 61, 117 (1998).
  14. T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. L. O’Brien, Quantum computers, Nature 464, 45 (2010).
  15. A. Abbas et al., Challenges and opportunities in quantum optimization, Nat. Rev. Phys. 6, 718 (2024).
  16. E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv:quant-ph/0001106.
  17. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science 292, 472 (2001).
  18. A. Das and B. K. Chakrabarti, Colloquium: Quantum annealing and analog quantum computation, Rev. Mod. Phys. 80, 1061 (2008).
  19. P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, Perspectives of quantum annealing: Methods and implementations, Rep. Prog. Phys. 83, 054401 (2020).
  20. T. Albash and D. A. Lidar, Demonstration of a scaling advantage for a quantum annealer over simulated annealing, Phys. Rev. X 8, 031016 (2018).
  21. S. Ebadi et al., Quantum optimization of maximum independent set using Rydberg atom arrays, Science 376, 1209 (2022).
  22. A. D. King et al., Quantum critical dynamics in a 5000-qubit programmable spin glass, Nature 617, 61 (2023).
  23. H. Munoz-Bauza and D. Lidar, Scaling advantage in approximate optimization with quantum annealing, Phys. Rev. Lett. 134, 160601 (2025).
  24. M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nat. Rev. Phys. 3, 625 (2021).
  25. E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028.
  26. K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer, A review on quantum approximate optimization algorithm and its variants, Phys. Rep. 1068, 1 (2024).
  27. E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size, Quantum 6, 759 (2022).
  28. J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, in 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), Leibniz International Proceedings in Informatics (LIPIcs), edited by F. Le Gall and T. Morimae (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022), Vol. 232, pp. 7:1–7:21.
  29. J. Wurtz and P. Love, Maxcut quantum approximate optimization algorithm performance guarantees for p¿1, Phys. Rev. A 103, 042612 (2021).
  30. A. Montanaro and L. Zhou, Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA, arXiv:2411.04979.
  31. R. Shaydulin et al., Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem, Sci. Adv. 10, eadm6761 (2024).
  32. J. A. Montañez-Barrera and K. Michielsen, Toward a linear-ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems, npj Quantum Inf. 11, 131 (2025).
  33. M. B. Hastings, A short path quantum algorithm for exact optimization, Quantum 2, 78 (2018).
  34. A. M. Dalzell, N. Pancotti, E. T. Campbell, and F. G. Brandão, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023 (Association for Computing Machinery, New York, NY, USA, 2023), pp. 1131–1144.
  35. E. Kapit, B. A. Barton, S. Feeney, G. Grattan, P. Patnaik, J. Sagal, L. D. Carr, and V. Oganesyan, On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms, arXiv:2312.06104.
  36. S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, and R. Babbush, Optimization by decoded quantum interferometry, arXiv:2408.08292.
  37. E. Turkel, Preconditioning techniques in computational fluid dynamics, Annu. Rev. Fluid Mech. 31, 385 (1999).
  38. A. J. Wathen, Preconditioning, Acta Numer. 24, 329 (2015).
  39. E. D. Andersen and K. D. Andersen, Presolving in linear programming, Math. Program. 71, 221 (1995).
  40. G. Gamrath, T. Koch, A. Martin, M. Miltenberger, and D. Weninger, Progress in presolving for mixed integer programming, Math. Program. Comput. 7, 367 (2015).
  41. A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014).
  42. D. Sherrington and S. Kirkpatrick, Solvable model of a spin-glass, Phys. Rev. Lett. 35, 1792 (1975).
  43. ARPA-E GridData Program, ACTIVSg500: 500 bus synthetic grid on footprint of South Carolina (2017).
  44. M. Dupont, B. Sundar, B. Evert, D. E. B. Neira, Z. Peng, S. Jeffrey, and M. J. Hodson, Benchmarking quantum optimization for the maximum-cut problem on a superconducting quantum computer, Phys. Rev. Appl. 23, 014045 (2025).
  45. K. Binder and A. P. Young, Spin glasses: Experimental facts, theoretical concepts, and open questions, Rev. Mod. Phys. 58, 801 (1986).
  46. T. Castellani and A. Cavagna, Spin-glass theory for pedestrians, J. Stat. Mech.: Theory Exp. 2005, P05012 (2005).
  47. P. Charbonneau, E. Marinari, M. Mézard, G. Parisi, F. Ricci-Tersenghi, G. Sicuro, and F. Zamponi, Spin Glass Theory and Far Beyond (World Scientific, Singapore, 2023).
  48. M. Dupont and B. Sundar, Extending relax-and-round combinatorial optimization solvers with quantum correlations, Phys. Rev. A 109, 012429 (2024).
  49. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys. 21, 1087 (2004).
  50. W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika 57, 97 (1970).
  51. J. Wurtz and D. Lykov, Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs, Phys. Rev. A 104, 052419 (2021).
  52. M. Dupont, B. Evert, M. J. Hodson, B. Sundar, S. Jeffrey, Y. Yamaguchi, D. Feng, F. B. Maciejewski, S. Hadfield, M. S. Alam, Z. Wang, S. Grabbe, P. A. Lott, E. G. Rieffel, D. Venturelli, and M. J. Reagor, Quantum-enhanced greedy combinatorial optimization solver, Sci. Adv. 9, eadi0487 (2023).
  53. F. B. Maciejewski, S. Hadfield, B. Hall, M. Hodson, M. Dupont, B. Evert, J. Sud, M. S. Alam, Z. Wang, S. Jeffrey, B. Sundar, P. A. Lott, S. Grabbe, E. G. Rieffel, M. J. Reagor, and D. Venturelli, Design and execution of quantum circuits using tens of superconducting qubits and thousands of gates for dense Ising optimization problems, Phys. Rev. Appl. 22, 044074 (2024).
  54. M. P. Harrigan et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys. 17, 332 (2021).
  55. D. Venturelli, S. Mandrà, S. Knysh, B. O’Gorman, R. Biswas, and V. Smelyanskiy, Quantum optimization of fully connected spin glasses, Phys. Rev. X 5, 031040 (2015).
  56. H. Jing, Y. Wang, and Y. Li, Data-driven quantum approximate optimization algorithm for power systems, Comms. Eng. 2, 12 (2023).
  57. H. Jing, Y. Wang, Y. Li, L. Du, and Z. Wu, in 2022 IEEE Transportation Electrification Conference & Expo (ITEC) (IEEE, Detroit, MI, USA, 2022), pp. 574–578.
  58. H. Jing, Y. Wang, Y. Li, L. Du, and Z. Wu, in 2022 IEEE Energy Conversion Congress and Exposition (ECCE) (IEEE, Detroit, MI, USA, 2022), pp. 1–5.
  59. N. Bauer, K. Yeter-Aydeniz, E. Kokkas, and G. Siopsis, Solving power grid optimization problems with Rydberg atoms, arXiv:2404.11440.
  60. K. M. Gegner, A. B. Birchfield, T. Xu, K. S. Shetye, and T. J. Overbye, in 2016 IEEE Power and Energy Conference at Illinois (PECI) (IEEE, Urbana, IL, USA, 2016), pp. 1–6.
  61. A. B. Birchfield, K. M. Gegner, T. Xu, K. S. Shetye, and T. J. Overbye, Statistical considerations in the creation of realistic synthetic power grids for geomagnetic disturbance studies, IEEE Trans. Power Syst. 32, 1502 (2017).
  62. A. B. Birchfield, T. Xu, K. M. Gegner, K. S. Shetye, and T. J. Overbye, Grid structural characteristics as validation criteria for synthetic networks, IEEE Trans. Power Syst. 32, 3258 (2017).
  63. T. Xu, A. B. Birchfield, K. S. Shetye, and T. J. Overbye, in The 10th Bulk Power Systems Dynamics and Control Symposium (IREP 2017) (IEEE, 2017), pp. 1–6.
  64. T. Xu, A. B. Birchfield, K. M. Gegner, K. S. Shetye, and T. J. Overbye, in 50th Hawaii International Conference on System Sciences (HICSS) (IEEE, 2017).
  65. C. G. Broyden, The convergence of a class of double-rank minimization algorithms 1. General considerations, IMA J. Appl. Math. 6, 76 (1970).
  66. R. Fletcher, A new approach to variable metric algorithms, Comput. J. 13, 317 (1970).
  67. D. Goldfarb, A family of variable-metric methods derived by variational means, Math. Comput. 24, 23 (1970).
  68. D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Math. Comput. 24, 647 (1970).
  69. B. O’Gorman, W. J. Huggins, E. G. Rieffel, and K. B. Whaley, Generalized swap networks for near-term quantum computing, arXiv:1905.05118.
  70. P. J. Karalekas, N. A. Tezak, E. C. Peterson, C. A. Ryan, M. P. da Silva, and R. S. Smith, A quantum-classical cloud platform optimized for variational hybrid algorithms, Quantum Sci. Technol. 5, 024003 (2020).
  71. R. Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Ann. Phys. (N. Y.) 349, 117 (2014).
  72. J. I. Cirac, D. Pérez-García, N. Schuch, and F. Verstraete, Matrix product states and projected entangled pair states: Concepts, symmetries, theorems, Rev. Mod. Phys. 93, 045003 (2021).
  73. M. Dupont, N. Didier, M. J. Hodson, J. E. Moore, and M. J. Reagor, Calibrating the classical hardness of the quantum approximate optimization algorithm, PRX Quantum 3, 040339 (2022).
  74. M. Dupont, N. Didier, M. J. Hodson, J. E. Moore, and M. J. Reagor, Entanglement perspective on the quantum approximate optimization algorithm, Phys. Rev. A 106, 022423 (2022).
  75. R. Sreedhar, P. Vikstål, M. Svensson, A. Ask, G. Johansson, and L. García-Álvarez, The quantum approximate optimization algorithm performance with low entanglement and high circuit depth, arXiv:2207.03404.
  76. T. Ayral, T. Louvet, Y. Zhou, C. Lambert, E. M. Stoudenmire, and X. Waintal, Density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity, PRX Quantum 4, 020304 (2023).
  77. J. Weidenfeller, L. C. Valor, J. Gacon, C. Tornow, L. Bello, S. Woerner, and D. J. Egger, Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware, Quantum 6, 870 (2022).
  78. A. Matsuo, S. Yamashita, and D. J. Egger, A SAT approach to the initial mapping problem in swap gate insertion for commuting gates, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E106.A, 1424 (2023).
  79. S. H. Sack and D. J. Egger, Large-scale quantum approximate optimization on nonplanar graphs with machine learning noise mitigation, Phys. Rev. Res. 6, 013223 (2024).
  80. C.-Y. Liu and H.-S. Goan, Hybrid gate-based and annealing quantum computing for large-size Ising problems, arXiv:2208.03283.
  81. T. L. Patti, J. Kossaifi, A. Anandkumar, and S. F. Yelin, Variational quantum optimization with multibasis encodings, Phys. Rev. Res. 4, 033142 (2022).
  82. M. Bechtold, J. Barzen, F. Leymann, A. Mandl, J. Obst, F. Truger, and B. Weder, Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices, Quantum Sci. Technol. 8, 045022 (2023).
  83. M. Ponce, R. Herrman, P. C. Lotshaw, S. Powers, G. Siopsis, T. Humble, and J. Ostrowski, Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms, Quantum Inf. Process. 24, 60 (2025).
  84. A. Angone, X. Liu, R. Shaydulin, and I. Safro, in 2023 IEEE High Performance Extreme Computing Conference (HPEC) (IEEE, 2023), pp. 1–7.
  85. M. Sciorilli, L. Borges, T. L. Patti, D. García-Martín, G. Camilo, A. Anandkumar, and L. Aolita, Towards large-scale quantum optimization solvers with few qubits, Nat. Comm. 16, 476 (2025).
  86. B. Bach, J. Falla, and I. Safro, in 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, Montreal, Quebec, Canada, 2024), Vol. 01, pp. 1–12.
  87. J. Moondra, P. C. Lotshaw, G. Mohler, and S. Gupta, Promise of graph sparsification and decomposition for noise reduction in QAOA: Analysis for trapped-ion compilations, arXiv:2406.14330.
  88. B. Sundar and M. Dupont, Qubit-efficient quantum combinatorial optimization solver, arXiv:2407.15539.
  89. F. B. Maciejewski, B. G. Bach, M. Dupont, P. A. Lott, B. Sundar, D. E. B. Neira, I. Safro, and D. Venturelli, in 2024 IEEE High Performance Extreme Computing Conference (HPEC) (IEEE, 2024), pp. 1–10.
  90. A. Acharya, R. Yalovetzky, P. Minssen, S. Chakrabarti, R. Shaydulin, R. Raymond, Y. Sun, D. Herman, R. S. Andrist, G. Salton, M. J. A. Schuetz, H. G. Katzgraber, and M. Pistoia, Decomposition pipeline for large-scale portfolio optimization with applications to near-term quantum computing, Phys. Rev. Res. 7, 023142 (2025).
  91. L. Bittel and M. Kliesch, Training variational quantum algorithms is NP-hard, Phys. Rev. Lett. 127, 120502 (2021).
  92. M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Biamonte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Barren plateaus in variational quantum computing, Nat. Rev. Phys. 7, 174 (2025).
  93. R. Shaydulin, I. Safro, and J. Larson, in 2019 IEEE High Performance Extreme Computing Conference (HPEC) (IEEE, 2019), pp. 1–8.
  94. L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices, Phys. Rev. X 10, 021067 (2020).
  95. A. Galda, X. Liu, D. Lykov, Y. Alexeev, and I. Safro, in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, 2021), pp. 171–180.
  96. A. Galda, E. Gupta, J. Falla, X. Liu, D. Lykov, Y. Alexeev, and I. Safro, Similarity-based parameter transferability in the quantum approximate optimization algorithm, Front. Quantum Sci. Technol. 2, 1200975 (2023).
  97. T. Lubinski, C. Coffrin, C. McGeoch, P. Sathe, J. Apanavicius, D. Bernal Neira, and Q. E. D. C.-C. Collaboration, Optimization applications as quantum performance benchmarks, ACM Trans. Quantum Comput. 5, 18 (2024).
  98. R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, Parameter transfer for quantum approximate optimization of weighted MaxCut, ACM Trans. Quantum Comput. 4, 1 (2023).
  99. S. H. Sureshbabu, D. Herman, R. Shaydulin, J. Basso, S. Chakrabarti, Y. Sun, and M. Pistoia, Parameter setting in quantum approximate optimization of weighted problems, Quantum 8, 1231 (2024).
  100. Z. He, R. Shaydulin, D. Herman, C. Li, R. Raymond, S. H. Sureshbabu, and M. Pistoia, in Proceedings of the 43rd IEEE/ACM International Conference on Computer-Aided Design, ICCAD ‘24 (Association for Computing Machinery, New York, NY, USA, 2025).
  101. S. Hadfield, Z. Wang, B. O’gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12, 34 (2019).
  102. F. G. Fuchs, K. O. Lye, H. Møll Nilsen, A. J. Stasik, and G. Sartor, Constraint preserving mixers for the quantum approximate optimization algorithm, Algorithms 15, 202 (2022).
  103. A. Glos, A. Krawiec, and Z. Zimborás, Space-efficient binary optimization for variational computing, npj Quantum Inf. 8, 39 (2022).
  104. M. Schnaus, L. Palackal, B. Poggel, X. Runge, H. Ehm, J. M. Lorenz, and C. B. Mendl, in 2024 IEEE International Conference on Quantum Software (QSW) (IEEE, Shenzhen, China, 2024), pp. 81–87.
  105. Z. Tabi, K. H. El-Safty, Z. Kallus, P. Hága, T. Kozsik, A. Glos, and Z. Zimborás, in 2020 IEEE international conference on quantum computing and engineering (QCE), Denver, CO, USA (IEEE, Denver, CO, USA, 2020), pp. 56–62.
  106. F. G. Fuchs, H. Ø. Kolden, N. H. Aase, and G. Sartor, Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA, SN Comput. Sci. 2, 89 (2021).
  107. S. Hadfield, On the representation of boolean and real functions as Hamiltonians for quantum computing, ACM T. Quant. Comput. 2, 1 (2021).
  108. R. Fakhimi, H. Validi, I. V. Hicks, T. Terlaky, and L. F. Zuluaga, Quantum-inspired formulations for the max k-cut problem, ISE Technical Report 21T-007 (2021).
  109. Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien, Quantum error mitigation, Rev. Mod. Phys. 95, 045005 (2023).
  110. Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme, and A. Kandala, Evidence for the utility of quantum computing before fault tolerance, Nature 618, 500 (2023).
  111. J. Robledo-Moreno, M. Motta, H. Haas, A. Javadi-Abhari, P. Jurcevic, W. Kirby, S. Martiel, K. Sharma, S. Sharma, T. Shirakawa, I. Sitdikov, R.-Y. Sun, K. J. Sung, M. Takita, M. C. Tran, S. Yunoki, and A. Mezzacapo, Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer, Sci. Adv. 11, eadu9991 (2025).
  112. J. J. Wallman and J. Emerson, Noise tailoring for scalable quantum computation via randomized compiling, Phys. Rev. A 94, 052325 (2016).
  113. A. Arrasmith, A. Patterson, A. Boughton, and M. Paini, Development and demonstration of an efficient readout error mitigation technique for use in NISQ algorithms, arXiv:2303.17741.
  114. Y. Chen, M. Farahzad, S. Yoo, and T.-C. Wei, Detector tomography on IBM quantum computers and mitigation of an imperfect measurement, Phys. Rev. A 100, 052315 (2019).
  115. F. B. Maciejewski, Z. Zimborás, and M. Oszmaniec, Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography, Quantum 4, 257 (2020).
  116. B. Nachman, M. Urbanek, W. A. de Jong, and C. W. Bauer, Unfolding quantum computer readout noise, npj Quantum Inf. 6, 84 (2020).
  117. M. R. Geller, Conditionally rigorous mitigation of multiqubit measurement errors, Phys. Rev. Lett. 127, 090502 (2021).
  118. K. E. Hamilton, T. Kharazi, T. Morris, A. J. McCaskey, R. S. Bennink, and R. C. Pooser, in 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), Denver, CO, USA (IEEE, Denver, CO, USA, 2020), pp. 430–440.
  119. M. R. Geller and M. Sun, Toward efficient correction of multiqubit measurement errors: Pair correlation method, Quantum Sci. Technol. 6, 025009 (2021).
  120. S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta, Mitigating measurement errors in multiqubit experiments, Phys. Rev. A 103, 042605 (2021).
  121. S. Seo, J. Seong, and J. Bae, Mitigation of crosstalk errors in a quantum measurement and its applications, arXiv:2112.10651.
  122. A. W. R. Smith, K. E. Khosla, C. N. Self, and M. S. Kim, Qubit readout error mitigation with bit-flip averaging, Sci. Adv. 7, eabi8009 (2021).
  123. E. Van Den Berg, Z. K. Minev, and K. Temme, Model-free readout-error mitigation for quantum expectation values, Phys. Rev. A 105, 032620 (2022).
  124. Z. He, D. Amaro, R. Shaydulin, and M. Pistoia, Performance of quantum approximate optimization with quantum error detection, Commun. Phys. 8, 217 (2025).
  125. D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, J. P. Bonilla Ataides, N. Maskara, I. Cong, X. Gao, P. Sales Rodriguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuletić, and M. D. Lukin, Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024).
  126. R. Acharya et al., Quantum error correction below the surface code threshold, Nature 638, 920 (2024).
  127. B. W. Reichardt et al., Logical computation demonstrated with a neutral atom quantum processor, arXiv:2411.11822.
  128. R. C. U. States, Data for “Optimization via quantum preconditioning” (2025), doi:10.5281/zenodo.14921060.
  129. R. Shaydulin and M. Pistoia, in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, 2023), Vol. 01, pp. 1074–1077.
  130. S. A. Moses et al., A race-track trapped-ion quantum processor, Phys. Rev. X 13, 041052 (2023).
  131. M. DeCross, E. Chertkov, M. Kohagen, and M. Foss-Feig, Qubit-reuse compilation with mid-circuit measurement and reset, Phys. Rev. X 13, 041057 (2023).
  132. R. Tate and S. Eidenbenz, Theoretical approximation ratios for warm-started QAOA on 3-regular max-cut instances at depth p=1, arXiv:2402.12631.
  133. N. Sachdeva, G. S. Hartnett, S. Maity, S. Marsh, Y. Wang, A. Winick, R. Dougherty, D. Canuto, Y. Q. Chong, M. Hush, P. S. Mundada, C. D. B. Bentley, M. J. Biercuk, and Y. Baum, Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems, arXiv:2406.01743.
  134. C. C. McGeoch, K. Chern, P. Farré, and A. K. King, A comment on comparing optimization on D-Wave and IBM quantum processors, arXiv:2406.19351.
  135. T. D. Morris, A. Kaushik, M. Roetteler, and P. C. Lotshaw, Performant near-term quantum combinatorial optimization, arXiv:2404.16135.
  136. B. Augustino, M. Cain, E. Farhi, S. Gupta, S. Gutmann, D. Ranard, E. Tang, and K. V. Kirk, Strategies for running the QAOA at hundreds of qubits, arXiv:2410.03015.
  137. D. Zhong, A. Francis, and E. Rrapaj, Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem, arXiv:2411.10737.
  138. P. Berman and M. Karpinski, in Automata, Languages and Programming, edited by J. Wiedermann, P. van Emde Boas, and M. Nielsen (Springer Berlin Heidelberg, Berlin, Heidelberg, 1999), pp. 200–209.
  139. E. Halperin, D. Livnat, and U. Zwick, MAX CUT in cubic graphs, J. Algorithms 53, 169 (2004).
  140. A. A. Hagberg, D. A. Schult, and P. J. Swart, in Proceedings of the 7th Python in Science Conference, edited by G. Varoquaux, T. Vaught, and J. Millman (Pasadena, CA USA, 2008), pp. 11–15.
  141. A. Steger and N. C. Wormald, Generating random regular graphs quickly, Comb. Probab. Comput. 8, 377 (1999).
  142. J. H. Kim and V. H. Vu, in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ‘03 (Association for Computing Machinery, New York, NY, USA, 2003), pp. 213–222.
  143. D. Lykov, J. Wurtz, C. Poole, M. Saffman, T. Noel, and Y. Alexeev, Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm, npj Quantum Inf. 9, 73 (2023).
  144. S. Boettcher and A. G. Percus, Extremal optimization for graph partitioning, Phys. Rev. E 64, 026114 (2001).
  145. E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. Zamponi, Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs, Phys. Rev. A 86, 052334 (2012).
  146. C.-W. Liu, A. Polkovnikov, and A. W. Sandvik, Quantum versus classical annealing: Insights from scaling theory and results for spin glasses on 3-regular graphs, Phys. Rev. Lett. 114, 147203 (2015).
  147. H. Goto, Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network, Sci. Rep. 6, 21686 (2016).
  148. H. Goto, K. Endo, M. Suzuki, Y. Sakai, T. Kanao, Y. Hamakawa, R. Hidaka, M. Yamasaki, and K. Tatsumura, High-performance combinatorial optimization based on classical mechanics, Sci. Adv. 7, eabe7953 (2021).
  149. H. Goto, K. Tatsumura, and A. R. Dixon, Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems, Sci. Adv. 5, eaav2372 (2019).
  150. Q.-G. Zeng, X.-P. Cui, B. Liu, Y. Wang, P. Mosharev, and M.-H. Yung, Performance of quantum annealing inspired algorithms for combinatorial optimization problems, Commun. Phys. 7, 249 (2024).
  151. M. J. A. Schuetz, J. K. Brubaker, and H. G. Katzgraber, Combinatorial optimization with physics-inspired graph neural networks, Nat. Mach. Intell. 4, 367 (2022).
  152. W. Yao, A. S. Bandeira, and S. Villar, in Wavelets and Sparsity XVIII, Vol. 11138, edited by D. V. D. Ville, M. Papadakis, and Y. M. Lu, International Society for Optics and Photonics (SPIE, San Diego, California, USA, 2019), p. 111380S.
  153. M. C. Angelini and F. Ricci-Tersenghi, Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set, Nat. Mach. Intell. 5, 29 (2023).
  154. S. Boettcher, Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems, Nat. Mach. Intell. 5, 24 (2023).
  155. M. J. A. Schuetz, J. K. Brubaker, and H. G. Katzgraber, Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set, Nat. Mach. Intell. 5, 32 (2023).
  156. M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura, and H. G. Katzgraber, Physics-inspired optimization for quadratic unconstrained problems using a digital annealer, Front. Phys. 7, 48 (2019).
  157. A. Montanari, in 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, Baltimore, Maryland, 2019), pp. 1417–1433.
  158. F. B. Maciejewski, J. Biamonte, S. Hadfield, and D. Venturelli, Improving quantum approximate optimization by noise-directed adaptive remapping, arXiv:2404.01412.
  159. M. Mézard and A. Montanari, Information, Physics, and Computation (Oxford University Press, Oxford, England, 2009).
  160. S. Aref, A. J. Mason, and M. C. Wilson, A modeling and computational study of the frustration index in signed networks, Networks 75, 95 (2020).
  161. Y. R. Pei, H. Manukian, and M. D. Ventra, Generating weighted MAX-2-SAT instances with frustrated loops: An RBM Case study, J. Mach. Learn. Res. 21, 1 (2020).
  162. S. F. Edwards and P. W. Anderson, Theory of spin glasses, J. Phys. F: Met. Phys. 5, 965 (1975).
  163. S. F. Edwards and P. W. Anderson, Theory of spin glasses. II, J. Phys. F: Met. Phys. 6, 1927 (1976).
  164. G. Parisi, Order parameter for spin-glasses, Phys. Rev. Lett. 50, 1946 (1983).
  165. E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland, Randomized benchmarking of quantum gates, Phys. Rev. A 77, 012307 (2008).
  166. D-Wave, dwave-samplers (2024).
  167. I. Waldspurger and A. Waters, Rank optimality for the Burer–Monteiro factorization, SIAM J. Optim. 30, 2577 (2020).
  168. N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs, Commun. Pure Appl. Math. 73, 581 (2020).
  169. J. Gray, quimb: A Python library for quantum information and many-body calculations, J. Open Source Softw. 3, 819 (2018).

Outline

Information

Phys. Rev. Applied 24, 044013– Published 3 October, 2025
  • Received 27 March 2025
  • Revised 13 August 2025
  • Accepted 12 September 2025
Crossmark - Check for updates button

© 2025 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation