Curso: Computación y Criptografía Cuántica


Lección 1. Modelo de Computación Cuántica
Dra. Alfonsa García, Dr. Francisco García, Dr. Jesús García - 19/05/2014


En esta lección se presenta una introducción al modelo de computación cuántica, incluyendo la forma de representar la información, la forma de medir estados cuánticos y las principales puertas de computación cuántica.

El curso completo se compone de tres lecciones:

  Lección 1. Modelo de Computación Cuántica
  Lección 2. Criptografía Cuántica
  Lección 3. Algoritmos Cuánticos

Si deseas descargar las diapositivas del curso en formato pdf, o las soluciones a los ejercicios propuestos, puedes hacerlo desde esta dirección del Material de GIEMATIC (Grupo de innovación educativa).

Los tres vídeos de apoyo a las lecciones de este MOOC presentados por el Dr. Jesús García, son los siguientes:

Seminario de introducción a la Computación y Criptografía Cuántica: 1

Seminario de introducción a la Computación y Criptografía Cuántica: 2

Seminario de introducción a la Computación y Criptografía Cuántica: 3

También puedes ver estos vídeos del "Seminario de Introducción a la Computación y Criptografía Cuántica" directamente en YouTube desde sus correspondientes enlaces:

Seminario de introducción a la Computación y Criptografía Cuántica: 1
Seminario de introducción a la Computación y Criptografía Cuántica: 2
Seminario de introducción a la Computación y Criptografía Cuántica: 3

El tiempo recomendado para el seguimiento de esta lección y la realización de actividades propuestas es de 10 horas semanales durante dos semanas. Puedes ampliar la información consultando el libro Quantum Computation and Quantum Information [4].

Temario

Objetivos

El objetivo de esta lección es presentar una introducción al modelo cuántico de computación y en concreto:

  • 1. Entender cómo usar estados cuánticos para representar la información.
  • 2. Entender los fundamentos del entrelazamiento y del paralelismo cuánticos.
  • 3. Conocer y manejar las puertas cuánticas elementales.

APARTADO 1.1. INTRODUCCIÓN HISTÓRICA


El vertiginoso avance de la computación en las últimas décadas está ligado al uso de transistores cada vez más pequeños y potentes. Pero pronto será imposible acumular más transistores en el mismo espacio, ya que a escala nanométrica las interacciones cuánticas son difíciles de controlar.

La computación cuántica empezó a desarrollarse en la década de los ochenta a raíz de las propuestas de Paul Benioff, David Deutsch y Richard Feynman (ver [3]). En 1982, sugirieron independientemente que, dado el elevado coste computacional del cálculo de la evolución de sistemas cuánticos, la evolución de estos sistemas se podría considerar como una herramienta de cálculo más que como un objeto a calcular. Poco después, en 1985, y también de forma independiente Deutsch propone la búsqueda de un ordenador que sea capaz de simular eficientemente un sistema físico arbitrario [2]. La conjunción de todas estas ideas ha conducido a la concepción actual de ordenador cuántico.  
img/DIAP_1A.jpg
Cuestionar el sistema de computación clásico, que cuenta con una sólida base teórica y con el aval de infinidad de aplicaciones en todos los ámbitos de la vida cotidiana, sólo tiene sentido si el modelo que se propone como alternativo es potencialmente mejor que el actual. En computación clásica la unidad de información es el bit que puede tomar los valores 0 y 1 pero la unidad de información cuántica es el qubit que puede ser una superposición de 0 y 1. Esto permite codificar una cantidad exponencial de información en el estado de un sistema cuántico de n qubits. De este modo, mientras que la capacidad de un ordenador clásico (de almacenamiento y de cálculo) crece linealmente con respecto a su tamaño, la de un ordenador cuántico crece exponencialmente.

