Quantum optimization algorithms: Difference between revisions

Revision as of 19:00, 15 August 2024

Latest revision as of 06:52, 27 August 2025

(9 intermediate revisions by 6 users not shown)

Line 35:

The quantum least-squares fitting algorithm<ref>{{cite journal|last1=Wiebe|first1=Nathan|last2=Braun|first2=Daniel|last3=Lloyd|first3=Seth|title=Quantum Algorithm for Data Fitting|journal=Physical Review Letters|date=2 August 2012|volume=109|issue=5|pages=050505|arxiv=1204.5242|doi=10.1103/PhysRevLett.109.050505|pmid=23006156|bibcode=2012PhRvL.109e0505W|s2cid=118439810 }}</ref> makes use of a version of Harrow, Hassidim, and Lloyd's [[quantum algorithm for linear systems of equations]] (HHL), and outputs the coefficients <math> \lambda_j </math> and the fit quality estimation <math> E </math>. It consists of three subroutines: an algorithm for performing a pseudo-[[matrix inversion|inverse]] operation, one routine for the fit quality estimation, and an algorithm for learning the fit parameters.

Because the quantum algorithm is mainly based on the HHL algorithm, it suggests an exponential improvement<ref>{{cite journal|last1=Montanaro|first1=Ashley|title=Quantum algorithms: an overview|journal=[[npj Quantum Information]] |date=12 January 2016|volume=2|pagesissue=1 |article-number=15023|arxiv=1511.04206|doi=10.1038/npjqi.2015.23|bibcode=2016npjQI...215023M|s2cid=2992738}}</ref> in the case where <math> F</math> is [[sparse matrix|sparse]] and the [[condition number]] (namely, the ratio between the largest and the smallest [[eigenvalues]]) of both <math> F F^\dagger </math> and <math> F^\dagger F </math> is small.

==Quantum semidefinite programming==

Line 54:

</math>

