Algoritmo de conteo cuántico

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 , la capacidad de realizar el conteo cuántico de manera eficiente es necesaria para utilizar 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 conjunto de "soluciones" (que es un subconjunto de ). Definir:${\displaystyle \{0,1\}^{n}}$${\displaystyle N=2^{n}}$${\displaystyle B}$${\displaystyle \{0,1\}^{n}}$

${\displaystyle {\begin{cases}f:\left\{0,1\right\}^{n}\to \{0,1\}\\f(x)={\begin{cases}1&x\in B\\0&x\notin B\end{cases}}\end{cases}}}$

En otras palabras, es la función indicadora de .${\displaystyle f}$${\displaystyle B}$

Calcula la cantidad de soluciones . ^[1]${\displaystyle M=\left\vert f^{-1}(1)\right\vert =\vert B\vert }$

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 deben ser inspeccionados (considere un caso donde el último elemento a inspeccionar es una solución) .${\displaystyle B}$${\displaystyle f}$${\displaystyle \Omega (N)}$${\displaystyle N}$${\displaystyle \{0,1\}^{n}}$

El algoritmo

Circuito de conteo cuántico

Configuración

La entrada consta de dos registros (es decir, dos partes): los qubits superiores comprenden el primer registro y los qubits inferiores son el segundo registro .${\displaystyle p}$${\displaystyle n}$

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${\displaystyle |0\rangle ^{\otimes p}|0\rangle ^{\otimes n}}$

${\displaystyle {\frac {1}{2^{p/2}}}(|0\rangle +|1\rangle )^{\otimes p}}$

y el estado del segundo registro es

${\displaystyle {\frac {1}{2^{n/2}}}(|0\rangle +|1\rangle )^{\otimes n}={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle }$

un estado de superposición igual en la base computacional.

Operador Grover

Debido a que el tamaño del espacio es y el número de soluciones es , podemos definir los estados normalizados: ^{[2] : 252}${\displaystyle \left\vert \{0,1\}^{n}\right\vert =2^{n}=N}$${\displaystyle \left\vert B\right\vert =M}$

${\displaystyle |\alpha \rangle ={\frac {1}{\sqrt {N-M}}}\sum _{x\notin B}{|x\rangle },\qquad {\text{and}}\qquad |\beta \rangle ={\frac {1}{\sqrt {M}}}\sum _{x\in B}{|x\rangle }.}$

Tenga en cuenta que

${\displaystyle {\sqrt {\frac {N-M}{N}}}|\alpha \rangle +{\sqrt {\frac {M}{N}}}|\beta \rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}{|x\rangle },}$

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${\displaystyle |\alpha \rangle }$${\displaystyle |\beta \rangle }$

${\displaystyle G={\begin{bmatrix}\cos \theta &-\sin \theta \\\sin \theta &\cos \theta \end{bmatrix}}}$

en la base ortonormal . ^{[2] : 252 [3] : 149}${\displaystyle \{|\alpha \rangle ,|\beta \rangle \}}$

Por las propiedades de las matrices de rotación sabemos que es una matriz unitaria con los dos valores propios . ^{[2] : 253}${\displaystyle G}$ ${\displaystyle e^{\pm i\theta }}$

Estimando el valor de ${\displaystyle \theta }$

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 la mejor aproximación de bits al número real (perteneciente a los autovalores del operador de Grover) con probabilidad superior a . ^{[4] : 348 [3] : 157}${\displaystyle p}$ ${\displaystyle \theta }$${\displaystyle e^{\pm i\theta }}$${\displaystyle {\frac {4}{\pi ^{2}}}}$

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}${\displaystyle \theta }$${\displaystyle 2\pi -\theta }$

Análisis

Suponiendo que el tamaño del espacio es al menos el doble del número de soluciones (es decir, asumiendo eso ), un resultado del análisis del algoritmo de Grover es: ^{[2] : 254}${\displaystyle N}$${\displaystyle M\leq {\tfrac {N}{2}}}$

${\displaystyle \sin {\frac {\theta }{2}}={\sqrt {\frac {M}{N}}}.}$

Por lo tanto, si encontramos , también podemos encontrar el valor de (porque se conoce).${\displaystyle \theta }$${\displaystyle M}$${\displaystyle N}$

El error

${\displaystyle {\frac {\vert \Delta M\vert }{N}}=\left\vert \sin ^{2}\left({\frac {\theta +\Delta \theta }{2}}\right)-\sin ^{2}\left({\frac {\theta }{2}}\right)\right\vert }$

está determinado por el error dentro de la estimación del valor de . El algoritmo de estimación de fase cuántica encuentra, con alta probabilidad, la mejor aproximación de bits de ; esto significa que si es lo suficientemente grande, tendremos , por lo tanto . ^{[2] : 263}${\displaystyle \theta }$${\displaystyle p}$${\displaystyle \theta }$${\displaystyle p}$${\displaystyle \Delta \theta \approx 0}$${\displaystyle \vert \Delta M\vert \approx 0}$

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}${\displaystyle {\frac {\pi }{4}}{\sqrt {\frac {N}{M}}}}$

Por lo tanto, si se conoce y se calcula mediante el algoritmo de conteo cuántico, el número de iteraciones del algoritmo de Grover se calcula fácilmente.${\displaystyle N}$${\displaystyle M}$

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 .${\displaystyle G=(V,E)}$

Una solución simple al problema del ciclo hamiltoniano es verificar, para cada orden de los vértices de , si es 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).${\displaystyle G}$

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 . Una solución trivial a este problema es usar directamente el algoritmo de conteo cuántico: el algoritmo cede , por lo que al verificar si obtenemos la respuesta al problema de existencia. Este enfoque implica cierta información general porque no estamos interesados ​​en el valor de .${\displaystyle M}$${\displaystyle M\neq 0}$${\displaystyle M}$${\displaystyle M\neq 0}$${\displaystyle M}$

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}${\displaystyle \theta }$${\displaystyle M}$

Ver también

• Algoritmo de estimación de fase cuántica
• El algoritmo de Grover
• Problema de conteo (complejidad)

Referencias

1. Brassard, Gilles; Hoyer, Peter; Tapp, Alain (13 a 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.
2. 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.
3. Benenti, Guiliano; 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.
4. Cleve, R .; 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 .