CoChat
Sign Up
Cited by 117Quantum Computing Algorithms and ArchitectureMetaheuristic Optimization Algorithms ResearchQuantum many-body systems

Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems

Open access
Khairy, Sami, Shaydulin, Ruslan, Cincio, Lukasz, Alexeev, Yuri, Balaprakash, Prasanna·2020·Proceedings of the AAAI Conference on Artificial Intelligence
DOI 10.1609/aaai.v34i03.5616
Open this paper in CoChat — free account

Abstract

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits. Our second approach adopts a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on small-sized problem instances that can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Extensive simulations using the IBM Qiskit Aer quantum circuit simulator demonstrate that our proposed RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 when compared with other commonly used off-the-shelf optimizers.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1609/aaai.v34i03.5616

Cites

13 of 13 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The experimental results of machine learning approaches for parameter optimization suggest a high degree of transferability and robustness to noise as well as an increased solution quality.

    “The experimental results suggest a high degree of transferability and robustness to noise as well as an increased solution quality.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [76]

    The Introduction (p. 1) and Results and Discussion (p. 7) support transfer to unseen, larger graph instances and improved solution quality relative to commonly used optimizers. But Results and Discussion (p. 6) says the circuit simulations were noiseless; it does not establish robustness to noise, despite discussing noise from measurement estimates. (LLM, conf=0.87)

    Experimental — accuracy not yet measured

  • Methods to conduct classical parameter optimization of a VQA beyond standard classical optimizers comprise machine learning approaches and sequential minimal optimization.

    “Methods to conduct the classical parameter optimization of a VQA that go beyond the standard classical optimizers (cf. [166]) comprise machine learning approaches [51, 75, 76, 141, 143, 146] and sequential minimal optimization [99].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [76]

  • Gradient-based, derivative-free, and reinforcement learning methods have been investigated for QAOA, and finding a good classical optimizer remains an active field.

    “Gradient-based [130, 131], derivative-free [43, 132], and reinforcement learning [133] methods were investigated, and this still remains an active field to guarantee a good performance for the QAOA.”

    From Variational quantum algorithms (2021) · cites this paper as [132]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 20

  1. [Apolloni, Carvalho, and de Falco 1989] Apolloni, B.; Carvalho, C.; and de Falco, D. 1989. Quantum stochastic optimization. Stochastic Processes and Their Applications 33(2):233-244.
  2. [Barkoutsos et al. 2019] Barkoutsos, P. K.; Nannicini, G.; Robert, A.; Tavernelli, I.; and Woerner, S. 2019. Improving variational quantum optimization using CVaR. arXiv preprint arXiv:1907.04769 . · arXiv
  3. [Brandao et al. 2018] Brandao, F. G.; Broughton, M.; Farhi, E.; Gutmann, S.; and Neven, H. 2018. For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances. arXiv:1812.04170 . · arXiv
  4. [Crooks 2018] Crooks, G. E. 2018. Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv:1811.08419 . · arXiv
  5. [Farhi, Goldstone, and Gutmann 2014] Farhi, E.; Goldstone, J.; and Gutmann, S. 2014. A quantum approximate optimization algorithm. arXiv:1411.4028 . · arXiv
  6. [Hadfield et al. 2017] Hadfield, S.; Wang, Z.; O'Gorman, B.; Rieffel, E. G.; Venturelli, D.; and Biswas, R. 2017. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. arXiv preprint arXiv:1709.03489 . · arXiv
  7. [Huang et al. 2019] Huang, C.; Szegedy, M.; Zhang, F.; Gao, X.; Chen, J.; and Shi, Y. 2019. Alibaba cloud quantum development platform: Applications to quantum algorithm design. arXiv preprint arXiv:1909.02559 . · arXiv
  8. [Hutter, Kotthoff, and Vanschoren 2018] Hutter, F.; Kotthoff, L.; and Vanschoren, J., eds. 2018. Automated Machine Learning: Methods, Systems, Challenges . Springer. available at http://automl.org/book.
  9. [Kato 1950] Kato, T. 1950. On the adiabatic theorem of quantum mechanics. Journal of the Physical Society of Japan 5(6):435-439.
  10. [Khairy et al. 2019] Khairy, S.; Shaydulin, R.; Cincio, L.; Alexeev, Y.; and Balaprakash, P. 2019. Reinforcementlearning-based variational quantum circuits optimization for combinatorial problems. arXiv preprint arXiv:1911.04574 . · arXiv
  11. [LaRose et al. 2019] LaRose, R.; Tikku, A.; ONeel-Judy, ´ E.; Cincio, L.; and Coles, P. J. 2019. Variational quantum state diagonalization. npj Quantum Information 5(1):8.
  12. [Li and Malik 2016] Li, K., and Malik, J. 2016. Learning to optimize. arXiv preprint arXiv:1606.01885 . · arXiv
  13. [Nakanishi, Fujii, and Todo 2019] Nakanishi, K. M.; Fujii, K.; and Todo, S. 2019. Sequential minimal optimization for quantum-classical hybrid algorithms. arXiv:1903.12166 . · arXiv
  14. [Pagano et al. 2019] Pagano, G.; Bapat, A.; Becker, P.; Collins, K.; De, A.; Hess, P.; Kaplan, H.; Kyprianidis, A.; Tan, W.; Baldwin, C.; et al. 2019. Quantum approximate optimization with a trapped-ion quantum simulator. arXiv preprint arXiv:1906.02700 . · arXiv
  15. [Shaydulin, Safro, and Larson 2019] Shaydulin, R.; Safro, I.; and Larson, J. 2019. Multistart methods for quantum approximate optimization. 2019 IEEE High Performance Extreme Computing Conference (HPEC) .
  16. [Streif and Leib 2019] Streif, M., and Leib, M. 2019. Comparison of QAOA with quantum and simulated annealing. arXiv preprint arXiv:1901.01903 . · arXiv
  17. [Sutton and Barto 2018] Sutton, R. S., and Barto, A. G. 2018. Reinforcement learning: An introduction . MIT Press.
  18. [Verdon et al. 2019] Verdon, G.; Broughton, M.; McClean, J. R.; Sung, K. J.; Babbush, R.; Jiang, Z.; Neven, H.; and Mohseni, M. 2019. Learning to learn with quantum neural networks via classical neural networks. arXiv preprint arXiv:1907.05415 . · arXiv
  19. [Wecker, Hastings, and Troyer 2016] Wecker, D.; Hastings, M. B.; and Troyer, M. 2016. Training a quantum optimizer. Physical Review A 94(2):022309.
  20. [Zhou et al. 2018] Zhou, L.; Wang, S.-T.; Choi, S.; Pichler, H.; and Lukin, M. D. 2018. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. arXiv:1812.01041 . · arXiv

