Algorismes d'optimització quàntica

Els algorismes d'optimització quàntica són algorismes quàntics que s'utilitzen per resoldre problemes d'optimització. L'optimització matemàtica tracta de trobar la millor solució a un problema (segons alguns criteris) a partir d'un conjunt de solucions possibles. Majoritàriament, el problema d'optimització es formula com un problema de minimització, on s'intenta minimitzar un error que depèn de la solució: la solució òptima té l'error mínim. S'apliquen diferents tècniques d'optimització en diversos camps com la mecànica, l'economia i l'enginyeria, i a mesura que augmenta la complexitat i la quantitat de dades implicades, es necessiten maneres més eficients de resoldre problemes d'optimització. La potència de la computació quàntica pot permetre resoldre problemes que no són pràcticament factibles en ordinadors clàssics, o suggerir una velocitat considerable respecte a l'algorisme clàssic més conegut.

L'ajust de dades és un procés de construcció d'una funció matemàtica que s'ajusti millor a un conjunt de punts de dades. La qualitat de l'ajust es mesura amb alguns criteris, normalment la distància entre la funció i els punts de dades.

Un dels tipus més comuns d'ajust de dades és resoldre el problema dels mínims quadrats, minimitzant la suma dels quadrats de les diferències entre els punts de dades i la funció ajustada.

L'algorisme es dona com a entrada $N$ punts de dades $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})$ i $M$ funcions contínues $f_{1},f_{2},...,f_{M}$. L'algorisme troba i dona com a sortida una funció contínua $f_{\vec {\lambda }}$ que és una combinació lineal de $f_{j}$ :

$f_{\vec {\lambda }}(x)=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}$

En altres paraules, l'algorisme troba els coeficients complexos $\lambda _{j}$, i així troba el vector ${\vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})$ .

L'algorisme té com a objectiu minimitzar l'error, que ve donat per:

$E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2}=\sum _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}\right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}$

on definim $F$ ser la matriu següent:

${F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}$

L'algoritme d'ajust quàntic de mínims quadrats fa ús d'una versió de l'algoritme quàntic de Harrow, Hassidim i Lloyd per a sistemes d'equacions lineals (HHL) i produeix els coeficients $\lambda _{j}$ i l'estimació de la qualitat de l'ajust $E$. Consta de tres subrutines: un algorisme per realitzar una operació pseudo- inversa, una rutina per a l'estimació de la qualitat de l'ajust i un algorisme per aprendre els paràmetres d'ajust.

Com que l'algoritme quàntic es basa principalment en l'algorisme HHL, suggereix una millora exponencial en el cas en què $F$ és escàs i el nombre de condició (és a dir, la relació entre els valors propis més gran i més petit) de tots dos $FF^{\dagger }$ i $F^{\dagger }F$ és petit.