Sin embargo, la medición de estados cuánticos es un inconveniente importante para la computación cuántica, ya que las medidas cuánticas no son deterministas. Esto quiere decir, por ejemplo, que si medimos dos estados iguales los resultados no tienen por qué ser iguales. El proceso de medida es un experimento aleatorio en el que la probabilidad de cada resultado está determinada por el estado del sistema.
En 1994 Peter W. Shor sorprendió a todos presentando sendos algoritmos polinomiales para factorizar números enteros y para calcular logaritmos discretos. Fueron los primeros problemas relevantes en los que se alcanzaba una aceleración exponencial con respecto a los mejores algoritmos clásicos conocidos. El algoritmo de Shor rompe teóricamente el sistema criptográfico más difundido en la actualidad, el sistema RSA. Este hecho contribuyó a su vez al desarrollo de los sistemas criptográficos cuánticos. Las técnicas que se utilizan para garantizar la confidencialidad de los canales cuánticos se apoyan en una propiedad característica de la mecánica cuántica: los estados cuánticos no se pueden copiar (clonar) y se modifican irremediablemente cuando se miden. img/DIAP_1A.jpg

Cuestiones para investigar:
Busca información sobre la ley de Moore y las tendencias de la microelectrónica.


APARTADO 1.2. REPRESENTACIÓN DE LA INFORMACIÓN

En computación cuántica la unidad elemental de información es el qubit o bit cuántico, que se define a partir de dos estados básicos denotados por |0> y |1>. Pero, además, el estado cuántico puede ser una superposición de los dos estados básicos, que modelizaremos por una combinación lineal. Ésta es la principal diferencia con el modelo de computación clásico. Un estado cuántico va a ser un vector de la forma a|0>+b|1>.

Físicamente se puede utilizar el spin de un electrón o la polarización de un fotón como soporte físico de un qubit. Un estado de polarización puede ser modelizado por un vector unidad apuntando en la dirección adecuada y se puede representar como un vector de norma uno en el espacio de Hilbert complejo H, que tiene como base ortonormal B1=[|0>,|1>].
img/DIAP_2.jpg

Para tener acceso a la información almacenada en un  estado cuántico necesitamos medirlo y al hacerlo el  estado va a quedar modificado.

Cualquier sistema de medida de estados cuánticos tiene asociada una base ortonormal, respecto de la cual se realiza la medición. Cuando de mide un estado, éste cambia irreversiblemente, salvo los estados de la propia base que se esté utilizando para medir (o múltiplos de ellos).

Al medir un estado cuántico, éste se proyecta sobre el subespacio generado por uno de los vectores de la base considerada. Por ejemplo, usando la base B1, se consideran las polarizaciones horizontal y vertical. Al medir el estado a|0>+b|1> podemos obtener 0, y el estado queda proyectado sobre el subespacio generado por |0>, o bien obtener 1 y el estado se transforma en un vector unitario en la misma dirección que el vector |1>. La probabilidad de cada resultado es el cuadrado de la amplitud correspondiente.

Aparatos o sistemas de medidas diferentes tienen asociadas bases distintas y las mediciones correspondientes dan lugar a resultados diferentes. Por ejemplo, podemos considerar la base ortogonal BX=[|+>,|->],que corresponde a las polarizaciones 45º y -45º. Para obtener el resultado de la medición de un estado respecto de BX, basta conocer las coordenadas del vector respecto de esta base.


img/DIAP_3.jpg img/DIAP_4.jpg

Ejercicio 1.2
¿Cuál es la probabilidad de obtener el estado |0> tras haber medido el estado u= 0.6|0>-0.8|1> con la base B1? ¿Y si se utiliza BX?


APARTADO 1.3. ESTADOS DE 2-QUBITS. ENTRELAZAMIENTO

La información que contiene un qubit es evidentemente muy pequeña. Para poder representar más información es necesario recurrir a estados de n-qubits. Para entender cómo son estos estados cuánticos, empezaremos con n=2: Un 2-qubit es un vector unitario del espacio vectorial de dimensión 4, generado por los vectores de la base ortonormal B2 =[|00>,|01>,|10>,|11>], cuyos elementos son todos los productos tensoriales de dos elementos de B1= [|0>, |1>].

