Algoritmos fundamentales en computación cuántica

ALGORITMOS FUNDAMENTALES EN COMPUTACIÓN CUÁNTICA Pastor Díaz, Ulises 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. Realizada por Ulises Pastor Díaz Tutorizada por Prof. José María Tornero Sánchez Índice general Abstract 7 1. Postulados y conceptos básicos 9 1.1. Postulados de la Mecánica Cuántica . . . . . . . . . . 9 1.1.1. Primer postulado . . . . . . . . . . . . . . . . 9 1.1.2. Segundo postulado . . . . . . . . . . . . . . . 11 1.1.3. Tercer postulado . . . . . . . . . . . . . . . . 13 1.1.4. Cuarto postulado . . . . . . . . . . . . . . . . 15 1.2. Entrelazamiento cuántico . . . . . . . . . . . . . . . . 19 1.2.1. Superdense coding . . . . . . . . . . . . . . . 20 1.2.2. Teleportación cuántica . . . . . . . . . . . . . 21 1.2.3. En computación . . . . . . . . . . . . . . . . . 22 2. Modelos de computación cuánticos 23 2.1. Maquinas de Turing cuánticas . . . . . . . . . . . . . 23 2.2. Modelo de circuitos cuántico . . . . . . . . . . . . . . 24 2.3. Puertas cuánticas . . . . . . . . . . . . . . . . . . . . 25 2.3.1. Puertas de un qubit . . . . . . . . . . . . . . 25 2.3.2. Conjuntos de puertas universales . . . . . . . 28 2.4. Complejidad computacional cuántica . . . . . . . . . 30 3. Algoritmos cuánticos 31 3.1. Phase Kick-Back . . . . . . . . . . . . . . . . . . . . 31 3.2. Problema del subgrupo oculto . . . . . . . . . . . . . 33 3.2.1. Algoritmo de Deutsch . . . . . . . . . . . . . 34 3.2.2. Algoritmo de Deutsch-Jozsa . . . . . . . . . . 36 3.2.3. Algoritmo de Simon . . . . . . . . . . . . . . 38 3.3. Algoritmo de Shor . . . . . . . . . . . . . . . . . . . 41 3.3.1. Transformada de Fourier cuántica . . . . . . . 41 3.3.2. El problema del orden . . . . . . . . . . . . . 44 4. Algoritmos de búsqueda y amplificación de amplitudes 47 4.1. Problema de Búsqueda . . . . . . . . . . . . . . . . . 47 4.1.1. Algoritmo de Grover . . . . . . . . . . . . . . 48 4.1.2. Soluciones múltiples . . . . . . . . . . . . . . 55 4.2. Quantum counting . . . . . . . . . . . . . . . . . . . 56 5. Conclusión 63 Anexo: Notación 65 Abstract “Use your little grey cells mon ami.” -Agatha Christie. At any point in history, we can find examples of problems solved mechanically, but it was in the 20th century with the arrival of computers that the paradigm shifted and the concept of problem-solving changed forever. It is at that moment when we start a race to not only solve problems but to solve them efficiently. A race against time itself. Many advances were made from that point on, but already in the childhood of computer science, a question clouded the horizon: how fast can we go? Are there problems which we cannot solve efficiently? In 1982 American physicist Richard Feynman pointed out that quantum systems could not be efficiently simulated with classical computers, proposing the idea of constructing a new model of computation. Computers fueled not by classical physics, but by quantum physics instead. This idea, which had already been introduced by American physicist Paul Benioff and Russian mathematician Yuri Manin in 1980, served as inspiration for British physicist David Deutsch to introduce in 1985 a quantum analog to the already well known Turing machines: a quantum Turing machine. And thus quantum computing was born. This new tool, which opened a new universe of possibilities, has been developed ever since, and many peaks have been reached in its short life. In 1994 American mathematician Peter W. Shor reached a milestone when he developed a quantum algorithm that solved the factoring problem in polynomial time. This achievement was soon followed by Indian-American Lov K. Grover, who in 1996 described a quantum algorithm that solved the search problem qua- dratically faster than a classical computer. In this memory our goal will be to present some of the main algorithms in quantum computing, but to do so we will have to start by introducing the postulates of quantum mechanics and the phenomenon of quantum entanglement. Next, we will propose a quantum computing model based on those ideas, which will allow us to finally construct some of the most important quantum algorithms so far. Capítulo 1 Postulados y conceptos básicos “Very few of us are what we seem.” -Agatha Christie. Antes de sumergirnos en la construcción de algoritmos basados en un modelo cuántico de computación, antes incluso de atrevernos a desarrollar dicho modelo debemos asentar los cimientos. ¿Qué es un sistema cuántico? ¿Cómo evolucionan? ¿Cuáles son las particularidades que los hacen tan interesantes? Responder a estas preguntas será nuestra primera tarea. 1.1. Postulados de la Mecánica Cuántica El primer enigma que resolveremos será el de definir qué es un sistema cuántico. En concreto, y dado que nuestros intereses son computacionales, nos centraremos en los sistemas cuánticos discretos. 1.1.1. Primer postulado Nuestra formalización del concepto de sistema cuántico deberá respetar tanto la naturaleza lineal de las funciones de onda como su comportamiento probabilístico, lo es que motivación suficiente para justificar el primer postulado. algoritmos fundamentales en computación cuántica Definición 1.7. Postulado IV: Medición cuántica. Una medición cuántica de un sistema cuántico Hserá un conjunto de operadores {Mi}de H, llamados operadores de medición, que satisfacen la ecuación de completitud:X i M∗ iMi=I, siendo Iel operador identidad. Los índices ide dichos operadores se corresponderán con los posibles resultados de la medición, cada uno de los cuáles ocurrirá con probabilidad: p(i) = hψ|M∗ iMi|ψi. Suponiendo que el sistema se encontraba en el estado |ψien el momento previo a la medición, el estado del sistema tras suceder el resultado iserá: |ψii=Mi|ψi qhψ|M∗ iMi|ψi. Observación 1.4.Los operadores {Pi}del ejemplo anterior son una medición, ya que cumplen la ecuación de completitud. Esta ecuación encierra la idea buscada de que la suma de las probabilidades es 1. Proposición 1.1.Un conjunto de operadores {Mi}cumplen la ecuación de completitud si y solo si para todo estado |ψise cumple X i p(i)=1. Demostración. Basta comprobar la siguiente secuencia: X i M∗ iMi=I⇐⇒ ∀|ψi,hψ| X i M∗ iMi!|ψi=hψ|I|ψi ⇐⇒ ∀|ψi,X ihψ|M∗ iMi|ψi=hψ|ψi ⇐⇒ ∀|ψi,X i p(i) = 1. Sin embargo, el caso del ejemplo anterior es algo más concreto, ya que los operadores de medición son proyecciones ortogonales. Definición 1.8. Observable. Sea Hun sistema, un observable es un operador hermítico de H. Página 16 §1.1. POSTULADOS DE LA MECÁNICA CUÁNTICA Observación 1.5.Usando el teorema de descomposición espectral para matrices hermíticas, sabemos que cualquier observable es diagonalizable en una base ortonormal. Tomando los proyectores ortogonales asociados a los espacios de autovectores (que son ortogonales entre sí), podemos concluir que, dado Mun observable con autovalores mi, entonces: M=X i miPi, donde los Pison los proyectores ortogonales ya mencionados. Definición 1.9. Medición proyectiva. Una medición proyectiva es un observable M=X i miPi, según el cual, dado un estado |ψi, la probabilidad de obtener el resultado mies: p(i) = hψ|Pi|ψi, y el estado tras la medición es: |ψii=Pi|ψi qp(i). Comprobemos que de hecho se trata de un caso concreto de medición cuántica. Proposición 1.2.La medición proyectiva es un caso concreto de medición cuántica en el cual los operadores se corresponden con proyectores ortogonales. Demostración. Los proyectores cumplen la ecuación de completitud trivialmente y además, sea un idado P∗ iPi=Piporque son operadores hermíticos y proyectores. Las mediciones que nosotros llevaremos a cabo, sin embargo, serán un tipo más general de medición proyectiva. Serán las llamadas mediciones de Von Neumann. Definición 1.10. Medición de Von Neumann. Sea H=NiHiun sistema formado por composición de los kqubits Hi, llamaremos medición de Von Neumann en la base computacional sobre el qubit etiquetado por ia la medición cuántica dada por los operadores: M0= (|0ih0|)i=I⊗···⊗I | {z } i−1veces ⊗(|0ih0|)⊗I⊗···⊗I | {z } k−iveces , M1= (|1ih1|)i=I⊗···⊗I | {z } i−1veces ⊗(|1ih1|)⊗I⊗···⊗I | {z } k−iveces . Página 17 algoritmos fundamentales en computación cuántica Lema 1.3.Los operadores de la medición de Von Neumann constituyen una medición cuántica, y en concreto una medición proyectiva. Demostración. Dado que |0ih0|+|1ih1|=Ies inmediato que M0+M1=Iy por tanto se trada de una medición. Como además M2 j=Mjpara j= 0,1es una medición proyectiva. Además, el siguiente resultado nos permite medir en más de un qubit de forma simultánea. Proposición 1.3.Mediciones en cascada. Sean M={Mi}yN={Nj}dos mediciones cuánticas, aplicar primero My luego Nequivale a aplicar una única medición L={Lij =MiNj}. Demostración. Les una medición cuántica, ya que: X ij Lij =X i Mi X j Nj =I. Sea |ψiun estado arbitrario del sistema, pasemos a calcular la probabilidad de que ocurra en primer lugar el resultado ien la medición My luego el jen la medición N: p(i)p(j) = hψ|M∗ iMi|ψihψi|N∗ jNj|ψii=hψ|N∗ jM∗ iMiNj|ψi. Y el estado resultante tras dichas mediciones será: |ψiji=Njψi qp(j)=NjMi|ψi qp(ij). Este tipo de medición nos permitirán medir un qubit de forma aislada sobre la base computacional. Existe una formulación equivalente a la de los cuatro postulados anteriores muy usada en teoría de la información cuántica, en la que en lugar de trabajar con vectores unitarios trabajamos con operadores de densidad. Esta formulación es muy útil cuando se trabaja con ruido, y se puede encontrar en [12] y [7]. Página 18 §1.2. ENTRELAZAMIENTO CUÁNTICO Una vez ya hemos visto los cuatro postulados que servirán de cimientos a la hora de construir nuestro sistema de computación pasemos a estudiar el fenómeno fundamental que usaremos como herramienta: el entrelazamiento cuántico. 1.2. Entrelazamiento cuántico Comencemos por considerar el estado EPR en un sistema con dos qubits: |EPRi=1 √2(|00i+|11i). Y veamos que no somos capaces de escribir este estado como producto tensorial de estados simples. Sean |ψ1i=α1|0i+β1|1i,|ψ2i=α2|0i+β2|1i. Sabemos que |ψ1i|ψ2i=α1α2|00i+α1β2|01i+β1α2|10i+β1β2|11i. Y por tanto tenemos las ecuaciones: α1α2=1 √2, α1β2= 0, β1α2= 0, β1β2=1 √2, lo que es una contradicción y por tanto no podemos escribir el estado compues- to como composición de estados de los qubits individuales. Este fenómeno lo conocemos como entrelazamiento cuántico, y diremos que el estado EPR está entrelazado. Definición 1.11. Entrelazamiento cuántico. Un estado |ψi ∈ n O i=1 Hise dice entrelazado si no existen |ψii ∈ Hitales que |ψi=|ψ1i⊗···⊗|ψni. En caso contrario se dice que el estado es separable. El interés de la existencia este fenómeno, que es consecuencia de una conocida propiedad del producto tensorial, es que cuando un sistema compuesto se encuentra en un estado entrelazado lo que ocurre a uno de los sistemas simples altera Página 19 algoritmos fundamentales en computación cuántica necesariamente al resto. Veámoslo llevando a cabo una medición sobre el primer qubit en el ejemplo anterior. Los operadores de la medición serán: M0=|0ih0|⊗I, M1=|1ih1|⊗I. Y por tanto, si obtenemos el resultado i, el estado resultante será: Mi|EPRi qp(i)=|iii. Por lo que el hecho de que el primer qubit colapse al estado |iifuerza al segundo a hacer lo mismo. Veamos algunas aplicaciones de este fenómeno. 1.2.1. Superdense coding Obviando la grandilocuencia del nombre, el superdense coding es una técnica que, mediante el entrelazamiento cuántico, nos permite transferir dos bits clásicos de información enviando únicamente un qubit. Consideremos dos agentes Alice yBob que quieren transmitirse dicha información. Cada uno de ellos tendrá un qubit (HAyHBrespectivamente) que previamente habrán entrelazado obteniendo el estado |EPRidel sistema formado por la composición de ambos qubits H=HA⊗HB. Una vez se han separado, Bob simplemente tendrá que alterar su qubit de forma que el estado conjunto se transforme en el estado de la base EPR (consultar anexo) que le interese siguiendo la siguiente tabla. Mensaje a transmitir Transformación Estado obtenido 00 Id |EPRi 01 Z:= 1 0 0−1!|00i−|11i √2 10 X:= 0 1 1 0!|10i+|01i √2 11 −iY:= 0−1 1 0!|01i−|10i √2 Tras esto, Bob enviará su qubit a Alice que llevará a cabo una medición proyectiva en la base EPR para discernir en que estado se encuentra el sistema conjunto, recibiendo 2bits de información habiendo sido enviado únicamente un qubit. Página 20 §1.2. ENTRELAZAMIENTO CUÁNTICO 1.2.2. Teleportación cuántica Este fenómeno de nombre también exagerado puede verse como el recíproco del anterior, ya que nos permite transmitir un qubit enviando únicamente dos bits de información. Para ello usaremos los siguientes operadores que introduciremos en el capítulo 2: H=1 √2 1 1 1−1!,CNOT =      1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0       . Supongamos que nos encontramos en la situación anterior, en la cual Alice y Bob comparten un sistema de dos qubits en el estado |EPRi. Supongamos que Alice quiere transmitir a Bob el qubit |ψi=α|0i+β|1i. Para ello, hará interaccionar dicho qubit con el sistema que ya compartían, obteniendo un nuevo sistema de tres qubits HA0⊗HA⊗HBen el estado: 1 √2hα|000i+α|011i+β|100i+β|111ii. Tras esto, Alice, que puede alterar únicamente los dos primeros qubits, aplicará sobre estos el operador unitario CNOT ⊗I, manteniendo el tercer qubit inalterado y obteniendo el estado: 1 √2hα|000i+α|011i+β|110i+β|101ii. Y posteriormente aplicará el operador H⊗I⊗I, obteniendo el estado: 1 2hα(|000i+|100i+|011i+|111i) + β(|010i−|110i+|001i−|101i)i= 1 2h|00i(α|0i+β|1i)+ |01i(β|0i+α|1i)+ |10i(α|0i−β|1i)+ |11i(β|0i−α|1i)i. Finalmente, Alice llevará a cabo una medición de sus dos qubits en la base computacional y enviará el resultado a Bob. Una vez recibido el mensaje, Bob simplemente tendrá que aplicar la transformación dada por la tabla para obtener el qubit |ψi=α|0i+β|1i. Página 21 algoritmos fundamentales en computación cuántica Mensaje recibido Transformación necesaria Estado de HB 00 Id α|0i+β|1i 01 X:= 0 1 1 0!β|0i+α|1i 10 Z:= 1 0 0−1!α|0i−β|1i 11 −iY:= 0−1 1 0!β|0i−α|1i Obteniendo Bob el estado buscado habiendo sido enviados únicamente dos bits de información clásica. 1.2.3. En computación La consecuencia más interesante del entrelazamiento para nosotros será que, sin este fenómeno, la computación cuántica no aporta ninguna ventaja sobre la clásica, lo que podemos ver gracias al siguiente resultado. Teorema 1.1. Gottesman-Knill. Un algoritmo cuántico que comienza en la base computacional y no hace uso del entrelazamiento cuántico puede ser simulado en tiempo polinomial por un ordenador clásico probabilístico. [6] Página 22 Capítulo 2 Modelos de computación cuánticos “I know there’s a proverb which that says ’To err is human,’ but a human error is nothing to what a computer can do if it tries.” -Agatha Christie. Una vez ya hemos consolidado los postulados y fenómenos de la mecánica cuántica podemos por fin plantearnos la construcción de modelos de computación cuánticos. Estos modelos se fundamentan necesariamente sobre dichos cimientos, pero al igual que ocurre con los modelos de computación clásicos, existen diferentes versiones análogas cada una de las cuales presenta sus logros y desventajas. 2.1. Maquinas de Turing cuánticas Fue David Deutsch quien basándose en los trabajos de Feynman, Manin y Benioff puso los primeros ladrillos y formalizó el concepto de máquina de Turing cuántica y el de ordenador cuántico universal en [3]. El concepto de máquina de Turing cuántica es análogo al clásico, pero presenta algunos cambios que lo hacen demasiado complejo de definir y trabajar con él, por lo que trabajaremos con el posteriormente introducido modelo cuántico de circuitos, que es completamente equivalente. Como idea sobre el funcionamiento de estas máquinas de Turing cuánticas, el conjunto de estados usual se sustituye por el correspondiente espacio de estados mientras que el lugar de la función de transición lo ocupan transformaciones unitarias de dicho espacio de estados, lo que justifica el modelo de circuitos. algoritmos fundamentales en computación cuántica 2.2. Modelo de circuitos cuántico El modelo de circuitos cuántico fue introducido por David Deutsch en [4] y es análogo a su correspondiente versión clásica con algunas diferencias. La primera salvedad es que por nuestros cables circulará información cuántica. En concreto, por cada cable circulará un qubit. La segunda diferencia será referente a las puertas lógicas, que serán sustituidas por puertas cuánticas. Definición 2.1. Puerta cuántica. Sea Hun sistema cuántico formado por composición de qubits. Una puerta cuántica es una transformación unitaria de H. De esta forma, en el contexto del modelo de circuitos, llamaremos puertas cuánticas a las transformaciones unitarias descritas en el postulado 2. Esto nos aporta además una diferencia adicional con el modelo clásico: las puertas cuánticas tienen necesariamente la misma cantidad de entradas que de salida, ya que todas las transformaciones son reversibles. Finalmente, la tercera diferencia es que en cualquier punto de un algoritmo cuántico podremos llevar a cabo una medición en uno o más qubits, obteniendo un resultado aleatorio en función del estado en el que se encontraba el cable medido. Siguiendo la analogía con el modelo clásico, podremos representar un algoritmo en el modelo de circuitos como un diagrama en el cual los cables son líneas horizontales que se leen de izquierda a derecha. A la izquierda de cada cable aparecerá el estado inicial y las puertas cuánticas estarán representadas por rectángulos en las que entrarán y saldrán algunos cables. Las mediciones aparecerán en forma de triángulos al final del cable. A continuación se presenta un ejemplo. Página 24 §2.3. PUERTAS CUÁNTICAS Figura 2.1: Ejemplo de un circuito 2.3. Puertas cuánticas Llegados a este punto merece la pena estudiar algunas de las puertas cuánticas más usadas y sus resultados más importantes. 2.3.1. Puertas de un qubit Veamos en primer lugar algunas de las puertas que actúan sobre un solo qubit, comenzando por la que quizás sea la más empleada de todas: la puerta de Hadamard. Definición 2.2. Puerta de Hadamard. Definimos la puerta de Hadamard como la siguiente puerta cuántica de un qubit. H=1 √2 1 1 1−1!. Quizás entendamos mejor esta puerta si consideramos su efecto sobre la base computacional. Lema 2.1.El efecto de la puerta de Hadamard sobre la base computacional del qubit es: H|ji=1 √2|0i+ (−1)j|1i, para j= 0,1. Como podemos comprobar, la puerta de Hadamard transforma estados de la base computacional en estados en el que todos los estados de la base computacional aparecen combinados con la misma probabilidad. Página 25 algoritmos fundamentales en computación cuántica Of:|xin|yim7→ |xin|y⊕f(x)im, para x∈ {0,1}ney∈ {0,1}m. Por ejemplo, la puerta CNOT ya estudiada es la puerta oráculo de la aplicación constante i:{0,1}→{0,1}. Aplicando la puerta oráculo al estado |xin|0imobtenemos |xin|f(x)im, en el cual el último registro, llamado qubit objetivo, recoge el valor de f(x). A primera vista estas puertas no alteran el estado de los primeros nqubits, ya que actúan sobre los múltimos. Sin embargo, tras algo de observación descubrimos que podemos usarlas para diferenciar los valores de fsegún su imagen gracias al siguiente resultado, previo al cual introduciremos la base de Hadamard del qubit: (|+i=|0i+|1i √2,|−i =|0i−|1i √2). Lema 3.1.Sea f:{0,1}n→ {0,1}una aplicación, cualquier estado de la forma |xin⊗|−i es un autovalor de la puerta Ofcon autovector (−1)f(x). Demostración. Podemos descomponer el estado |xin|−i (sobrentenderemos el subíndice na partir de ahora) como: 1 √2|xi|0i−|xi|1i. Y por tanto, al aplicar Ofobtenemos: Of 1 √2|xi|0i−|xi|1i=1 √2|xi|f(x)i−|xi|1⊕f(x)i =   1 √2|xi|0i−|xi|1isi f(x)=0 1 √2|xi|1i−|xi|0isi f(x)=1, lo que se corresponde con (−1)f(x)|xi|−i. De esta forma, sea X⊂ {0,1}nun subconjunto de estados de la base computacional de nqubits y |ϕinun estado combinación de los mismos Página 32 §3.2. PROBLEMA DEL SUBGRUPO OCULTO |ϕin=1 q|X|X x∈X|xin. Entonces, al aplicar Ofsobre |ϕin|−i obtendremos el estado:  1 q|X|X x∈X (−1)f(x)|xin ⊗|−i. Codificando aquellos elementos cuya imagen es 1invirtiendo su signo. A esta técnica es a lo que llamamos Phase Kick-Back, y la usaremos de forma frecuente. 3.2. Problema del subgrupo oculto A continuación vamos a construir nuestros primeros algoritmos usando la técnica descrita anteriormente. Estos primeros algoritmos tendrán en común que pretenderán resolver el problema del subgrupo oculto en alguna de sus versiones. Definición 3.2. Problema del subgrupo oculto. Sea Gun grupo finitamente generado, K⊂Gun subgrupo y Xun conjunto finito con una aplicación f:G→Xtal que f(x) = f(y)⇐⇒ xK =yK (resp. a derecha), entonces denominamos problema del subgrupo oculto o HSP (del inglés "hidden subgroup problem") al problema de determinar un conjunto generador de Kusando fcomo una caja negra. Los problemas que plantearemos a continuación serán versiones del HSP para cuya resolución vamos a construir algoritmos que trabajen en tiempo polinomial. Comenzaremos por problemas sencillos para acabar llegando finalmente al algortimo de factorización de Shor, el que quizás sea el más conocido de los algoritmos cuánticos hasta la fecha. Página 33 algoritmos fundamentales en computación cuántica 3.2.1. Algoritmo de Deutsch El primer problema que vamos a lanzar a la arena de combate será una versión de HSP para la cual G= ({0,1},⊕)yX={0,1}. Es decir, sea f:{0,1} → {0,1} dada como una caja negra, el objetivo es determinar si fes constante o no, lo que se corresponde con averiguar si K={0,1}(fconstante) o K={0}(fno constante). Veamos como podemos llevarlo a cabo con una sola aplicación de la puerta Of. Algoritmo de Deutsch: INICIO |ϕ0i2← |0i⊗|1i Como queremos obtener el estado |+i⊗|−ipara poder aplicar el Phase Kick-Back, lo más sencillo será comenzar en este estado y aplicar la puerta de Hadamard a ambos qubits. PASO 1 |ϕ1i2←H⊗2(|ϕ0i2) Como ya esperábamos |ϕ1i2= |0i+|1i √2!⊗ |0i−|1i √2!=|+i|−i, por lo que ahora podemos aplicar la puerta oráculo. PASO 2 |ϕ2i2←Of|ϕ1i2 Usando el Phase Kick-Back podemos convencernos de que tras aplicar la puerta Página 34 §3.2. PROBLEMA DEL SUBGRUPO OCULTO oráculo hemos obtenido el estado |ϕ2i2=Of |0i|−i+|1i|−i √2!= (−1)f(0)|0i+ (−1)f(1)|1i √2!⊗|−i. Por lo que hemos codificado en el signo de las amplitudes del primer qubit si la aplicación fes constante o no. Si aplicamos ahora la puerta de Hadamard en el primer registro para obtener un estado de la base computacional estaremos listos para medir y obtener el resultado. PASO 3 |ϕ3i2←(H⊗I)|ϕ1i2 Para entender bien el resultado de este paso consideremos las dos posibles situaciones. Si f(0) = f(1), entonces |ϕ2i2= (−1)f(0)|+i|−i, por lo que al aplicar H⊗I obtenemos |ϕ3i2= (−1)f(0)|0i|−i. Si f(0) 6=f(1), entonces |ϕ2i2= (−1)f(0)|−i|−i, y al aplicar H⊗Iobtenemos |ϕ3i2= (−1)f(0)|1i|−i. En general, el resultado tras el paso 3será: |ϕ2i2= (−1)f(0)|f(0) ⊕f(1)i|−i. PASO 4 δ←medimos el primer qubit. Como era previsible, tras medir el primer registro obtendremos δ∈ {0,1}. Si δ= 0, entonces f(0) = f(1) y por tanto K={0,1}. Si por otro lado δ= 1 entonces f(0) 6=f(1) y por tanto K={0}.Gracias a este análisis podemos enunciar el siguiente teorema de corrección. Página 35 algoritmos fundamentales en computación cuántica Teorema 3.1. Corrección del algoritmo de Deutsch. El algoritmo de Deutsch resuelve el HSP para G={0,1}yX={0,1}con una única aplicación de la puerta oráculo. Con este simple problema ya podemos observar la ventaja de los algoritmos cuánticos frente a los clásicos. Un algoritmo clásico determinista necesita dos comprobaciones de fpara resolver este problema, mientras que nuestro algoritmo puede aplicar fa ambos estados a la vez y por tanto resolverlo con una única aplicación. 3.2.2. Algoritmo de Deutsch-Jozsa La pregunta que nos surge ahora es, ¿podremos generalizar este resultado para el caso en el que tenemos una aplicación f:{0,1}n→ {0,1}? Este será el objetivo de nuestro próximo algoritmo. El problema que nos plantearemos ahora será el de, dado el grupo G= ({0,1}n,⊕) yX={0,1}determinar si la aplicación fes constante o no. Dado que se trata de un problema de subgrupo oculto, en caso de no ser constante será equilibrada, es decir, habrá tantos valores x∈ {0,1}ncon f(x) = 0 como valores con f(x) = 1. Este problema se conoce como el problema de Deutsch. Definición 3.3. Problema de Deutsch. Se llama problema de Deutsch al problema del subgrupo oculto en el cual G= ({0,1}n,⊕)yX={0,1}. Veamos el algoritmo que lo resuelve. Algoritmo de Deutsch-Jozsa: INICIO |ϕ0in+1 ← |0in⊗|1i Nuevamente queremos obtener un estado de la forma |xin|−i siendo |xinuna combinación de todos los estados de la base computacional con la misma amplitud. Página 36 §3.2. PROBLEMA DEL SUBGRUPO OCULTO PASO 1 |ϕ1in+1 ←H⊗n+1(|ϕ0in+1) Como ya esperábamos |ϕ1in+1 = 1 √2n 2n−1 X x=0 |xin!⊗|−i. PASO 2 |ϕ2in+1 ←Of|ϕ1in+1 Usando el Phase Kick-Back no es complicado comprobar que |ϕ2in+1 = 1 √2n 2n−1 X x=0 (−1)f(x)|xin!⊗|−i, donde nuevamente hemos codificado el valor de los estados de base en sus amplitudes. PASO 3 |ϕ3in+1 ←H⊗n⊗I|ϕ1in+1 Usando ahora la proposición 2.1podemos comprobar que el estado antes de la medición es |ϕ3in+1 = 1 2n 2n−1 X y=0 2n−1 X x=0 (−1)f(x)+x·y!|yin ⊗|−i. Página 37 algoritmos fundamentales en computación cuántica PASO 4 ¯ δ←medimos los nprimeros qubits de |ϕ3in+1 Y aunque parezca un estado muy complicado, basta comprobar que la amplitud de |0incumple que: |a0|2= 1 √2n 2n−1 X x=0 (−1)f(x) 2 =   1si fes constante 0si fes equilibrada. Este análisis nos permite enunciar el teorema de corrección. Teorema 3.2. Corrección del algoritmo de Deutsch-Jozsa. El algoritmo de Deutsch-Jozsa resuelve el problema de Deutsch con una única aplicación de la puerta oráculo. Esto tiene unas implicaciones mucho más profundas que en el caso anterior, ya que para resolver este problema un algoritmo clásico determinista necesitaría 2n−1+1 comprobaciones del oráculo de f. Como consecuencia, la versión de decisión del problema de Deutsch se encuentra en la clase EQP de aquellos problemas que se pueden resolver de forma exacta mediante un algoritmo cuántico en tiempo polinomial, pero no pertenece a su análogo determinista P. 3.2.3. Algoritmo de Simon Veamos otro problema de subgrupo oculto antes de proceder con el algoritmo de Shor. Se tratará del problema de Simon. Definición 3.4. Problema de Simon. Sea f:{0,1}n→ {0,1}nuna aplicación y s∈ {0,1}ntal que f(x) = f(y)si y solo si o bien x=y⊕so bien y=x⊕s. El problema de Simon trata de encontrar susando fcomo una caja negra. Página 38 §3.2. PROBLEMA DEL SUBGRUPO OCULTO Observación 3.1.El problema de Simon es un problema de subgrupo oculto con G= ({0,1}n,⊕),X={0,1}nyKes de la forma K={0, s}para algún s∈ {0,1}n. Además, a sse la suele llamar la máscara xor de f. Veamos el algoritmo para resolver este problema. Algoritmo de Simon: INICIO |ϕ0i2n← |0in⊗|0in En este caso queremos obtener f(x)para cada x∈ {0,1}nen los núltimos qubits. PASO 1 |ϕ1i2n←H⊗n⊗I⊗n(|ϕ0i2n) Nuevamente por la proposición 1.2obtenemos |ϕ1i2n=1 √2n 2n−1 X x=0 |xin|0in. PASO 2 |ϕ2i2n←Of|ϕ1i2n Según era nuestro objetivo, tras aplicar la puerta oráculo el estado será |ϕ2i2n=1 √2n 2n−1 X x=0 |xin|f(x)in. Página 39 algoritmos fundamentales en computación cuántica PASO 3 ¯ δ←medimos los nqubits finales de |ϕ2i2n |ϕ3in← |ϕ2i2ntras la medición Aquí usamos una nueva herramienta no empleada hasta ahora, llevar a cabo una medición previamente al final del algoritmo. El objetivo es que si obtenemos un determinado ¯ δ∈ {0,1}n, gracias al entrelazamiento el estado que quedará en los nprimeros qubits será |ϕ3in=1 √2|x0in+|x0⊕sin, siendo {x0, x0⊕s}=f−1(¯ δ). PASO 4 |ϕ4in←H⊗n(|ϕ3in) Si calculamos el resultado de este paso obtenemos: |ϕ4in=H⊗n|ϕ3in=1 √2H⊗n|x0in+H⊗n|x0⊕sin =1 √2 1 √2n 2n−1 X y=0 (−1)y·x0|yin+1 √2n 2n−1 X z=0 (−1)z·(x0⊕s)|yin  =1 √2n+1 2n−1 X y=0 (−1)y·x0[(−1)y·s|yin], donde lo realmente importante es que los estados |yinde la base computacional cuya amplitud no es cero cumplen que y·s= 0 y tras medir los obtenemos con probabilidad 1/2n−1. Página 40 §3.3. ALGORITMO DE SHOR PASO 5 ¯ω←medimos |ϕ4in Si obtenemos al menos n−1resultados ¯ωilinealmente independientes tales que ¯ω·s= 0 podemos obtener sresolviendo un sistema de ecuaciones, por lo que la pregunta es cuántas veces tenemos que iterar el algoritmo para obtener suficientes ecuaciones. Teorema 3.3. Corrección del algoritmo de Simon. El algoritmo de Simon resuelve el problema de Simon con probabilidad al menos 2/3con una O(n)aplicaciones de la puerta oráculo y O(n3)aplicaciones de otras puertas elementales si llevamos a cabo n+ 3 repeticiones del algoritmo. [7] La importancia de este problema reside en que un algoritmo probabilístico necesita Ω(2n/3)evaluaciones de fpara obtener la solución con probabilidad al menos 2/3, por lo que estamos frente a una mejora exponencial frente al caso clásico no determinista. 3.3. Algoritmo de Shor Por último veamos el más importante de los algoritmos cuánticos a razón de sus múltiples aplicaciones: el algoritmo de Shor. Este algoritmo resuelve el problema de la factorización, que dado un entero N∈ Z≥0pretende encontrar la única descomposición en factores primos que garantiza el Teorema Fundamental de la Aritmética. Antes de comenzar veamos una importante técnica que introduce este algoritmo y que se puede extender a otros algoritmos cuánticos. 3.3.1. Transformada de Fourier cuántica Hasta ahora hemos usado la puerta de Hadamard seguida de una puerta oráculo para codificar información el las amplitudes de la combinación de todos los estados Página 41 algoritmos fundamentales en computación cuántica Definición 4.1. Problema de Búsqueda. Sea nun entero positivo y Ofun oráculo para computar la función f:{0,1}n→ {0,1}, el Problema de Búsqueda asociado a estos datos será encontrar un x∈ {0,1}ntal que f(x) = 1. En concreto vamos a suponer que existe un único valor válido, aunque posteriormente eliminaremos esta condición. Una vez tenemos formalizado el problema, podemos plantearnos la siguiente pregunta: ¿cuántas llamadas a Ofnecesitamos para resolver este problema con probabilidad al menos 2/3? En el caso clásico necesitamos Ω(2n)llamadas, ya que tendremos que hacer una búsqueda exhaustiva. De forma intuitiva, podemos comprobar fácilmente que si tomamos secuencialmente kelementos de forma aleatoria entre los {0,1}n, la probabilidad de que uno de ellos sea el xtal que f(x) = 1 es k/2n. Sin embargo, en el caso cuántico existe un algoritmo, llamado Algoritmo de Grover, que es capaz de hallar la solución con alta probabilidad realizando O(√2n) llamadas a Of, lo que supone una mejora cuadrática del caso clásico. Procedamos a describir este algoritmo. 4.1.1. Algoritmo de Grover Nuevamente vamos a suponer que se nos provee una puerta oráculo del sistema de n+ 1 qubits Of:Hn+1 → Hn+1 cuyo efecto, recordamos, es: Of:|xin⊗|bi 7→ |xin⊗|b⊕f(x)i, lo que nos permite computar la aplicación fpreparando el último qubit (qubit objetivo) en el estado |0i. Como era de esperar, vamos a apoyarnos en la idea del Phase Kick-Back para señalar el único estado que verifica la propiedad, con el aliciente de que ahora aplicaremos técnicas para aumentar la amplitud de dicho estado. Para ello veamos una nueva puerta cuántica, llamada puerta de cambio de fase, cuyo efecto será alterar la amplitud de todos los estados ortogonales a |0inen un sistema de nqubits, dejando el estado |0ininvariante. Página 48 §4.1. PROBLEMA DE BÚSQUEDA Definición 4.2. Cambio de fase. Sea Hun sistema de nqubits, llamaremos puerta de cambio de fase del sistema a la puerta cuántica U0⊥:H → H cuyo efecto en la base computacional es:    U0⊥:|0in7→ |0in U0⊥:|xin7→ −|xinsi x6= 0. Consideremos además la siguiente puerta cuántica que construiremos a partir del cambio de fase y que llamaremos puerta de difusión de Grover. Definición 4.3. Puerta de difusión de Grover. Llamaremos peurta de difusión de Grover a la siguiente puerta cuántica. Γn=H⊗nU0⊥H⊗n. Para entender el efecto de esta puerta tomemos la base ortonormal del sistema de nqubits dada por: (|ψiin=H⊗n|iin|i= 0,...,2n−1), y veamos el siguiente resultado. Lema 4.1.Sea Γnla puerta cuántica definido anteriormente, su efecto en la base de los |ψiies el siguiente: Γn|ψii=  |ψiinsi i= 0 −|ψiines caso contrario. Demostración. Basta hacer la comprobación, en la que H⊗n=Hpor simplicidad: Γn|ψii=HU0⊥HH|ii=HU0⊥|ii=   H|iisi i= 0 −H|iien caso contrario. Y tenemos el resultado. Veamos ahora algunas propiedades importantes de esta puerta cuántica. Página 49 algoritmos fundamentales en computación cuántica Proposición 4.1.Sea Γnla puerta de difusión, {|ψii} la base ortogonal dada y N= 2n, entonces: i. Γn= 2|ψ0ihψ0|−I. ii. El estado |ϕi= N−1 X x=0 αx|xies ortogonal a |ψ0isi y solo si: N−1 X x=0 αx= 0. iii. Sea |ϕi= N−1 X x=0 αx|xiun estado cualquiera, y sea µla media de sus amplitudes: µ=1 N N−1 X x=0 αx. Entonces: Γn|ϕi= N−1 X x=0 (2µ−αx)|xi. Demostración. i. Para esto veamos que ambas puertas tienen el mismo efecto sobre la base {|ψii}. Es decir: 2|ψ0ihψ0|−I|ψ0i= 2|ψ0ihψ0|ψ0i−|ψ0i=|ψ0i. Y para i6= 0: 2|ψ0ihψ0|−I|ψii= 2|ψ0ihψ0|ψii−|ψii=−|ψii. ii. Calculemos: hϕ|ψ0i= N−1 X x=0 αxhx|! N−1 X x=0 |xi!= N−1 X x=0 αx= 0. iii. En primer lugar, escribamos |ϕicomo α|ψ0i+β|¯ ψ0idonde |¯ ψ0ies un estado ortogonal a |ψ0i.Para ello, tomemos: |ϕi=µ|ψ0i+β N−1 X x=0 αx−µ β|xi!. El estado |¯ ψ0i= N−1 X x=0 αx−µ β|xi, donde β=v u u t N−1 X x=0 |αx−µ|2 Página 50 §4.1. PROBLEMA DE BÚSQUEDA es ortogonal a |ψ0i, ya que si sumamos sus amplitudes: N−1 X x=0 αx−µ β= N−1 X x=0 αx!−Nµ β= 0. Estudiando el efecto de Γny usando itenemos que: Γn|ϕi=µ|ψ0i−β N−1 X x=0 αx−µ β|xi!= µ N−1 X x=0 |xi!+β N−1 X x=0 αx−µ β|xi!= N−1 X x=0 (2µ−αx)|xi. Y obtenemos el resultado buscado. A la puerta cuántica resultante de aplicar primero Ofy posteriormente Γnla denotaremos puerta de Grover. Definición 4.4. Puerta de Grover. Llamaremos puerta de Grover a la puerta cuántica del sistema de n+ 1 qubits: G= (Γn⊗I)Of. Veamos cómo podemos usar esta puerta para aumentar la amplitud del estado que nos interesa. Lema 4.2.En las condiciones del problema de búsqueda, sea x0∈ {0,1}ntal que f(x0)=1, y sea |ψ(α, β)i=α|x0i+β    N−1 X x=0 x6=x0 |xi   . Tal que |α|2+ (N−1)|β|2= 1. Sea |ψ(α0, β0)in⊗|−i =G(|ψ(α, β)in⊗|−i),entonces: α0=2N−2 Nβ+N−2 Nα, β0=N−2 Nβ−2 Nα. Página 51 algoritmos fundamentales en computación cuántica Demostración. En primer lugar calculamos Of|ψ(α, β)i⊗|−i=−α|x0i|−i+β    N−1 X x=0 x6=x0 |xi|−i   . Y aplicando Γn⊗I, por el resultado anterior que µ=(N−1)β−α Ny por tanto: α0= (2µ+α) = 2N−2 Nβ−2 Nβ+α=2N−2 Nβ+N−2 Nα. β0= (2µ−β) = 2N−2 Nβ−2 Nα−β=N−2 Nβ−2 Nα. Corolario 4.1.Aplicar Gal estado |ψ(α, β)in⊗|−i aumenta la amplitud de |x0i en |ψ(α0, β0)insi y solo si (N−1)β > α. Estamos ahora preparados para presentar el algoritmo de Grover. Algoritmo de Grover: INICIO |ϕ0in+1 ← |0in⊗|1i PASO 1 |ϕ1in+1 ←H⊗n+1(|ϕ0in+1) PASO 2 |ϕ2in+1 ←G|ϕ1in+1 Página 52 §4.1. PROBLEMA DE BÚSQUEDA PASO 3 Se repite el paso 2hasta alcanzar amplitud máxima en el registro que nos interesa, lo que debemos de llevar a cabo O(√2n)veces. Tras esto, medimos los primeros nqubits. Antes de analizar el algoritmo veamos un ejemplo. Ejemplo: Consideremos el caso n= 4 yx0= 7. El algoritmo comenzará en el estado: |0i4|1i,y tras el paso 1tendremos el estado: H⊗5|0i4|1i= 1 4 15 X x=0 |xi4!⊗|−i, en el que todos los elementos de base tienen la misma amplitud. Al aplicar Of obtenemos el estado:    −1 4|7i4+1 4 15 X x=0 x6=7 |xi4   ⊗|−i, en el que el |7iaparece señalado con el cambio de signo de la amplitud. Si aplicamos ahora Γ4⊗Iobtenemos:     11 16|7i4+5 16 15 X x=0 x6=7 |xi4   ⊗|−i. Y hemos aumentado la amplitud de |7ide α0= 0.25 aα1≈0.4726. Si volvemos a aplicar Gpodemos comprobar que obtenemos α2≈0.9084 y si la volvemos a aplicar otra vez obtenemos α3≈0.9613 y podríamos plantearnos hasta cuando podemos aplicar Gy seguir aumentando la amplitud. Por desgracia, si volvemos a aplicar Gobtenemos α4≈0.5817, por lo que es necesario estudiar más rigurosamente como evoluciona la iteración de esta puerta. Para ello, consideremos el siguiente resultado. Página 53 algoritmos fundamentales en computación cuántica Teorema 4.1. Corrección del algoritmo. El algoritmo de Grover necesita O(2n)iteraciones de Gpara maximizar la amplitud del estado deseado |x0i. Demostración. Para facilitar la prueba consideremos los siguientes estados. Sea |x0inel estado buscado y N= 2n, definiremos: |γin=1 √N−1 N−1 X x=0 x6=x0 |xin. Sea ahora θtal que sen (θ) = 1/√N, consideramos los estados ortogonales: |ψ0i= sen (θ)|x0i+ cos (θ)|γi,|¯ ψ0i= cos (θ)|x0i+ sen (θ)|γi. El estado del algoritmo tras el paso 1será: |ψ0i⊗|−i = (sen (θ)|x0i+ cos (θ)|γi)⊗|−i. Y tras aplicar Of, usando las relaciones |x0i= sen (θ)|ψ0i+ cos (θ)|¯ ψ0iy|γi= cos (θ)|ψ0i−sen (θ)|¯ ψ0itenemos el estado: −sen (θ)|x0i+ cos θ|γi⊗|−i =cos (2θ)|ψ0i−sen 2θ|¯ ψ0i⊗|−i. Y tras aplicar Γn⊗I=2|ψ0ihψ0|−I⊗Iobtenemos: cos (2θ)|ψ0i+ sen (2θ)|¯ ψ0i⊗|−i =sen (3θ)|x0i+ cos (3θ)|γi⊗|−i. Siguiendo este razonamiento podemos probar por inducción que tras aplicar m veces la puerta de Grover Gobtendremos el estado: sen ((2m+ 1) θ)|x0i+ cos ((2m+ 1) θ)|γi⊗|−i. Por tanto, nuestro problema será encontrar el mayor mtal que θ(2m+ 1) ≤π/2, lo que se traduce en m≤(π−2θ)/4θy por tanto m=b(π−2θ)/4θc.Dado que si nes grande θ≈1 √2ntenemos que m∼ O(√2n). Página 54 §4.1. PROBLEMA DE BÚSQUEDA El interés del algoritmo de Grover reside en que la mejora cuadrática que plantea, a pesar de ser inferior a la que dan otros algoritmos, es estricta frente al caso clásico. En otros algoritmos (el algoritmo de Shor por ejemplo) la mejora se basa en la hipótesis de que no se pueden mejorar las versiones clásicas de los algoritmos que resuelven el problema dado. 4.1.2. Soluciones múltiples Supongamos ahora que nos encontramos de nuevo en la situación del problema de búsqueda, pero en este caso existirá todo un conjunto de elementos A={x∈ {0,1}n|f(x) = 1}que verifican nuestra condición con |A|=t. Para facilitarnos el trabajo denotaremos como B=¯ Acon |B|= 2n−t. Veamos cómo podemos generalizar la amplificación de amplitudes a este problema. En primer lugar, podemos definir los estados: |ψAi=1 √tX x∈A|xin,|ψBi=1 √2n−tX x∈B|xin. Entonces, si aplicamos las puertas de Hadamard obtendremos el estado |ψ0in+1 =st 2n|ψAin+s2n−1 2n|ψBin. Sea ahora θtal que sen (θ) = qt/2npodemos escribir nuestro estado como: |¯ ψ0in= cos(θ)|ψAin−sen(θ)|ψBin. Definiendo su estado ortogonal |ψ0in= sen(θ)|ψAin+ cos(θ)|ψBin, podemos llevar a cabo el mismo análisis que en el caso anterior y llegar al siguiente resultado. Página 55 algoritmos fundamentales en computación cuántica Lema 4.3.Tras aplicar mveces la puerta de Grover Ga|¯ ψ0in⊗|−i el estado: sen ((2m+ 1) θ)|ψAi+ cos ((2m+ 1) θ)|ψBi⊗|−i. El problema ahora reside en calcular cuantas veces hemos de aplicar la puerta de Grover para aumentar la probabilidad de obtener uno de los estados que nos interesan, lo que se complica ya que el valor de θdepende de tque es en principio desconocido. La cantidad de iteraciones que debemos aplicar es del orden O(q2n/t)pero no probaremos dicho resultado. [2] 4.2. Quantum counting El problema que se presentaba en el caso anterior va a inspirar esta sección. Definición 4.5. Counting problem. Sea nun entero positivo y Ofuna puerta oráculo para computar la función f: {0,1}n→ {0,1}, el counting problem es el problema de determinar el número de valores x∈ {0,1}nque verifican f(x)=1. Para resolver este problema haremos uso no solo de la amplificación de amplitudes si no también de la transformada de Fourier cuántica. En términos de lo visto en la sección anterior, nuestro objetivo a partir de ahora no será hallar un valor que satisfaga la función; nuestro objetivo será hallar cuántos valores satisfacen dicha condición. Recordando la notación anterior, tendremos que A={x∈ {0,1}n|f(x) = 1} con |A|=tyB=¯ Acon |B|= 2n−ty nuestro objetivo será hallar t. De esta forma, volveremos a tener los estados: |ψAi=1 √tX x∈A|xin,|ψBi=1 √2n−tX x∈B|xin. Antes de ver el algoritmo estudiemos una de las puertas que usa y sus efectos: la puerta de conteo. Página 56 §4.2. QUANTUM COUNTING Definición 4.6. Puerta de conteo. Definimos la puerta de conteo Cp,n del sistema de p+nqubits como aquella cuyo efecto en la base computacional es el siguiente: Cp,n :|xip⊗|yin7→ |xip⊗(Gx n)|yin, para x∈ {0,1}p,y∈ {0,1}nyGnes la puerta de Grover tras aplicarla al sistema de n+ 1 qubits con el qubit objetivo en el estado |−i y descartar dicho qubit. Para ver sus efectos veamos un resultado previo. Lema 4.4.Sea Gncomo hemos definido anteriormente y ωtal que sen2(πω) = t/2n, entonces: 1. Los estados |µ+in=1 √2|ψBin−i|ψAin,|µ−in=1 √2|ψBin+i|ψAin, con autovectores de Gncon autovalores e2iω ye−2iω respectivamente. 2. Sea |γin=1 √2n−1 2n−1 X x=0 x6=x0 |xin. Entonces |γin= sen(πω)|ψAin+ cos(πω)|ψBin=eiπω √2|µ+in+e−iπω √2|µ−in. Demostración. En primer lugar es sencillo comprobar que |γin= sen(πω)|ψAin+ cos(πω)|ψBin. Y tras ello podemos ver que Gn|ψAin=2|γihγ|n−I⊗n(−|ψAin)=2|γihγ|n+|ψAin =−2 sen(πω)|γin+|ψAin=−2 sen(πω) cos(πω)|ψBin+1−2 sen2(πω)|ψAin =−sen(2πω)|ψBin+ cos(2πω)|ψAin. Página 57 algoritmos fundamentales en computación cuántica es teórico. La inclusión de este modelo teórico en el plano de las ciencias de la computación permite establecer nuevas relaciones entre las ya bien conocidas clases de complejidad computacional de los modelos clásicos, por lo que el desarrollo de algoritmos cuánticos puede aportar nuevas vías para resolver problemas de complejidad ya conocidos. Página 64 Anexo: Notación “Good advice is always certain to be ignored, but that’s no reason not to give it.” -Agatha Christie. Durante el desarrollo de toda la memoria usaremos la notación particular llamada notación de Dirac. Para sentar las bases de dicha notación y evitar confusiones es conveniente resumirla en este anexo. Los vectores se notarán como kets:|ψi. Los vectores duales se notarán como bras:hψ|. El producto escalar de dos vectores se notará como un braket:hψ|ϕi. El producto tensorial de dos vectores se notará como producto de bras o de kets respectivamente: hψ|⊗hϕ|=hψ|hϕ|=hψϕ|y|ψi⊗|ϕi=|ψi|ϕi=|ψϕi. A lo largo del texto introduciremos el concepto de qubit como un espacio de Hilbert bidimensional. Este sistema cuántico tiene ciertas bases con notaciones estandarizadas. La base computacional del qubit es la dada por: |0i= 1 0!y|1i= 0 1!. La base de Hadamard del qubit es la dada por: |+i=1 √2(|0i+|1i) = 1 √2 1 1!y|−i =1 √2(|0i−|1i) = 1 √2 1 −1!. Algunos de los operadores cuánticos (o matrices o puertas cuánticas) de un qubit más importantes son: La puerta de Hadamard, usualmente notada: H=1 √2 1 1 1−1!. algoritmos fundamentales en computación cuántica Cuyo efecto en la base computacional es: H|ji=1 √2|0i+ (−1)j|1i, para j= 0,1. Las matrices de Pauli con respecto a los ejes X,YyZrespectivamente: X= 0 1 1 0!,Y= 0−i i0!,Z= 1 0 0−1!. Cuyos efectos en la base computacional son: X|ji=|1⊕ji,Y|ii= (−i)j|1⊕ji,Z|ji= (−1)j|ji, para j= 0,1. Y podemos comprobar fácilmente que: Lema 5.1.Todos los operadores anteriores son unitarios, y además, las matrices de Pauli son hermíticas. Sea ahora Hun sistema cuántico formado por composición de nqubits, un estado cualquiera de Hse notará |ψin. Sabemos que los productos tensoriales de las bases computacionales de los respectivos qubits formarán una base de H, que llamaremos base computacional, y que estará formada por los elementos de la forma {|i0. . . in−1i} con i0, . . . , in−1= 0,1. Sea un dicho elemento notaremos: |i0. . . in−1i=|ji,siendo j= n−1 X k=0 ik2n−k−1. De esta forma, un elemento arbitrario de Hse escribirá: |ψin= 2n−1 X i=0 αi|ii. Además, identificando Hcon C2ntenemos el siguiente resultado. Lema 5.2.El elemento de la base |iise corresponde con el elemento de la base canónica de C2nque tiene un 1en la posición i+ 1. Página 66 §anexo: notación La prueba es elemental por inducción. Otra importante base del sistema formado por 2qubits es la base EPR, llamada así en honor a Albert Einstein, Boris Podolsky y Nathan Rosen. Es la dada por los siguientes estados: |00i+|11i √2,|00i−|11i √2,|01i+|10i √2,|01i−|10i √2. De ellos, solo el primero se conoce como estado EPR. |EPRi=|00i+|11i √2. La importancia de esta base es que se trata de una base ortonormal de estados entrelazados, por lo que tiene numerosas aplicaciones. De igual manera que podemos considerar productos tensoriales de estados para construir sistemas compuestos, dados unos operadores en los sistemas originales, podemos considerar el producto tensorial de dichos operadores que actuará sobre el sistema compuesto. Sean {Xi}operadores de un qubit, notaremos: X1⊗X2⊗···⊗Xn=X1X2. . . Xn. En casos en el que muchos de estos operadores sean la identidad, podremos acortar esta notación escribiendo como subíndice el sistema sobre el que actúa cada operador y obviando las identidades. Por ejemplo: X3Y5=IIXIYI. Siendo XeYlas correspondientes matrices de Pauli. Algunas de las puertas cuánticas en un sistema de múltiples qubits y sus efectos sobre la base computacional son: El NOT controlado en un sistema de dos qubits: CNOT =      1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0       . Página 67 algoritmos fundamentales en computación cuántica Cuyo efecto sobre la base computacional es: CNOT |iji=|ii|i⊕ji, con i, j ={0,1}. El Ucontrolado en un sistema de dos qubits: CU|0ji=|0ji,CU|1ji=|1iU|ji, con j={0,1}. Cuyo efecto sobre la base computacional es: CU|0ji=|0ji,CU|1ji=|1iU|ji, con j={0,1}. La puerta oráculo asociada a una aplicación f:{0,1}n→ {0,1}men un sistema de n+mqubits, cuyo efecto es: Of:|xin|yim7→ |xin|y⊕f(x)im, para x∈ {0,1}ney∈ {0,1}m. La transformada de Fourier cuántica en un sistema de nqubits con m≤2n, cuyo efecto es: QTFm:|xin7→ 1 √m m−1 X y=0 e2πiyx/m|yin, para x∈ {0,1}n. La puerta de cambio de fase en un sistema de nqubits, cuyo efecto sobre la base computacional es:    U0⊥:|0in7→ |0in U0⊥:|xin7→ −|xinsi x6= 0. La puerta de difusión de Grover en un sistema de nqubits: Γn=H⊗nU0⊥H⊗n. La puerta de Grover asociada a un problema de búsqueda con función característica fen un sistema de n+ 1 qubits: G= (Γn⊗I)Of. La puerta de conteo en un sistema de n+pqubits, cuyo efecto en la base computacional es el siguiente: Cp,n :|xip⊗|yin7→ |xip⊗(Gx n)|yin, para x∈ {0,1}p,y∈ {0,1}n. Página 68 Bibliografía [1] Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., ... & Weinfurter, H. (1995). Elementary gates for quantum computation. Physical review A, 52(5), 3457. [2] Boyer, M., Brassard, G., Høyer, P. & Tapp, A. (1998). Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46(4-5), 493-505. [3] Deutsch, D. (1985). Quantum theory, the Church–Turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818), 97-117. [4] Deutsch, D. (1989). Quantum computational networks. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 425(1868), 73-90. [5] Gómez Serván, C. (2017) Introducción a la mecánica cuántica. http://hdl.handle.net/11441/66967 [6] Gottesman, D. (1998) The Heisenberg representation of quantum computers. arXiv preprint quant-ph/9807006. [7] Kaye, P., Laflamme, R. & Mosca, M. (2007). An introduction to quantum computing. Oxford University Press. [8] Landsberg, J. M. (2018) A very brief introduction to quantum computing and quantum information theory for mathematicians. https://arxiv.org/abs/1801.05893 [9] Lyons, D. W. (2003). An elementary introduction to the Hopf fibration. Mathematics magazine, 76(2), 87-98. [10] Nielsen, M. A. & Chuang I. L. (2010). Quantum Computation and Quantum Information. New York: Cambridge University Press. [11] Ossorio-Castillo, J. & Tornero, J. M. (2018) Quantum computing from a mathematical perspective: a description of the quantum circuit model. arXiv:1810.08277 [12] Pastor Díaz, U. (2018) Códigos correctores de errores cuánticos. https://hdl.handle.net/11441/77568 [13] Pérez-Jiménez, M., & Riscos-Núnez, A. (2004) Modelos de computación celular, molecular y cuántica. Fénix Editorial. Sevilla. [14] Shor, P. W. (1994) Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). IEEE.