Quantum optimization algorithms: Difference between revisions

Revision as of 13:20, 18 January 2017

Revision as of 14:01, 18 January 2017

Line 10:

The quantum least-squares fitting algorithm<ref>{{cite journal|last1=Wiebe|first1=Nathan|last2=Braun|first2=Daniel|last3=Lloyd|first3=Seth|title=Quantum Algorithm for Data Fitting|journal=Physical Review Letters|date=2 August 2012|volume=109|issue=5|doi=10.1103/PhysRevLett.109.050505}}</ref> takes use in a version of Harrow, Hassidim, and Lloyd's [[quantum algorithm for linear systems of equations]], and produces fit parameters and a fit quality estimation. It is consisted of three subroutines: an algorithm for performing pseudo-inverse operation, one routine for the fit quality estimation, and an algorithm for learning the fit parameters.

Denote a single data point {<math> {(x_i, y_i}) </math>}, of a set of <math> N </math> data points. The algorithm is aimed to finding a continuous function of the form:

:<math>

f(x,\lambda)=\sum_{j=1}^M

Line 31:

The required inputs are a quantum state which holds the data of the <math> y_i, i=1...N</math>, an upper bound to the [[condition number]], namely the ratio between the maximal and minimal eigenvalues of <math> FF^\dagger </math> and <math> F^\dagger F </math>, the sparseness of <math> F</math>, a maximal number of inner fit functions allowed, and the error and quality thresholds.

==Quantum Semidefinite Programming==