Usuari:Model d'arbre de decisió

Representació en circuit quàntic de l'algorisme de Grover

torEn informàtica quàntica, l'algoritme de Grover, també conegut com algorisme de cerca quàntica, es refereix a un algorisme quàntic per a la cerca no estructurada que troba amb alta probabilitat l'entrada única a una funció de caixa negra que produeix un valor de sortida particular, utilitzant només $O({\sqrt {N}})$ avaluacions de la funció, on $N$ és la mida del domini de la funció. Va ser ideat per Lov Grover el 1996.

Imatge que mostra la interpretació geomètrica de la primera iteració de l'algorisme de Grover. El vector d'estat $|s\rangle$ es gira cap al vector objectiu $|\omega \rangle$ com es mostra.

El problema anàleg de la computació clàssica no es pot resoldre en menys de $O(N)$ avaluacions (perquè, de mitjana, s'ha de comprovar la meitat del domini per tenir un 50% de possibilitats de trobar l'entrada adequada). Charles H. Bennett, Ethan Bernstein, Gilles Brassard i Umesh Vazirani van demostrar que qualsevol solució quàntica al problema necessita avaluar la funció. $\Omega ({\sqrt {N}})$ vegades, de manera que l'algoritme de Grover és asimptòticament òptim. Com que els algorismes clàssics per a problemes NP-complets requereixen de manera exponencial molts passos, i l'algoritme de Grover proporciona com a màxim una acceleració quadràtica sobre la solució clàssica per a la cerca no estructurada, això suggereix que l'algoritme de Grover per si mateix no proporcionarà solucions en temps polinomial per a problemes NP-complets ( ja que l'arrel quadrada d'una funció exponencial és una funció exponencial, no polinomial).

A diferència d'altres algorismes quàntics, que poden proporcionar una acceleració exponencial respecte als seus homòlegs clàssics, l'algoritme de Grover només proporciona una acceleració quadràtica. Tanmateix, fins i tot l'acceleració quadràtica és considerable quan $N$ és gran i l'algoritme de Grover es pot aplicar per accelerar classes àmplies d'algorismes. L'algoritme de Grover podria forçar una clau criptogràfica simètrica de 128 bits en aproximadament 2⁶⁴ iteracions, o una clau de 256 bits en aproximadament 2 ¹²⁸ iteracions. Tanmateix, pot ser que no sigui el cas que l'algoritme de Grover suposi un risc significativament augmentat per al xifratge respecte als algorismes clàssics existents.

Aplicacions i limitacions

L'algoritme de Grover, juntament amb variants com l'amplificació d'amplitud, es pot utilitzar per accelerar una àmplia gamma d'algorismes. En particular, els algorismes per a problemes NP-complets contenen generalment una cerca exhaustiva com a subrutina, que es pot accelerar amb l'algorisme de Grover. El millor algorisme actual per a 3SAT n'és un exemple. Els problemes genèrics de satisfacció de restriccions també veuen acceleracions quadràtiques amb Grover. Aquests algorismes no requereixen que l'entrada es doni en forma d'oracle, ja que l'algoritme de Grover s'està aplicant amb una funció explícita, per exemple, la funció que verifica que un conjunt de bits satisfà una instància 3SAT.

L'algoritme de Grover també pot donar acceleracions demostrables per als problemes de caixa negra en la complexitat de la consulta quàntica, incloent la distinció d'elements i el problema de col·lisió (resolt amb l'algorisme de Brassard–Høyer–Tapp). En aquest tipus de problemes, es tracta la funció oracle f com una base de dades, i l'objectiu és utilitzar la consulta quàntica a aquesta funció el mínim de vegades possible.

Algoritme

Els passos de l'algorisme de Grover es donen de la següent manera:

1. Inicialitzar el sistema a la superposició uniforme sobre tots els estats

$|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .$

1. Realitzeu la següent "iteració de Grover" $r(N)$ vegades:
   1. Aplicar l'operador $U_{\omega }$
   2. Aplicar l'operador de difusió Grover $U_{s}=2\left|s\right\rangle \left\langle s\right|-I$c
2. Mesura l'estat quàntic resultant en la base computacional.

Pel valor correctament triat de $r$, la sortida serà $|\omega \rangle$ amb una probabilitat propera a 1 per a N ≫ 1. L'anàlisi mostra que aquest valor eventual per $r(N)$ satisfà $r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }$.

La implementació dels passos per a aquest algorisme es pot fer utilitzant un nombre de portes lineals en el nombre de qubits. Per tant, la complexitat de la porta d'aquest algorisme és $O(\log(N)r(N))$, o $O(\log(N))$ per iteració.