Teoría de la Complejidad en Computación Cuántica

Teoría de la Complejidad en Computación Cuántica Jesús Camacho Moro Teoría de la Complejidad en Computación Cuántica Jesús Camacho Moro Memoria presentada como parte de los requisitos para la obtención del título de Máster Universitario en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. José María Tornero Sánchez Índice general English Abstract 1 1. Máquinas de Turing cuánticas 3 1.1. Definición ................................. 4 1.2. Máquinauniversal............................. 8 1.2.1. Máquinas bien formadas . . . . . . . . . . . . . . . . . . . . . 8 1.2.2. Reversibilidad........................... 9 1.2.3. Herramientas........................... 11 1.2.4. Cambiosdebase ......................... 12 1.2.5. Matrices especiales . . . . . . . . . . . . . . . . . . . . . . . . 18 1.2.6. Construcción de una máquina universal . . . . . . . . . . . . 19 2. Clases de complejidad 29 2.1. Complejidad en tiempo en el paradigma cuántico . . . . . . . . . . . 29 2.2. Clases de complejidad cuánticas . . . . . . . . . . . . . . . . . . . . . 30 2.3. Comparación con clases de complejidad clásicas . . . . . . . . . . . . 30 2.3.1. 𝐍𝐏 y𝐁𝐐𝐏 ............................. 35 ii teoría de la complejidad en computación cuántica 3. Algoritmos 39 3.1. De máquina universal a puertas cuánticas . . . . . . . . . . . . . . . . 39 3.2. Algoritmo de Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . 41 4. Conclusión 45 Abstract During the first half of the 20th century, the need of faster calculations brought the first computers to our world. Those machines were designed following the same abstract blueprint: a structure called Turing Machine. Since then, the creation and improvement of algorithms solving well known mathematical problems have continued. Following the same path, scientists from different areas studied the complexity theory around classical computers. In 1982 American physicist Richard Feynman stepped out of this paradigm when he realized that quantum systems could not be efficiently simulated using any of the previous computers. British physicist David Deutsch introduced a new machine based on this idea in 1985, named quantum Turing machines, given the similarities with Turing machines and the fact that it took advantage of the principles of quantum mechanics. After the formal definition, quantum complexity theory and algorithms appeared hand by hand. In this memory we will take a look into the construction of an universal quantum Turing machine and its associated complexity theory, which is still an open and fruitful field of current research. Next, we will present an algoritm stated by David Deutsch and Australian mathematician Richard Jozsa in 1992 as an example of the intrinsic power inside quantum Turing machines. 1 Máquinas de Turing cuánticas A lo largo de la primera mitad del siglo XX el mundo vio avanzar a la teoría de la computabilidad a pasos agigantados. En 1933, Kurt Gödel y Jacques Herbrand definieron de manera formal la clase de funciones recursivas. Posteriormente, Alonzo Church creó las funciones 𝜆-calculables, a priori sin relación con las recursivas. Al mismo tiempo, Alan Turing construye el modelo teórico de máquinas por el que es conocido y crea un nuevo grupo de funciones que son las que hoy conocemos por Turing computables. Church y Turing probaron que estas tres clases de funciones coinciden en realidad. Además, afirmaron que dichas clases de funciones computables definidas formalmente coinciden con la noción intuitiva de funciones calculables de forma eficiente. Al igual que la teoría de la computabilidad recae sobre la tesis Church-Turing, la teoría de complejidad computacional depende de una versión moderna de esta misma tesis. En ella se asegura que cualquier modelo de computación "razonable" puede ser simulado eficientemente en una máquina de Turing probabilística. Entendemos por razonable aquella máquina que puede ser físicamente realizable. El problema que se plantea con este tipo de máquinas de Turing reside en el uso de modelos físicos clásicos para la realización de una misma. Es por ello que la llegada de grandes avances en el campo de la física durante el siglo XX, como el modelo de partículas cuántico, permitieron abordar el problema de forma distinta. Este nuevo enfoque para la definición de nuevos modelos computacionales dirigido por resultados como el propuesto por Feynman [7] en 1982 tuvo gran impacto. En el artículo citado afirmaba que la simulación de un sistema físico cuántico en una máquina de Turing probabilística requería un coste exponencial. La posibilidad de definir un nuevo modelo que pudiera ser representado físicamente por algún tipo de máquina y cuyo poder computacional fuera mayor abría un nuevo mundo. 10 teoría de la complejidad en computación cuántica Lema 1.1.Dada una MTC 𝑀con función de transición 𝛿,𝑀está bien formada si y sólo si la aplicación de configuraciones 𝛿′que revierte la acción de 𝛿y conjuga las amplitudes deshace la computación de 𝛿. Es claro que esta formalización generaliza el concepto clásico, y como apuntaba Deutsch [5], las MT reversibles son una subclase de MTC. Este concepto de reversibilidad encaja muy bien con las MTC bien formadas. Ya conocemos una caracterización global de MTC bien formadas gracias a la proposición 1.1. Más adelante, exigiremos condiciones locales a las máquinas cuánticas y así podremos trabajar con un conjunto de máquinas más pequeño. Teorema 1.1. Cualquier MT reversible es también una MTC bien formada. Demostración. La función de transición 𝛿de una MT determinista lleva el estado actual y el símbolo leído a un triplete. Podemos plantearlo como enviar la superposición unitaria de amplitud 1para dicho triplete y 0en el resto. Entonces, 𝛿es también una función de transición y define una MTC. La matriz de evolución en el tiempo correspondiente a dicha MTC tiene como entradas 0o1. Puesto que cada configuración tiene un solo predecesor en MT reversibles, esta matriz representa realmente una permutación. Por lo tanto, cualquier superposición de configuraciones ∑𝑖𝛼𝑖|𝑐𝑖⟩es enviada por la matriz de evolución temporal a otra superposición ∑𝑖𝛼𝑖|𝑐′ 𝑖⟩. Es decir, preserva la norma. Teorema 1.2 (Sincronización). Sea 𝑓una aplicación entre cadenas que puede ser computada en tiempo polinomial determinista y tal que la longitud de 𝑓(𝑥)depende solo de la longitud de 𝑥. Entonces existe una MT reversible en forma normal estacionaria que dada una entrada 𝑥, devuelve 𝑓(𝑥)en tiempo sólo dependiente de la longitud de 𝑥. Si 𝑓es una función de cadenas en cadenas tal que 𝑓y𝑓−1 pueden ser computadas en tiempo polinomial determinista y tal que la longitud de 𝑓(𝑥)sólo depende de la longitud de 𝑥, entonces existe una MT reversible en forma normal, estacionaria que dada una entrada 𝑥, produce la salida 𝑓(𝑥)con un tiempo de ejecución que depende únicamente de la longitud de 𝑥. Demostración. La prueba se puede encontrar en el texto [4]. 1. máqinas de turing cuánticas 11 1.2.3 Herramientas Introducimos varios lemas técnicos de gran utilidad. Con ellos podremos reordenar las cintas de forma adecuada para poder, entre otras cosas, encadenar la acción de varias máquinas. Lema 1.2.Dada una MTC 𝑀= (Σ, 𝑄, 𝛿)y un conjunto cualquiera Σ′, existe una MT de dos tramos 𝑀′= (Σ × Σ′, 𝑄, 𝜎′)tal que su primer tramo se comporta como 𝑀 mientras que deja su segundo tramo sin modificar. Lema 1.3.Dada una MTC 𝑀= (Σ1× … × Σ𝑘, 𝑄, 𝛿)y una permutación 𝜋∶ [1, 𝑘]→ [1, 𝑘], existe una MTC 𝑀′= (Σ𝜋(1) ×…×Σ𝜋(𝑘), 𝑄, 𝛿′)tal que 𝑀′se comporta igual que 𝑀excepto que sus tramos se permutan según indica 𝜋. Ambos resultados son directos, por lo que no daremos demostración. Lema 1.4.Existe una MT 𝑀estacionaria, reversible en forma normal y una constante 𝑐con las siguientes propiedades: para cualquier entrada entera positiva 𝑘en notación binaria, 𝑀trabaja en tiempo (𝑘log𝑐𝑘)y para con su cinta sin modificar. Más aún, 𝑀tiene un estado especial 𝑞∗tal que al introducir 𝑘,𝑀visita el estado 𝑞∗ exactamente 𝑘veces y cada una de ellas con la cabeza lectora/escritora en la celda inicial. Demostración. Usando el Teorema 1.2 de sincronización podemos construir una MT reversible 𝑀1= (Σ, 𝑄, 𝛿)estacionaria, en forma normal, con tres tramos y trabajando en tiempo polinomial en log 𝑘. Esta máquina devuelve (𝑏′, 𝑥 + 1, 𝑘)al introducir (𝑏, 𝑥, 𝑘),𝑏∈ {0,1}, donde 𝑏′es el opuesto de 𝑏si 𝑥= 0 o𝑘− 1 (no al mismo tiempo) y𝑏′=𝑏en otro caso. Si llamamos 𝑞0,𝑞𝑓a los estados inicial y final de 𝑀1, construimos una máquina reversible 𝑀2como sigue. Denotamos por 𝑞𝑎,𝑞𝑧a los nuevos estados inicial y final a los que exigimos una serie de propiedades: 1. Comenzando en el estado 𝑞𝑎con un 0en el primer tramo, 𝑀2mueve a izquierda y vuelve a derecha, cambiando el símbolo 0por 1, además de entrar en el estado 𝑞0. 2. Cuándo entramos en el estado 𝑞𝑓con un 0en el primer tramo, 𝑀2mueve a izquierda y vuelve a derecha, además de entrar en el estado 𝑞0. 12 teoría de la complejidad en computación cuántica 3. Cuándo entramos en el estado 𝑞𝑓con un 1en el primer tramo, 𝑀2mueve a izquierda y vuelve a derecha, cambiando el símbolo 1por 0y parando. En estas condiciones, con entrada (0,0, 𝑘)𝑀2avanza a izquierda y vuelve a derecha entrando en el estado 𝑞0y modificando la cinta en (1,0, 𝑘). Entonces la máquina 𝑀1 cambia dicho contenido por (0,1, 𝑘)y para en estado 𝑞𝑓. Cuándo 𝑀2se encuentra en estado 𝑞𝑓con 0en el primer tramo, entra al estado 𝑞0y repite el proceso, Continuando con este bucle, 𝑀2trabajará 𝑘−1 veces más hasta llegar a (1, 𝑘, 𝑘). En dicho momento, 𝑀2cambia el contenido a (0, 𝑘, 𝑘)y para. Es decir, para la entrada (0,0, 𝑘)la máquina 𝑀2visita el estado 𝑞𝑓exactamente 𝑘veces, cada una de ellas con el cabezal en la celda inicial. Nuestra máquina objetivo 𝑀será la concatenación de 𝑀2entre dos MT reversibles, obtenidas mediante el Teorema de sincronización, al transformar 𝑘en (0,0, 𝑘)y(0, 𝑘, 𝑘)en 𝑘. Para completar la prueba basta construir una 𝑀2reversible, en forma normal que satisfaga las tres propiedades anteriores. Asociamos a 𝑀2el mismo alfabeto de 𝑀1y añadimos los estados 𝑞𝑎, 𝑞𝑏, 𝑞𝑦, 𝑞𝑧. La función de transición de 𝑀2será la misma en los estados 𝑄−𝑞𝑓y en el resto sólo dependerá del primer tramo de cinta. Describimos dicha función con la siguiente tabla: #01 𝑞𝑎(1, 𝑞𝑏, 𝐿) 𝑞𝑏(#, 𝑞0, 𝑅) 𝑞𝑓(0, 𝑞𝑏, 𝐿) (0, 𝑞𝑦, 𝐿) 𝑞𝑦(#, 𝑞𝑧, 𝑅) 𝑞𝑧(#, 𝑞𝑎, 𝑅) (0, 𝑞𝑎, 𝑅) (1, 𝑞𝑎, 𝑅) Las comprobaciones de que 𝑀2está efectivamente en forma normal, al igual que las propiedades exigidas, se dejan para el lector interesado. 1.2.4 Cambios de base La herramienta de cambiar bases a lo largo de las computaciones en una MTC es muy útil para probar varios resultados centrales de la teoría de computación cuántica. Generalmente, trataremos de pasar a una base ortonormal para la función de transición y así simular una MTC general con una que sea unidireccional. De hecho, también nos servirá para extender MTC parciales a MTC bien formadas. Esto nos permite seguir el guión comentado al principio de la sección. 1. máqinas de turing cuánticas 13 Lema 1.5.Dada una MTC 𝑀= (Σ, 𝑄, 𝛿)y un conjunto de vectores 𝐵∈ 𝐂𝑄que forme una base ortonormal de 𝐂𝑄, existe una MTC 𝑀′= (Σ, 𝑄, 𝛿′)que evoluciona igual que 𝑀bajo un cambio de base entre 𝑄y𝐵. Demostración. Sea 𝑀= (Σ, 𝑄, 𝛿)una MTC y sea 𝐵una base ortonormal de  𝐂𝑄. Como 𝐵es base ortonormal, esta define una transformación unitaria entre el espacio de superposiciones de estados en 𝑄y el espacio de superposiciones de estados en 𝐵. Es decir, para cada 𝑝∈𝑄tenemos la aplicación |𝑝⟩→∑ 𝑣∈𝐵⟨𝑝|𝑣⟩⋅|𝑣⟩ De igual forma, tenemos una transformación unitaria entre los espacios de configuraciones. En este caso, una configuración con estado 𝑝se asocia con la configuración correspondiente cuyo estado 𝑣aparezca con amplitud ⟨𝑝|𝑣⟩. Fijado un estado 𝑝y leyendo 𝜎, la máquina evoluciona en un paso a la siguiente superposición: 𝛿(𝑝, 𝜎) = ∑ 𝜏,𝑞,𝜎 𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑)|𝜏⟩|𝑞⟩|𝑑⟩. Con el cambio de bases, la superposición será: ∑ 𝜏,𝑣,𝜎 (∑ 𝑞⟨𝑞|𝑣⟩𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑))|𝜏⟩|𝑣⟩|𝑑⟩. Puesto que el símbolo de estado |𝑣⟩|𝜎⟩de 𝑀′corresponde en 𝑀con la configuración ∑ 𝑝⟨𝑣|𝑝⟩|𝑝⟩|𝜎⟩, debemos tener en 𝑀′ 𝛿′(𝑝, 𝜎) = ∑ 𝑝⟨𝑣|𝑝⟩(∑ 𝜏,𝑣′,𝜎 (∑ 𝑞⟨𝑞|𝑣′⟩𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑)))|𝜏⟩|𝑣′⟩|𝑑⟩. Por lo tanto, 𝑀′se comportará como 𝑀bajo el cambio de base si definimos 𝛿′como hemos visto previamente. Dado que los vectores de 𝐵están contenidos en  𝐂𝑄, cada amplitud de 𝛿′estará en  𝐂. Además, el operador de evolución en el tiempo de 𝑀′que hemos definido preserva la norma 𝐿2por herencia de 𝛿bajo un cambio de base ortonormal. Por tanto, 𝛿′está bien definido. 14 teoría de la complejidad en computación cuántica Como ya vimos previamente, las MT reversibles son una buena base de trabajo. Este tipo de máquinas se caracterizaban por ser MTC bien formadas (Teorema 1.1), por lo que es conveniente que estudiemos con mayor detenimiento esta propiedad. Teorema 1.3. Una MTC 𝑀= (Σ, 𝑄, 𝛿)está bien formada si y sólo si satisface lo siguiente: 1. El vector de amplitudes que dejan cualquier par de estado y símbolo, tiene norma constante igual a 1: ∀𝑝, 𝜎 ∈𝑄× Σ ∑ 𝜏,𝑞,𝑑 |𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑)|2= 1 2. Las superposiciones con un símbolo de escritura, un estado de llegada y un movimiento son ortogonales para cualesquiera dos estados-símbolos distintos: ∀ (𝑝1, 𝜎1)≠(𝑝2, 𝜎2) ∈ 𝑄× Σ ∑ 𝜏,𝑞,𝑑 𝛿(𝑝1, 𝜎1, 𝜏, 𝑞, 𝑑)⋅𝛿∗(𝑝2, 𝜎2, 𝜏, 𝑞, 𝑑)=0 3. Si fijamos todos los parámetros de 𝛿salvo el nuevo estado, 𝛿describe una superposición de nuevos estados que deben ser consistentes con los datos fijados. El espacio de estados de superposiciones consiste en dos subespacios mutuamente ortogonales, uno para cada dirección, tales que cubren todo el espacio. ∀(𝑝1, 𝜎1, 𝜏1),(𝑝2, 𝜎2, 𝜏2) ∈ 𝑄× Σ × Σ 𝛿(𝑝1, 𝜎1, 𝜏1, 𝑞, 𝐿)⋅𝛿(𝑝2, 𝜎2, 𝜏2, 𝑞, 𝑅)=0 Demostración. Sea 𝑈el operador de evolución en el tiempo de una MTC 𝑀= (Σ, 𝑄, 𝛿). Sabemos por la Proposición 1.1 que 𝑀está bien formada si y sólo si existe 𝑈∗cumpliendo 𝑈∗⋅𝑈=𝐼o, equivalentemente, las columnas de 𝑈tienen norma uno y son mutuamente ortogonales. Obviamente, la primera condición es consecuencia directa. En general, configuraciones cuyas cintas difieren en una celda que no estén debajo de ninguna de las cabezas lectoras, o configuraciones cuyas cabezas lectoras no estén en la misma celda o exactamente a dos celdas de distancia, no pueden coincidir en la misma configuración en un solo paso. Por tanto, tales pares de columnas deben ser ortogonales y sólo tenemos que considerar las configuraciones en las que esto no ocurre. La segunda condición justamente especifica la ortogonalidad de pares de columnas de configuraciones que difieran solo en la que en el estado 𝑝1se lee 𝜎1 mientras que la otra pareja está en el estado 𝑝2y se lee 𝜎2. Finalmente, consideramos parejas de configuraciones con sus cabezas lectoras a dos celdas de distancia. Si quisiéramos pasar de una configuración a la otra en un 1. máqinas de turing cuánticas 15 sólo paso es porque como mucho difieren en sus estados y en el símbolo que vayan a escribir en la celda. La tercera condición precisamente especifica la ortogonalidad de parejas de columnas para configuraciones que son idénticas salvo que la cabeza lectora está desplazada exactamente dos celdas. La condición 3de separabilidad vista en el Teorema 1.3 nos permite simular cualquier MTC con una que sea unidireccional al aplicar un cambio de base. El mismo cambio nos permite completar cualquier función de transición parcial cuántica que preserve la norma. Es directo simular una MT determinista con otra que sea unidireccional. Simplemente dividimos los estados 𝑞en dos nuevos estados 𝑞𝑟y𝑞𝑙. El problema es que la máquina resultante no es reversible, puesto que perdemos la relación uno a uno entre estados. Para corregir esto damos el siguiente lema: Lema 1.6.Dados 𝑘conjuntos de estados 𝑄0,…, 𝑄𝑘−1, 𝑄𝑘=𝑄0y𝑘funciones de transición 𝛿𝑖∶𝑄𝑖× Σ → 𝐂Σ × 𝑄𝑖+1 × {𝐿,𝑅}que preserven la norma, existe una MTC bien formada 𝑀con conjunto de estados ⋃𝑖(𝑄𝑖, 𝑖)que son accesibles según indican las 𝑘funciones de transición. Demostración. Supongamos que tenemos 𝑘funciones de transición. Entonces tomamos 𝑀la MTC con el mismo alfabeto, con conjunto de estados dado por la unión de estados ⋃𝑖(𝑄𝑖, 𝑖)y con función de transición asociada a los 𝛿𝑖de la siguiente forma: 𝛿((𝑝, 𝑖), 𝜎) = ∑ 𝜏,𝑞,𝑑 𝛿𝑖(𝑝, 𝜎, 𝜏, 𝑞, 𝑑)|𝜏⟩|𝑞, 𝑖 + 1⟩|𝑑⟩. Claramente, la máquina 𝑀va saltando según indican 𝛿0,…, 𝛿𝑘−1 y su operador de evolución en tiempo preserva la norma por herencia de las 𝛿𝑖. Lema 1.7 (Unidireccional).Cualquier MTC 𝑀es simulada, con coste un factor de 5, por una MTC unidireccional 𝑀′. Además, si 𝑀se comporta bien y está en forma normal, 𝑀′también cumplirá dichas propiedades. Demostración. La clave está en la condición de separabilidad del las MTC bien formadas que vimos en el Teorema 1.3. Esto significa que podemos dividir 𝐂𝑄en dos subespacios mutuamente ortogonales 𝐂𝐿y𝐂𝑅tales que para cada 𝑞∈𝑄, 𝛿(𝑝1, 𝜎1, 𝜏1, 𝑞, 𝑑) ∈ 𝐂𝑑∀ (𝑝1, 𝜎1, 𝜏1) ∈ 𝑄× Σ × Σ, donde 𝐂𝑑representa el conjunto de amplitudes asociadas a la dirección 𝑑. 16 teoría de la complejidad en computación cuántica Como vimos en el Lema 1.5, bajo un cambio de base desde el conjunto de estados 𝑄al conjunto de estados 𝐵la nueva función de transición se define como 𝛿′(𝑣, 𝜎, 𝜏, 𝑣′, 𝑑) = ∑ 𝑝,𝑞 ⟨𝑣|𝑝⟩⟨𝑞|𝑣′⟩𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑). Así que, tomamos bases ortonormales 𝐵𝐿y𝐵𝑅de los espacios 𝐂𝐿y𝐂𝑅respectivamente y definimos 𝑀′= (𝜎, 𝐵𝐿∪𝐵𝑅, 𝛿′)como la MTC resultante del Lema 1.5 que evoluciona exactamente como 𝑀bajo el cambio de base desde 𝑄a𝐵=𝐵𝐿∪𝐵𝑅. Entonces cualquier estado en 𝑀′es accesible desde una única dirección. Para probar esta afirmación, observamos en primer lugar que para 𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑) ∈ 𝐵𝑑, con 𝑑∈ {𝐿, 𝑅}y𝑣=∑𝑞⟨𝑣|𝑞⟩|𝑞⟩, la condición de separabilidad implica que para todo 𝑣∈𝐵𝑑,∑ 𝑞 𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑)⟨𝑣|𝑞⟩∗= 0. Por tanto, para todo 𝑣, 𝜎, 𝜏, 𝑣′∈𝐵×Σ×Σ×𝐵𝑑, 𝛿′(𝑣, 𝜎, 𝜏, 𝑣′, 𝑑) = ∑ 𝑝⟨𝑣|𝑝⟩∑ 𝑞⟨𝑞|𝑣′⟩𝛿(𝑝, 𝜎, 𝜏, 𝑞, 𝑑)=0. Es decir, cualquier estado en 𝐵es accesible moviéndonos en una sola dirección. El problema de este proceso es que no nos asegura la simulación de 𝑀por parte de 𝑀′. Para solucionarlo, usamos 5pasos para simular cada uno de los de 𝑀e intercalar las 5funciones de transición que nos indica el Lema 1.6. 1. Mover a la derecha dejando la cinta y el estados sin modificar: 𝛿0(𝑝, 𝜎) = |𝜎⟩|𝑝⟩|𝑅⟩. 2. Cambiar de la base 𝑄a𝐵mientras nos desplazamos a la izquierda: 𝛿1(𝑝, 𝜎) = ∑ 𝑏∈𝐵⟨𝑝|𝑏⟩|𝜎⟩|𝑏⟩|𝐿⟩. 3. 𝑀′realiza un paso de la computación de 𝑀. Así que, 𝛿2es simplemente la función de transición 𝛿′que construimos antes. 4. Deshacemos el cambio de base mientras nos movemos a la izquierda: 𝛿3(𝑏, 𝜎) = ∑ 𝑏∈𝑄⟨𝑏|𝑝⟩|𝜎⟩|𝑝⟩|𝐿⟩. 1. máqinas de turing cuánticas 17 5. Mover a la derecha dejando la cinta y el estado sin modificar: 𝛿4(𝑝, 𝜎) = |𝜎⟩|𝑝⟩|𝑅⟩. Si construimos 𝑀′con conjunto de estados (𝑄×{0,1,4}∪(𝐵×{2,3}) usando el Lema 1.6 y fijando los estados inicial y final como (𝑞0,0),(𝑞𝑓,0) respectivamente, entonces 𝑀′simula 𝑀con coste un factor de 5. Debemos probar que todas las funciones de transición implicadas preservan la norma para que la máquina resultante sea bien formada. Está claro que 𝛿2=𝛿′cumple las condiciones porque las hereda de 𝛿. Como 𝛿0y𝛿4son deterministas y reversibles, también preservan la norma. Por último, 𝛿1y𝛿3cumplen por un lado las propiedades de longitud unitaria y ortogonalidad al ser un cambio de base, y por otro, son separables al realizar un movimiento en una sola dirección. Para terminar, nos falta probar que si 𝑀se comporta bien y está en forma normal, transmite dichas propiedades a 𝑀′. Supongamos por tanto que 𝑀se comporta bien y está en forma normal. Entonces existirá un 𝑇tal que transcurrido tiempo 𝑇la superposición incluye configuraciones con estado 𝑞𝑓con la cabeza lectora/escritora en la celda de salida y para cualquier tiempo previo las configuraciones no contienen a 𝑞𝑓. Esto significa que al introducir 𝑥en 𝑀′, las superposiciones tras 5𝑇pasos tiene la cabeza lectora/escritora en la celda de salida e incluyen sólo configuraciones con estado (𝑞𝑓,0), pero no lo incluyen en ningún tiempo previo. Por lo tanto, 𝑀′se comporta bien. Entonces para cada entrada 𝑥existe un 𝑇tal que 𝑀sucede 𝑇−1 superposiciones de configuraciones con estados en 𝑄⧵{𝑞0, 𝑞𝑓}y una superposición de configuraciones finales , todas ellas con estado 𝑞𝑓y la cabeza lectora/escritora en la celda inicial. De lo que se deduce que al introducir 𝑥en 𝑀′entramos en una serie de 5𝑇− 1 superposiciones de configuraciones con estados en 𝑄⧵{(𝑞𝑓,0),(𝑞0,4)}y una superposición de configuraciones finales con estado (𝑞𝑓,0) y la cabeza lectora/escritora sobre la celda inicial. De igual forma que antes, 𝑀′se comporta bien y nos permite intercambiar los estados (𝑞𝑓,0) y(𝑞0,4) para pasarla a forma normal sin alterar las computaciones de 𝑥por 𝑀′. Combinando reversibilidad con patrones de interferencia conseguimos simplificar en gran medida las máquinas a considerar. El efecto de interferencia se ilustra con el siguiente ejemplo: 18 teoría de la complejidad en computación cuántica Ejemplo 1.1.Consideramos la máquina dada por 𝑄= {𝑞},Σ = {0,1} y la función 𝛿(𝑞, 𝑏1, 𝑏2, 𝑞, 𝑅)=−1 √2si 𝑏1=𝑏2= 1 ó1 √2, y 𝛿= 0 en otro caso. Puesto que 𝛿cumple las condiciones del Teorema 1.3 trivialmente, se trata de una máquina bien formada. Si observamos las configuraciones 𝑐1,𝑐2que difieran solo en la cabeza lectora, nos vemos obligados a acabar en la misma configuración final asociada a0cuya amplitud es 1 √2. Por tanto, esta máquina tan simple exhibe las dificultades de interferencias. 1.2.5 Matrices especiales Definición 1.14. Una matriz 𝑑×𝑑unitaria 𝑀se dice casi trivial si satisface una de las siguientes condiciones: 𝑀es la identidad exceptuando una de las entradas de la diagonal, que es de la forma 𝑒𝑖𝜃 con 𝜃∈ [0,2𝜋]. 𝑀es la identidad exceptuando que tiene una submatriz de dimensión 2×2 definida por los índices 𝑖,𝑗, con 𝑖≠𝑗, que constituye una rotación de ángulo 𝜃∈ [0,2𝜋]. Es decir, si existe un 𝜃y𝑖≠𝑗tales que 𝑀𝑒𝑖= (cos 𝜃)𝑒𝑖+ (sin 𝜃)𝑒𝑗,𝑀𝑒𝑗= −(sin 𝜃)𝑒𝑖+ (cos 𝜃)𝑒𝑗y𝑀𝑒𝑘=𝑒𝑘en el resto. Observación 1.6.Describiremos las matrices casi triviales de la siguiente forma: Si 𝑀es del primer tipo, 𝑒𝑖𝜃 de dimensión 𝑗, lo denotaremos por (𝑗, 𝑗, 𝜃). Si 𝑀es del segundo tipo, con ángulo de rotación 𝜃, lo denotaremos por (𝑖, 𝑗, 𝜃). Para dichas matrices tenemos el siguiente lema técnico del cual encontramos la prueba en el texto de Bernstein y Vazirani [4]. Lema 1.8.Existe un algoritmo determinista que con entrada 𝑣∈𝐂𝑑y una cota 𝜀 > 0 computa matrices casi triviales 𝑈1,…, 𝑈2𝑑−1 tal que ‖(𝑈1⋯𝑈2𝑑−1𝑣−|𝑣|𝑒1)‖≤𝜀 donde 𝑒1es el vector unitario (1,0,…,0). El tiempo de computación de este algoritmo está acotado polinomialmente en 𝑑,log 1 𝜀y la longitud de la entrada. Observación 1.7.La norma usada en el lema anterior es ‖𝑀‖= m ax |𝑣|=1 |𝑀𝑣|. 1. máqinas de turing cuánticas 19 Otro tipo de matrices simples que nos interesará para aproximar matrices (y por tanto, evoluciones en tiempo de las máquinas) son las siguientes: Definición 1.15. Un operador lineal 𝑈se dice 𝜀-cercano a unitario si existe un operador unitario 𝑉tal que ‖𝑈−𝑉‖≤𝜀. Asociados a los operadores lineales tenemos siempre una matriz a la que podemos otorgar de una definición completamente análoga. Para dichas matrices, existe una serie de lemas técnicos con demostraciones simples. Por ello los dejaremos sin demostrar. En cualquier caso se puede encontrar el razonamiento en el texto de Bernstein y Vazirani [4]. Lema 1.9.Si una matriz compleja 𝑀de dimensión 𝑑es 𝜀-cercana a unitaria, entonces 1 − 𝜀≤|𝑀𝑖|≤1 + 𝜀, (1.1) ‖𝑀𝑖𝑀∗ 𝑗‖≤2𝜀+ 3𝜀2∀𝑖≠𝑗. (1.2) Entendemos por 𝑀𝑖la fila 𝑖-ésima de la matriz 𝑀. Lema 1.10.Si 𝑀es una matriz compleja de dimensión 𝑑×𝑑tal que |𝑚𝑖,𝑗|≤𝜀para todo 𝑖, 𝑗, entonces ‖𝑀‖≤𝑑𝜀. Definición 1.16. Se dice que una matriz compleja 𝑈es 𝑘-simple para sus primeras 𝑘filas y columnas si forman la matriz identidad Estas matrices actúan como puente entre las matrices casi triviales, que son similares a las 𝑘-simples, y otras más complejas de las que tengamos menos propiedades. 1.2.6 Construcción de una máquina universal Estamos en disposición de mostrar uno de los pilares fundamentales para alcanzar nuestro objetivo de construir una máquina universal. Para ello nos basaremos en todos los lemas que hemos descrito previamente, que trabajan con matrices sencillas, pero que tienen ciertamente grandes propiedades a la hora de acotar los tiempos de ejecución. Teorema 1.4. Existe un algoritmo determinista con tiempo de ejecución polinomial en 𝑑,log 1∕𝜀y la longitud de la entrada tal que al darle (𝑈, 𝜀)como entrada, 𝜀 > 0y𝑈 26 teoría de la complejidad en computación cuántica Teorema 1.6. Existe una MTC en forma normal tal que para cualesquiera MTC 𝑀bien formada, 𝜀 > 0y entero 𝑇,simula 𝑇pasos de 𝑀con precisión 𝜀y coste en tiempo polinomial en 𝑇y1∕𝜀. Demostración. El guión que seguiremos para esta prueba consiste en construir una MTC 𝑀′unidireccional con el Lema 1.7 que simule 𝑀con coste en tiempo un factor de orden 5. Posteriormente simular 𝑀′para tener la construcción completa. Este sería el proceso natural, pero nosotros probaremos primero la factibilidad de simular 𝑀′y luego volveremos al Lema 1.7. Supongamos que 𝑀= (Σ, 𝑄, 𝛿)es una MTC unidireccional y queremos simular nuestra MTC universal. Usaremos una cinta de nuestra MTC universal específicamente para simular la configuración actual de 𝑀. Dado que el alfabeto y conjunto de estados de 𝑀puede tener cualquier tamaño prefijado, necesitemos usar log(card(𝑄× Σ)) celdas de nuestra cinta, que llamaremos supercelda, para simular cada una de las celdas de 𝑀. Cada una de estas superceldas contiene una pareja de enteros 𝑝, 𝜎, donde 𝜎∈ [1,card(Σ)] representa el contenido de la celda correspondiente de 𝑀, y 𝑝∈ [0,card(𝑄)] representando el estado de 𝑀si la cabeza lectora/escritora observa la celda correspondiente (𝑝= 0 en otro caso). Puesto que la cabeza lectora/escritora de 𝑀solo puede moverse a una distancia 𝑇de la celda inicial en tiempo 𝑇, solo necesitamos superceldas para las 2𝑇+ 1 celdas centradas en la casilla inicial de 𝑀. Con este pequeño truco podemos dejar de preocuparnos por actualizar la dirección. Entonces 𝛿será una transformación unitaria 𝑈de dimensión 𝑑=card(𝑄× Σ) que va desde un par (estado, símbolo) leído, a una superposición nueva de estado y símbolo. Esto significa que podemos dividir el proceso de actualizar la superposición en dos pasos, uno para aplicar 𝑈y otro para movernos la especificación de nuevos estados a izquierda o derecha de la supercelda, según indique la dirección en la que se entra al estado en 𝑀. A continuación construimos una MTC STEP que lleva a cabo un paso de la simulación. Además de la cinta que usemos para simular, la máquina recibe como entrada la precisión deseada 𝛾, una especificación de 𝑈que sea 𝛾 2(10√𝑑)𝑑-cercana a unitaria, y una cadena 𝑠∈ {0,1}card(𝑄)que indique la dirección en la que se entra a los estados de 𝑀. La máquina STEP opera como sigue: 1. Transferir el estado actual y símbolo (𝑝, 𝜎)a la zona más cercana a la celda inicial que esté vacía y dejar una marca especial en su lugar. 2. Aplicar 𝑈a(𝑝, 𝜎)tomando 𝛾en consideración, que los transforma en un nuevo 1. máqinas de turing cuánticas 27 par de estado y símbolo (𝑞, 𝜏). 3. Revertir 1, transfiriendo (𝑞, 𝜏)a donde dejamos el marcador y vaciando el contenido de la supercelda de partida. 4. Transferir la especificación del estado 𝑞una supercelda a izquierda o derecha en función de si el 𝑞-ésimo qubit de 𝑠es 0o1. Usando el Teorema 1.2 de sincronización, podemos construir MTCs en forma normal y estacionarias para los pasos 1,3y4, que toman tiempo polinomial en 𝑇y solo dependen de 𝑇(fijado el 𝑀). El paso 2del algoritmo puede ejecutarse en tiempo polinomial en card(Σ),card(𝑄)y𝛾usando la construcción del Teorema 1.5 de transformaciones unitarias. Aplicando de forma apropiada los Lemas 1.2 y 1.3, obtenemos de estas cuatro MTCs en forma normal la MTC en forma normal que llamamos STEP. Puesto que cada una de estas cuatro MTCs toman un tiempo que solo depende de 𝑇y𝜀, también lo hará STEP (siempre para una 𝑀prefijada). Por lo tanto, si introducimos STEP como el estado especial en la MT reversible construida en el Lema 1.4 y añadimos 𝑇a la entrada, la MTC resultante STEP’ para tras un tiempo polinomial en 𝑇y1∕𝜀, además de haber simulado 𝑇pasos de 𝑀con precisión 𝑇 𝜀. Finalmente, construimos la MTC universal ensamblando STEP’ tras una MTC que realice el preproceso adecuado. En general, la máquina universal debe simular MTCs que no sean unidireccionales. Así pues, el preproceso sobre una MTC 𝑀, con una entrada 𝑥y una precisión 𝜀 consistirá en llevar a cabo la construcción del Lema 1.7 para obtener una MTC 𝑀′ unidireccional que simule 𝑀con coste un factor de 5. Entonces, las entradas que realmente recibe STEP’ son: 1. La representación de las 2𝑇+ 1 superceldas de la configuración inicial de 𝑀′ con entrada 𝑥. 2. La transformación 𝑑-dimensional 𝑈para 𝑀′con cada entrada escrita con precisión 𝜀 40𝑇(10√𝑑)𝑑+2 . 3. La cadena de direcciones 𝑠para 𝑀′. 4. EL número de pasos a simular, 5𝑇, y la precisión deseada 𝛾=𝜀 40𝑇. Veamos de dónde provienen estas exigencias. Todas estas entradas para pueden ser computadas de forma determinista con tiempo polinomial en 𝑇,1∕𝜀y la longitud de la entrada. 28 teoría de la complejidad en computación cuántica Además, si la transformación 𝑈se computa con la precisión especificada en (2), la transformación para STEP estará en un rango de 𝜀 40𝑇(10√𝑑)𝑑de la unitaria deseada 𝑈, es decir, será 𝜀 40𝑇(10√𝑑)𝑑-cercana a unitaria, como pedíamos cuando definimos STEP. Así, cada vez que aplicamos STEP con precisión 𝜀∕40𝑇, habremos aplicado una transformación unitaria a distancia 𝜀∕20𝑇de 𝑈. Por tanto, tras 5𝑇procesos de STEP, habremos aplicado una transformación unitaria que está a distancia 𝜀∕4 de la transformación de 5𝑇pasos de 𝑀′. Esto significa que observando la cinta de simulación de tras haberse completado, podremos dar una muestra de una distribución que esté a distancia variacional total 𝜀de la distribución que pudiéramos obtener al observar 𝑀con entrada 𝑥en tiempo 𝑇. 2 Clases de complejidad 2.1 Complejidad en tiempo en el paradigma cuántico Durante el primer capítulo hemos definido rigurosamente lo que entendemos por una MTC. Al igual que sucede en el entorno de MT clásicas, estas máquinas tienen asociado un lenguaje aceptado. Como suele ser habitual, la noción de aceptación de un lenguaje tiene asociada una medida de complejidad computacional, generalmente espacio y tiempo. Nuestra misión en este capítulo será la de extender los conceptos de clases de complejidad clásicos a nuestras nuevas máquinas y si es posible, compararlos. La mayoría de relaciones de contención entre las clases están aún por determinar, aunque gracias a Bernstein y Vazirani [4] sabemos que 𝐁𝐐𝐏 ⊆𝐏𝐒𝐏𝐀𝐂𝐄. Además, se cree que 𝐍𝐏 ⊈𝐁𝐐𝐏. Como veremos en el próximo capítulo, existen varios algoritmos que resuelven problemas clásicos pero desarrollados en el entrono de la computación cuántica. El ejemplo que estudiaremos se debe a David Deutsch y Richard Jozsa [6], que aportaron un algoritmo cuántico con oráculo de coste en tiempo polinomial que resuelve el problema planteado por el propio Deutsch. Se escoge específicamente este problema porque no es posible encontrar un algoritmo clásico con el mismo oráculo que tome tiempo polinomial. Definición 2.1. Sea una MTC 𝑀estacionaria, en forma normal y con múltiples tramos cuyo último tramo tiene alfabeto {#,0,1}. Si ejecutamos 𝑀con entrada 𝑥en el primer tramo y la cadena vacía en el resto, la máquina para y observamos la celda de entrada de su último tramo, veremos un 1con probabilidad 𝑝. Diremos que 𝑀acepta 𝑥 con probabilidad 𝑝y rechaza 𝑥con probabilidad 1 − 𝑝. La aceptación de una cadena está irremediablemente ligada a fijar una casilla de 30 teoría de la complejidad en computación cuántica aceptación y observarla. Puesto que el proceso de observación tiene una probabilidad asociada a las magnitudes de la configuración, nuestra definición de aceptación de un lenguaje debe darse en términos probabilísticos como los expuestos anteriormente. Para un lenguaje genérico ⊆(Σ − #)∗tenemos la siguiente definición. Definición 2.2. Diremos que una MTC 𝑀acepta exactamente si 𝑀acepta cada cadena 𝑥∈con probabilidad 1y rechaza cada cadena 𝑥∈ (Σ − #)∗−con probabilidad 1. Esta definición aún persigue en cierta medida el concepto clásico de aceptar un lenguaje, puesto que impone que no haya errores al observar. Podemos relajar cuanto queramos dicha restricción, aunque generalmente se exige una probabilidad estrictamente superior a 1∕2. 2.2 Clases de complejidad cuánticas Una vez aclarado qué entendemos por aceptar un lenguaje en este nuevo marco, podemos definir una serie de clases de complejidad asociadas al tiempo de computación que toma la máquina para aceptar o rechazar un lenguaje. Definición 2.3. Definimos la clase 𝐄𝐐𝐏 (error-free quantum polynomial time) como el conjunto de lenguajes que son aceptados exactamente por alguna MTC de tiempo polinomial. Definición 2.4. Definimos la clase 𝐁𝐐𝐏 como el conjunto de lenguajes que son aceptados con probabilidad 2∕3 por alguna MTC de tiempo polinomial. Estas son las dos clases principales, aunque existen muchas otras que podrían llegar a ser útiles. Está claro que 𝐄𝐐𝐏 ⊆𝐁𝐐𝐏. Por la caracterización que vimos en el capítulo anterior 1.1, toda MT reversible es un caso especial de MTC, por lo que 𝐏⊆𝐄𝐐𝐏. 2.3 Comparación con clases de complejidad clásicas Antes de entrar en materia, es conveniente recordar la versión clásica de la clase 𝐁𝐐𝐏, para luego comprobar si las contenciones de clases asociadas son iguales en el mundo clásico como en el cuántico. 2. clases de complejidad 31 Definición 2.5. Definimos la clase 𝐁𝐏𝐏 como el conjunto de todos los lenguajes que se pueden computar por una máquina clásica (probabilística) en tiempo polinomial. De esta definición deducimos que 𝐁𝐏𝐏 ⊆𝐁𝐐𝐏, aunque es recomendable precisar los detalles al menos una vez: Sea un lenguaje en 𝐁𝐏𝐏. Entonces existe un polinomio 𝑝(𝑛)y una MT determinista de tiempo polinomial 𝑀con salida {0,1} que satisface lo siguiente: Para cualquier entrada 𝑥de longitud 𝑛, si llamamos 𝑆𝑥al conjunto de 2𝑝(𝑛)qubits computados por 𝑀con entradas (𝑥;𝑦)con 𝑦∈ {0,1}𝑝(𝑛), entonces la proporción de 1’s en 𝑆𝑥es al menos 2∕3 siempre que 𝑥∈y1∕3 en otro caso. Podemos usar una MTC para decidir si una cadena 𝑥está en el lenguaje creando primero una superposición que divida equitativamente todos los |𝑥⟩|𝑦⟩y luego usar el algoritmo determinista. Primero, encadenamos una MTC estacionaria y en forma normal que tome 𝑥como entrada y devuelva (𝑥; 0𝑝(𝑛))con otra MTC estacionaria y en forma normal construida como sigue. Tomamos como alfabeto {#,0,1} y conjunto de estados {𝑞0, 𝑞𝑎, 𝑞𝑏, 𝑞𝑐, 𝑞𝑓}. Describimos la función de transición con una tabla: # 0 1 𝑞0|0⟩|𝑞𝑎⟩|𝑅⟩ |1⟩|𝑞𝑎⟩|𝑅⟩ 𝑞𝑎|#⟩|𝑞𝑏⟩|𝐿⟩ 𝑞𝑏|#⟩|𝑞𝑐⟩|𝐿⟩1 √2|0⟩|𝑞𝑏⟩|𝑅⟩+1 √2|1⟩|𝑞𝑏⟩|𝑅⟩1 √2|0⟩|𝑞𝑏⟩|𝑅⟩−1 √2|1⟩|𝑞𝑏⟩|𝑅⟩ 𝑞𝑐|#⟩|𝑞𝑓⟩|𝐿⟩ |0⟩|𝑞𝑐⟩|𝐿⟩ |1⟩|𝑞𝑐⟩|𝐿⟩ 𝑞𝑓|#⟩|𝑞0⟩|𝑅⟩ |0⟩|𝑞0⟩|𝑅⟩ |1⟩|𝑞0⟩|𝑅⟩ Esta máquina es estacionaria, se encuentra en forma normal y para en tiempo polinomial respecto a la entrada. Aunque no se exprese como una función total, es sencillo extender su función de transición para que así lo sea, sin afectar a la funcionalidad de la versión parcial aquí mostrada. Esto nos da una MTC estacionaria y en forma normal que con entrada 𝑥produce una superposición ∑ 𝑦∈{0,1}𝑝(𝑛) 1 2𝑝(𝑛)∕2 |𝑥⟩|𝑦⟩. Aplicando una vez más el Teorema 1.2 de sincronización para concatenarlo con 𝑀 obtenemos una MTC de tiempo polinomial que con entrada 𝑥produce la superposi- 32 teoría de la complejidad en computación cuántica ción ∑ 𝑦∈{0,1}𝑝(𝑛) 1 2𝑝(𝑛)∕2 |𝑥⟩|𝑦⟩|𝑀(𝑥;𝑦)⟩. Puesto que la proporción de 1’s en 𝑆𝑥es de al menos 2∕3 si 𝑥∈y como mucho 1∕3 en otro caso, observando el qubit del tercer tramo nos dará la clasificación correcta de 𝑥con probabilidad al menos 2∕3. Esto completa la comprobación de 𝐁𝐏𝐏 ⊆𝐁𝐐𝐏. Siguiendo con esta cadena de contenciones observamos que 𝐁𝐐𝐏 está dentro de la clase exponencial en tiempo. Esta cota se puede refinar como veremos posteriormente, pero antes debemos introducir una clase de máquinas que siguen el mismo patrón que las 𝜀-cercanas a unitarias. Definición 2.6. Diremos que dos MTC 𝑀y𝑀′son 𝜀-cercanas si tienen el mismo conjunto de estados, alfabeto y la diferencia entre cada pareja de amplitudes correspondiente tiene magnitud acotada por 𝜀 > 0. Al igual que ocurría en el caso de máquinas 𝜀-cercanas a unitarias, esta clase de máquinas también tiene un lema técnico que acota la diferencia de los operadores de evolución en el tiempo. Como consecuencia, tenemos el siguiente corolario. Corolario 2.1.Sea 𝑀= (Σ, 𝑄, 𝛿)una MTC bien formada y sea 𝑀′una MTC 𝜆𝜀 𝑇cercana a 𝑀, con 𝜆𝜀 𝑇=𝜀 24 card(Σ) card(𝑄)𝑇y𝜀 > 0. Entonces 𝑀′simula 𝑀durante 𝑇 pasos con precisión 𝜀. Los detalles de ambos resultados pueden encontrarse en el texto de Bernstein y Vazirani [4]. Teorema 2.1. 𝐁𝐐𝐏 ⊆𝐏𝐒𝐏𝐀𝐂𝐄. Demostración. Sea 𝑀= (Σ, 𝑄, 𝛿)una máquina que decida un lenguaje en 𝐁𝐐𝐏 con tiempo de computación 𝑝(𝑛). Por el corolario 2.1, cualquier MTC 𝑀′que sea 𝜆𝜀 𝑝(𝑛)-cercana a 𝑀simulará 𝑀durante 𝑝(𝑛)pasos con precisión 𝜀. Si simulamos 𝑀 con precisión 1∕12, entonces la probabilidad de éxito será al menos 7∕12 . Por tanto, nos basta trabajar con la MTC 𝑀′, donde cada amplitud de 𝑀se computará por los primeros log(288 card(Σ) card(𝑄)𝑝(𝑛)) qubits. Recordamos que la amplitud de cualquier configuración tras 𝑇pasos es la suma de las amplitudes de cada posible camino de decisiones en 𝑀′de longitud 𝑇desde la configuración inicial hasta la deseada. En nuestro caso, si mantenemos a lo más 𝑝(𝑛)configuraciones intermedias podemos llevar a cabo una búsqueda profunda en el árbol computacional asociado a 𝑀para calcular la amplitud de una configuración 2. clases de complejidad 33 deseada. El coste en tiempo es exponencial, pero el espacio usado es polinomial en las entradas. Por último, debemos determinar si una cadena 𝑥de longitud 𝑛es aceptada por 𝑀. Para ello calculamos la norma de los vectores de magnitud de cada configuración alcanzable en tiempo 𝑝(𝑛)por 𝑀′con un 1en la celda de entrada y comparamos con 7∕12. Puesto que las únicas configuraciones de aceptación alcanzables por 𝑀′son aquellas que tienen un 1en la casilla inicial y todas las casillas a distancia mayor de 𝑝(𝑛)están en blanco, sólo necesitamos espacio de orden polinomial. Esta cota puede mejorarse a 𝐏#𝐏usando el siguiente teorema de [3], del que no veremos la prueba por motivos de espacio. Aún así, es interesante definir los nuevos conceptos que aparecen en este resultado. Definición 2.7. Definimos la clase 𝐁𝐐𝐓𝐢𝐦𝐞(𝑇(𝑛)) como el conjunto de lenguajes que son aceptados con probabilidad 2∕3 por alguna MTC cuyo tiempo de funcionamiento en cualquier entrada de longitud 𝑛esté acotado por 𝑇(𝑛). Definición 2.8. Diremos que una función 𝑓es constructible en tiempo si existe una MT 𝑀tal que al introducir una cadena {1}𝑛, devuelve la representación binaria de 𝑓(𝑛) en tiempo (𝑓(𝑛)). Recordamos que #𝐏es el conjunto de funciones 𝑓que mandan una cadena en un entero para las que existe un polinomio 𝑝(𝑛)y un lenguaje ∈𝐏tales que al introducir 𝑥como entrada, el valor 𝑓(𝑥)es el número de cadenas 𝑦de longitud 𝑝(|𝑥|) para los que 𝑥𝑦 está contenido en . Por último, vamos a entender por una MTC oráculo aquella que tiene un tramo especial para realizar las preguntas al oráculo. Las MTC oráculo tienen dos estados distinguidos correspondientes al estado previo a la pregunta 𝑞𝑞y al posterior 𝑞𝑎. Una pregunta es ejecutada siempre que la máquina entre en el estado 𝑞𝑞con un único bloque no vacío de celdas en el tramo destinado a las preguntas. Teorema 2.2. Si el lenguaje está contenido en la clase 𝐁𝐐𝐓𝐢𝐦𝐞(𝑇(𝑛)), con 𝑇(𝑛)> 𝑛y𝑇(𝑛)constructible en tiempo, entonces para todo 𝜀 > 0, existe una MTC 𝑀′que acepta con probabilidad 1−𝜀y tiene la siguiente propiedad: cuándo introducimos una entrada 𝑥de longitud 𝑛,𝑀′opera en tiempo acotado por 𝑐𝑇 (𝑛), donde 𝑐es polinomial en log(1∕𝜀), y produce una superposición final en la que |𝑥⟩|(𝑥)⟩, con (𝑥)=1si 𝑥∈ y0en otro caso, tiene norma al menos 1 − 𝜀. Este resultado nos permite depurar la cota que vimos anteriormente para 𝐁𝐐𝐏 de 34 teoría de la complejidad en computación cuántica la siguiente forma. Teorema 2.3. 𝐁𝐐𝐏 ⊆𝐏#𝐏. Demostración. Sea 𝑀= (𝜎, 𝑄, 𝛿)una máquina que decida un lenguaje en 𝐁𝐐𝐏 con tiempo de observación 𝑝(𝑛). Siguiendo el Teorema 2.2 podemos suponer sin pérdida de generalidad que 𝑀se comporta apropiadamente, tal como indica dicho resultado. Esta máquina, a su vez, puede simularse por otra MTC 𝑀′que sea 𝜆𝜀 𝑝(𝑛)-cercana a𝑀gracias al Teorema 2.1. De hecho, hemos probado que cada amplitud de 𝑀puede ser computada para los primeros log(288 card(Σ) card(𝑄)𝑝(𝑛)) qubits, además de mantener la norma de cada configuración final de aceptación por encima de 7∕12. Puesto que queremos demostrar la pertenencia a 𝐏#𝐏, vamos a usar #𝐏como oráculo para computar la amplitud de la configuración final (𝑥; 1) de 𝑀′con un error menor de 1∕36 en tiempo 𝑇. Puesto que la amplitud real es como mucho 1, la norma de nuestra configuración aproximada debe estar a distancia 1∕12 de la real. Veamos que es cierto suponiendo que 𝛼es el valor real y ‖𝛼′−𝛼‖<1∕36, |||‖𝛼‖2−‖𝛼′‖2|||≤‖𝛼′−𝛼‖2+ 2‖𝛼‖‖𝛼′−𝛼‖≤1 36(2 + 1 36)<1 12. Dado que la probabilidad de éxito de 𝑀′es al menos 7∕12, podemos clasificar 𝑥correctamente. Resta probar que efectivamente podemos aproximar esta configuración final. En primer lugar, podemos estudiar cada amplitud separando parte real e imaginaria, obteniendo así una suma de 2𝑇términos para cada camino que nos lleve a una configuración en tiempo 𝑇. De nuevo podemos separar esta suma en cuatro: Reales positivos, reales negativos, imaginarios positivos e imaginarios negativos. Con la ayuda de un algoritmo en #𝐏podemos computar cada una de estas sumas con un error de magnitudes menor de 1∕144. Tomando la diferencia entre ellos nos proporcionará la amplitud de a configuración deseada con un error de 1∕36 a lo sumo. Por último, computemos la suma de los reales positivos como ejemplo del algoritmo. Supongamos que para una constante 𝑐polinomial en 𝑇recibimos las siguientes entradas (todas de longitud polinomial en 𝑇): El camino 𝑝de 𝑀′en 𝑇pasos, una especificación 𝑡de alguno de los 2𝑇términos y un entero 𝑤entre 0y2𝑐𝑇 . Entonces es sencillo ver que podemos decidir en tiempo polinomial determinista en 𝑡si 𝑝es realmente un camino desde la configuración inicial de 𝑀en 𝑥hasta la configuración final deseada, si 𝑡es real y positivo, y si el término 𝑡de la amplitud del camino 𝑝es mayor que 𝑤∕2𝑐𝑇 . Si fijamos una camino 𝑝y un término 𝑡que satisfaga las 2. clases de complejidad 35 condiciones anteriores, entonces el número de enteros 𝑤para los que este algoritmo acepta, dividido por 2𝑐𝑇 , está a distancia 1∕2𝑐𝑇 del valor del término 𝑡del camino 𝑝. Así, si fijamos tan solo un camino 𝑝que satisfaga las condiciones previas, el número de términos 𝑡y enteros 𝑤para los que el algoritmo acepta, dividido por 2𝑐𝑇 , está a distancia 1∕2(𝑐−1)𝑇de la suma de términos reales positivos para el camino 𝑝. Por tanto, el número de elementos 𝑝, 𝑡, 𝑤 para los que el algoritmo acepta, dividido por 1∕2𝑐𝑇 , está a distancia 𝑁∕2(𝑐−1)𝑇de la suma de todos los términos reales positivos de todos los caminos de 𝑀′con 𝑇pasos que parten desde la configuración inicial y terminan en la configuración deseada. Puesto que hay 2card(Σ) card(𝑄)posibles sucesores de cualquier configuración, como mucho, eligiendo 𝑐 > 1 + log(144) 𝑇+2card(Σ) card(𝑄) log(𝑇) 𝑇 cumple 𝑁∕2(𝑐−1)𝑇<1∕144 como requeríamos. El razonamiento para el resto de sumas es análogo. 2.3.1 𝐍𝐏 y𝐁𝐐𝐏 El hecho de que tanto 𝐍𝐏 como 𝐁𝐐𝐏 contengan a 𝐏nos lleva a plantear qué relación existe entre ambas clases. Peter Shor construyó en [11] el algoritmo que lleva su nombre, permitiendo resolver en tiempo polinomial con una MTC el problema de la factorización de enteros, cuya pertenencia a 𝐏se desconoce. De igual forma, existen indicios de que 𝐍𝐏 ⊈𝐁𝐐𝐏. Cualquier demostración rigurosa que aclare alguna de estas contenciones se asocia directamente con la respuesta a 𝐏? =𝐍𝐏. La aproximación para estudiar 𝐍𝐏 ⊈𝐁𝐐𝐏 que veremos se basa en la dada por C.H. Bennett, E. Bernstein, G. Brassard y U. Vazirani [3]. Siguiendo su notación, llamaremos 𝐁𝐐𝐓𝐢𝐦𝐞(𝑇(𝑛))𝐴al conjunto de lenguajes aceptados con probabilidad al menos 2∕3 por una MTC con oráculo 𝑀𝐴cuyo tiempo de ejecución esté acotado por 𝑇(𝑛). Asociado al oráculo 𝐴podemos definir una permutación 𝐴(𝑥)que consiste en interpretar la respuesta del oráculo al par (𝑥, 𝑖)como el 𝑖-ésimo qubit del valor de la función. Para realizar este cálculo, el par (𝑥, 𝑖)debe escribirse como una cadena binaria. En lo que resta de capítulo supondremos sin pérdida de generalidad que las máquinas con las que trabajemos tendrán como alfabeto {0,1,#} para cada tramo. Además, todos los tramos comienzan en blanco, excepto la destinada a la entrada. 42 teoría de la complejidad en computación cuántica R. Simon, que resuelve el problema que el mismo planteó en [12]. Basándose en dicho trabajo, Peter Shor construyó su rompedor algoritmo cuántico [11] para la factorización en primos tomando tiempo polinomial, con las implicaciones que esto tiene sobre la teoría de la complejidad. El problema a resolver consiste en dada una función 𝑓∶ {0,1}𝑛→{0,1} que sea constante para todos sus valores o bien equilibrada en 0y1(i.e. la mitad de las entradas devuelven un 0y la otra mitad un 1), determinar si dicha función es constante o equilibrada, permitiendo el uso de dicha función como caja negra. Este se conoce como el problema de Deutsch, que en su versión clásica requiera 2𝑛−1 +1 evaluaciones de la función 𝑓en el peor caso. En primer lugar, supondremos que la máquina recibe como entrada |𝜓0⟩𝑛,1= |0⟩𝑛⊗|1⟩, usando esta notación para especificar que se trata del producto tensorial entre un 𝑛-qubit y un qubit. Por tanto, trabajamos con una MTC de al menos 𝑛+1 qubits. El resto del algoritmo consiste en la ejecución de los siguientes pasos: 1. |𝜓1⟩𝑛,1←𝐇⊗𝑛+1(|𝜓0⟩𝑛,1) 2. |𝜓2⟩𝑛,1←𝐎𝑓(|𝜓1⟩𝑛,1) 3. |𝜓3⟩𝑛,1←(𝐇⊗𝑛 ⊗𝐈)(|𝜓2⟩𝑛,1) 4. 𝑠←medir el 𝑛-qubit de |𝜓3⟩𝑛,1, donde puerta notada por 𝐈representa la asociada a la matriz identidad. Veamos que efectivamente el algoritmo resuelve el problema. En el primer paso se aplica la puerta de Hadamard al (𝑛+ 1)-qubit de partida. Como ya hemos visto anteriormente, la acción de esta puerta sobre el 𝑛-qubit |0⟩𝑛es la de construir una superposición equiprobable en los estados básicos. Por otro lado, el qubit |1⟩, que nos es necesario para la posterior aplicación de la puerta oráculo de 𝑓se convierte en el qubit |−⟩, obteniendo así el nuevo estado |𝜓⟩𝑛,1=(𝐇⊗𝑛|0⟩𝑛)⊗(𝐇|1⟩)=(1 √2𝑛 2𝑛−1 ∑ 𝑗=0 |𝑗⟩𝑛)⊗|−⟩. En el segundo paso, la aplicación del oráculo sobre el estado actual produce las siguientes transformaciones: |𝜓2⟩𝑛,1=𝐎𝑓[( 1 √2𝑛 2𝑛−1 ∑ 𝑗=0 |𝑗⟩𝑛)⊗|−⟩](3.1) 3. algoritmos 43 Usando la linealidad en el operador, podemos establecer que (3.1) = 1 √2𝑛 2𝑛−1 ∑ 𝑗=0 𝐎𝑓(|𝑗⟩𝑛⊗|−⟩)=1 √2𝑛 2𝑛−1 ∑ 𝑗=0 𝐎𝑓(|𝑗⟩𝑛⊗|0⟩−|1⟩ √2) =1 √2𝑛 2𝑛−1 ∑ 𝑗=0 |𝑗⟩𝑛⊗|𝑓(𝑗)⟩−|𝑗⟩𝑛⊗|1⊕ 𝑓(𝑗)⟩ √2 =1 √2𝑛 2𝑛−1 ∑ 𝑗=0 (−1)𝑓(𝑗)|𝑗⟩𝑛⊗(|0⟩−|1⟩ √2)=1 √2𝑛 2𝑛−1 ∑ 𝑗=0 (−1)𝑓(𝑗)|𝑗⟩𝑛⊗|−⟩ Tras aplicar la puerta oráculo obtenemos una configuración de estados parecida a la que teníamos previamente. La observación obvia es que ahora aparece nuestra función 𝑓desconocida en las amplitudes cambiando el signo de los estados básicos para los que 𝑓(𝑗)=1. Alcanzar nuestro objetivo pasará por explotar esta propiedad al aplicar los pasos restantes del algoritmo. En el último paso de cálculo puro, aplicamos la puerta de Hadamard de dimensión 𝑛al 𝑛-qubit que contiene la información sobre 𝑓, mientras que el qubit adicional quedará invariante. Dado que los cálculos son análogos al primer paso, no los detallaremos en exceso: 𝐇⊗𝑛 (1 √2𝑛 2𝑛−1 ∑ 𝑗=0 (−1)𝑓(𝑗)|𝑗⟩𝑛)=1 2𝑛 2𝑛−1 ∑ 𝑖=0 (2𝑛−1 ∑ 𝑗=0 (−1)𝑓(𝑗)+𝑗⋅𝑖)|𝑖⟩𝑛 donde 𝑗⋅𝑘representa el producto aplicado bit a bit, visto módulo 2. Esta forma de escribirlo es más concisa y fácilmente generalizable a partir de la definición de la puerta de Hadamard aplicada a un qubit genérico: 𝐇(|𝑗⟩) = 1 √2 1 ∑ 𝑘=0 (−1)𝑗⋅𝑖|𝑖⟩ Una vez termina el proceso de transformaciones aplicadas a la configuración de entrada, que sólo ha requerido una evaluación de 𝑓actuando como oráculo, medimos el 𝑛-qubit que contiene la información sobre 𝑓. La máquina devolverá uno de los 2𝑛 posibles estados básicos con una distribución de probabilidad dada por las amplitudes, que en nuestro caso tienen la siguiente forma: 𝛼𝑖=1 2𝑛 2𝑛−1 ∑ 𝑗=0 (−1)𝑓(𝑗)+𝑗⋅𝑖. 44 teoría de la complejidad en computación cuántica La verdadera importancia del paso 3aparece ahora, al mirar detalladamente la probabilidad asociada al valor 𝑖= 0. Sin más que sustituir, obtenemos |𝛼0|2=|||||| 1 2𝑛 2𝑛−1 ∑ 𝑗=0 (−1)𝑓(𝑗)|||||| 2 . Puesto que 𝑓devuelve los valores 0o1, es directo comprobar que |𝛼0|2={1si 𝑓es constante 0si 𝑓es equilibrada Por tanto, un simple test que compruebe |0⟩𝑛como posible salida del algoritmo, resuelve el problema planteado en esta sección. Durante el capítulo 2hicimos incidencia en varias contenciones entre clases de complejidad que aún no se conoce si son estrictas. En particular, este algoritmo induce a pensar que 𝐏≠𝐄𝐐𝐏, aunque solo confirma que se diferencian bajo la acción de un oráculo. Además, existen varios herederos del algoritmo de Deutsch-Jozsa. El algoritmo de Simon es un claro ejemplo, junto con el algoritmo de factorización de Shor. Alejado de ellos se encuentra el algoritmo de búsqueda Grover [8], cuyo nombre se debe al informático Lov K. Grover. Gracias a él, se establece cómo aceptar la clase 𝐍𝐏 con una MTC y el uso de un oráculo en tiempo (2𝑛∕2). A su vez, Bennett, Bernstein, Brassard y Vazirani prueban en [3] que la cota es realmente óptima, es decir, la clase 𝐍𝐏 ∩𝐜𝐨−𝐍𝐏 no puede ser aceptada por una MTC con oráculo elegido aleatoriamente en tiempo (2𝑛∕3). Una guía completa y ordenada de los algoritmos nombrados anteriormente se encuentra en [10]. 4 Conclusión Echando la vista atrás, nos hemos adentrado en el mundo de la computación cuántica, centrándonos en construir una máquina que generalice, en la medida de lo posible, la definida en la primera mitad del siglo XX por Alan Turing. Una vez vistas las propiedades que comparten, avanzamos en busca de las que son distintas. Nuestro objetivo final era, sin duda, emular cualquier máquina de Turing cuántica a un bajo precio. Asociado a este nuevo modelo se construye una teoría de la complejidad computacional paralela a la clásica. Encontramos dificultades similares a las que plantea el problema 𝐏? =𝐍𝐏, además de abrir nuevos problemas aún sin resolver. Un ejemplo de la potencia de estas máquinas se observa con el algoritmo de DeutschJozsa. Este resuelve de manera exacta y eficiente un problema especialmente diseñado para que cualquier algoritmo clásico que lo resuelva sea altamente costoso. Eso, por supuesto, no quiere decir que las máquinas de Turing cuánticas sean más potentes. En 2019 la compañía Google anunció que había alcanzado la ‘supremacía cuántica’ con su nueva máquina, aunque generó controversia sobre las condiciones en las que trabaja y los problemas que puede resolver eficientemente. En general, aún se considera un problema físico abierto en el que muchas empresas tecnológicas están apostando. Queda patente el interés que suscita el paradigma cuántico a todos los niveles. Un descubrimiento importante en el campo de complejidad computacional tendría gran repercusión en las matemáticas y la ciencia en general. Lo mismo ocurre si hablamos de la creación de nuevos algoritmos eficientes, dado que la mayoría de problemas clásicos aún no tienen una resolución elegante que aproveche el potencial de estas máquinas en sus algoritmos. Bibliografía [1] Adleman, L. M., DeMarrais, J., and Huang, M.-D. A. Quantum computability. SIAM J. Comput. 26, 5 (Oct. 1997), 1524–1540. [2] Bennett, C. H. Logical reversibility of computation. IBM J. Res. Dev. 17, 6 (Nov. 1973), 525–532. [3] Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani, U. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (Oct 1997), 1510–1523. [4] Bernstein, E., and Vazirani, U. Quantum complexity theory. SIAM J. Comput. 26, 5 (Oct. 1997), 1411–1473. [5] Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London Series A 400, 1818 (July 1985), 97–117. [6] Deutsch, D., and Jozsa, R. Rapid Solution of Problems by Quantum Computation. Proceedings of the Royal Society of London Series A 439, 1907 (Dec. 1992), 553–558. [7] Feynman, R. P. Simulating physics with computers. Int. J. Theor. Phys. 21 (1982), 467–488. [8] Grover, L. K. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (New York, NY, USA, 1996), STOC ’96, Association for Computing Machinery, p. 212–219. [9] Nielsen, M. A., and Chuang, I. L. Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th ed. Cambridge University Press, USA, 2011. 48 teoría de la complejidad en computación cuántica [10] Ossorio-Castillo, J., and Tornero, J. M. Quantum computing from a mathematical perspective: a description of the quantum circuit model. arXiv: Quantum Physics (2018). [11] Shor, P. W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (USA, 1994), SFCS ’94, IEEE Computer Society, p. 124–134. [12] Simon, D. R. On the power of quantum computation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (USA, 1994), SFCS ’94, IEEE Computer Society, p. 116–123. [13] Solovay, R., and Yao., A. Manuscript, 1996.