Algoritmo de conteo cuántico

Sin ningún conocimiento previo sobre el conjunto de soluciones${\displaystyle B}$(o la estructura de la función)${\displaystyle f}$), una solución determinista clásica no puede tener un rendimiento mejor que${\displaystyle \Omega (N)}$, porque todos los${\displaystyle N}$elementos de${\displaystyle \{0,1\}^{n}}$debe ser inspeccionado (considere un caso en el que el último elemento a inspeccionar sea una solución).

La entrada consta de dos registros (es decir, dos partes): el superior${\displaystyle p}$Los cúbits comprenden el primer registro y el inferior.${\displaystyle n}$Los cúbits son el segundo registro .

El estado inicial del sistema es${\displaystyle |0\rangle ^{\otimes p}|0\rangle ^{\otimes n}}$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 {\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.

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

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

Tenga en cuenta que

${\displaystyle {\sqrt {\frac {NM}{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 transformación de Hadamard.

La visualización geométrica del algoritmo de Grover muestra que en el espacio bidimensional abarcado por${\displaystyle |\alpha \rangle }$y${\displaystyle |\beta \rangle }$, el operador Grover es una rotación en sentido antihorario ; por lo tanto, se puede expresar como

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

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

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

A partir de aquí, seguimos el esquema del algoritmo de estimación de fase cuántica : aplicamos operaciones de Grover controladas seguidas de la transformada inversa de Fourier cuántica ; y según el análisis , encontraremos el mejor${\displaystyle p}$aproximación de bits al número real${\displaystyle \theta }$(pertenecientes a los valores propios)${\displaystyle e^{\pm i\theta }}$del operador Grover) con una probabilidad mayor que${\displaystyle {\frac {4}{\pi ^{2}}}}$. ^{[ 4 ] : 348 [ 3 ] : 157}

Nótese que el segundo registro se encuentra en realidad en una superposición de los autovectores del operador de Grover (mientras que en el algoritmo original de estimación de fase cuántica, el segundo registro es el autovector requerido). Esto significa que, con cierta probabilidad, aproximamos${\displaystyle \theta }$y con cierta probabilidad, nos aproximamos${\displaystyle 2\pi -\theta }$; esas dos aproximaciones son equivalentes. ^{[ 2 ] : 224–225}

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

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

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

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${\displaystyle \theta }$El algoritmo de estimación de fase cuántica encuentra, con alta probabilidad, el mejor${\displaystyle p}$aproximación de bits de${\displaystyle \theta }$; esto significa que si${\displaystyle p}$es lo suficientemente grande, tendremos${\displaystyle \Delta \theta \approx 0}$, por eso${\displaystyle \vert \Delta M\vert \approx 0}$. ^{[ 2 ] : 263}

En el algoritmo de búsqueda de Grover, el número de iteraciones que se deben realizar es${\displaystyle {\frac {\pi }{4}}{\sqrt {\frac {N}{M}}}}$. ^{[ 2 ] : 254 [ 3 ] : 150}

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

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 consiste en determinar si un grafo${\displaystyle G=(V,E)}$tiene un ciclo hamiltoniano .

Una solución simple al problema del ciclo hamiltoniano es comprobar, para cada ordenación de los vértices de${\displaystyle G}$, sea o no un ciclo hamiltoniano. La búsqueda a través de todos los posibles ordenamientos de los vértices del grafo se puede realizar con 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 propio algoritmo de conteo cuántico es suficiente (e incluso el algoritmo de existencia cuántica, descrito más adelante, es suficiente).

El problema de existencia cuántica es un caso especial de conteo cuántico donde no queremos calcular el valor de${\displaystyle M}$, pero solo deseamos saber si${\displaystyle M\neq 0}$o no. ^{[ 5 ] : 147}

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

Si no le interesa el control de la probabilidad de error, entonces usar una configuración con un número pequeño de cúbits en el registro superior no producirá una estimación precisa del valor de${\displaystyle \theta }$, pero bastará para determinar si${\displaystyle M}$es igual a cero o no. ^{[ 2 ] : 263}

Pruebas de relaciones cuánticas${\displaystyle QRT(valor,relación)}$. 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${\displaystyle QRT(5,>)}$Devuelve SÍ si la base de datos contiene algún valor mayor que 5; de lo contrario, devuelve NO. La prueba de relación cuántica combinada con la búsqueda logarítmica clásica forma un algoritmo eficiente de búsqueda cuántica min/max. ^{[ 5 ] : 152 [ 7 ]}