Content deleted Content added
Xphileprof (talk | contribs) m " |
Xphileprof (talk | contribs) Minor fixes to grammar. More logical organization of ==Quantum combinatorial optimization== section. Corrected statement of relationship between the algorithms proposed by Farhi, et al. and by Barak, et al. (the latter is known to be more effective, not more efficient). |
||
Line 55:
The best classical algorithm known runs [[polynomial time]] in the worst case.
The quantum algorithm provides a quadratic improvement in the general case, and an exponential improvement when the input matrices are of low [[Rank (linear algebra)|rank]].▼
===The quantum algorithm===
Line 72:
In each iteration, a different threshold <math>t</math> is chosen, and the algorithm outputs either a solution <math>X</math> such that <math> \langle C, X\rangle_{\mathbb{S}^n} \leq t</math> (and the other constraints are satisfied, too) or an indication that no such solution exists. The algorithm performs a [[binary search]] to find the minimal threshold <math>t</math> for which a solution <math>X</math> still exists: this gives the minimal solution to the SDP problem.
▲The quantum algorithm provides a quadratic improvement over the best classical algorithm in the general case, and an exponential improvement when the input matrices are of low [[Rank (linear algebra)|rank]].
==Quantum combinatorial optimization==▼
[[Approximation algorithm|Approximate optimization]] is a way of finding an approximate solution to an optimization problem, which is often [[NP-hard]]. For [[combinatorial optimization]], there is a quantum algorithm<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> that had previously been considered to have a better approximation ratio than any [[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 an efficient classical algorithm was proposed.<ref>{{cite arxiv|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|eprint=1505.03424|class=cs.CC|year=2015}}</ref> However, the relative speed-up of the quantum algorithm is an open research question.▼
▲==Quantum combinatorial optimization==
The [[combinatorial optimization]] problem is aimed at finding an optimal object from a [[finite set]] of objects. The problem can be phrased as a maximization of an [[objective function]] which is a sum of [[boolean function]]s. Each boolean function <math>\,C_\alpha \colon \lbrace {0,1 \rbrace}^n \rightarrow \lbrace {0,1} \rbrace </math> gets as input the <math>n</math>-bit string <math>z = z_1 z_2 \ldots z_n</math> and gives as output one bit (0 or 1). The combinatorial optimization problem of <math>n</math> bits and <math>m</math> clauses is finding an <math>n</math>-bit string <math>z</math> that
:<math>
C(z) = \sum_{\alpha=1}^m C_\alpha(z)
</math>
[[Approximation algorithm|Approximate optimization]] is a way of finding an approximate solution to an optimization problem, which is often [[NP-hard]]. The approximated solution of the combinatorial optimization problem is a string <math> z </math> that is close to maximizing <math> C(z) </math>.
===Quantum Approximate Optimization Algorithm===
▲
The heart of the
▲The heart of the algorithm relies on the use of [[unitary operators]] dependent on <math> 2p </math> [[angle]]s, where <math> p>1 </math> in 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 be optimal as well.
== See also ==
| |||