Algorisme quàntic per a sistemes d'equacions lineals

L'algorisme quàntic per a sistemes d'equacions lineals, també anomenat algorisme HHL, dissenyat per Aram Harrow, Avinatan Hassidim i Seth Lloyd, és un algorisme quàntic publicat el 2008 per resoldre sistemes lineals. L'algorisme estima el resultat d'una mesura escalar sobre el vector solució a un sistema lineal d'equacions donat.

L'algoritme és un dels principals algorismes fonamentals que s'espera que proporcioni una acceleració respecte als seus homòlegs clàssics, juntament amb l'algoritme de factorització de Shor, l'algoritme de cerca de Grover i la transformada quàntica de Fourier. Sempre que el sistema lineal sigui escàs i tingui un nombre de condició baix $\kappa$, i que l'usuari estigui interessat en el resultat d'una mesura escalar sobre el vector solució, en lloc dels valors del propi vector solució, aleshores l'algorisme té un temps d'execució de $O(\log(N)\kappa ^{2})$, on $N$ és el nombre de variables del sistema lineal. Això ofereix una acceleració exponencial respecte a l'algorisme clàssic més ràpid, que s'executa $O(N\kappa )$ (o $O(N{\sqrt {\kappa }})$ per a matrius semidefinides positives).

Una implementació de l'algorisme quàntic per a sistemes lineals d'equacions es va demostrar per primera vegada el 2013 per Cai et al., Barz et al. i Pan et al. en paral·lel. Les demostracions consistien en equacions lineals simples en dispositius quàntics especialment dissenyats. La primera demostració d'una versió de propòsit general de l'algorisme va aparèixer el 2018 en el treball de Zhao et al.

A causa de la prevalença de sistemes lineals en pràcticament totes les àrees de la ciència i l'enginyeria, l'algoritme quàntic per a sistemes lineals d'equacions té el potencial d'aplicabilitat generalitzada.

Aplicacions

Els ordinadors quàntics són dispositius que aprofiten la mecànica quàntica per realitzar càlculs d'una manera que els ordinadors clàssics no poden. Per a certs problemes, els algorismes quàntics proporcionen acceleracions exponencials sobre els seus homòlegs clàssics, l'exemple més famós és l'algorisme de factorització de Shor. Es coneixen poques acceleracions exponencials d'aquest tipus, i les que sí (com l'ús d'ordinadors quàntics per simular altres sistemes quàntics) fins ara han trobat un ús limitat fora del domini de la mecànica quàntica. Aquest algorisme proporciona un mètode exponencialment més ràpid per estimar les característiques de la solució d'un conjunt d'equacions lineals, que és un problema omnipresent en la ciència i l'enginyeria, tant per si mateix com com a subrutina en problemes més complexos.

Dispersió electromagnètica

Clader et al. va proporcionar una versió prèviament condicionada de l'algorisme de sistemes lineals que va proporcionar dos avenços. En primer lloc, van demostrar com es podia incloure un precondicionador dins de l'algorisme quàntic. Això amplia la classe de problemes que poden assolir l'acceleració exponencial prometida, ja que l'escala de HHL i els millors algorismes clàssics són tots dos polinomials en la condició número. El segon avenç va ser la demostració de com utilitzar HHL per resoldre la secció transversal del radar d'una forma complexa. Aquest va ser un dels primers exemples extrem a extrem de com utilitzar HHL per resoldre un problema concret exponencialment més ràpid que l'algorisme clàssic més conegut.