Quantum optimization algorithms: Difference between revisions

Revision as of 23:49, 28 January 2022

Revision as of 16:02, 30 January 2022

Line 59:

The algorithm inputs are <math> A_1 ... A_m, C , b_1 ... b_m</math> and parameters regarding the solution's [[Trace class|trace]], precision and optimal value (the objective function's value at the optimal point).

The quantum algorithm<ref>{{cite arxivarXiv|last1=Brandao|first1=Fernando G. S. L.|last2=Svore|first2=Krysta|author2-link= Krysta Svore |title=Quantum Speed-ups for Semidefinite Programming|eprint=1609.05537|class=quant-ph|year=2016}}</ref> consists of several iterations. In each iteration, it solves a [[Mathematical optimization#Feasibility problem|feasibility problem]], namely, finds any solution satisfying the following conditions (giving a threshold <math>t</math>):

:<math>

Line 82:

===Quantum approximate optimization algorithm===

For combinatorial optimization, the '''quantum approximate optimization algorithm''' (QAOA)<ref>{{cite arxivarXiv|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> briefly had a better approximation ratio than any known [[polynomial time]] classical algorithm (for a certain problem),<ref>{{cite arxivarXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem|eprint=1412.6062|class=quant-ph|year=2014}}</ref> until a more effective classical algorithm was proposed.<ref>{{cite arxivarXiv|last1=Barak|first1=Boaz|last2=Moitra|first2=Ankur|last3=O'Donnell|first3=Ryan|last4=Raghavendra|first4=Prasad|last5=Regev|first5=Oded|last6=Steurer|first6=David|last7=Trevisan|first7=Luca|last8=Vijayaraghavan|first8=Aravindan|last9=Witmer|first9=David|last10=Wright|first10=John|title=Beating the random assignment on constraint satisfaction problems of bounded degree|eprint=1505.03424|class=cs.CC|year=2015}}</ref> The relative speed-up of the quantum algorithm is an open research question.

The heart of QAOA relies on the use of [[unitary operators]] dependent on <math> 2p </math> [[angle]]s, where <math> p>1 </math> is an input integer. 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 <math> C(z) </math> is calculated. After a sufficient number of repetitions, the value of <math> C(z) </math> is almost optimal, and the state being measured is close to being optimal as well.

In 2020, 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?|url=http://arxiv.org/abs/1805.05224|journal=Quantum|volume=4|pages=264|doi=10.22331/q-2020-05-11-264|arxiv=1805.05224|issn=2521-327X|doi-access=free}}</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 sufficient for [[Quantum supremacy|quantum computational supremacy]].

== See also ==