img/DIAP_5.jpg img/DIAP_6.jpg

Como podemos ver en las diapositivas anteriores, hay estados de 2-qubits que son producto tensorial de dos estados de 1-qubit. Pero también hay otros que no se pueden poner como producto tensorial de estados de 1-qubit. Estos estados se denominan entrelazados y tienen gran importancia en algorítmica y criptografía cuánticas.

Ejercicio 1.3.1
Pon otro ejemplo de estado entrelazado.

En un 2-qubit se puede medir el primer qubit o el segundo, usando una base ortonormal B de H1 Para ello se considera la expresión del estado a medir como combinación lineal de los productos tensoriales de dos vectores de B. El resultado de la medida dependerá de las amplitudes.

img/DIAP_7.jpg img/DIAP_8.jpg

Cuando se mide el primer qubit del estado entrelazado que aparece en la diapositiva anterior, con la base B1=[|0>,|1>], si el resultado de la medida es 0, lo que ocurre con probabilidad 1/2, el estado resultante sería |00>; si el resultado es 1, el estado resultante sería |11>. En cualquier caso, si después se mide el segundo qubit, se obtendrá con probabilidad 1 el mismo resultado de la primera medición. Es decir el resultado de la medida del segundo qubit está condicionado por el de la primera medición. Esta es una característica de los estados entrelazados, que da lugar a la famosa paradoja de Einstein, Podolsky y Rosen (EPR). Los dos qubits de un estado cuántico entrelazado pueden representar sistemas físicos que estén en el espacio arbitrariamente lejos y si se mide el primero de ellos ya se conoce el resultado de la medida del segundo.

Ejercicio 1.3.2
Estudiar cuál puede ser el estado resultante tras medir el segundo qubit de u=0.5(|00>+01>+|10>+|11>), usando la base B1.

Cuestiones para reflexionar e investigar:
Buscar información sobre la paradoja EPR y sobre el "teletransporte" de información cuántica.


APARTADO 1.4. ESTADOS DE N-QUBITS

Un estado cuántico de n-qubits es un vector de norma 1 del espacio de Hilbert complejo Hn, de dimensión 2n.

Se puede construir una base ortonormal de Hn, con todos los productos tensoriales de n vectores de B1.

Los vectores de esta base se pueden identificar con todas las posibles cadenas de n bits o con las expresiones binarias de los números 0…2n-1.

La identificación de cada vector de la base con una cadena de n bits resulta muy conveniente para codificar la información.

Conviene resaltar que la dimensión exponencial de Hn es la clave de la potencia de la computación cuántica, que se basa en el llamado paralelismo cuántico, derivado del hecho de que manejar un estado cuántico, superposición de todos los estados de la base, es como operar simultáneamente con todas las cadenas de n bits. Esto permite un incremento exponencial de la velocidad de cálculo.
img/DIAP_9

En un n-qubit podemos medir cualquiera de los qubits. Por ejemplo, si usamos B1 y medimos el primer qubit de un estado de n-qubits podemos obtener como resultado de la medida 0 ó 1. Si el resultado es 0, el estado se proyectará sobre el subespacio generado por los vectores de la base que tienen cero en el primer qubit y si el resultado es 1 se proyectará sobre el subespacio correspondiente. La probabilidad de cada opción viene dada por la suma de los cuadrados de las amplitudes correspondientes. La siguiente tabla muestra el esquema de medición del k-ésimo qubit usando la base B1.

img/DIAP_10

APARTADO 1.5. TRANSFORMACIÓN DE LA INFORMACIÓN. PUERTAS CUÁNTICAS

La evolución de un estado cuántico se describe mediante transformaciones cuánticas, que son operadores lineales unitarios definidos en el espacio de Hilbert correspondiente.

