Quantum optimization algorithms: Difference between revisions

Revision as of 01:28, 3 November 2022

Revision as of 00:58, 12 November 2022

Line 1:

{{Use American English|date=January 2019}}

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

{{Use American English|date=January 2019}}

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

Line 92:

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?|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 [[Necessity and sufficiency#Sufficiency|sufficient]] for [[Quantum supremacy|quantum computational supremacy]].

A rigorous comparison of QAOA with classical algorithms can give estimates on depth <math> p </math> and number of qubits required for quantum advantage. A study of QAOA and [[Maximum_cutMaximum cut|MaxCut]] algorithm shows that <math>p>11</math> is required for scalable advantage. <ref name="Lykov Wurtz Poole Saffman p. ">{{cite journalarxiv | last=Lykov | first=Danylo | last2=Wurtz | first2=Jonathan | last3=Poole | first3=Cody | last4=Saffman | first4=Mark | last5=Noel | first5=Tom | last6=Alexeev | first6=Yuri | title=Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm | publisherarxiv=arXiv | doi=10.48550/ARXIV.2206.03579 | url=https://arxiv.org/abs/2206.03579 | access-date=2022-11-03}}</ref>

== See also ==