Quantum optimization algorithms: Difference between revisions

Revision as of 07:31, 30 October 2020

Revision as of 07:14, 3 November 2020

Line 2:

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

[[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 solving problems which are not practically feasible on classical computers, or suggest a considerable speed up with respect to the best known classical algorithm. Among other [[quantum algorithms]], there are '''quantum optimization algorithms''' which might suggest improvement in solving 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>

==Quantum data fitting==

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}}</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|pages=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 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 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 a paper<ref name=":0">{{Cite journal|lastlast1=Akshay|firstfirst1=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|lastlast1=Dalzell|firstfirst1=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 ==