Si se considera una base ortonormal, cada operador lineal se identifica con una matriz cuadrada, cuyas columnas son las coordenadas de las imágenes de los elementos de esta base. Si M es la matriz asociada a un operador y M* su traspuesta conjugada, el operador lineal es unitario cuando el producto de M por M* es la matriz unidad.

Un algoritmo cuántico se llevará a cabo mediante una de estas transformaciones. Aquí tenemos una de las características importantes de la computación cuántica, que la diferencia del modelo clásico. La computación cuántica es reversible, es decir para cualquier transformación es sencillo obtener la transformación inversa.

Como no cabe esperar que sea posible implementar en un ordenador cuántico cualquier transformación unitaria, será necesario descomponerla en transformaciones elementales denominadas puertas cuánticas [1].

Las puertas cuántica más simples son las transformaciones unitarias de un qubit, definidas en el espacio de Hilbert H en el que podemos considerar la base B1=[|0>, |1>].

Para definir un operador basta conocer las imágenes de los elementos de la base, o lo que es equivalente disponer de su matriz asociada.

img/DIAP_11jpg img/DIAP_12.jpg

Ejercicio 1.5.1
Demuestra que HXH=Z y que HZH=X (lo puedes hacer sin más que multiplicar las matrices). Teniendo en cuenta que la matriz H es unitaria, deduce del resultado anterior que para cualquier entero positivo k es HZkH=Xk

Ejercicio 1.5.2
Determina U tal que U2=Z y V tal que V2=X

Vamos a considerar ahora transformaciones unitarias en el espacio de dimensión cuatro de los 2-qubits, H2.

En dicho espacio, se pueden definir transformaciones que sean producto tensorial de dos puertas simples (que actúan separadamente en cada uno de los qubits) y transformaciones específicas, que no se pueden poner como producto tensorial de dos puertas simples.

img/DIAP_13jpg img/DIAP_14.jpg

El producto tensorial de una puerta simple U por la identidad es una transformación de 2-qubits consistente en modificar sólo uno de los qubits. Así, por ejemplo, el producto tensorial de X por I es la puerta simple X actuando sobre el primer qubit.

La transformación de Walsh-Hadamard es un ejemplo importante de transformación producto tensorial. Es la transformación definida mediante el producto tensorial de dos transformaciones de Hadamard de 1-qubit. La imagen del estado |00> por esta transformación es una superposición de los cuatro estados básicos.

Ejercicio 1.5.3
¿Cuál es la imagen del estado |01> por la transformación de Walsh-Hadamard W2?

Ejercicio 1.5.4
Indica en cada caso si es posible encontrar dos puertas de un qubit cuyo producto tensorial transforme:
i) el estado a|01>+ b|10> en a|11>+ b|00>
ii) el estado |00> en uno de la forma a|00>+ b|10>
iii) el estado |00> en uno de la forma a|11>+ b|00>

Respecto a las transformaciones específicas de 2-qubits, la más sencilla es la CNOT o negación controlada que niega uno de los bits cuando el otro vale 1. De modo análogo se puede definir la puerta control-U que aplica la transformación de 1-qubit U a un bit usando el otro como bit de control.

img/DIAP_15.jpg img/DIAP_17.jpg

La puerta CNOT, junto con la transformación de Hadamard se puede usar para preparar un estado entrelazado

img/DIAP_16.jpg

Otra transformación de 2-qubits importante es la transformación Swap que intercambia los bits. Como ejemplo de puerta de 3-qubits cabe citar la puerta clásica de Toffoly, que cambia el tercer qubit cuando los dos primeros son iguales a 1.

img/DIAP_18.jpg img/DIAP_19.jpg

Ejercicio 1.5.5
Escribe la matriz asociada la la puerta de Toffoly para la base B3=[|000>,|001>,|010>,>,|010>,|100>,|101>,|110>,|111>].

Ejercicio 1.5.6
Construye un circuito que transforme a|000>+b|100> en a|000>+b|111>

