Algorisme de Grover

En computació quàntica, l'algorisme de Grover és un algorisme quàntic per a la cerca en una seqüència no ordenada de dades amb N components en un temps $O({\sqrt {N}})$, i amb una necessitat addicional d'espai d'emmagatzematge d'$O(\log N)$ (vegeu notació O). Va ser inventat per Lov K. Grover en 1996

En una cerca normal d'una dada, si tenim una seqüència desordenada s'ha de realitzar una inspecció lineal, que necessita un temps d'$O(N)$, cosa per la qual l'algorisme de Grover és una millora bastant substancial, evitant, a més, la necessitat de l'ordenació prèvia. El guany obtingut és "només" de l'arrel quadrada, cosa que contrasta amb altres millores dels algorismes quàntics que obtenen millores d'ordre exponencial sobre les seves contrapartides clàssiques.

Igual que altres algorismes de naturalesa quàntica, l'algorisme de Grover és un algorisme de caràcter probabilístic, per la qual cosa produeix la resposta correcta amb una determinada probabilitat d'error, que no obstant això, pot obtenir-se tan baixa com es desitje per mitjà d'iteracions.

Aplicacions

Encara que el propòsit de l'algorisme és, com ha estat indicat, la cerca en una seqüència, es podria descriure d'una manera més adequada com la "inversió d'una funció". Així, si tenim la funció y=f (x), que pot ser avaluada en un computador quàntic, aquest algorisme ens permet calcular el valor de x quan se'ns dona com a entrada el valor d'y. Invertir una funció pot relacionar-se amb la cerca en una seqüència, si considerem que la mateixa és una funció que produeix el valor d'y com la posició ocupada pel valor x en aquesta seqüència.

L'algorisme de Grover també es pot utilitzar per al càlcul de la mitjana i la mitjana d'un conjunt de nombres, i per resoldre altres problemes de naturalesa anàloga. També es pot utilitzar per resoldre alguns problemes de naturalesa NP-completa, per mitjà d'inspeccions exhaustives en un espai de possibles solucions. Això resulta en una apreciable millora sobre solucions clàssiques.

Descripció

Inicialització

Es considera una seqüència desordenada amb N components. L'algorisme requereix un espai d'estats N-dimensional $H$, que pot ser modelat amb $\log _{2}N$ qubits.

Numerem les entrades de la seqüència amb 0, 1,... (N-1); i seleccionem un observable Ω, actuant sobre H, amb N autovalors diferents coneguts. Cadascun dels autovalors d'Ω codifica una de les entrades de la seqüència, d'una forma que es descriurà més endavant. Denotarem els autoestats utilitzant la notació bra-ket en la forma:

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

i els autovalors corresponents com

$\{\lambda _{0},\lambda _{1},\cdots ,\lambda _{N-1}\}$

Ara prenem un operador unari, Uω, que actua com una subrutina que compara les diferents entrades d'acord al criteri de cerca. L'algorisme no especifica com funciona la subrutina, però ha de ser una subrutina quàntica que treballe sota una superposició d'estats. A més, ha d'actuar de manera especial sobre un dels autoestats, |ω>, que correspondrà amb l'entrada que satisfà el criteri de cerca. Més precisament, requerirem Uω amb els següents efectes:

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

$U_{\omega }|x\rangle =|x\rangle \qquad {\mbox{per a tot}}\ x\neq \omega$

En concret,

$\langle \omega |\omega \rangle =1$.

$\langle \omega |x\rangle =\langle x|\omega \rangle =0$.$U_{\omega }|\omega \rangle =(I-2|\omega \rangle \langle \omega |)|\omega \rangle =|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle$.

$U_{\omega }|x\rangle =(I-2|\omega \rangle \langle \omega |)|x\rangle =|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle$.

El nostre objectiu és identificar l'autoestat |_ω>, o de manera equivalent, l'autovalor ω, tal que Uω actua especialment sobre ell.

Iteracions de l'algorisme

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

1. Inicialitzar el sistema a l'estat

   $|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}|x\rangle$

2. Realitzar la següent iteració r (N) vegades. On la funció r (N) es descriu més endavant.
   1. Aplicar l'operador $U_{\omega }$
   2. Aplicar l'operador $U_{s}=2\left|s\right\rangle \left\langle s\right|-I$.
3. Realitzar la mesura Ω. La mesura correspondrà al valor λω amb una certa probabilitat que es pot aproximar a 1, per a un cert N>>1. A partir de λ_ω, es pot obtenir ω.

Podem escriure les operacions realitzades:

$\langle s|s\rangle =1$.

$\langle \omega |s\rangle =\langle s|\omega \rangle ={\frac {1}{\sqrt {N}}}$.

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

