La amplificación de amplitud es una técnica en computación cuántica que generaliza la idea detrás del algoritmo de búsqueda de Grover y da lugar a una familia de algoritmos cuánticos . Fue descubierto por Gilles Brassard y Peter Høyer en 1997, [1] y redescubierto de forma independiente por Lov Grover en 1998. [2]
En una computadora cuántica, la amplificación de amplitud se puede utilizar para obtener una aceleración cuadrática sobre varios algoritmos clásicos.
Algoritmo
La derivación presentada aquí sigue aproximadamente a la dada en. [3] Suponga que tenemos un espacio de Hilbert de dimensión N que representa el espacio de estados de nuestro sistema cuántico, abarcado por los estados de base computacional ortonormales. Además, supongamos que tenemos un operador de proyección hermitiano . . Alternativamente,puede ser dado en términos de un valor booleano oráculo función y una base operativa ortonormal , en ese caso
- .
se puede utilizar para particionar en una suma directa de dos subespacios mutuamente ortogonales, el subespacio buenoy el mal subespacio:
Dado un vector de estado normalizado con una superposición distinta de cero con ambos subespacios, podemos descomponerlo de forma única como
- ,
dónde , y y son las proyecciones normalizadas de en los subespacios y , respectivamente. Esta descomposición define un subespacio bidimensional, atravesado por los vectores y . La probabilidad de encontrar el sistema en buen estado cuando se mide es.
Definir un operador unitario , dónde
invierte la fase de los estados en el subespacio bueno , mientras que cambia la fase del estado inicial .
La acción de este operador sobre es dado por
- y
- .
Así en el subespacio corresponde a una rotación por el ángulo :
- .
Aplicando tiempos en el estado da
- ,
rotando el estado entre los subespacios buenos y malos . Despuésiteraciones la probabilidad de encontrar el sistema en buen estado es.
La probabilidad se maximiza si elegimos
- .
Hasta este punto, cada iteración aumenta la amplitud de los buenos estados, de ahí el nombre de la técnica.
Aplicaciones
Supongamos que tenemos una base de datos sin clasificar con N elementos y una función de oráculo que puede reconocer las buenas entradas que estamos buscando, y por simplicidad.
Si hay buenas entradas en la base de datos en total, entonces podemos encontrarlas inicializando un registro cuántico con qubits dondeen una superposición uniforme de todos los elementos de la base de datos tal que
y ejecutando el algoritmo anterior. En este caso, la superposición del estado inicial con el subespacio bueno es igual a la raíz cuadrada de la frecuencia de las entradas buenas en la base de datos,. Si, podemos aproximar el número de iteraciones requeridas como
Medir el estado ahora dará una de las buenas entradas con alta probabilidad . Dado que cada aplicación derequiere una sola consulta de oráculo (asumiendo que el oráculo se implementa como una puerta cuántica ), podemos encontrar una buena entrada con soloconsultas de Oracle, obteniendo así una aceleración cuadrática sobre el mejor algoritmo clásico posible. (El método clásico para buscar en la base de datos sería realizar la consulta para cada hasta que se encuentre una solución, lo que cuesta consultas). Además, podemos encontrar todos soluciones usando consultas.
Si establecemos el tamaño del conjunto a uno, el escenario anterior se reduce esencialmente a la búsqueda original de Grover .
Conteo cuántico
Suponga que se desconoce el número de buenas entradas. Nuestro objetivo es estimar tal que Para pequeños . Podemos resolver para aplicando el algoritmo de estimación de fase cuántica en un operador unitario .
Desde y son los dos únicos valores propios de , podemos dejar que sus correspondientes autovectores sean y . Podemos encontrar el valor propio de , que en este caso equivale a estimar la fase . Esto se puede hacer aplicando transformadas de Fourier y operaciones unitarias controladas, como se describe en el algoritmo de estimación de fase cuántica. Con el presupuesto, podemos estimar , que a su vez estima .
Supongamos que queremos estimar con estado inicial arbitrario , en lugar de los autovectores y . Podemos hacer esto descomponiendo en una combinación lineal de y y luego aplicar el algoritmo de estimación de fase.
Referencias
- ^ Gilles Brassard; Peter Høyer (junio de 1997). "Un algoritmo de tiempo polinomial cuántico exacto para el problema de Simon". Actas del Quinto Simposio Israelí sobre Teoría de Computación y Sistemas . IEEE Computer Society Press: 12–23. arXiv : quant-ph / 9704027 . Código Bibliográfico : 1997quant.ph..4027B .
- ^ Grover, Lov K. (mayo de 1998). "Las computadoras cuánticas pueden buscar rápidamente utilizando casi cualquier transformación". Phys. Rev. Lett . 80 (19): 4329–4332. arXiv : quant-ph / 9712011 . Código Bibliográfico : 1998PhRvL..80.4329G . doi : 10.1103 / PhysRevLett.80.4329 .
- ^ Gilles Brassard; Peter Høyer; Michele Mosca; Alain Tapp (15 de mayo de 2000). "Estimación y amplificación de amplitud cuántica". arXiv : quant-ph / 0005055 .