Algoritmo de conteo cuántico

Algoritmo cuántico para contar soluciones a problemas de búsqueda.

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 determinado. 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 la estimación estadística, la física estadística, las redes, etc. En cuanto a la computación cuántica , se necesita la capacidad de realizar un conteo cuántico de manera eficiente para poder 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 existencia cuántica (es decir, decidir si existe alguna solución) como un caso especial.

El algoritmo fue ideado 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 el número 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 se deben inspeccionar todos los elementos (considere un caso en el que 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

Como 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 dos valores propios . ^{[2] : 253} ${\displaystyle G}$ ${\displaystyle e^{\pm i\theta }}$

Estimando el valor de θ

De aquí en adelante, seguimos el esquema del algoritmo de estimación de fase cuántica : aplicamos operaciones de Grover controladas seguidas de transformada cuántica inversa de Fourier ; y según el análisis encontraremos la mejor aproximación de bits al número real (perteneciente a los valores propios del operador 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 vectores propios del operador Grover (mientras que en el algoritmo de estimación de fase cuántica original, el segundo registro es el vector propio requerido). Esto significa que con cierta probabilidad aproximamos y con cierta probabilidad 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, suponiendo que ), 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 en 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

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}$

Acelerar problemas NP-completos

El algoritmo de conteo cuántico se puede utilizar para acelerar la solución de problemas que son NP-completos .

Un ejemplo de 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 sencilla al problema del ciclo hamiltoniano es comprobar, para cada orden de los vértices de , si se trata de un ciclo hamiltoniano o no. La búsqueda en todos los ordenamientos posibles de los vértices del gráfico se puede realizar 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 , solo queremos saber si lo es o no. ^{[5] : 147} ${\displaystyle M}$ ${\displaystyle M\neq 0}$

Una solución trivial a este problema es utilizar directamente el algoritmo de conteo cuántico: el algoritmo produce , comprobando si obtenemos la respuesta al problema de existencia. Este enfoque implica cierta información general porque no estamos interesados ​​en el valor de . La estimación de la fase cuántica se puede optimizar para eliminar esta sobrecarga. ^{[5] : 148} ${\displaystyle M}$ ${\displaystyle M\neq 0}$ ${\displaystyle M}$

Si no está interesado en el control de la probabilidad de error, utilizar una configuración con una pequeña cantidad 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}$

Problema de prueba de relaciones cuánticas

Pruebas de relaciones cuánticas . es una extensión de la prueba de existencia cuántica, decide si se puede encontrar al menos una entrada en la base de datos que cumpla la relación con un determinado valor de referencia. ^[6] Por ejemplo, devuelve SÍ si la base de datos contiene algún valor mayor que 5; de lo contrario, devuelve NO. Las pruebas de relaciones cuánticas combinadas con la búsqueda logarítmica clásica forman un algoritmo de búsqueda cuántica mínimo/máximo eficiente. ^{[5] : 152  [7]} ${\displaystyle QRT(value,relation)}$ ${\displaystyle QRT(5,>)}$

Ver también

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

Referencias

1. 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. S2CID  14147978.{{cite book}}: CS1 maint: location (link)
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, Giuliano; Strini, Giulio Casati, Giuliano (2004). Principios de información y computación cuántica (Reimpreso. Ed.). Nueva Jersey [ua]: Científico mundial. ISBN 978-9812388582.{{cite book}}: CS1 maint: multiple names: authors list (link)
4. Cleve, R.; Ekert, A.; Maquiavelo, C.; Mosca, M. (8 de enero de 1998). "Revisión de los algoritmos cuánticos". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería . 454 (1969): 339–354. arXiv : quant-ph/9708016 . Código Bib : 1998RSPSA.454..339C. doi :10.1098/rspa.1998.0164. S2CID  16128238.
5. Imre, Sandor; Balazs, Ferenc (enero de 2005). Computación cuántica y comunicaciones: un enfoque de ingeniería . Wiley. ISBN 978-0470869024.
6. Elegativamente, Sara; Imre, Sandor (2021). "Optimización cuántica restringida para la gestión de la distribución de recursos". Revista internacional de aplicaciones y ciencias informáticas avanzadas . 12 (8).
7. Imre, Sandor (2007). "Pruebas de existencia cuántica y su aplicación para encontrar valores extremos en bases de datos sin clasificar". Transacciones IEEE en computadoras . 56 (5): 706–710. doi :10.1109/TC.2007.1032. S2CID  29588344.

enlaces externos

• Implementación del algoritmo de conteo cuántico con Classiq