Algoritme de Grover

Algoritme de Grover

En computació quàntica, el algoritme de Grover és un algoritme quàntic per a la busca en una seqüència no ordenada de senyes en N components en un temps O (N^1/2), i en una necessitat adicional d'espai d'almagasenament de O(logN) (vore notació O). Va ser inventat per Lov K. Grover en 1996.

En una busca normal d'una senya, si tenim una seqüència desordenada es deu realisar una inspecció llineal, que necessita un temps de O (N), per lo que l'algoritme de Grover és una millora prou substancial, evitant, ademés, la necessitat de l'ordenació prèvia. El guany obtingut és quadràtica, lo que contrasta en atres millores dels algoritmes quàntics que obtenen millores d'orde exponencial sobre les seues contrapartides clàssiques.

De la mateixa manera que atres algoritmes de naturalea quàntica, l'algoritme de Grover és un algoritme de caràcter provabilístic, per lo que produïx la resposta correcta en una determinada provabilitat d'error, que, no obstant, pot obtindre's tan baixa com es desige per mig de iteraciones.

Aplicacions

Encara que el propòsit de l'algoritme és, com ha segut indicat, la busca en una seqüència, es podria descriure d'una manera més adequada com la "inversió d'una funció". Aixina, si tenim la funció i=f (x), que pot ser evaluada en un computador quàntic, este algoritme nos permet calcular el valor de x quan se nos dona com a entrada el valor de i. Invertir una funció pot relacionar-se en la busca en una seqüència, si considerem que la mateixa és una funció que produïx el valor de i com la posició ocupada pel valor x en dita seqüència.

L'algoritme de Grover també es pot utilisar per al càlcul de la mija i la mijana d'un conjunt de números, i per a resoldre atres problemes de naturalea anàloga. També es pot utilisar per a resoldre alguns problemes de naturalea NP-completa, per mig d'inspeccions exhaustives en un espai de possibles solucions. Açò resulta en una apreciable millora sobre solucions clàssiques.

Descripció

Inicialisació

Es considera una seqüència desordenada en N components. L'algoritme requerix un espai d'estats N-dimensional H, que pot ser modelat en log₂N qubits.

Numerem les entrades de la seqüència en 0, 1,... (N-1); i seleccionem un observable Ω, actuant sobre H, en N autovalores distints coneguts. Cada u dels autovalores de Ω codifica una de les entrades de la seqüència, d'una forma que es descriurà més alvance. Denotarem els autoestados utilisant la [[notació bra-ket]] en la forma:

$\{|0⟩,|1⟩,\cdots ,|N-1⟩\}$

i els autovalores corresponents com

$\{{\lambda }_0,{\lambda }_1,\cdots ,{\lambda }_{N-1}\}$

Ara prenem un operador unario, O_ω, que actua com una subrutina que compara les diferents entrades d'acort al criteri de busca. L'algoritme no especifica cóm funciona la subrutina, pero deu ser una subrutina quàntica que treballe baix una superposició d'estats. Ademés, deu actuar de manera especial sobre un dels autoestados, |ω>, que correspondrà en l'entrada que satisfà el criteri de busca. Més precisament, requerirem O_ω en els següents efectes:

$U_{\omega }|\omega ⟩=-|\omega ⟩$

$U_{\omega }|x⟩=|x⟩\text{para todo}x\ne \omega$

En concret,

$⟨\omega |\omega ⟩=1$.

$⟨\omega |x⟩=⟨x|\omega ⟩=0$.

$U_{\omega }|\omega ⟩=(I-2|\omega ⟩⟨\omega |)|\omega ⟩=|\omega ⟩-2|\omega ⟩⟨\omega |\omega ⟩=-|\omega ⟩$.

$U_{\omega }|x⟩=(I-2|\omega ⟩⟨\omega |)|x⟩=|x⟩-2|\omega ⟩⟨\omega |x⟩=|x⟩$.

El nostre objectiu és identificar el autoestado |ω>, o de manera equivalent, el autovalor ω, tal que O_ω actua especialment sobre ell.

Iteraciones de l'algoritme

Els passos de l'algoritme de Grover són els següents:

1. Inicializar el sistema a l'estat

   $|s⟩=\frac{1}{\sqrt{N}}\sum _x|x⟩$

2. Realisar la següent iteración r (N) voltes. A on la funció r (N) es descriu més alvance.
   1. Aplicar l'operador $U_{\omega }$
   2. Aplicar l'operador $U_s=2|s⟩⟨s|-I$.
