Teoría Cuántica de la Complejidad Computacional

La teoría cuántica de la complejidad computacional 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. Esto se explica porque hay problemas que son clásicamente irresolubles en tiempo polinómico, pero que mediante un algoritmo cuántico podrían resolverse en tiempo polinómico. Es importante tener en cuenta que la teoría de la complejidad computacional es más que una revisión de la teoría clásica análoga: introduce sus propias clases y ha cambiado el paradigma de la computación. Las clases más importantes son la BQP y la QMA.

Introducción

Una clase de complejidad es una colección o 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. Esto se debe a que si no que un problema perteneciera o no a una clase dependería del estado actual de la tecnología. 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). Aunque existen evidencias que lo sugieren, la tesis moderna de Church-Turing sigue siendo un problema abierto en la teoría de la computación.

Antes hemos usado la notación $O(N)$. Es la llamada notación asintótica o notación de Landau. 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 o, con mayor generalidad, el número medio de unidades del recurso en cuestió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)$ y similarmente si el recurso no es el tiempo. Finalmente,$\Theta (T(N))$ engloba ambas clases.

Clases de complejidad computacional

Algunas clases relevantes son P, BPP, BQP, PP, y P-SPACE​. Para definir una clase de complejidad primero se define lo que se conoce como un problema de promesa (del inglés, promise problem). 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; por ejemplo, escoger una letra del alfabeto latino y responder a si es o no vocal (caso en que sí admite una respuesta binaria) o tomar una palabra del diccionario y decir cuántas vocales tiene (respuesta no binaria). 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).​

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 en el 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, al igual que el segundo: 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, a día de hoy se sabe que P ⊆ BPP ⊆ BQP ⊆ PP ⊆ P−SPACE.

QMA

La clase QMA o Quantum Merlin-Arthur es la extensión al mundo cuántico de la clase MA (Merlin-Arthur), que a su vez es un caso probabilístico de la NP: es decir, la conforman aquellos problemas que, si bien no pueden ser resueltos de manera eficiente, permiten comprobar de forma eficiente si un respuesta es o no solución de manera probabilística.

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.

El análisis superior muestra la necesidad de emplear ordenadores cuánticos para simular sistemas cuánticos: el tamaño de un espacio de Hilbert crece de manera exponencial con el número de partículas y se necesita un hardware con propiedades cuánticas para hacer una simulación eficiente. Alternativamente, también se pueden emplear otros sistemas cuánticos que ofrezcan un elevado grado de control y que guarden parecido con el otro sistema que se desea simular o emplear técnicas algorítmicas cuánticas. El primer caso es un ejemplo de simulación digital y tiene la ventaja de que es universal, mientras que el segundo caso se conoce como simulación analógica y aunque no es universal, suele ser más eficiente (porque se hace para un problema en concreto). Todo esto conforma el campo de la simulación cuántica​.

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); en esta línea, los llamados problemas de consulta, donde se tiene que comprobar que una lista de elementos satisfaga una o varias propiedades, son de especial interés porque ilustran el poder superior que ofrecen los algoritmos cuánticos​.

Algoritmo de Grover

El algoritmo de Grover​​ es un algoritmo cuántico de búsqueda: dada una lista de N elementos, devuelve uno que se quiera 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. Esta reducción en la complejidad del problema es el resultado conjunto del principio de superposición cuántica y la interferencia cuántica.

Algoritmo de Deutsch-Jozsa

El algoritmo de Deutsch-Jozsa responde a la siguiente pregunta: dada una función $f:\{0,1\}\rightarrow {}\{0,1\}$, ¿es constante o balanceada? Que una función sea constante significa que siempre devuelve el mismo valor (en este caso, 1 o 0), mientras que sea balanceada significa que devuelve tantos ceros como unos 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 (esto dada la naturaleza del problema, ya que sabemos que la función es de un tipo u otro). 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. Este problema, si bien de aplicaciones prácticas limitadas, es interesante porque ilustra la mayor rapidez que generalmente tienen los algoritmos cuánticos.

La algoritmia cuántica necesita para su implementación un hardware cuántico, lo que a día de hoy supone un problema por las limitaciones tecnológicas existentes. Existen algoritmos híbridos que combinan algoritmos cuánticos y clásicos, de tal modo que algunos pasos los realiza un ordenador clásico con un algoritmo clásico y otras etapas las realiza uno cuántico empleando algoritmia cuántica. Esta forma de trabajo está muy extendida en el aprendizaje automático cuántico, como los Quantum Hamiltonian Based Models​.

Encriptado RSA y computación cuántica

Detrás de la criptografía existen dos objetivos: por un lado, proteger la información frente a los ataques de aquellos que quisieran acceder a ella sin un permiso dado; por el otro, acceder a información ajena. De este modo, es importante desde un punto de vista defensivo idear protocolos para encriptar la información, que garanticen la creación de claves que sean seguras. Desde un punto de vista ofensivo el deseo es elaborar técnicas algorítmicas que permitan averiguar dichas claves.

La mayoría de protocolos de encriptado clásicos se basan en la descomposición de un número en sus factores primos. Este es un problema de alta dificultad computacional y los algoritmos clásicos consisten en idear estrategias óptimas para averiguar los factores y romper así la clave. Por ejemplo, 323.593.250.087 y 599.287.024.067 son los dos números primos y su producto es 193.925.235.852.806.718.843.829. Esta es la idea detrás del protocolo de encriptado RSA (llamado así por Ron Rivest, Adi Shamir y Leonard Adleman).

La fortaleza del protocolo se basa en que averiguar la clave es un problema de complejidad exponencial, pero esto solo es cierto si se trabaja con técnicas algorítmicas clásicas. Se puede probar que existen algoritmos cuánticos que pueden resolver el problema de forma eficiente, lo que ha convertido el reto tecnológico de diseñar un ordenador cuántico en un asunto de seguridad para las diferentes naciones.

Véase también

• Teoría de la complejidad computacional 
• Clases de complejidad
• Clase P
• Computación cuántica
• Máquina de Turing
• Máquina de Turing universal
• Alan Turing
• Tesis de Church-Turing
• [1]
• Anexo:Problemas no resueltos de las ciencias de la computación
• Criptografía cuántica

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.
• https://scottaaronson.com/ web personal del profesor Aaronson.
• https://www.scottaaronson.com/showcase2/report/adam-bookatz.pdf se exploran los problemas computacionales QMA-completos.
• https://documents.epfl.ch/groups/i/ip/ipg/www/2016-2017/Calcul_Quantique/chapter3corrected.pdf documento en el que se expone el modelo circuital de la computación cuántica.