$U_{s}(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=(2\left|s\right\rangle \left\langle s\right|-I)(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )$

$=2\left|s\right\rangle \left\langle s\right|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\left|s\right\rangle \left\langle s\right|\omega \rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle$

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

$={\frac {1}{N{\sqrt {N}}}}\left((N-4)\sum _{x\neq w}|x\rangle +(3N-4)|\omega \rangle \right)$

Després d'aplicar els dos operadors ($U_{\omega }$ i $U_{s}$), l'amplitud de l'element buscat es veu incrementada. I aquesta és una iteració de Grover.

Nombre d'iteracions

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

$\langle \omega |s\rangle ={\frac {1}{\sqrt {N}}}$

En termes geomètrics, hi ha un angle (π/2 - θ) entre |ω> i |s>, on θ donat per:

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

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

L'operador Uω és un reflex de l'hiperpla ortogonal a |ω> pels vectors en el pla definit per |s> i |ω>, a més, actua com un reflex de la línia |ω×>. L'operador Us és un reflex de la línia |s>.

Aleshores, el vector d'estat roman en el plànol de |s> i |ω> després de cada aplicació de Us i després de cada aplicació d'Uω, i es pot comprovar que l'operador UsUω de cada pas d'iteració rota el vector d'estat en un angle de 2θ cap a |ω>.

L'algorisme es detindrà quan el vector d'estat s'acosta a |ω> després d'això, les següents iteracions roten el vector d'estat fora de |ω>, reduint la probabilitat d'obtenir la resposta correcta. El nombre d'iteracions necessàries és donat per r. Per alinear correctament el vector d'estat amb |ω>, necessitem:

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

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

Una consideració és que r ha de ser sencer, per la qual cosa, en general, r serà l'enter més proper a (π/θ - 2)/4. Llavors, l'angle entre |ω> i el vector d'estat final és O(θ), i la probabilitat d'obtenir una resposta incorrecta és O(1 - cos2θ) = O (sin2θ).

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

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

A més, la probabilitat d'obtenir una resposta incorrecta serà O(1/N), que tendeix a 0 per a un valor de N suficientment elevat.

Implementació

A continuació presentem una implementació concreta de l'algorisme de Grover. Suposem que tenim una seqüència de 2n elements que anem a referenciar pel seu índex x. Suposem també que disposem d'una funció f (x) que ens diu si el valor emmagatzemat en la posició x és el que estem buscant. En concret sigui f (x)=1 per al valor buscat i f (x)=0 per a la resta.

Oracle

Oracle.

A partir de la funció f (x) anem a construir un oracle, tal com es mostra en la figura de la dreta. El funcionament d'aquest bloc és el mateix que el corresponent de l'algorisme de Deutsch-Jozsa. L'operació d'aquest bloc és:

$U_{f}(|x\rangle (|0\rangle -|1\rangle ))=(-1)^{f(x)}|x\rangle |(|0\rangle -|1\rangle )$

Ja que l'últim estat no es modifica, anem a ignorar-ho i escriurem:

$U_{f}(|x\rangle )=(-1)^{f(x)}|x\rangle$

Inversió sobre la mitjana

Inversió sobre la mitjana.

El bloc que el realitza es mostra en la figura de la dreta. Aquesta operació pot escriure's:

$H^{\oplus n}(2|0\rangle \langle 0|-I)H^{\oplus n}=2|\psi \rangle \langle \psi |-I$

amb $\textstyle \psi ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle$.

Aquesta operació s'interpreta com a inversió sobre la mitjana, car si l'apliquem sobre un estat genèric $\textstyle a=\sum _{x=0}^{2^{n}-1}a_{x}|x\rangle$, obtenim:

$(2|\psi \rangle \langle \psi |-I)(\sum _{x=0}^{2^{n}-1}a_{x}|x\rangle )=\sum _{x=0}^{2^{n}-1}\left(2\langle a\rangle -a_{x}\right)|x\rangle$,

on $\textstyle \langle a\rangle =(1/2^{n})\sum _{x=0}^{2^{n}-1}a_{x}$

Iteració de Grover

Algorisme de Grover. Detalladament es mostra una de les iteracions.

Una iteració de Grover es compon de dos passos:

1. Aplicació de l'oracle
2. Inversió sobre la mitjana

Per tant, la iteració de Grover pot escriure's:

$G_{f}=(2|\psi \rangle \langle \psi |-I)U_{f}$.

L'algorisme complet es mostra en la figura de la dreta.

Interpretació

Fem els comptes per a la primera iteració de Grover. Preparem un estat fent passar el qubit |0> (realment compost de n zeros) a través d'una porta d'Hadamard:

$|a\rangle =H^{\oplus n}|0\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle$

Aquest estat passa a través de l'oracle, obtenint:

$|b\rangle =U_{f}(|a\rangle )={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle$

A continuació, apliquem la inversió sobre la mitjana, i obtenim:

$|c\rangle =(2|\psi \rangle \langle \psi |-I)(|b\rangle )={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(2<b>-b_{x})|x\rangle$

$={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left(\sum _{y=0}^{2^{n}-1}b_{y}\right)-2^{n}b_{x}\right)|x\rangle$

$={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left(\sum _{y=0}^{2^{n}-1}(-1)^{f(y)}\right)-2^{n}(-1)^{f(x)}\right)|x\rangle$

Interpretem ara aquest resultat. Suposem que en la posició x_i es troba el valor buscat, això és, f (xi)=1 i per a la resta, f (x)=0, obtenim:

$|c\rangle ={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left((2^{n}-1)(+1)+(-1)\right)-2^{n}(-1)^{f(x)}\right)|x\rangle$

$={\frac {2^{n+1}+2^{n}-4}{2^{n}{\sqrt {2^{n}}}}}|x_{i}\rangle +{\frac {2^{n+1}-2^{n}-4}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0,x\neq x_{i}}^{2^{n}-1}|x\rangle$

Com pot observar-se, el terme que ens interessa augmenta la seva amplitud en comparació dels altres termes. Repetint aquesta operació en diverses iteracions, aquest efecte es veurà incrementat. Si al final de l'algorisme fem un mesurament, molt probablement obtindrem el valor buscat.

Referències

1. Grover L.K.: From Schrödinger's equation to quàntum search algorithm. Versió pedagògica de l'algorisme i història (en anglès).
2. https://web.archive.org/web/20140201230754/http://www.bell-labs.com/user/feature/archives/lkgrover/
3. 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.