Usuario:Jim Beaumont/Taller/Complejidad Computacional Cuántica

La complejidad computacional cuántica es un subcampo de la teoría de la complejidad computacional que estudia las diferentes clases de complejidad que existen desde la perspectiva de la computación cuántica. La computación cuántica, que es un modelo de computación que se beneficia de la superposición y entrelazamiento cuántico, conduce a una redefinición de las clases de complejidad tradicionales, puesto que hay problemas clásicamente irresolubles en tiempo polinómico que mediante un algoritmo cuántico podrían resolverse en tiempo polinómico. La teoría de la complejidad computacional es más que una revisión de la teoría clásica análoga, ya que introduce sus propias clases. Las más importantes son la BQP y la QMA.

Introducción

Una clase de complejidad es un familia de problemas computacionales que pueden ser resueltos sujetos a unas mismas constricciones en el tamaño de los recursos, generalmente como recurso más importante y que sirve para delimitar las clases se toma el tiempo de cálculo necesario. Así, por ejemplo, la clase P abarca todos aquellos problemas que puedan ser resueltos por una máquina de Turing clásica en un tiempo polinómico. Por tiempo polinómico se refiere a que el tiempo de resolución escala polinómicamente con el tamaño del problema (por ejemplo, en el algoritmo de búsqueda el tiempo escala como $O(N)$ . Cuánticamente, las clases de complejidad se definen similarmente a partir del tiempo que le tomaría a una máquina de Turing cuántica o a un ordenador cuántico en un modelo circuital resolver los problemas.

Uno de los objetivos de la teoría cuántica de la complejidad es relacionar las clases de complejidad de las dos teorías. Es importante notar que el tiempo de resolución se ha definido mediante modelos de computación universales tanto para el caso clásico como para el cuántico, porque que un problema pertenezca o no a una clase, dependerá de la potencia de la tecnología actual. Uno de los aspectos más importantes de la teoría es que podría probar la falsedad de la tesis moderna de Church-Turing, según la cual todo problema computacional podría ser simulado en tiempo polinómico por una máquina de Turing probabilística (que diera la solución con precisión finita), puesto que hay evidencias que lo sugieren.

Antes hemos usado la notación $O(N)$ . Es la llamada notación asintótica. Más generalmente, para una función $T(N)$ , que un problema sea de una complejidad $O(T(N))$ significa que es necesario un tiempo $cT(N)$ para resolverlo, donde $c$ es una constante que indica el tiempo medio por iteración y $N$ es el tamaño o número de bits involucrados en el problema. Si un problema es $\Omega (T(N))$ , entonces puede ser resuelto en un tiempo menor que $cT(N)$ . Finalmente, $\Theta (T(N))$ engloba ambas clases.

Clases de complejidad computacional

Algunas clases relevantes son P, BPP, BQP, PP, y P-SPACE^[1]. Para definir una clase de complejidad primero se define un problema de promesa. Un problema de promesa es un problema computacional que recibe como variable de entrada una cadena de caracteres de entre un conjunto de posibles entradas y que admite por solución una respuesta que no es necesariamente sí o no. El problema queda definido entonces como un par de conjuntos $(A_{yes},A_{no})$ , donde $A_{yes}$ es el conjunto de instancias para cuya entrada se obtuvo un sí y $A_{no}$ aquel para el que se obtuvo un no. Ambos conjuntos no pueden tener instancias en común, por lo que $A_{yes}\cap A_{no}=\emptyset$ . Además, la unión de ambos conjuntos no constituye, según lo dicho antes, el conjunto de todas las posibles respuestas a dicho problema de promesa.

BQP

Formalmente, la clase BQP engloba aquellos problemas que pueden ser resueltos por una máquina de Turing cuántica en tiempo polinómico con una probabilidad de error en la solución inferior a 1/3 (las siglas provienen de bounded error, quantum, polynomial time).^[2]

Esta clase es el análogo cuántico de la clase BPP (bounded error, probabilistic, polynomial time), que abarca los problemas computacionales que una máquina de Turing probabilística puede resolver con un error finito. Se sabe que la primera engloba a la segunda, es decir, que BPP ⊆ BQP, pero el recíproco BPP ⊇ BQP se piensa que es falso, aunque todavía no ha sido probado. Dentro de las clases de complejidad, BQP ⊆ PP, aquellos problemas para los que una máquina de Turing probabilística puede dar una solución en tiempo polinómico con probabilidad de error menor de 1/2. Las relaciones de inclusión entre todas las clases y el lugar que ocupa BQP entre ellas se desconoce, pero sí se sabe que P ⊆ BQP ⊆ P-SPACE; esto es, todo problema que pueda ser resuelto eficientemente por un ordenador clásico de forma determinista puede ser resuelto por uno cuántico de forma probabilística. Sin embargo esta última no incluye ningún problema que pueda ser resuelto por una máquina de Turing clásica y determinista en un tiempo ilimitado, pero empleando una memoria de tamaño polinómico. También existen pruebas de que P ⊂ BQP, que es más restrictivo que la relación de inclusión superior, ya que entonces habría problemas que un ordenador cuántico podría resolver de manera eficiente (pero no necesariamente determinista) que un ordenador clásico determinista no sería capaz de hacer de manera eficiente.

Dos ejemplos los encontramos en la factorización en enteros y del cálculo del logaritmo discreto; el primero incluye la factorización en números primos y es por lo tanto relevante para la criptografía: esto es, clásicamente no es posible obtener una clave criptográfica en un tiempo razonable (en una escala humana), pero, cuánticamente, sí que lo es. Sobre la relación entre BQP y NP, la familia de problemas para los que se puede comprobar si una supuesta solución lo es de verdad en un tiempo polinómico y de manera determinista, se cree que son disjuntos. Como consecuencia de esta creencia se piensa que BQP tampoco está incluido en el conjunto NP-completo. De hecho, BQP ⊇ NP-completo implicaría BQP ⊇ NP. En resumen, de momento se sabe que P ⊆ BPP ⊆ BQP ⊆ PP ⊆ P−SPACE.

Simulación clásica de sistemas cuánticos

No existe una forma eficiente de simular un circuito cuántico por medio de puertas lógicas y canales clásicos. Sí que es posible, sin embargo, simularlo en tiempo exponencial. Si el circuito tiene $S(N)$ cúbits y $T(N)$ puertas cuánticas, serían necesarias $O(2S(N)T(N)^{3})$ puertas clásicas. El factor $2S(N)$ viene simplemente de que es necesario almacenar el estado de los $S(N)$ cúbits. Cada uno de los cúbits, cuyo espacio de Hilbert tiene dimensión 2, debe ser conocido con una cierta precisión, que tomamos como $O(T(N))$ , teniendo en cuenta la acción de todas las puertas. Cada puerta se representa como una matriz unitaria $2S(N)$ -cuadrada, por lo que el número de operaciones realizadas (y que deben ser almacenadas) es de ese mismo orden y consecuentemente, son necesarios $O(2S(N)T(N)^{2})$ para almacenar la información de la acción de una sola puerta. Si ahora tenemos en cuenta que hay $T(N)$ puertas, obtenemos $O(2S(N)T(N)^{3})$ bits o, equivalentemente, $O(2S(N)T(N)^{3})$ puertas clásicas necesarias para llevar a cabo la simulación.

Complejidad cuántica en problemas de consulta

La computación cuántica tiene dos grandes beneficios frente a la clásica: por un lado, permite resolver de manera eficiente algunos problemas de complejidad exponencial y, por otro lado, optimiza otros problemas para los que ya se conoce una solución eficiente. Sobre este segundo punto, es interesante conocer cuantas llamadas a la función que da una solución aproximada al problema son necesarias para darle a este una respuesta satisfactoria (i.e, por encima de un cierto umbral de precisión).

Algoritmo de Grover

El algoritmo de Grover es un algoritmo cuántico de búsqueda: dada una lista de N elementos, devuelve uno que queramos encontrar, pero lo hace de manera probabilística. Además, la probabilidad de haber acertado en la búsqueda oscila de forma periódica. Por lo tanto, por encima de un cierto número de iteraciones, iterar más no solo consumiría más recursos, sino que no devolvería, en general, el elemento deseado con la máxima probabilidad. Mientras que los algoritmos clásicos de búsqueda tienen una complejidad $O(N)$ , la del de Grover es $O({\sqrt {N}})$ , lo que supone un notable aumento en su eficiencia.

Algoritmo de Deutsch-Jozsa

Este algoritmo responde a la pregunta de si una función $f:\{0,1\}\rightarrow {}\{0,1\}$ es constante o balanceada (esto segundo significa que devuelve tantas veces 0 como 1 cuando opera sobre una cadena de $N$ bits). Clásicamente, la complejidad del problema es $2^{N-1}+1$ , ya que como poco se deben consultar la mitad de los bits. Por el contrario, en el caso cuántico existe una solución que, por medio del paralelismo cuántico, da una solución con una única consulta o llamada al oráculo.

Véase también

Referencias

↑ Alberto Galindo, y Miguel Ángel Martin-Delgado (2002). «Information and computation: Classical and quantum aspects». Reviews of Modern Physics, 74(2), 347.
↑ Aaronson, Scott, et al. (19 de diciembre de 2014). «The Space "Just Above" BQP». arXiv:1412.6507 [quant-ph].

Enlaces externos

https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.2.030316 Artículo en el que se enuncian y demuestran varios resultados de la teoría de la complejidad computacional cuántica, además de discutir la relevancia de esta disciplina en otras ramas de la física y las ciencias de la computación.
https://www.youtube.com/watch?v=moPtwq_cVH8&ab_channel=MITOpenCourseWare Vídeo del MIT Open Course en el que se hace una introducción a la teoría de la complejidad computacional clásica.
https://www.youtube.com/watch?v=0jrybODBUpA&ab_channel=YCombinator Vídeo en el que Scott Aaronson habla sobre la teoría de la complejidad computacional en el nuevo marco de la computación cuántica.

[1] Alberto Galindo, y Miguel Ángel Martin-Delgado (2002). «Information and computation: Classical and quantum aspects». Reviews of Modern Physics, 74(2), 347.

[2] Aaronson, Scott, et al. (19 de diciembre de 2014). «The Space "Just Above" BQP». arXiv:1412.6507 [quant-ph].

[1]

[2]