Cited by

Sorted by citations

Authors
Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y., & Balaprakash, P.
Affiliations
  • Illinois Institute of Technology (US)
  • Clemson University (US)
  • Los Alamos National Laboratory (US)
  • Argonne National Laboratory (US)
ORCID
Venue
Proceedings of the AAAI Conference on Artificial Intelligence
Publisher
Association for the Advancement of Artificial Intelligence (AAAI)
Published
2020-04-03
Volume
34
Issue
03
Pages
2367-2375
ISSN
  • 2159-5399 (ISSN-L)
  • 2374-3468
DOI
10.1609/aaai.v34i03.5616
OpenAlex
W2990613907
Cited by
117
References
13
Citations by year
2026: 10 · 2025: 21 · 2024: 27 · 2023: 18 · 2022: 17 · 2021: 16 · 2020: 7 · 2019: 1
FWCI
5.53
Type
conference paper
Language
en
Open access
Licence
www.aaai.org/ (unspecified)
Locations
  • Proceedings of the AAAI Conference on Artificial Intelligence (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)) (submittedVersion)
  • OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • U.S. Department of Energy (DE‐ AC02‐06CH11357, Contract No. DE-AC02-06CH11357., AC02‐06CH11357, 06CH11357, No. DE-AC02-06CH11357, DE-AC02-)
  • University of Chicago (DE-AC02-06CH11357)
  • Office of Science (Contract No. DE-AC02-06CH11357, AC02‐06CH11357, DE-AC02, No. DE-AC02-06CH11357., 06CH11357, DE-AC02-06CH11357)
  • Advanced Scientific Computing Research (DE-AC02-06CH11357)
  • Laboratory Directed Research and Development (No. DE-AC02-06CH11357, DE‐AC02‐06CH11357)
  • Argonne National Laboratory (DE- AC02-06-CH11357, DE-AC02, AC02–06CH11357, Contract DE-AC02-06CH11357, No. DE-AC02-06CH11357, 06CH11357, Contract No. DE-AC02-06CH11357.)
  • Los Alamos National Laboratory (DE-AC02-06CH11357)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum approximate optimization algorithm, variational quantum circuits, combinatorial optimization, reinforcement learning, kernel density estimation, generative models, variational parameter optimization, hybrid quantum-classical algorithms, quantum advantage, policy networks

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review