Quantum optimization algorithms: Difference between revisions

Revision as of 21:17, 19 June 2025

Latest revision as of 06:52, 27 August 2025

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 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 journal |lastlast1=Vijendran |firstfirst1=V |last2=Das |first2=Aritra |last3=Koh |first3=Dax Enshan |last4=Assad |first4=Syed M |last5=Lam |first5=Ping Koy |date=2024-04-01 |title=An expressive ansatz for low-depth quantum approximate optimisation |url=https://iopscience.iop.org/article/10.1088/2058-9565/ad200a |journal=Quantum Science and Technology |volume=9 |issue=2 |pages=025010 |doi=10.1088/2058-9565/ad200a |issn=2058-9565|arxiv=2302.04479 |bibcode=2024QS&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) |chapter-url=https://ieeexplore.ieee.org/document/9951267 |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.