Quantum optimization algorithms: Difference between revisions

Revision as of 15:50, 29 November 2020

Revision as of 20:22, 4 December 2020

Line 87:

In a paper<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]].

== See also ==