nach oben

4OR

Erschienen in:

31.07.2023 | Invited Survey

An introduction to variational quantum algorithms for combinatorial optimization problems

verfasst von: Camille Grange, Michael Poss, Eric Bourreau

Erschienen in: 4OR | Ausgabe 3/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Noisy intermediate-scale quantum computers (NISQ computers) are now readily available, motivating many researchers to experiment with Variational Quantum Algorithms (VQAs). Among them, the Quantum Approximate Optimization Algorithm (QAOA) is one of the most popular one studied by the combinatorial optimization community. In this tutorial, we provide a mathematical description of the class of Variational Quantum Algorithms, assuming no previous knowledge of quantum physics from the readers. We introduce precisely the key aspects of these hybrid algorithms on the quantum side (parametrized quantum circuit) and the classical side (guiding function, optimizer). We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions. Finally, we discuss the recent literature on QAOA, highlighting several research trends.

Nächster Artikel Integer knapsack problems with profit functions of the same value range

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Two quantum states \(\vert \psi \rangle \) and \(\vert \psi '\rangle = e^{i\alpha }\vert \psi \rangle \), with \(\alpha \in [0,2\pi [\), that only differ by a global phase are indiscernible by measurement. Thus, we do not consider global phase of quantum states nor quantum gates.

A complex square matrix is Hermitian if it is equal to its conjugate transpose.

For \(t\in \{k\pi : k\in \mathbb {Z}\},\,R_{Z,j}(2t) = I\). Thus, \(CX_{i,j} R_{Z,j}(2t)CX_{i,j} = CX_{i,j}CX_{i,j} = I\) because CNOT is its own inverse.

Notice that here we talk about the general depth, not p, which is the longest path in the circuit, namely the maximum number of gates executed on a qubit.

Amaro D, Modica C, Rosenkranz M, Fiorentini M, Benedetti M, Lubasch M (2022) Filtering variational quantum algorithms for combinatorial optimization. Quantum Sci Technol 7(1):015021CrossRef

Ambainis A, Balodis K, Iraids J, Kokainis M, Prūsis K, Vihrovs J (2019) Quantum speedups for exponential-time dynamic programming algorithms. In: Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms, pp 1783–1793. SIAM

Barkoutsos PK, Nannicini G, Robert A, Tavernelli I, Woerner S (2020) Improving variational quantum optimization using CVaR. Quantum 4:256CrossRef

Bravyi S, Kliesch A, Koenig R, Tang E (2020) Obstacles to variational quantum optimization from symmetry protection. Phys Rev Lett 125(26):260505CrossRef

Bravyi S, Kliesch A, Koenig R, Tang E (2022) Hybrid quantum-classical algorithms for approximate graph coloring. Quantum 6:678CrossRef

Cerezo M, Arrasmith A, Babbush R, Benjamin SC, Endo S, Fujii K, McClean JR, Mitarai K, Yuan X, Cincio L et al (2021) Variational quantum algorithms. Nat Rev Phys 3(9):625–644CrossRef

Crooks GE (2018) Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419

De Palma G, Marvian M, Rouzé C, França DS (2023) Limitations of variational quantum algorithms: a quantum optimal transport approach. PRX Quantum 4(1):010309CrossRef

Egger DJ, Marecek J, Woerner S (2021) Warm-starting quantum optimization. Quantum 5:479CrossRef

Farhi E, Gamarnik D, Gutmann S (2020) The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv preprint arXiv:2004.09002

Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028

Farhi E, Goldstone J, Gutmann S, Sipser M (2000) Quantum computation by adiabatic evolution. arXiv preprint arXiv:quant-ph/0001106

Farhi E, Harrow AW (2016) Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674

Fortran I, Press W, Teukolsky S, Vetterling W, Flannery B (1992) Numerical recipes. Cambridge, UK, Cambridge University Press

Glover F, Kochenberger G, Du Y (2019) Quantum bridge analytics I: a tutorial on formulating and using QUBO models. 4OR, 17:335–371

Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM (JACM) 42(6):1115–1145CrossRef

Grover LK (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp 212–219

Guerreschi GG, Matsuura AY (2019) QAOA for max-cut requires hundreds of qubits for quantum speed-up. Sci Rep 9(1):1–7CrossRef

Hadfield S, Wang Z, O’gorman B, Rieffel EG, Venturelli D, Biswas R (2019) From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12(2):34CrossRef

Hastings MB (2019) Classical and quantum bounded depth approximation algorithms. arXiv preprint arXiv:1905.07047

Hellemo L, Barton PI, Tomasgard A (2018) Decision-dependent probabilities in stochastic programs with recourse. CMS 15(3):369–395CrossRef

Herrman R, Treffert L, Ostrowski J, Lotshaw PC, Humble TS, Siopsis G (2021) Globally optimizing QAOA circuit depth for constrained optimization problems. Algorithms 14(10):294CrossRef

Holmes Z, Sharma K, Cerezo M, Coles PJ (2022) Connecting ansatz expressibility to gradient magnitudes and barren plateaus. PRX Quantum 3(1):010313CrossRef

Kerenidis I, Prakash A (2020) A quantum interior point method for LPs and SDPs. ACM Trans Quantum Comput 1(1):1–32CrossRef

Kerenidis I, Prakash A, Szilágyi D (2021) Quantum algorithms for second-order cone programming and support vector machines. Quantum 5:427CrossRef

Khumalo MT, Chieza HA, Prag K, Woolway M (2022) An investigation of IBM quantum computing device performance on combinatorial optimisation problems. Neural Comput Appl. https://doi.org/10.1007/s00521-022-07438-4CrossRef

Kingma DP, Ba J (2014) Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980

Kitaev AY (1995) Quantum measurements and the Abelian stabilizer problem. arXiv preprint arXiv:quant-ph/9511026

Kurowski K, Pecyna T, Slysz M, Różycki R, Waligóra G, Weglarz J (2023) Application of quantum approximate optimization algorithm to job shop scheduling problem. European J Operat Res 310(2):518–28CrossRef

Lao L, Manzano D, van Someren H, Ashraf I, Almudever CG (2019) Mapping of quantum circuits onto NISQ superconducting processors. Quantum Physics. arXiv:1908.04226

Li L, Fan M, Coram M, Riley P, Leichenauer S et al (2020) Quantum optimization with a novel Gibbs objective function and ansatz architecture search. Phys Rev Res 2(2):023074CrossRef

Lotshaw PC, Humble TS, Herrman R, Ostrowski J, Siopsis G (2021) Empirical performance bounds for quantum approximate optimization. Quantum Inf Process 20(12):1–32CrossRef

Lucas A (2014) Ising formulations of many NP problems. Front Phys, 5

Marwaha K, Hadfield S (2022) Bounds on approximating Max \(k\)XOR with quantum and classical local algorithms. Quantum 6:757CrossRef

McClean JR, Boixo S, Smelyanskiy VN, Babbush R, Neven H (2018) Barren plateaus in quantum neural network training landscapes. Nat Commun 9(1):1–6CrossRef

Mosseri R, Dandoloff R (2001) Geometry of entangled states, Bloch spheres and Hopf fibrations. J Phys A Math Gen 34(47):10243CrossRef

Nagarajan H, Lockwood O, Coffrin C (2021) QuantumCircuitOpt: an open-source framework for provably optimal quantum circuit design. In: 2021 IEEE/ACM second international workshop on quantum computing software (QCS), pp 55–63. IEEE

Nannicini G (2019) Performance of hybrid quantum-classical variational heuristics for combinatorial optimization. Phys Rev E 99(1):013304CrossRef

Nannicini G (2021) Fast Quantum Subroutines for the Simplex Method. In: Singh M, Williamson DP (eds) Integer programming and combinatorial optimization–22nd international conference, IPCO 2021, Atlanta, GA, USA, proceedings, vol 12707 of Lecture Notes in Computer Science, pp 311–325. Springer

Nelder JA, Mead R (1965) A simplex method for function minimization. Comput J 7(4):308–313CrossRef

Nielsen MA, Chuang I (2002) Quantum computation and quantum information

Nüßlein J, Gabor T, Linnhoff-Popien C, Feld S (2022) Algorithmic QUBO formulations for k-SAT and hamiltonian cycles. In: Proceedings of the genetic and evolutionary computation conference companion, pp 2240–2246

Oh YH, Mohammadbagherpoor H, Dreher P, Singh A, Yu X, Rindos AJ (2019) Solving multi-coloring combinatorial optimization problems using hybrid quantum algorithms. arXiv preprint arXiv:1911.00595

Peruzzo A, McClean J, Shadbolt P, Yung M-H, Zhou X-Q, Love PJ, Aspuru-Guzik A, O’brien JL (2014) A variational eigenvalue solver on a photonic quantum processor. Nat Commun 5(1):1–7CrossRef

Powell MJ (1994) A direct search optimization method that models the objective and constraint functions by linear interpolation. Springer, NetherlandsCrossRef

Preskill J (2018) Quantum computing in the NISQ era and beyond. Quantum 2:79CrossRef

Radzihovsky M, Murphy J, Mason S (2019) A QAOA solution to the traveling salesman problem using pyQuil

Ruan Y, Marsh S, Xue X, Liu Z, Wang J et al (2020) The quantum approximate algorithm for solving traveling salesman problem. Comput Mater Continua 63(3):1237–1247CrossRef

Ruder S (2016) An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747

Shapiro A (2003) Monte Carlo sampling methods. Handbooks Oper Res Manag Sci 10:353–425CrossRef

Shor PW (1994) Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th annual symposium on foundations of computer science, pp 124–134. IEEE

Soloviev VP, Larrañaga P, Bielza C (2022) Quantum parametric circuit optimization with estimation of distribution algorithms. In: Proceedings of the genetic and evolutionary computation conference companion, pp 2247–2250

Spall JC (1992) Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans Autom Control 37(3):332–341CrossRef

Tabi Z, El-Safty KH, Kallus Z, Hága P, Kozsik T, Glos A, Zimborás Z (2020) Quantum optimization for the graph coloring problem with space-efficient embedding. In: 2020 IEEE international conference on quantum computing and engineering (QCE), pp 56–62. IEEE

Wang Z, Hadfield S, Jiang Z, Rieffel EG (2018) Quantum approximate optimization algorithm for MaxCut: a fermionic view. Phys Rev A 97(2):022304CrossRef

Wurtz J, Love PJ (2022) Counterdiabaticity and the quantum approximate optimization algorithm. Quantum 6:635CrossRef

Yang Z-C, Rahmani A, Shabani A, Neven H, Chamon C (2017) Optimizing variational quantum algorithms using Pontryagin’s minimum principle. Phys Rev X 7(2):021027

Zhou L, Wang S-T, Choi S, Pichler H, Lukin MD (2020) Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Phys Rev X 10(2):021067

Zhu L, Tang HL, Barron GS, Calderon-Vargas F, Mayhall NJ, Barnes E, Economou SE (2022) Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. Phys Rev Res 4(3):033029CrossRef

Titel: An introduction to variational quantum algorithms for combinatorial optimization problems
verfasst von: Camille Grange
Michael Poss
Eric Bourreau
Publikationsdatum: 31.07.2023
Verlag: Springer Berlin Heidelberg
Erschienen in: 4OR / Ausgabe 3/2023
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI: https://doi.org/10.1007/s10288-023-00549-1

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2023

Lexicographic optimization for the multi-container loading problem with open dimensions for a shoe manufacturer

Critical node/edge detection problems on trees

A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work

A note on batch scheduling on a two-machine flowshop with machine-dependent processing times

Approximating the chance-constrained capacitated vehicle routing problem with robust optimization

A bilevel optimization model for the newsvendor problem with the focus theory of choice

Premium Partner

Marktübersichten