Quantum optimization algorithms: Difference between revisions

Revision as of 20:22, 4 December 2020

Revision as of 16:33, 14 January 2021

Line 2:

{{Short description|Optimization algorithms using quantum computing}}

'''Quantum optimization algorithms''' are [[quantum algorithms]] that are used to solve optimization problems.<ref>{{cite journal|last1=Moll|first1=Nikolaj|last2=Barkoutsos|first2=Panagiotis|last3=Bishop|first3=Lev S.|last4=Chow|first4=Jerry M.|last5=Cross|first5=Andrew|last6=Egger|first6=Daniel J.|last7=Filipp|first7=Stefan|last8=Fuhrer|first8=Andreas|last9=Gambetta|first9=Jay M.|last10=Ganzhorn|first10=Marc|last11=Kandala|first11=Abhinav|last12=Mezzacapo|first12=Antonio|last13=Müller|first13=Peter|last14=Riess|first14=Walter|last15=Salis|first15=Gian|last16=Smolin|first16=John|last17=Tavernelli|first17=Ivano|last18=Temme|first18=Kristan|title=Quantum optimization using variational algorithms on near-term quantum devices|journal=Quantum Science and Technology|date=2018|volume=3|issue=3|pages= 030503|doi=10.1088/2058-9565/aab822|arxiv=1710.01022|bibcode=2018QS&T....3c0503M|s2cid=56376912}}</ref> [[Mathematical optimization]] deals with finding the best solution to a problem (according to some criteria) from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as [[mechanics]], [[economics]] and [[engineering]], and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. The power of [[quantum computing]] may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

==Quantum data fitting==

[[curve fitting|Data fitting]] is a process of constructing a [[mathematical function]] that best fits a set of data points. The fit's quality is measured by some criteria, usually the distance between the function and the data points.

Line 53 ⟶ 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}}</ref>.

===The quantum algorithm===

Line 87 ⟶ 88:

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 ==