El algoritmo de conteo cuántico es un algoritmo cuántico para contar de manera eficiente el número de soluciones para un problema de búsqueda dado. El algoritmo se basa en el algoritmo de estimación de fase cuántica y en el algoritmo de búsqueda de Grover .
Los problemas de conteo son comunes en diversos campos, como estimación estadística, física estadística, redes, etc. En cuanto a la computación cuántica , se necesita la capacidad de realizar el conteo cuántico de manera eficiente para usar el algoritmo de búsqueda de Grover (porque ejecutar el algoritmo de búsqueda de Grover requiere saber cuántos existen soluciones). Además, este algoritmo resuelve el problema de la existencia cuántica (es decir, decidir si existe alguna solución) como un caso especial.
El algoritmo fue diseñado por Gilles Brassard , Peter Høyer y Alain Tapp en 1998.
El problema
Considere un conjunto finito de tamaño y un set de "soluciones" (que es un subconjunto de ). Definir:
En otras palabras, es la función indicadora de.
Calcule la cantidad de soluciones . [1]
Solución clásica
Sin ningún conocimiento previo sobre el conjunto de soluciones (o la estructura de la función ), una solución determinista clásica no puede funcionar mejor que , porque todos los elementos de debe ser inspeccionado (considere un caso donde el último elemento a inspeccionar es una solución).
El algoritmo
Configuración
La entrada consta de dos registros (a saber, dos partes): el superiorqubits comprenden el primer registro , y el inferiorlos qubits son el segundo registro .
Crear superposición
El estado inicial del sistema es . Después de aplicar la operación de puerta Hadamard de múltiples bits en cada uno de los registros por separado, el estado del primer registro es
y el estado del segundo registro es
un estado de superposición igual en la base computacional.
Operador Grover
Porque el tamaño del espacio es y la cantidad de soluciones es , podemos definir los estados normalizados: [2] : 252
Tenga en cuenta que
que es el estado del segundo registro después de la transformada de Hadamard.
La visualización geométrica del algoritmo de Grover muestra que en el espacio bidimensional abarcado por y , el operador de Grover es una rotación en sentido antihorario ; por lo tanto, se puede expresar como
en la base ortonormal . [2] : 252 [3] : 149
De las propiedades de las matrices de rotación sabemos quees una matriz unitaria con los dos valores propios . [2] : 253
Estimando el valor de
De aquí en adelante, seguimos el esquema del algoritmo de estimación de fase cuántica : aplicamos operaciones controladas de Grover seguidas de la transformada cuántica de Fourier inversa ; y según el análisis encontraremos el mejoraproximación de bits al número real (perteneciente a los valores propios del operador Grover) con probabilidad superior a . [4] : 348 [3] : 157
Tenga en cuenta que el segundo registro está en realidad en una superposición de los autovectores del operador de Grover (mientras que en el algoritmo de estimación de fase cuántica original, el segundo registro es el autovector requerido). Esto significa que, con cierta probabilidad, nos aproximamos, y con cierta probabilidad, nos aproximamos ; esas dos aproximaciones son equivalentes. [2] : 224–225
Análisis
Asumiendo que el tamaño del espacio es al menos el doble del número de soluciones (es decir, suponiendo que ), un resultado del análisis del algoritmo de Grover es: [2] : 254
Por tanto, si encontramos , también podemos encontrar el valor de (porque es conocida).
El error
está determinada por el error dentro de la estimación del valor de . El algoritmo de estimación de fase cuántica encuentra, con alta probabilidad, el mejor-proximación de bits de ; esto significa que si es lo suficientemente grande, tendremos , por eso . [2] : 263
Usos
El algoritmo de búsqueda de Grover para un número inicialmente desconocido de soluciones
En el algoritmo de búsqueda de Grover, el número de iteraciones que se deben realizar es . [2] : 254 [3] : 150
Por tanto, si es conocido y se calcula mediante el algoritmo de conteo cuántico, el número de iteraciones para el algoritmo de Grover se calcula fácilmente.
Acelerando problemas NP-completos
El algoritmo de conteo cuántico se puede utilizar para acelerar la solución de problemas NP-completos .
Un ejemplo de un problema NP-completo es el problema del ciclo hamiltoniano , que es el problema de determinar si una gráfica tiene un ciclo hamiltoniano .
Una solución simple al problema del ciclo hamiltoniano es verificar, para cada orden de los vértices de , ya sea un ciclo hamiltoniano o no. La búsqueda a través de todos los posibles ordenamientos de los vértices del gráfico se puede hacer con el conteo cuántico seguido del algoritmo de Grover, logrando una aceleración de la raíz cuadrada, similar al algoritmo de Grover. [2] : 264 Este enfoque encuentra un ciclo hamiltoniano (si existe); para determinar si existe un ciclo hamiltoniano, el algoritmo de conteo cuántico en sí es suficiente (e incluso el algoritmo de existencia cuántica, que se describe a continuación, es suficiente).
Problema de existencia cuántica
El problema de existencia cuántica es un caso especial de conteo cuántico en el que no queremos calcular el valor de , pero solo queremos saber si o no. Una solución trivial a este problema es utilizar directamente el algoritmo de conteo cuántico: el algoritmo produce, así que comprobando si obtenemos la respuesta al problema de la existencia. Este enfoque implica cierta información general porque no estamos interesados en el valor de.
El uso de una configuración con un pequeño número de qubits en el registro superior no producirá una estimación precisa del valor de , pero será suficiente para determinar si es igual a cero o no. [2] : 263
Ver también
Referencias
- ^ Brassard, Gilles; Hoyer, Peter; Tapp, Alain (13 al 17 de julio de 1998). Autómatas, lenguajes y programación (25º Coloquio Internacional ed.). ICALP'98 Aalborg, Dinamarca: Springer Berlin Heidelberg. págs. 820–831. arXiv : quant-ph / 9805082 . doi : 10.1007 / BFb0055105 . ISBN 978-3-540-64781-2.Mantenimiento de CS1: ubicación ( enlace )
- ^ a b c d e f g h yo Chuang, Michael A. Nielsen e Isaac L. (2001). Computación cuántica e información cuántica (Repr. Ed.). Cambridge [ua]: Universidad de Cambridge. Prensa. ISBN 978-0521635035.
- ^ a b c Benenti, Giuliano; Strini, Giulio Casati, Giuliano (2004). Principios de la computación cuántica y la información (reimpreso. Ed.). Nueva Jersey [ua]: World Scientific. ISBN 978-9812388582.
- ^ Inteligente.; Ekert, A .; Macchiavello, C .; Mosca, M. (8 de enero de 1998). "Algoritmos cuánticos revisitados". Actas de la Royal Society A: Ciencias Matemáticas, Físicas e Ingeniería . 454 (1969). arXiv : quant-ph / 9708016 . Código bibliográfico : 1998RSPSA.454..339C . doi : 10.1098 / rspa.1998.0164 .