The best classical algorithm is not known to unconditionally run in [[polynomial time]]. The corresponding feasibility problem is known to either lie outside of the union of the complexity classes NP and co-NP, or in the intersection of NP and co-NP.<ref>{{Cite journal|url=https://doi.org/10.1007/BF02614433|doi = 10.1007/BF02614433|title = An exact duality theory for semidefinite programming and its complexity implications|year = 1997|last1 = Ramana|first1 = Motakuri V.|journal = Mathematical Programming|volume = 77|pages = 129–162|s2cid = 12886462|url-access = subscription}}</ref>

===The quantum algorithm===

Line 74:

==Quantum combinatorial optimization==

The [[combinatorial optimization]] problem is aimed at finding an optimal object from a [[finite set]] of objects. The problem can be phrased as a maximization of an [[objective function]] which is a sum of [[booleanBoolean function]]s. Each booleanBoolean function <math>\,C_\alpha \colon \lbrace {0,1 \rbrace}^n \rightarrow \lbrace {0,1} \rbrace </math> gets as input the <math>n</math>-bit string <math>z = z_1 z_2 \ldots z_n</math> and gives as output one bit (0 or 1). The combinatorial optimization problem of <math>n</math> bits and <math>m</math> clauses is finding an <math>n</math>-bit string <math>z</math> that maximizes the function

:<math>

C(z) = \sum_{\alpha=1}^m C_\alpha(z)

Line 93:

# Using classical methods to optimize the parameters <math>\boldsymbol\gamma, \boldsymbol\alpha</math> and measure the output state of the optimized circuit to obtain the approximate optimal solution to the cost Hamiltonian. An optimal solution will be one that maximizes the expectation value of the cost Hamiltonian <math>H_C</math>.

[[File:QAOAcircuit.png|thumb|457x457px|Sample QAOA ansatz for a three qubit circuit]]

The layout of the algorithm, viz, the use of cost and mixer Hamiltonians are inspired from the [[Quantum Adiabatic Theorem|Quantum Adiabatic theorem]], which states that starting in a ground state of a time-dependent Hamiltonian, if the Hamiltonian evolves slowly enough, the final state will be a ground state of the final Hamiltonian. Moreover, the adiabatic theorem can be generalized to any other eigenstate as long as there is no overlap (degeneracy) between different eigenstates across the evolution. Identifying the initial Hamiltonian with <math>H_M</math> and the final Hamiltonian with <math>H_C</math>, whose ground states encode the solution to the optimization problem of interest, one can approximate the optimization problem as the adiabatic evolution of the Hamiltonian from an initial to the final one, whose ground (eigen) statedstate gives the optimal solutiondsolution. In general, QAOA relies on the use of [[unitary operators]] dependent on <math> 2p </math> [[angle]]s (parameters), where <math> p>1 </math> is an input integer, which can be identified the number of layers of the oracle <math>U(\boldsymbol\gamma, \boldsymbol\alpha)</math>. These operators are iteratively applied on a state that is an equal-weighted [[quantum superposition]] of all the possible states in the computational basis. In each iteration, the state is measured in the computational basis and the booleanBoolean function <math> C(z) </math> is estimated. The angles are then updated classically to increase <math> C(z) </math>. After this procedure is repeated a sufficient number of times, the value of <math> C(z) </math> is almost optimal, and the state being measured is close to being optimal as well. A sample circuit that implements QAOA on a quantum computer is given in figure. This procedure is highlighted using the following example of finding the [[minimum vertex cover]] of a graph.<ref>{{Cite journal |last=Ceroni |first=Jack |date=2020-11-18 |title=Intro to QAOA |url=https://pennylane.aiundefinedai/qml/demos/tutorial_qaoa_intro |journal=PennyLane Demos |language=en}}</ref>

=== QAOA for finding the minimum vertex cover of a graph ===

Line 108:

=== Generalization of QAOA to constrained combinatorial optimisation ===

In principle the optimal value of <math> C(z) </math> can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm|eprint=1411.4028|class=quant-ph|year=2014}}</ref><ref>{{Cite journal|last1=Binkowski|first1=Lennart |last2=Koßmann|first2=Gereon |last3=Ziegler|first3=Timo |last4=Schwonnek|first4=René |year=2024|title=Elementary proof of QAOA convergence|journal=New Journal of Physics|volume=26|issue=7|pages=073001|doi=10.1088/1367-2630/ad59bb|arxiv=2302.04968 |bibcode=2024NJPh...26g3001B }}</ref> or alternatively by the universality of the QAOA unitaries.<ref>{{Cite journal|last1=Morales|first1=M. E. |last2=Biamonte|first2=J. D.|last3=Zimborás|first3=Z. |date=2019-09-20|title=On the universality of the quantum approximate optimization algorithm|journal=Quantum Information Processing|volume=19|issue=9 |pages=291|doi=10.1007/s11128-020-02748-9|arxiv=1909.03123 }}</ref> However, it is an open question whether this can be done in a feasible way.

For example, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's [[Constraint (mathematics)|constraint]] to [[Variable (mathematics)|variables]] (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding [[Loss function|objective function]].<ref name=":0">{{Cite journal|last1=Akshay|first1=V.|last2=Philathong|first2=H.|last3=Morales|first3=M. E. S.|last4=Biamonte|first4=J. D.|date=2020-03-05|title=Reachability Deficits in Quantum Approximate Optimization|journal=Physical Review Letters|volume=124|issue=9|pages=090504|doi=10.1103/PhysRevLett.124.090504|pmid=32202873|arxiv=1906.11259|bibcode=2020PhRvL.124i0504A|s2cid=195699685}}</ref>

It was soon recognized that a generalization of the QAOA process is essentially an alternating application of a continuous-time quantum walk on an underlying graph followed by a quality-dependent phase shift applied to each solution state. This generalized QAOA was termed as QWOA (Quantum Walk-based Optimisation Algorithm).<ref>{{Cite journal|last1=Marsh|first1=S.|last2=Wang|first2=J. B.|date=2020-06-08|title=Combinatorial optimization via highly efficient quantum walks|journal=Physical Review Research|volume=2|issue=2|pages=023302|doi=10.1103/PhysRevResearch.2.023302|arxiv=1912.07353 |bibcode=2020PhRvR...2b3302M|s2cid=216080740}}</ref>

In the paper ''How many qubits are needed for quantum computational supremacy'' submitted to arXiv,<ref>{{Cite journal|last1=Dalzell|first1=Alexander M.|last2=Harrow|first2=Aram W.|last3=Koh|first3=Dax Enshan|last4=La Placa|first4=Rolando L.|date=2020-05-11|title=How many qubits are needed for quantum computational supremacy?|journal=Quantum|volume=4|pagesarticle-number=264|doi=10.22331/q-2020-05-11-264|arxiv=1805.05224|issn=2521-327X|doi-access=free|bibcode=2020Quant...4..264D }}</ref> the authors conclude that a QAOA circuit with 420 [[qubits]] and 500 [[Constraint (mathematics)|constraints]] would require at least one century to be simulated using a classical simulation algorithm running on [[State of the art|state-of-the-art]] [[supercomputers]] so that would be [[Necessity and sufficiency#Sufficiency|sufficient]] for [[Quantum supremacy|quantum computational supremacy]].

A rigorous comparison of QAOA with classical algorithms can give estimates on depth <math> p </math> and number of qubits required for quantum advantage. A study of QAOA and [[Maximum cut|MaxCut]] algorithm shows that <math>p>11</math> is required for scalable advantage.<ref name="Lykov Wurtz Poole Saffman p. ">{{cite journal | last1=Lykov | first1=Danylo | last2=Wurtz | first2=Jonathan | last3=Poole | first3=Cody | last4=Saffman | first4=Mark | last5=Noel | first5=Tom | last6=Alexeev | first6=Yuri | title=Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm | journal=npj Quantum Information | year=2023 | volume=9 | pageissue=1 | article-number=73 | doi=10.1038/s41534-023-00718-4 | arxiv=2206.03579 | bibcode=2023npjQI...9...73L }}</ref>

=== Variations of QAOA ===

Line 121:

# Multi-angle QAOA<ref>{{Cite journal |last1=Herrman |first1=Rebekah |last2=Lotshaw |first2=Phillip C. |last3=Ostrowski |first3=James |last4=Humble |first4=Travis S. |last5=Siopsis |first5=George |date=2022-04-26 |title=Multi-angle quantum approximate optimization algorithm |journal=Scientific Reports |language=en |volume=12 |issue=1 |page=6781 |doi=10.1038/s41598-022-10555-8 |issn=2045-2322 |pmc=9043219 |pmid=35474081|arxiv=2109.11455 |bibcode=2022NatSR..12.6781H }}</ref>

# Expressive QAOA+ (XQAOA)<ref>{{Cite bookjournal |last1=ChalupnikVijendran |first1=MichelleV |last2=MeloDas |first2=HansAritra |last3=AlexeevKoh |first3=YuriDax Enshan |last4=GaldaAssad |first4=AlexeySyed M |chapterlast5=AugmentingLam QAOA|first5=Ping Ansatz with Multiparameter Problem-Independent LayerKoy |date=September 20222024-04-01 |title=2022An IEEEexpressive Internationalansatz Conferencefor onlow-depth Quantumquantum Computingapproximate and Engineering (QCE)optimisation |chapter-url=https://ieeexploreiopscience.ieeeiop.org/documentarticle/995126710.1088/2058-9565/ad200a |journal=Quantum Science and Technology |volume=9 |publisherissue=IEEE2 |pages=97–103025010 |doi=10.11091088/QCE53715.2022.000282058-9565/ad200a |issn=2058-9565|arxiv=22052302.0119204479 |isbnbibcode=978-1-6654-9113-62024QS&T....9b5010V }}</ref>

# QAOA+<ref>{{Cite book |last1=Chalupnik |first1=Michelle |last2=Melo |first2=Hans |last3=Alexeev |first3=Yuri |last4=Galda |first4=Alexey |chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer |date=September 2022 |title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) |publisher=IEEE |pages=97–103 |doi=10.1109/QCE53715.2022.00028 |arxiv=2205.01192 |isbn=978-1-6654-9113-6}}</ref>

# Digitised counteradiabatic QAOA<ref>{{Cite journal |last1=Chandarana |first1=P. |last2=Hegade |first2=N. N. |last3=Paul |first3=K. |last4=Albarrán-Arriagada |first4=F. |last5=Solano |first5=E. |last6=del Campo |first6=A. |last7=Chen |first7=Xi |date=2022-02-22 |title=Digitized-counterdiabatic quantum approximate optimization algorithm |url=https://link.aps.org/doi/10.1103/PhysRevResearch.4.013141 |journal=Physical Review Research |language=en |volume=4 |issue=1 |page=013141 |doi=10.1103/PhysRevResearch.4.013141 |arxiv=2107.02789 |bibcode=2022PhRvR...4a3141C |issn=2643-1564}}</ref>

# Quantum alternating operator ansatz<ref>{{Cite journal |last1=Hadfield |first1=Stuart |last2=Wang |first2=Zhihui |last3=O'Gorman |first3=Bryan |last4=Rieffel |first4=Eleanor |last5=Venturelli |first5=Davide |last6=Biswas |first6=Rupak |date=2019-02-12 |title=From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz |journal=Algorithms |language=en |volume=12 |issue=2 |pages=34 |doi=10.3390/a12020034 |doi-access=free |issn=1999-4893|arxiv=1709.03489 }}</ref>,which allows for constrains on the optimization problem etc.

Line 128 ⟶ 129:

Finally, there has been significant research interest in leveraging specific hardware to enhance the performance of QAOA across various platforms, such as trapped ion, neutral atoms, superconducting qubits, and photonic quantum computers. The goals of these approaches include overcoming hardware connectivity limitations and mitigating noise-related issues to broaden the applicability of QAOA to a wide range of combinatorial optimization problems.

==QAOA algorithm Qiskit implementation==

[[File:QAOA quantum circuit.png|thumb|QAOA quantum circuit]]

The quantum circuit shown here is from a simple example of how the QAOA algorithm can be implemented in Python<ref>{{cite web |url=https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm |title=Solve utility-scale quantum optimization problems |access-date=2025-02-24}}</ref> using [[Qiskit]], an open-source quantum computing software development framework by IBM.

== See also ==

*[[Adiabatic quantum computation]]

*[[Quantum annealing]]

{{clear}}

== References ==

{{reflist}}

==External links==

* [https://short.classiq.io/qaoa_knapsack Implementation of the QAOA algorithm for the knapsack problem with Classiq]