3. Realisar la mida Ω. La mida correspondrà al valor λ_ω en una certa provabilitat que es pot aproximar a 1, per a un cert N>>1. A partir de λ_ω, es pot obtindre ω.

Podem escriure les operacions realisades:

$⟨s|s⟩=1$.

$⟨\omega |s⟩=⟨s|\omega ⟩=\frac{1}{\sqrt{N}}$.

$U_{\omega }|s⟩=(I-2|\omega ⟩⟨\omega |)|s⟩=|s⟩-2|\omega ⟩⟨\omega |s⟩=|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩$.

$U_s(|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩)=(2|s⟩⟨s|-I)(|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩)$

$=2|s⟩⟨s|s⟩-|s⟩-\frac{4}{\sqrt{N}}|s⟩⟨s|\omega ⟩+\frac{2}{\sqrt{N}}|\omega ⟩$

$=2|s⟩-|s⟩-\frac{4}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}|s⟩+\frac{2}{\sqrt{N}}|\omega ⟩=\frac{N-4}{N}|s⟩+\frac{2}{\sqrt{N}}|\omega ⟩$

$=\frac{1}{N\sqrt{N}}((N-4)\sum _{x\ne w}|x⟩+(3N-4)|\omega ⟩)$

Despuix d'aplicar els dos operadors ( $U_{\omega }$ i $U_s$ ), l'amplitut de l'element buscat es veu incrementat. I esta és una iteración de Grover.

Número de iteraciones

Ara considerem el pla definit per |s> i |ω>. Siga |ω^×> que és perpendicular a |ω>. Llavors |ω> és un dels vectores base, i tenim

$⟨\omega |s⟩=\frac{1}{\sqrt{N}}$

En térmens geomètrics, hi ha un àngul (π/2 - θ) entre |ω> i |s>, a on θ donat per:

$\cos (\frac{\pi }{2}-\theta )=\frac{1}{\sqrt{N}}$

$\sin \theta =\frac{1}{\sqrt{N}}$

L'operador O_ω és un reflex del hiperplano ortogonal a |ω> per als vectors en el pla definit per |s> i |ω>, ademés, actua com un reflex de la llínea |ω^×>. L'operador O_s és un reflex de la llínea |s>.

Llavors, el vector d'estat permaneix en el pla de |s> i |ω> despuix de cada aplicació d'O_s i despuix de cada aplicació d'O_ω, i es pot comprovar que l'operador O_sO_ω de cada pas de iteración trencada el vector d'estat en un àngul de 2θ cap a |ω>.

L'algoritme es detindrà quan el vector d'estat s'acosta a |ω> despuix d'açò, les següents iteraciones rotan el vector d'estat fòra de |ω>, reduint la provabilitat d'obtindre la resposta correcta. El número de iteraciones necessàries és donat per r. Per a alinear correctament el vector d'estat en |ω>, necessitem:

$\frac{\pi }{2}-\theta =2\theta r$

$r=\frac{(\frac{\pi }{\theta }-2)}{4}$

Una consideració és que r deu ser sancer, per lo que, en general, r serà el sancer més propenc a (π/θ - 2)/4. Llavors, l'àngul entre |ω> i el vector d'estat final és O(θ), i la provabilitat d'obtindre una resposta incorrecta és O(1 - cos²θ) = O (sense²θ).

Llavors, per a N>>1, θ ≈ N^-1/2, tenim

$r\to \frac{\pi \sqrt{N}}{4}$

Ademés, la provabilitat d'obtindre una resposta incorrecta serà O(1/N), que tendix a 0 per a un valor de N suficientment elevat.

Vore també

• Algoritme de Shor

Referències

1. Grover L.K.: A fast quàntum mechanical algorithm for database search. Presentació original de l'algoritme (en anglés).
2. Grover L.K.: From Schrödinger's equation to quàntum search algorithm. Versió pedagògica de l'algoritme i història (en anglés).
3. https://web.archive.org/web/20140201230754/http://www.bell-labs.com/user/feature/archives/lkgrover/
4. Notes de les Charrades Introductòries a la Computació Quàntica (Alejandro Díaz-Car).
5. Michael A. Nielsen i Isaac L. Chuang, Quàntum Computation and Quàntum Information, Cambridge University Press, Regne Unit, 2000, ISBN 0-521-63503-9.