Content deleted Content added
m added author link |
|||
Line 82:
===Quantum approximate optimization algorithm===
For combinatorial optimization, the '''quantum approximate optimization algorithm''' (QAOA)<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm|eprint=1411.4028|class=quant-ph|year=2014}}</ref> briefly had a better approximation ratio than any known [[polynomial time]] classical algorithm (for a certain problem),<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem|eprint=1412.6062|class=quant-ph|year=2014}}</ref> until a more effective classical algorithm was proposed.<ref>{{cite arXiv|last1=Barak|first1=Boaz|last2=Moitra|first2=Ankur|last3=O'Donnell|first3=Ryan| author3-link = Ryan O'Donnell (computer scientist) |last4=Raghavendra|first4=Prasad|last5=Regev|first5=Oded|last6=Steurer|first6=David|last7=Trevisan|first7=Luca|last8=Vijayaraghavan|first8=Aravindan|last9=Witmer|first9=David|last10=Wright|first10=John|title=Beating the random assignment on constraint satisfaction problems of bounded degree|eprint=1505.03424|class=cs.CC|year=2015}}</ref> The relative speed-up of the quantum algorithm is an open research question.
The heart of 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 estimated. The angles are then updated classically to increase <math> C(z) </math>. After this procedure is repeated a sufficient number of times, the value of <math> C(z) </math> is almost optimal, and the state being measured is close to being optimal as well. In principle the optimal value of <math> C(z) </math> can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm|eprint=1411.4028|class=quant-ph|year=2014}}</ref> or alternatively by the universality of the QAOA unitaries.<ref>{{Cite journal|last1=Morales|first1=M. E. |last2=Biamonte|first2=J. D.|last3=Zimborás|first3=Z. |date=2019-09-20|title=On the universality of the quantum approximate optimization algorithm|journal=Quantum Information Processing|volume=19|pages=291|doi=10.1007/s11128-020-02748-9|arxiv=1909.03123 }}</ref> However, it is an open question whether this can be done in a feasible way.
| |||