Algunas transformaciones de n-qubits: La transformación de Walsh-Hadamard, Wn es una trasformación unitaria definida en Hn, que consiste en aplicar H a cada uno de los qubits. Su matriz asociada es el producto tensorial n veces de la matriz de Hadamard. La imagen del estado |0> de n-qubits, por esta transformación, es una superposición de todos los estados de la base. Por ello se suele usar Wn para preparar un estado que sea combinación lineal de todos los de la base, de modo que actuar sobre dicho estado es como actuar simultáneamente sobre todas las posibles cadenas de n bits.

img/DIAP_20A.jpg

Cualquier función booleana f de n bits en m bits se puede implementar mediante una transformación unitaria que trabaje con un (n+m)-qubit

img/DIAP_20B.jpg
img/DIAP_21.jpg

APARTADO 1.6. TEOREMA DE NO CLONING

El teorema de no cloning, de demostración sorprendentemente sencilla,  fue formulado por Wootters, Zurek y Dieks en 1982. Como consecuencia del mismo,  no se puede diseñar un dispositivo que copie un estado cuántico; sin alterar el original de algún modo.

Este hecho, que puede suponer una desventaja de la computación cuántica, ya que impide, por ejemplo, hacer copias de seguridad, tiene una importante aplicación en criptografía cuántica, pues un espía no puede hacer impunemente una copia de la información cuántica que se estén intercambiando dos usuarios legítimos.
img/DIAP_22.jpg

APARTADO 1.7. TEST DE AUTOEVALUACIÓN



1. El estado resultante tras medir el estado |0>, respecto de la base B=[u,v],
 con u= 0.6 |0>+ 0.8 |1> y v= 0.8 |0> -0.6 |1>, puede ser:

a) |0>, con probabilidad 0.6.
b) u, con probabilidad 0.36.
c) v, con probabilidad 0.6.

2. El estado de 2-qubits 0.6 |01>+ 0.8 |10>
a) es entrelazado.
b) es producto tensorial de dos estados de 1 qubit.
c) no es un estado cuántico, pues no es un vector de norma 1.

3. El estado resultante tras medir el primer qubit del estado b=0.6|00> + 0.8|01> con la base B1 puede ser:
a) El propio estado b, con probabilidad 1.
b) El estado |00>, con probabilidad 0.36.
c) El estado |01>, con probabilidad 0.64.

4. La salida del siguiente circuito, correspondiente a la entrada |00> es
img/circuitest.jpg
a) ½ (|00>+|01>+ |10>+|11>).
b) ½ (|00>+|01>- |10>+|11>).
c) ½ (|00>-|01>+ |10>-|11>).

5. Dados los estados u=a|00>+ b|10>, v=a|00>+ b|11>,
a) No existe una transformación unitaria T tal que T(u)=v.
b) La única transformación unitaria tal que T(u)=v es T=C12.
c)Hay más de una transformación unitaria tal que T(u)=v.


APARTADO 1.8. REFERENCIAS BIBLIOGRÁFICAS Y ENLACES DE INTERÉS

[1] Barenco, A.; Bennet, C. y otros. Elementary gates for quantum computation. Phys. Rev. 52 (1995), pp. 3457--3467 (arXiv:quant-ph/9503016).

[2] Deutsh, D. Quantum theory, the Church-Turing principle and the universal quantum computer. R. Soc, Lond. Proc. Ser. A Math. Phys. Sci. 400, (1985), pp. 97-117.

[3] Feynman, R. Simulating physics wtiy computers. Inter. J. Theroret. Phys. 21 (1982), pp.467-488

[4] Nielsen, M. A.; Chuang, L. I., Quantum Computation and Quantum Information, Cambridge University Press, 2000.

http://www.fisicafundamental.net/misterios/computacion.html

http://www.ic-itcr.ac.cr/~jcastro/libro/libro/libro.html


Ir a: [Principio]