Content deleted Content added
No edit summary |
No edit summary |
||
Line 42:
[[Approximation algorithm|Approximate optimization]] is a way to find an approximate solution to an optimization problem, which is often [[NP-hard]]. For [[combinatorial optimization]], there is a quantum algorithm<ref>{{cite journal|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm|journal=arXiv:1411.4028 [quant-ph]|date=14 November 2014|url=https://arxiv.org/abs/1411.4028}}</ref> that was previously considered to have a better approximation ratio than any polynomial-time classical algorithm (for a certain problem)<ref>{{cite journal|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|journal=arXiv:1412.6062 [quant-ph]|date=18 December 2014|url=https://arxiv.org/abs/1412.6062}}</ref>, until an efficient classical algorithm was proposed<ref>{{cite journal|last1=Barak|first1=Boaz|last2=Moitra|first2=Ankur|last3=O'Donnell|first3=Ryan|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|journal=arXiv:1505.03424 [cs]|date=13 May 2015|url=https://arxiv.org/abs/1505.03424}}</ref>. However, the relative speedup of the quantum algorithm is an open research question.
===The
The objective function for a combinatorial optimization problem of <math> n </math> bits and <math> m </math> clauses can be written as:
:<math>
C(z) = \sum_{\alpha=1}^m C_\alpha(z)
</math>
Where <math> z=z_1...z_n </math> is the bit string and <math> C_\alpha(z)=1 </math> if <math> z </math> satisfies clause <math> \alpha </math> (and 0 otherwise). The approximated solution is a string <math> z </math> that is close to maximizing <math> C_\alpha(z) </math>.
===Quantum Approximation Optimization Algorithm (QAOA)===
The heart of the algorithm relies on applying [[unitary operators]] dependent on <math> 2p </math> angles, where <math> p>1 </math> in an input integer, on the [[completely mixed state]].
== References ==
| |||