¿Algoritmo de Grover y su relación con las clases de complejidad?

Me estoy confundiendo sobre el algoritmo de Grover y su conexión con las clases de complejidad.

El algoritmo de Grover encuentra y el elemento en una base de datos de (tal que ) de elementos con llama al oráculo.N = 2 n f ( k ) = 1 ∼ $k$$N=2^n$$f(k)=1$

Entonces tenemos el siguiente problema:

Problema: Encuentre una en la base de datos tal quef ( k ) = $k$$f(k)=1$

Ahora soy consciente de que este no es un problema de decisión y, por lo tanto, nuestras definiciones normales de clase de complejidad , etc., no se aplican realmente. Pero tengo curiosidad por saber cómo definiríamos la clase de complejidad en tal caso, ¿y si se hace con respecto a o ?NP N $\text{P}$$\text{NP}$$N$$n$

Además, el algoritmo de Grover se puede usar como una subrutina. He leído en varios lugares que el algoritmo de Grover no cambia la clase de complejidad como un problema, ¿hay alguna forma heurística de ver esto?

Resumen

• Existe una teoría de la complejidad de los problemas de búsqueda (también conocidos como problemas de relación). Esta teoría incluye clases llamadas FP , FNP y FBQP que tratan de resolver problemas de búsqueda con diferentes tipos de recursos.
• A partir de los problemas de búsqueda, también puede definir problemas de decisión, lo que le permite relacionar los problemas de búsqueda con las clases habituales P , NP y BQP .
• Ya sea que considere la versión de búsqueda de la versión de decisión del problema, la forma en que considere la entrada al problema de Búsqueda no estructurada determinará qué límites superiores puede poner en su complejidad.

La complejidad de los problemas de relación.

Como observa, el problema de Grover resuelve un problema de búsqueda , que en la literatura de complejidad a veces también se conoce como un problema de relación . Es decir, es un problema del siguiente tipo:

