Quantum optimization algorithms: Difference between revisions

Revision as of 09:22, 2 January 2017

Revision as of 10:32, 2 January 2017

Line 1:

==Quantum Semidefinite Programming==

[[Semidefinite programming]] (SDP) is an optimization subfield with a wide range of applications. The problems addressed by it are scaling, so it's important to find more efficient ways to solve them.

Line 22:

===The quantum algorithm===

The algorithm inputs are [[Oracle machine|oracles]] for <math> A_iA_1 ... A_m, C , b_1 ... b_m<\/math> and parameters regarding the solution [[trace]], precision and optimal value.

**Requirements

The algorithm inputs are [[Oracle machine|oracles]] for <math> A_i , C <\math>

The quantum algorithm reduces the problem to a [[Mathematical optimization#Feasibility problem | feasibility problem]], performing a binary search on the solution. One algorithm iteration can either output a feasible solution with an objective smaller than some value, or indicate that the optimal objective is larger than an other value, when these values are determined by chosen input parameters. Therefore, it can be run again with different parameters, binary searching the optimal objective value and solution.

The algorithm takes use in a [[Gibbs sampling |Gibbs sampler]], as a probabilistic oracle sampler for estimating the mixed [[quantum state|states]] of the [[density matrix]] through iterations. These samples of the density matrix oracle are used to determine final solution<ref>{{cite journal|last1=Brandao|first1=Fernando G. S. L.|last2=Svore|first2=Krysta|title=Quantum Speed-ups for Semidefinite Programming|journal=arXiv:1609.05537 [quant-ph]|date=18 September 2016|url=https://arxiv.org/abs/1609.05537}}</ref>.