Quantum optimization algorithms: Difference between revisions

Revision as of 14:33, 24 May 2021

Revision as of 14:43, 24 May 2021

Line 86:

The heart of the 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 paperstrong dependence on the ratio of a problems [[Constraint (mathematics)|constraint]] to [[Variable (mathematics)|variables]] (problem density) placing a limiting restriction on the algorithms 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}}</ref> published in [[Physical Review Letters]] on March 5, 2020 (pre-print<ref name=":0" /> submitted on 26 Jun 2019 to [[arXiv]]), the authors report that QAOA exhibits a strong dependence on the ratio of a problems [[Constraint (mathematics)|constraint]] to [[Variable (mathematics)|variables]] (problem density) placing a limiting restriction on the algorithms capacity to minimize a corresponding [[Loss function|objective function]].

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]].