La estructura de un problema de búsqueda general.
Dada una entrada una relación binaria , encuentre a tal que mantenga.R y R ( x , y $x$$R$$y$$R(x,y)$

Las clases de complejidad FP y FNP se definen en términos de tales problemas, donde en particular uno está interesado en el caso donde tiene longitud como máximo una función polinómica de la longitud de , y donde la relación puede por sí misma se calculará en una cantidad de tiempo limitada por algún polinomio en la longitud de .x R ( x , y ) ( x , y $y$$x$$R(x,y)$$(x,y)$

En particular: el ejemplo del problema de 'búsqueda en la base de datos' para el que generalmente se aplica la búsqueda de Grover se puede describir de la siguiente manera.

Búsqueda no estructurada.
Dado un oráculo de entrada tal que para alguna función , encuentre un tal que . O | un ⟩ | b ⟩ = | un ⟩ | b ⊕ f ( a ) ⟩ f : { 0 , 1 } m → { 0 , 1 } y O | y ⟩ | 0 ⟩ = | y ⟩ | 1 $\mathcal O: \mathcal H_2^{\otimes m+1} \!\to \mathcal H_2^{\otimes m+1}$$\mathcal O \lvert a \rangle \lvert b \rangle = \lvert a \rangle \lvert b \oplus f(a) \rangle$$f: \{0,1\}^m \to \{0,1\}$$y$$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Aquí, el oráculo mismo es la entrada al problema: desempeña el papel de , y la relación que estamos calculando es R ( O , y $x$

Supongamos que, en lugar de un oráculo, se nos proporciona una entrada específica que describe cómo se debe calcular la función , entonces podemos considerar a qué clase de complejidad pertenece este problema. Como indica , la clase de complejidad apropiada que obtenemos depende de cómo se proporciona la entrada.$x$$f$pyramids

• Suponga que la función de entrada se proporciona como una base de datos (como a veces se describe el problema), donde cada entrada a la base de datos tiene cierta longitud . Si es la longitud de la cadena utilizada para describir la base de datos completa , entonces la base de datos tiene entradas. Entonces es posible buscar exhaustivamente en toda la base de datos consultando cada una de las entradas en secuencia, y detenerse si encontramos una entrada tal que . Suponiendo que cada consulta a la base de datos toma algo como tiempo, este procedimiento se detiene en el tiempon x N = n / ℓ N y f ( y ) = 1 O ( log N ) ⊆ O ( log n ) O ( N log N ) ⊆ O ( n log n $\ell$$n$$x$$N = n\big/\ell$$N$$y$$f(y) = 1$$O(\log N) \subseteq O(\log n)$$O(N \log N) \subseteq O(n \log n)$, por lo que el problema está en FP .

  Suponiendo que la búsqueda en la base de datos se puede realizar en superposición coherente, el algoritmo de Grover permite que este problema esté en FBQP . Sin embargo, como FP  ⊆  FBQP , la búsqueda exhaustiva clásica también demuestra que este problema está en FBQP . Todo lo que obtenemos (hasta factores de registro) es una aceleración cuadrática debido a un ahorro en el número de consultas a la base de datos.
  
  

• Suponga que la función de entrada se describe sucintamente, mediante un algoritmo de tiempo polinómico que toma una especificación y un argumento calculasobre una base estándar, , donde puede ser mucho más grande que . Un ejemplo sería donde especifica la forma CNF de alguna función booleana para , en cuyo caso podemos evaluar eficientemente en una entrada y ∈ { 0 , 1 } m O : H m + 1$x \in \{0,1\}^n$$y \in \{0,1\}^m$$\mathcal O : \mathcal H_2^{m+1} \!\to \mathcal H_2^{m+1}\!$m Ω ( log n ) x f : { 0 , 1 } m → { 0 , 1 } m ∈ O ( n ) f ( y ) y ∈ { 0 , 1 } m $\lvert y \rangle\lvert b \rangle$$m$$\Omega(\log n)$$x$$f: \{0,1\}^m \to \{0,1\}$$m \in O(n)$$f(y)$$y \in \{0,1\}^m$y de ese modo evaluar eficientemente en estados de base estándar. Esto pone el problema en FNP .$\mathcal O$

  Dado un procedimiento para evaluar desde en el tiempo para , el algoritmo de Grover resuelve el problema de la búsqueda no estructurada de en el tiempo . Esto no es polinomial en , por lo que no es suficiente para poner este problema en FBQP : solo obtenemos una aceleración cuadrática, aunque esto sigue siendo un ahorro potencialmente enorme de tiempo de cálculo, suponiendo que la ventaja proporcionada por el algoritmo de Grover no se pierda la sobrecarga requerida para el cálculo cuántico tolerante a fallas.( x , y ) O ( p ( n ) ) n = | x | O O ( p ( n ) $f(y)$$(x,y)$$O(p(n))$$n = \lvert x \rvert$$\mathcal O$⊆O(p(n)$O(p(n) \sqrt{2^m})$ $\subseteq O(p(n) \sqrt{2^n})$$n$
  
  

En ambos casos, la complejidad se determina en función de la longitud de la cadena *, que especifica cómo calcular el oráculo . En el caso de que represente una tabla de consulta, tenemos , en cuyo caso el rendimiento en función de es similar al rendimiento en función de ; pero en el caso de que especifique de manera sucinta , y , el mensaje general de que Grover resuelve el problema en$n$$x$$\mathcal O$$x$$N = n\big/\ell$$N$$n$$x$$\mathcal O$$N \in O(2^{n/2})$$O(\sqrt N)$ las consultas oscurecen el mensaje más detallado de que este algoritmo sigue siendo tiempo exponencial para una computadora cuántica.

Complejidad de decisión por problemas de relación

Hay una forma directa de obtener problemas de decisión a partir de problemas de relación, que es bien conocido por la teoría de los problemas completos de NP : convertir el problema de búsqueda en una cuestión de la existencia de una solución válida.

La versión de decisión de un problema de búsqueda general.
Dada una entrada una relación binaria , determine si cumple.$x$$R$$\exists y: R(x,y)$

La clase de complejidad NP se puede definir esencialmente en términos de tales problemas, cuando la relación es eficientemente computable: los problemas completos NP más famosos (CNF-SAT, HAMCYCLE, 3-COLORING) se refieren a la mera existencia de una solución válida para Un problema de relación eficientemente verificable. Este cambio de producir soluciones a simplemente afirmar la existencia de soluciones es también lo que nos permite describir versiones de factorización entera que están en BQP (preguntando si existen factores no triviales, en lugar de preguntar por los valores de factores no triviales) .$R$

En el caso de la búsqueda no estructurada, nuevamente qué clase de complejidad describe mejor el problema depende de cómo esté estructurada la entrada. Determinar si existe una solución a un problema de relación puede reducirse a encontrar y verificar una solución a ese problema. Por lo tanto, en el caso de que la entrada sea una cadena especifica el oráculo como una tabla de búsqueda, el problema de la búsqueda no estructurada está en P ; y más generalmente si especifica un medio eficiente de evaluar el oráculo, el problema está en NP . También es posible que haya una forma de determinar si existe$x$$x$ una solución para la búsqueda no estructurada que lo hace sin encontrar una solución, aunque en general no está claro cómo hacerlo de una manera que ofrezca una ventaja sobre la búsqueda real de una solución.

Complejidad de Oracle

Me visiblemente han ido cambiando de hablar sobre el oráculo , de manera que una entrada se puede utilizar para especificar (y evalúo) el oráculo . Pero, por supuesto, la forma principal en la que consideramos el algoritmo de Grover es como un resultado de oráculo en el que evaluar el oráculo toma un solo paso de tiempo y no requiere especulación. ¿Cómo consideramos la complejidad del problema en este caso?$\mathcal O$$x$$\mathcal O$

En este caso, estamos tratando con un modelo relativizado de cómputo, en el que evaluar este oráculo específico (que, recuerden, es la entrada al problema) es una operación primitiva. Este oráculo se define en todos los tamaños de entrada: para considerar el problema al buscar cadenas de longitud , debe especificar que está considerando cómo actúa el oráculo matemático en las entradas de longitud , lo que de nuevo se haría considerando la longitud de una cadena booleana tomada como entrada. En este caso, la forma en que presentaríamos el problema podría ser la siguiente.$\mathcal O$$n$$\mathcal O$$n$$x$

Buscar no estructurada en relación con Oracle . $\mathcal O$
Dada una entrada de longitud ,$x = 11\cdots 1$$n$

• encuentre un (problema de relación) o$y \in \{0,1\}^n$

• determinar si existe un (problema de decisión)$y \in \{0,1\}^n$

tal que .$\mathcal O \lvert y \rangle \lvert 0 \rangle = \lvert y \rangle \lvert 1 \rangle$

Este problema está en (para el problema de decisión) o (para el problema de relación), dependiendo de la versión del problema que desee considerar. Debido a que el algoritmo de Grover no es un algoritmo de tiempo polinómico, no se sabe que este problema esté en o . De hecho, podemos decir algo más fuerte, como pronto veremos.$\mathsf{NP}^{\mathcal O}$$\mathsf{FNP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$$\mathsf{FBQP}^{\mathcal O}$

La razón por la que pasé por alto la descripción real, basada en Oracle, de la búsqueda no estructurada fue para tocar su punto de complejidad, y en particular para tocar la cuestión del tamaño de entrada . La complejidad de los problemas depende en gran medida de cómo se especifican las entradas: como una especificación sucinta (en el caso de cómo se especifica una función en CNF-SAT), como una especificación explícita (en el caso de una tabla de búsqueda para un función), o incluso como un número entero especificado en unario, es decir, como la longitud de una cadena de 1s como arriba (como en "Búsqueda no estructurada relativa a Oracle " arriba).$\mathcal O$

Como podemos ver en el último caso, si tratamos la entrada solo como un oráculo, la situación parece un poco poco intuitiva, y ciertamente hace imposible hablar sobre las formas en que se puede realizar la "base de datos". Pero una virtud de considerar la versión relativizada del problema, con un oráculo real, es que podemos probar cosas que de lo contrario no tenemos idea de cómo probar. Si pudiéramos demostrar que la versión de decisión del sucinto problema de búsqueda no estructurada estaba en BQP , entonces podríamos darnos cuenta de un enorme avance en la computación práctica; y si pudiéramos demostrar que el problema de decisión no estaba realmente en BQP , entonces habríamos demostrado que P ≠ PSPACE, lo que sería un gran avance en la complejidad computacional. Tampoco sabemos cómo hacerlo. Pero para el problema relativizado, podemos mostrar que hay oráculos para los cuales la versión de decisión de "Búsqueda no estructurada relativa a " está en pero no en . Esto nos permite mostrar que, si bien la computación cuántica es potencialmente poderosa, hay razones para esperar que BQP probablemente no contenga NP , y que la versión de relación de Búsqueda no estructurada en particular es poco probable que esté contenida en FBQP sin imponer fuertes restricciones sobre cómo La entrada está representada.$\mathcal O$$\mathcal O$$\mathsf{NP}^{\mathcal O}$$\mathsf{BQP}^{\mathcal O}$

Las clases de complejidad generalmente se definen con respecto al tamaño de la entrada. Los tamaños relevantes aquí son (el número de qubits en los que dejas que funcione el algoritmo de Grover) y un número que aún no has mencionado, llámalo , de bits necesarios para describir la subrutina generalmente conocida como el oráculo. Por lo general, el oráculo se implementará de manera eficiente de una manera que se escala polinomialmente en , que es el caso, por ejemplo, si codifica un problema típico de satisfacción booleana en el oráculo.$n$$m$$n$

En cualquier caso, no obtienes una ganancia en la clase de complejidad usando el algoritmo de Grover: se requieren exponencialmente muchas operaciones cuánticas, típicamente , para resolver un problema que podríamos aplicar fuerza bruta en muchos pasos exponencialmente, típicamente , en una computadora clásica de todos modos. Esto significa que los problemas conocidos (p. Ej., EXPTIME) o sospechosos (p. Ej., NP) de tomar tiempo de ejecución exponencial aún requerirán tiempo de ejecución exponencial.$m*2^{n/2}$$m*2^{n-1}$

Sin embargo, a los físicos les gusta apelar a la noción de que esto sigue siendo una aceleración exponencial sin un equivalente clásico conocido (o de hecho fácilmente concebible). Esto es más evidente en el ejemplo de la base de datos donde la función oracle es una búsqueda en la base de datos y el algoritmo de Grover puede hacer que uno necesite muchas menos búsquedas que datos en la base de datos. En este sentido, todavía hay una ventaja significativa, aunque está completamente perdida en la imagen de la clase de complejidad.

Todo el recuento se realiza en términos de , el número de bits necesarios para describir la entrada.$n$

Definimos la clase de problemas de la siguiente manera (o, esta es una forma de hacerlo):$\text{NP}$

Supongamos que es una función que acepta una entrada y devuelve un solo valor de bit 0 o 1. La tarea es que debe encontrar si un valor dado de devuelve un 1. Sin embargo, el problema tiene una estructura adicional: si , se garantiza que existe una prueba (de tamaño ) tal que una función solo si , y la función es eficientemente computable (es decir, tiene un tiempo de ejecución de .$f(x)$$x\in\{0,1\}^n$$x$$f(x)=1$$p_x$$m\sim\text{poly}(n)$$g(x,p_x)=1$$f(x)=1$$g(x,p_x)$$\text{poly}(n)$

Permítanme dar algunos ejemplos (¿quizás estos son lo que estaban pidiendo aquí ?):

• Paridad: responde la pregunta '¿es impar?'. Esto es tan trivial (solo tome el bit menos significativo de ) que se calcula de manera eficiente directamente, y por lo tanto una prueba es innecesaria, .$f(x)$$x$$x$$f(x)$$g(x,p_x)=f(x)$

• Números compuestos: responde a la pregunta '¿es la representación decimal de un número compuesto?'. Una posible prueba en la dirección sí (solo tiene que demostrar esa dirección) es dar un par de factores. por ejemplo, , . Entonces simplemente implica multiplicar los factores y verificar que son iguales a .$f(x)$$x$$x=72$$p_x=(8,9)$$g(x,p)$$x$

• Isomorfismo de gráfico: dados dos gráficos y (aquí contiene la descripción de ambos gráficos), responde a la pregunta '¿son los dos gráficos isomorfos?'. La prueba es una permutación: una declaración de cómo los vértices en corresponden con los de . La función verifica que es una permutación válida, permuta los vértices de utilizando la permutación especificada y verifica que la matriz de adyacencia sea la misma que la de .$G_1$$G_2$$x$$f(x)$$p_x$$G_1$$G_2$$g(x,p_x)$$p_x$$G_1$$G_2$

• Buscaminas : el viejo juego favorito integrado en Windows (y otros) se puede expresar así. Imagine un tablero de buscaminas que está parcialmente descubierto, por lo que algunas células son desconocidas, y algunas células han sido descubiertas para revelar cuántas minas hay en las células vecinas. Todo esto está integrado en la variable . hace la pregunta "¿hay una asignación válida de minas en la región descubierta?". La prueba, es simplemente una de esas asignaciones de minas. Esto se verifica fácilmente utilizando que simplemente garantiza la coherencia con cada restricción conocida.$x$$f(x)$$p_x$$g(x,p_x)$

Todos estos problemas están en porque se ajustan a la definición de una solución eficientemente verificable. Se sabe que algunos de ellos también están en : ya hemos dicho que las pruebas extrañas están en . Los números compuestos también lo son, porque es eficiente verificar si un número es primo usando la prueba de primalidad AKS .$\text{NP}$$\text{P}$$\text{P}$

No se sabe que el isomorfismo gráfico y el buscaminas estén en . De hecho, se sabe que el buscaminas es -completo, es decir, si se puede resolver de manera eficiente, cada problema en está en . Muchas personas sospechan que , y por lo tanto, Minesweeper tendría instancias que tardan más que el tiempo polinómico en resolverse.$\text{P}$$\text{NP}$$\text{NP}$$\text{P}$$\text{P}\neq\text{NP}$

Una posible forma de resolver un problema de es, para una fija , simplemente probar todas las pruebas posibles hasta una longitud máxima , y ver si hay una solución satisfactoria, es decir, buscar una solución . Obviamente, eso lleva tiempo , ya que hay exponencialmente muchos elementos para buscar, cada uno de los cuales requiere un tiempo polinómico para calcular. Esto se puede mejorar implementando la búsqueda de Grover: solo buscamos una solución (es decir, el válido se convierte en el elemento marcado), y esto lleva un tiempox p x m = poli ( n ) g ( x , p x ) = 1 O ( 2 m poli ( m ) ) g ( x , p x ) = 1 p x O ( 2 m / 2 poli ( m ) $\text{NP}$$x$$p_x$$m=\text{poly}(n)$$g(x,p_x)=1$$O(2^m\text{poly}(m))$$g(x,p_x)=1$$p_x$$O(2^{m/2}\text{poly}(m))$. Esto es masivamente más rápido, pero no cambia la evaluación de si el tiempo de ejecución es polinómico o algo peor; No se ha convertido en un algoritmo de tiempo polinómico. Por ejemplo, el isomorfismo gráfico debería buscar en todas las permutaciones posibles. Buscaminas tendría que buscar todas las posibles asignaciones de minas en cuadrados descubiertos.

Por supuesto, algunas veces, la estructura adicional del problema permite diferentes soluciones que no requieren la búsqueda de todas las pruebas posibles. Allí, la búsqueda de Grover es de menor utilidad, o incluso no, para nosotros, pero podría ser que podamos idear un algoritmo de tiempo polinómico de otra manera. Por ejemplo, el caso de las pruebas compuestas: clásicamente, encontrar los factores de un número parece ser difícil: no podemos hacer mucho mejor que probar todos los factores posibles, por lo que hacer uso de esa forma de prueba no ayuda mucho, pero , como ya se mencionó, la pregunta se puede resolver de manera eficiente a través de otra ruta, la prueba de primalidad AKS.

Olvídate de la base de datos. El algoritmo de Grover resuelve el problema booleano de satisfacción , a saber:

Tiene un circuito booleano con entradas y una sola salida. Las salidas del circuito para una configuración única de bits de entrada, de lo contrario son las salidas . Encuentra la configuración de bits de entrada.1 $n$$1$$0$

Se sabe que el problema es NP-completo.