Quantum optimization algorithms: Difference between revisions

Revision as of 12:43, 11 January 2017

Revision as of 13:18, 11 January 2017

Line 57:

===Quantum Least Squares Fitting===

The quantum least-squares fitting algorithm 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 the lastalgorithm 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 find a continuous function of the form:

The required inputs are a quantum state which holds the data of the <math> y_i </math>

:<math>

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

f_{j}(x)\lambda_{j}.

</math>

The fitting function is linear in respect to <math>\lambda_j </math>, the fitting parameters, but is not necessarily linear in respect to x. The algorithm searches for the optimal fit parameters, by minimizing the error denoted by:

:<math>

E=\sum_{i=1}^N

|f(x_i,\lambda)-y_i|^2=|F\lambda-y|^2.

</math>

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]] of <math> FF^\dagger </math> and <math> F^\dagger F </math>, the sparseness of <math> F </math>, a maximal number of inner fit function allowed, and the error and quality thresholds.