Algunos elementos introductorios acerca de la computaci´on cu´antica* Andr´es Sicard R. email: [email protected] Mario Elkin V´elez R. email: [email protected] Departamento de Ciencias B´asicas Universidad EAFIT Medell´ın, Colombia, S.A. Junio 10 de 1999

Resumen Inicialmente se presenta una introducci´ on y una motivaci´ on a la computaci´ on cu´ antica. Se ofrecen algunas definiciones y operaciones de la mec´ anica cu´ antica relevantes para la computaci´ on cua´ ntica. Se muestran algunas compuertas cu´ anticas, sus matrices unitarias correspondientes y como operar con ellas para construir circuitos cu´ anticos. Se se˜ nalan dos caracter´ısticas inherentes a la computaci´ on cu´ antica: la reversibilidad y los estados enredados. Se presenta el efecto llamado paralelismo cu´ antico. Finalmente, se muestra la transformada cu´ antica r´ apida de Fourier.

1.

Introducci´ on

Las m´ aquinas de Turing cu´ anticas y los circuitos cu´anticos son un modelo de la computaci´on, tal como lo son las m´ aquinas de Turing, las funciones recursivas y el λ-c´alculo, entre otros. Estos modelos se inscriben dentro de un ´ area conocida como computaci´on cu´antica y, como su nombre lo indica, hacen uso de las propiedades y efectos considerados por la mec´anica cu´antica. Esta ´area fue inicialmente sugerida por Richard Feymman en los a˜ nos 80, formalizada por David Deutsch (en la forma de m´aquinas de Turing cu´anticas en 1985 ( [6]) y en la forma de circuitos cu´ anticos en 1989 ([7])) y resaltada su potencialidad por Peter Shor en 1994 [14]. El trabajo de Shor se˜ nalo el aspecto fundamental en el cual se diferencian la computaci´on cl´asica y la computaci´ on cu´ antica: la complejidad algor´ıtmica. Esta diferencia consiste en que es posible definir algoritmos cu´ anticos cuya complejidad temporal sea menor que sus an´alogos cl´asicos (conocidos hasta el momento). En particular Shor realiz´ o la descripci´ on de un algoritmo cu´antico de complejidad temporal de tipo polinomial para la factorizaci´ on de n´ umeros enteros. M´as interesante -desde el punto de vista de los autores-, es * Este

art´ıculo fue realizado como parte del proyecto de investigaci´ on N0 . 817407 financiado por la Universidad EAFIT.

33

la pregunta por la potencia desde la perspectiva de la computabilidad, de la computaci´on cu´antica; algunos autores afirman que una m´ aquina de Turing y una m´aquina de Turing cu´antica son equipotentes en relaci´ on a las funciones que ellas pueden computar (cf. [6], [11]), otros autores por su parte, suponen que bajo ciertas circunstancias la computaci´ on cu´ antica pueda ofrecer caracter´ısticas de “super-Turing” computaci´on (cf. [15]), pero ´esto hasta el momento es una cuesti´on abierta. Este art´ıculo espera proporcionar al lector algunos elementos necesarios para adquirir un breve panorama de la computaci´ on cu´ antica. Una de las principales dificultades con las que se han encontrado los autores, es que los papers (con algunas excepciones) que presentan el tema, no presentan el detalle del desarrollo de las operaciones realizadas, lo cual dificulta enormente el seguimiento para el lector ne´ofito. Por esta raz´on, los autores han hecho hincapi´e en este aspecto. Inicialmente, la secci´ on 2, presenta algunas definiciones y operaciones de la mec´anica cu´antica relevantes para la computaci´ on cu´ antica. En particular: se define el elemento b´asico de la computaci´on cu´antica denominado qubit; se indica el procedimiento de medida de los qubits, el cual involucra la probabilidad cu´ antica y se presenta el procedimiento de evoluci´ on temporal de los qubits, el cual es realizado por medio de un operador de evoluci´ on. La secci´ on 3 desarrolla los circuitos cu´ anticos. Inicialmente se muestran algunas compuertas y circuitos cl´ asicos. Se presentan: algunas compuertas cu´anticas de uno y dos qubits; el procedimiento para construir la matriz unitaria correspondiente a una compuerta cu´antica, con base en su comportamiento entrada-salida; los procedimientos de manipulaci´ on de los kets y las matrices unitarias. Finalmente se realiza la construcci´ on de un circuito cu´ antico a partir de algunas compuertas cu´anticas definidas anteriormente. La secci´ on 4 presenta dos caracter´ısticas inherentes a la computaci´on cu´antica: la reversibilidad y los estados enredados. La reversibilidad es una condici´on impuesta por la mec´anica cu´antica, ´esta es ejemplarizada en la compuerta cu´ antica de Toffoli, para la cual se realiza un desarrollo completo de construcci´on en un circuito cu´ antico, esta compuerta adem´ as ofrece propiedades de computaci´on universal y se constituye en una compuerta cu´ antica de uso general. Por otra parte, un estado enredado es una propiedad que no tiene un an´ alogo cl´ asico y, para la cual existe una relaci´on estrecha con la medida cu´antica, la cual es presentada. La secci´ on 5 presenta el efecto llamado paralelismo cu´ antico. Las ventajas ofrecidas por la computaci´ on cu´ antica en lo relacionado a la complejidad temporal son debidas a este efecto. Como ilustraci´on, se presenta y soluciona un problema que hace uso de este paralelismo cu´antico, conocido como el problema de Deutsch Finalmente, la secci´ on 6 presenta la transformada cu´antica r´apida de Fourier. Esta transformada es utilizada con frecuencia por los algoritmos cu´ anticos en la preparaci´on de los estados cu´anticos. para posibilitar el paralelismo cu´ antico. Existen dos aspectos que aunque no ser´ an considerados en este art´ıculo es importante mencionar, por una parte, la computaci´ on cu´ antica es hoy por un ´area esencialmente te´orica, es decir, las m´aquinas cu´anticas son constructos te´ oricos. En la actualidad existe una discusi´on abierta acerca de la posibilidad o no de construir m´ aquinas cu´ anticas concretas, y se han realizado ciertas implementaciones muy limitadas. La direcci´ on http://xxx.lanl.gov contiene una excelente compilaci´on de art´ıculos acerca de la computaci´on cu´antica, y entre otros temas esta lo relacionado con su construcci´on. Por otra parte, existen algunos simuladores y librer´ıas que permiten programar cu´ anticamente en m´aquinas cl´asicas, en http://home.plutonium.net/˜ da34

greve/qdd.html se ofrece una buena referencia al respecto.

2. 2.1.

Definiciones y operaciones preliminares Qubits

La unidad fundamental de informaci´ on cu´antica es el qubit o bit cu´antico, ´este es un elemento del espacio de Hilbert de funciones de onda m´ as simple no trivial de dos dimensiones, el cual es generado por los kets {| 0i , | 1i}, elementos de la base, y que convencionalmente pueden elegirse en una representaci´on particular como,     1 0 | 0i = , | 1i = ; (1) 0 1 estos dos vectores son ortonormales, lo cual significa que bajo el producto escalar hx | yi definido en el espacio, los vectores base se comportan de la siguiente forma: h0 | 0i = h1 | 1i = 1,

(2)

h0 | 1i = h1 | 0i = 0.

(3)

En las dos u ´ltimas ecuaciones los vectores bra h0 |, h1 |, duales de los ket | 0i, | 1i, se obtienen como los traspuestos herm´ıticos de los ket y se representan de la siguiente manera: h0 | = 1


0 ,

h1 | = 0


1 .

(4)

El 1-qubit normalizado m´ as general que se puede formar en este espacio es la superposici´on lineal de los dos elementos de la base, es decir: | xi = a0 | 0i + a1 | 1i ,

donde

a0 , a1 ∈ C;

|a0 |2 + |a1 |2 = 1.

(5)

Ahora, ¿cu´ al es el estado de un sistema que consiste no solo de un qubit sino de un conjunto de n qubits c´ uanticos ?. La respuesta es que el estado en conjunto se describe como el producto tensorial de los n qubits individuales. Inicialmente se presenta como ejemplo la situaci´on cu´antica para n = 2, es decir, dos qubits o un 2-qubit; la dimensi´ on del espacio es 22 = 4. La base de este espacio es: | ui i ⊗ | vj i = | ui , vj i ,

(6)

en esta u ´ltima expresi´ on i, j = 0, 1, entonces: | u0 i = | 0i ,

| u1 i = | 1i ,

| v0 i = | 0i , 35

| v1 i = | 1i ;

(7)

las relaciones expresadas por las ecuaciones (6) y (7), permiten definir la base del espacio estado cuatrodimensional como: {| 0i ⊗ | 0i , | 0i ⊗ | 1i , | 1i ⊗ | 0i , | 1i ⊗ | 1i};

(8)

lo que puede ser escrito en una forma completamente equivalente como: {| 0, 0i , | 0, 1i , | 1, 0i , | 1, 1i}.

(9)

| x1 , x2 i = | x1 i ⊗ | x2 i , |{z} |{z}

(10)

El 2-qubit normalizado m´ as general

1er qubit

2do qubit

que se puede formar en este espacio es la superposici´on lineal de los cuatro elementos de la base, es decir:

| x1 , x2 i = a0 | 0, 0i + a1 | 0, 1i + a2 | 1, 0i + a3 | 1, 1i ,

donde

a0 , a1 , a2 , a3 ∈ C;

2 2X −1

|ai |2 = 1.

(11)

i=0

Una convenci´ on utilizada en computaci´ on cu´antica es: | x1 , x2 , . . . , xm i ≡ | xi ,

(12)

donde x1 , x2 , . . . , xm es la representaci´ on binaria del entero x, es decir x = x1 2m−1 + x2 2m−2 + · · · + xm−1 21 + xm 20 .

(13)

De acuerdo con las ecuaciones (12) y (13) la base de un espacio formado por n qubits cuya dimensi´on es 2n est´ a formada por: {| 0i , | 1i , | 2i , . . . , | 2n − 1i};

(14)

entonces el n-qubit normalizado m´ as general | x1 , . . . , x n i = | x1 i ⊗ · · · ⊗ | xn i , |{z} |{z} 1er qubit

(15)

n qubit

viene dado por la superposici´ on lineal de los 2n elementos de la base: | x1 , x2 , . . . , xn i =

n 2X −1

ai | ii ,

donde a0 , . . . an−1 ∈ C;

i=0

n 2X −1

i=0

36

|ai |2 = 1.

(16)

2.2.

Medida cu´ antica

Sea | xi un qubit normalizado. Si se realiza una medida sobre la base {| u0 i , | u1 i, la probabilidad de encontrar el qubit en el estado | ui i, denotada por P (| ui i), est´a dada por: P (| ui i) = | hui | xi |2 .

(17)

Ejemplo 2.1. La medici´ on de un qubit | xi = a0 | 0i + a1 | 1i sobre la base {| 0i , | 1i}, genera las siguientes probabilidades: P (| 0i) = | h0 | xi |2

P (| 1i) = | h1 | xi |2

= | h0 | (a0 | 0i + a1 | 1i)|2

= | h1 | (a0 | 0i + a1 | 1i)|2

= |a0 h0 | 0i + a1 h0 | 1i |2

= |a0 h1 | 0i + a1 h1 | 1i |2

= |a0 |2

= |a1 |2 .

(18)

Ejemplo 2.2. La medici´ on de un qubit | xi = a0 | 0i + a1 | 1i sobre la base {| 0i + | 1i , | 0i − | 1i}, genera las siguientes probabilidades: P (| 0i + | 1i) = |(h0 | + h1 |) | xi |2 = |(h0 | + h1 |)(a0 | 0i + a1 | 1i)|2 = |a0 h0 | 0i + a1 h0 | 1i + a0 h1 | 0i + a1 h1 | 1i |2 = |a0 + a1 |2 .

(19)

P (| 0i − | 1i) = |(h0 | − h1 |) | xi |2 = |(h0 | − h1 |)(a0 | 0i + a1 | 1i)|2 = |a0 h0 | 0i + a1 h0 | 1i − a0 h1 | 0i − a1 h1 | 1i |2 = |a0 − a1 |2 .

(20)

La medida de los qubits de un 2-qubit | x1 , x2 i = a0 | 0, 0i + a1 | 0, 1i + a2 | 1, 0i + a3 | 1, 1i sobre la base {| 0i , | 1i} genera las siguientes probabilidades: la probabilidad de encontrar el primer qubit en el estado | 0i denotada por P1 (| 0i); la probabilidad de encontrar el primer qubit en el estado | 1i denotada por P1 (| 1i); la probabilidad de encontrar el segundo qubit en el estado | 0i denotada por P2 (| 0i) y la probabilidad de encontrar el segundo qubit en el estado | 1i denotada por P2 (| 1i); estas probabilidades estan dadas por: P1 (| 0i) = |a0 |2 + |a1 |2 ,

P1 (| 1i) = |a2 |2 + |a3 |2 ,

P2 (| 0i) = |a0 |2 + |a2 |2 ,

P2 (| 1i) = |a1 |2 + |a3 |2 . (21)

S´ı una vez realizada la medida sobre el primer qubit del 2-qubit | x1 , x2 i = a0 | 0, 0i + a1 | 0, 1i + a2 | 1, 0i + a3 | 1, 1i, se obtiene que ´este est´ a en el estado | 0i, el 2-qubit evoluciona a un nuevo estado normalizado dado por: 37

| x0 , y 0 i =

a0 | 0, 0i + a1 | 0, 1i p ; |a0 |2 + |a1 |2

(22)

y se obtiene que ´este est´ a en el estado | 1i, el 2-qubit evoluciona a un nuevo estado normalizado dado por: | x0 , y 0 i =

a2 | 1, 0i + a3 | 1, 1i p . |a2 |2 + |a3 |2

(23)

Expresiones similares a las anteriores se obtienen para los resultados de la medida del segundo qubit del 2-qubit.

2.3.

Evoluci´ on cu´ antica

La evoluci´ on o din´ amica de un n-qubit es determinada por un operador unitario U sobre el espacio de Hilbert, este operador es denominado operador de evoluci´ on. Un operador es unitario si su adjunto es igual a su inverso, y puede expresarse como: U † U = I. (24) Sea | ψ(t)i = | x1 , . . . , xn i un n-qubit, la evoluci´on con base en el operador U de un paso de computaci´ on, est´ a dada por: U | ψ(0)i → | ψ(1)i ,

(25)

y en general, la evoluci´ on de m pasos de computaci´on est´a dada por (cf. [6]): U m | ψ(0)i → | ψ(m)i .

(26)

En el contexto de la computaci´ on cu´ antica un operador de evoluci´on que opera sobre un n-qubit, corresponde a una matriz unitaria de dimensi´ on 2n . la pr´oxima secci´on indica la construcci´on de estas matrices unitarias y su relaci´ on con las compuertas cu´ anticas.

3.

Circuitos cu´ anticos

En la introducci´ on se indic´ o que la computaci´on cu´antica ofrece dos modelos de computaci´on: las m´aquinas de Turing cu´ anticas (MTQ) y los circuitos cu´anticos. Para la presentaci´on de un modelo de computaci´ on cu´ antica, se seleccion´ o el modelo de los circuitos cu´anticos por considerarlos m´as cercanos a sus an´alogos, los circuitos cl´ asicos. El modelo de las MTQ no ser´a presentado, el lector interesado en ´este, puede consultar [4], [1] y [6].

38

x 0 0 1 1

y 0 1 0 1

¬x 1 1 0 0

x∧y 0 0 0 1

x∨y 0 1 1 1

Cuadro 1: Operaciones l´ogicas not, and y or.

x

not

¬x

x y

x∧y

and

x y

or

x∨y

Figura 1: Compuerta l´ogicas not,and y or.

3.1.

Compuertas y circuitos l´ ogicos

Las operaciones l´ ogicas presentadas en la tabla 1, pueden ser representadas por compuertas l´ogicas, tal como lo indican las figura 1. Con estas operaciones l´ ogicas es posible construir otras operaciones l´ogicas, tales como el nand (↑), xor (⊕) y el nor (↓) indicadas en la tabla 2. Estas nuevas operaciones l´ogicas pueden ser representadas por circuitos l´ ogicos tal como lo indica la figura 2, en donde el s´ımbolo ’≡’ significa que los circuitos son equivalentes. Se puede adem´ as, expresar las compuertas nor y xor en t´erminos de las compuertas not, and y or. Es posible tambi´en, combinando las diferentes compuertas l´ogicas obtener circuitos l´ogicos de mayor complejidad. Por convenci´ on en estos circuitos l´ogicos (tambi´en se aplicar´a a los circuitos cu´anticos), el tiempo procede de izquierda a derecha, es decir, el orden de operaci´on de las compuertas es de izquierda a derecha (cf. [2]).

3.2.

Compuertas cu´ anticas

A diferencia de las compuertas l´ ogicas que pueden operar de n-bits en m-bits, las compuertas cu´anticas deben operar de n-qubits en n-qubits. Esta es una condici´on necesaria pero no suficiente para satisfacer una propiedad (la reversivilidad) de las compuertas cu´anticas que ser´a presentada en una pr´oxima secci´on. Cada compuerta cu´ antica de n-qubits puede ser representada por una matriz unitaria de dimensi´on 2n , en donde la transformaci´ on realizada por la compuerta cu´antica es realizada por el operador matriz asociado a ella. x 0 0 1 1

y 0 1 0 1

x↑y 0 0 0 1

x↓y 1 0 0 0

x⊕y 0 1 1 0

Cuadro 2: Operaciones l´ogicas nand, nor y xor.

39

x y

x↑y

nand

≡

x y

¬

∧

¬(x ∧ y)

Figura 2: Compuerta l´ ogica nand en t´erminos de las compuertas l´ogicas and y not.

Con base en la descripci´ on de la tranformaci´on que realiza una compuerta cu´antica sobre los elementos de la base del espacio, la matriz unitaria asociada a ella se obtiene a partir del siguiente procedimiento: Las filas de la matriz corresponden a los vectores base de entrada y las columnas de la matriz corresponden a los vectores base de salida; la (j, i) posici´ on de la matriz corresponde, cuando el i-´esimo vector base es la entrada a la compuerta, al coeficiente del j-´esimo vector base en la salida de la compuerta. 3.2.1.

Compuertas cu´ anticas de 1-qubit

Las compuertas cu´ anticas que operan sobre un qubit (un qubit de entrada y un qubit de salida) tienen asociadas matrices 2 × 2. La convenci´on utilizada en los cuatro ejemplos siguentes para representar vectorialmente el ket | 0i y el ket | 1i es la misma que la representada por la ecuaci´on (1), es decir:     1 0 . (27) | 0i = , | 1i = 0 1 Inicialmente se presenta la compuerta cu´antica identidad. Aunque su comportamiento -como su nombre lo indica- no modifica el qubit sobre el que actua, se busca con este ejemplo ilustrar el procedimiento de construcci´ on de la matriz unitaria asociada a una compuerta cu´antica. Ejemplo 3.1 (Compuerta identidad). El comportamiento de la compuerta identidad est´ a dado por: Uidentidad | xi → | xi. La transformaci´ on de los qubits que realiza la compuerta y su representaci´ on gr´ afica es:

| xi

Uidentidad | 0i → | 0i ,

identidad

| xi

Uidentidad | 1i → | 1i ,

Entonces, la matriz unitaria correspondiente a la compuerta cu´ antica identida, est´ a dada por: | 0i

| 1i

| 0i

1

0

| 1i

0

1

,

la cual es representada por:

Uidentidad

 1 = 0

 0 . 1

(28)

El comportamiento de la compuerta cu´ antica identidad en t´erminos de la matriz (28) es descrito por:

40

Uidentidad | 0i =

 1 0

    0 1 1 = = | 0i , 1 0 0

Uidentidad | 1i =

 1 0

0 1

    0 0 = = | 1i . 1 1

El siguiente ejemplo ilustra el comportamiento de una compuerta cu´antica conocida como la compuerta de Hadamard. Esta compuerta transforma un qubit en una superposici´on de los elementos de la base {| 0i , | 1i}. Aunque no ser´ a ilustrado, es posible generalizar la compuerta de Hadamard para que opere sobre un n-qubit con un comportamiento similar al caso de 1-qubit, es decir, la compuerta de Hadamard sobre un n-qubit transforma ´este en una superposici´ on de los elementos de la base {| 0i , . . . , | 2n − 1i}. Ejemplo 3.2 (Compuerta de Hadamard). La transformaci´ on de los qubits que realiza la compuerta de Hadamard est´ a dada por: 1 Uhadamard | 0i → √ (|0i + |1i), 2 1 Uhadamard | 1i → √ (|0i − |1i), 2

La matriz para la compuerta de Hadamard est´ a dada por: | 0i | 0i | 1i

√1 2 √1 2

| 1i + √12 ,

y se representa por:

− √12

1 Uhadamard = √ 2

 1 1

 1 . −1

(29)

El comportamiento de la compuerta de Hadamard en t´erminos de la matriz (29) es descrito por: 1 Uhadamard |0i = √ 2



1 1

1 −1

    1 1 1 1 =√ = √ (|0i + |1i), 0 2 1 2

1 Uhadamard |1i = √ 2



1 1

1 −1

    1 1 0 1 =√ = √ (|0i − |1i). 1 2 −1 2

El ejemplo siguiente -a diferencia de los ejemplos anteriores- ilustra como obtener la transformaci´on que realiza una compuerta cu´ antica sobre los elementos de la base, a partir de la matriz unitaria asociada a ´esta, adem´ as ilustra el uso de compuertas cu´ nticas parametrizadas. 41

Ejemplo 3.3 (Compuerta cu´ antica parametrizada). Una matriz unitaria parametrizada determina una compuerta cu´ antica parametrizda. A manera de ejemplo, sea   cos( θ2 ) sen( θ2 ) . (30) U (θ) =  α θ −sen( 2 ) cos( 2 ) La matriz U (θ) tiene el siguiente comportamiento sobre los elementos de la base {| 0i , | 1i}:      1 cos( θ2 ) cos( θ2 ) sen( θ2 )   =   = cos( θ ) | 0i − sen( θ ) | 1i . U (θ) | 0i =  2 2 0 −sen( θ2 ) cos( θ2 ) −sen( θ2 )      cos( θ2 ) sen( θ2 ) 0 −sen( θ2 )   =   = sen( θ ) | 0i + cos( θ ) | 1i . U (θ) | 1i =  2 2 1 −sen( θ2 ) cos( θ2 ) cos( θ2 )

(31)

(32)

Con base en las ecuaciones (31) y (32), la transformaci´ on de la compuerta cu´ antica U (θ) est´ a dada por: θ θ U (θ) | 0i → cos( ) | 0i − sen( ) | 1i , 2 2 θ θ U (θ) | 1i → sen( ) | 0i + cos( ) | 1i . 2 2 Para la construcci´ on de un circuito cu´ antico que ser´ a presentado en una secci´ on pr´ oxima, es necesaria la siguiente transformaci´ on realizada por la compuerta U (θ):     cos( θ2 ) cos(θ) sen( θ2 ) θ θ  =  U (θ)(cos( ) | 0i − sen( ) | 1i) =  2 2 −sen(θ) −sen( θ2 ) cos( θ2 ) −sen( θ2 ) 

cos( θ2 )

= cos(θ) | 0i − sen(θ) | 1i .

(33)

La unitariedad de la matriz M asociada a una compuerta cu´antica M , permite construir una nueva compuerta cu´ antica M † con base en la matriz herm´ıtica conjugada M † de M . La posibilidad de obtener una nueva compuerta M † sustenta la propiedad de reversibilidad de las compuertas cu´anticas, tal como ser´a expuesto posteriormente. Se ilustra entonces, una compuerta M † . Ejemplo 3.4 (Compuerta M † ). La matriz herm´ıtica conjugada de la matriz U (θ) representada por la ecuaci´ on (30) y las transformaciones que realiza la compuerta U † (θ) estan dadas por:

42

θ θ U † (θ) | 0i → cos( ) | 0i + sen( ) | 1i , 2 2 θ θ U † (θ) | 1i → −sen( ) | 0i + cos( ) | 1i . 2 2

 −sen( θ2 ) , U † (θ) =  sen( θ2 ) cos( α2 ) 

cos( θ2 )

(34)

Para la construcci´ on de un circuito cu´ antico que ser´ a presentado en una secci´ on pr´ oxima, son necesarias las siguientes transformaciones realizadas por la compuerta U † (θ):      cos( θ2 ) −sen( θ2 ) cos(θ) cos( θ2 )    = . U † (θ) cos(θ) | 0i − sen(θ) | 1i =  (35) θ θ θ −sen(θ) sen( 2 ) cos( 2 ) −sen( 2 )       cos( θ2 ) 1 cos( θ2 ) −sen( θ2 )   θ θ   =   = | 0i . (36) U † (θ) cos( ) | 0i − sen( ) | 1i =  2 2 θ θ θ 0 sen( 2 ) cos( 2 ) −sen( 2 ) 3.2.2.

Matriz unitaria 2 × 2 general

Cada matriz unitaria 2 × 2 es de la forma representada por la ecuaci´on (37) y esta a su vez puede ser factorizada en cuatro matrices representadas por la ecuaci´on (38). 

α

β

ei(δ+ 2 + 2 ) cos( θ2 )

U (α, β, δ, θ) =  β α −ei(δ− 2 + 2 ) sen( θ2 )  iδ e = 0

  iα e 2 · 0 eiδ 0

 β α ei(δ+ 2 − 2 ) sen( θ2 ) , α

(37)

β

ei(δ− 2 − 2 ) cos( θ2 )   iβ e 2 sen( θ2 ) · · α e−i 2 −sen( θ2 ) cos( α2 ) 0 0

 

cos( θ2 )

0 −i β 2

 .

(38)

e

Con base en la ecuaci´ on (38) se define la matriz Ry (θ) por(a la cual se har´a referencia en una secci´ on posterior):   cos( θ2 ) sen( θ2 ) . Ry (θ) =  (39) −sen( θ2 ) cos( θ2 )

3.2.3.

Compuertas cu´ anticas de 2-qubit

Se presentan ahora algunas compuertas que operan sobre dos qubits (dos qubits de entrada y dos qubits de salida) y sus matrices 4 × 4 correspondientes. La convenci´on utilizada en los siguientes ejemplos, para representar vectorialmente los kets | 0, 0i, | 0, 1i, | 1, 0i y | 1, 1i es: 43

  1 0  | 0, 0i =   , 0 0

  0 1  | 0, 1i =   , 0 0

  0 0  | 1, 0i =   , 1 0

  0 0  | 1, 1i =   . 0 1

(40)

Ejemplo 3.5. Este ejemplo presenta una compuerta que realiza el intercambio de dos qubits, es decir la compuerta realiza la transformaci´ on Uintercambio | x, yi → | y, xi. La transformaci´ on de los dos qubits que realiza la compuerta y su representaci´ on gr´ afica estan dadas por: | xi

Uintercambio | 0, 0i → | 0, 0i Uintercambio | 0, 1i → | 1, 0i

| yi

| yi intercambio

| xi

Uintercambio | 1, 0i → | 0, 1i Uintercambio | 1, 1i → | 1, 1i

La matriz unitaria contruida con base en el procedimiento descrito en el ejemplo 3.1 est´ a dada por: | 00i | 00i | 01i | 10i | 11i

1 0 0 0

| 01i 0 0 1 0

| 10i 0 1 0 0

| 11i 0 0 0 1

,

representada por:

El comportamiento de la compuerta intercambio  1 0 Uintercambio | 0, 0i =  0 0  1 0 Uintercambio | 0, 1i =  0 0  1 0  Uintercambio | 1, 0i =  0 0  1 0 Uintercambio | 1, 1i =  0 0

Uintercambio

 1 0 = 0 0

0 0 1 0

0 1 0 0

 0 0  0 1

(41)

en t´erminos de la matriz (41) es descrito por:     1 1 0 0 0 0 0 0 1 0    =   = | 0, 0i , 1 0 0 0 0 0 0 0 1 0     0 0 0 0 0 1 0 0 1 0    =   = | 1, 0i , 1 0 0 0 1 0 0 0 0 1     0 0 0 0 0     0 1 0  0 = 1 = | 0, 1i , 1 0 0 1 0 0 0 1 0 0     0 0 0 0 0 0 0 0 1 0    =   = | 1, 1i . 1 0 0 0 0 0 0 1 1 1

Ejemplo 3.6. Para la compuerta que tiene el comportamiento Uxor | x, yi → | x, x ⊕ yi corresponde la matriz: 44

Uxor |0, 0i → | 0, 0 ⊕ 0i = |0, 0i Uxor

Uxor |0, 1i → | 0, 0 ⊕ 1i = |0, 1i Uxor |1, 0i → | 1, 1 ⊕ 0i = |1, 1i

 1 0  = 0 0

0 1 0 0

0 0 0 1

 0 0 . 1 0

(42)

Uxor |1, 1i → | 1, 1 ⊕ 1i = |1, 0i

El comportamiento de la compuerta Uxor en  1 0 Uxor |0, 0i =  0 0  1 0 Uxor |0, 1i =  0 0  1 0 Uxor |1, 0i =  0 0  1 0 Uxor |1, 1i =  0 0

t´erminos de la matriz (42) es descrito por     1 1 0 0 0 0 0 1 0 0    =   = |0, 0i, 0 0 1 0 0 0 0 0 1 0     0 0 0 0 0 1 1 1 0 0    =   = |0, 1i, 0 0 1 0 0 0 0 0 1 0     0 0 0 0 0 0 0 1 0 0    =   = |1, 1i, 0 0 1 1 0 1 0 0 1 0     0 0 0 0 0 0 0 1 0 0    =   = |1, 0i. 0 0 1 0 1 0 1 0 1 0

Esta compuerta corresponde a un xor cu´ antico, tambi´en llamado controlled-not. Este xor cambia el segundo qubit si el primer qubit es 1 y deja sin cambiar el segundo qubit si el primero es 0. Esta compuerta es representada por el circuito de la figura 3.

| xi

| xi xor

| yi

| xi

r

| yi

⊕

| xi

≡ | x ⊕ yi

| x ⊕ yi

Figura 3: Compuerta xor cu´antica.

La compuerta xor tambi´en puede actuar sobre un qubit formado por cualquier combinaci´ on lineal y su comportamiento es similar al descrito anteriormente, el cambio o no del segundo qubit es controlado por el primer qubit y es desarrollado de la siguiente forma: 45

 1 
 0 Uxor | 0i ⊗ a | 0i + b | 1i =  0 0

0 1 0 0

  0     1 0 0 1 a  ⊗ = 0 1 0 b 0 0

0 0 0 1

0 1 0 0

0 0 0 1

  a 0 b 0   1  0  0 0

  a     b
1 a = = = | 0i ⊗ a | 0i + b | 1i , ⊗ 0 0 b 0

(43)

es decir, si el primer qubit es cero el segundo qubit no cambia; pero si el primer qubit es uno, se obtiene:  1 
 0 Uxor | 1i ⊗ a | 0i + b | 1i =  0 0

0 1 0 0

  1 0     0 0 a 0  ⊗ = 0 1 b 1 0 0

0 0 0 1

0 1 0 0

0 0 0 1

  0 0 0 0   1 a 0 b

  0     0
0 b   ⊗ = | 1i ⊗ b | 0i + a | 1i , = = 1 a b a

(44)

es decir, si el primer qubit es uno el segundo qubit intercambia sus coeficientes. 3.2.4.

Construcci´ on de circuitos cu´ anticos a partir de compuertas cu´ anticas

Se presenta la contrucci´ on de un circuito cu´antico que intercambia dos qubits por medio del uso de tres xor cu´ anticos, adem´ as se construye la matriz 4×4 correspondiente a dicho circuito. El circuito de intercambio de dos qubits, realiza la transformaci´ on Uintercambio | x, yi → | y, xi presentada en el ejemplo 3.5. Este circuito es representado por la figura 4 en la cual se utilizan tres xor cu´anticos.

| xi

r

⊕

r

| yi

| yi

⊕

r

⊕

| xi

Figura 4: Circuito cu´antico que intercambia dos qubits.

Siguiendo el circuito de la figura 4 de izquierda a derecha se obtiene la transformaci´on que intercambia dos qubits:

46

| x, yi → | x, x ⊕ yi ,

resultado primer xor

→ | (x ⊕ y) ⊕ x, x ⊕ yi , = | y, x ⊕ yi ,

resultado segundo xor

→ | y, y ⊕ (x ⊕ yi , = | y, xi .

resultado tercer xor

Para construir la matriz unitaria 4 × 4 que representa el intercambio de dos qubits, se procede de la siguiente manera: El primer subcircuito del circuito de la figura 4 representado por la figura 5 realiza la transformaci´ on | x, yi → | x, x ⊕ yi y corresponde a la compuerta xor cu´antica presentada en el ejemplo 3.6 cuya matriz unitaria es:   1 0 0 0  0 1 0 0  m1 = Uxor =  (45)  0 0 0 1 . 0 0 1 0

| xi

r

| yi

⊕

| xi | x ⊕ yi

Figura 5: Primer subcircuito para el intercambio de dos qubits. El segundo subcircuito del circuito de la figura 4 es representado por la figura 6 y realiza la transformaci´ on | x, yi → | y ⊕ x, yi. La transformaci´ on que realiza el subcircuito y la matriz unitaria asociada ella est´ an dadas por:  1 0 m2 =  0 0

| 0, 0i → | 0, 0i , | 0, 1i → | 1, 1i , | 1, 0i → | 1, 0i ,

0 0 0 1

0 0 1 0

 0 1 . 0 0

| 1, 1i → | 0, 1i ,

El tercer subcircuito es similar al primer subcircuito por la tanto la matriz m3 es igual a la matriz m1 . La matriz Uintercambio correspondiente al circuito de intercambio de dos qubits est´a dada por:

47

(46)

| xi

⊕

| yi

r

| yi | y ⊕ xi

Figura 6: Segundo subcircuito para el intercambio de dos qubits.

Uintercambio = (m1 × m2 ) × m3    1 " 1 0 0 0 0 1 0 0 0   =  0 0 0 1 × 0 0 0 0 1 0

0 0 0 1

0 0 1 0

  1 0 # 0 1  × 0 0 0 0

0 1 0 0

0 0 0 1

  1 0 0 0 = 1  0 0 0

0 0 1 0

0 1 0 0

 0 0 . 0 1

La verificaci´ on de que Uintercambio es la matriz unitaria correspondiente a la tranformaci´on que realiza el intercambio de dos qubits fue presentada en el ejemplo 3.5 en donde se multiplica cada par de qubits | 0, 0i, | 0, 1i, | 1, 0i y | 1, 1i (en su representaci´ on vectorial) por la matriz Uintercambio y se obtiene los qubits | 0, 0i, | 1, 0i, | 0, 1i y | 1, 1i respectivamente (en su representaci´on vectorial).

4. 4.1.

Reversibilidad y estados enredados Reversibilidad

Se puede clasificar los procesos de c´ omputo, am´en de que satisfacen las leyes fundamentales de la f´ısica, en aquellos para los que lo fundamental es una operaci´on irreversible (disipativa), y del otro lado aquellos para los cuales eso no es fundamental. Las compuertas l´ogicas-cu´anticas, materializadas en dispositivos de alg´ un tipo, son las encargadas de realizar las operaciones, los c´omputos. Una compuerta l´ogica cuya informaci´ on de salida sea menor que la de entrada es irreversible (disipativa), pues tuvo que desechar informaci´on, lo cual se traduce en u ´ltima instancia en una perdida de energ´ıa de alg´ un tipo. Por el contrario, una compuerta l´ ogica cuya informaci´ on de salida sea igual a la informaci´on de entrada sera reversible (no disipativa), la informaci´ on permanece invariante, lo cual lleva consigo una energ´ıa manifiestamente constante. Una compuerta de este tipo, m´ as a´ un, un sistema de compuertas de este estilo, conectadas de alguna forma, capaz de realizar una operaci´ on l´ ogica, es susceptible de que en ella se invierta el proceso de c´omputo y al final se recupere las condiciones iniciales sin perdida alguna de energ´ıa. Una caracter´ıstica importante al estudiar las compuertas reversibles, es que Bennett en 1973 (cf. [3]) demostr´o que las compuertas irreversibles no son esenciales en los procesos de c´ omputo. Del mismo modo Fredkin con Toffoli y otros miembros del MIT, han demostrado que en particular la fricci´ on no es esencial en los procesos de computo, seg´ un Fredkin, puede construirse un ordenador basado exclusivamente en un tipo de compuertas reversibles que llevan su nombre. Textualmente en [3], pag. 39, se concluye: “As´ı pues, seg´ un la termodin´ amica cl´ asica, para realizar un c´ omputo no har´ıa falta consumir, como m´ınimo, una cuota prefijada de energ´ıa”. Desde el punto de vista de las compuertas cu´anticas, su reversibilidad es una consecuencia de la unitariedad de los operadores que las implementan. Sea Uf la matriz unitaria asociada a una compuerta f entonces para cualesquiera estados | xi , | yi se obtiene: 48

Uf | xi = | yi =⇒ Uf† Uf | xi = Uf† | yi , =⇒ | xi = Uf† | yi , es decir, desde la infomarci´ on de salida (ket | yi) es posible obtener la informaci´on de entrada (ket | xi). A partir de una funci´ on f de n bits en m bits se puede construir una funci´on reversible freversible de m + n bits en m + n bits dada por (cf. [1]): f : x → f (x)

99K

freversible : (x, y) → (x, y ⊕ f (x));

(47)

entonces, una funci´ on f puede ser implementada por un circuito cu´antico Uf , cumpliendo las condiciones de reversibilidad exigidas a ´este, si Uf realiza la transformaci´on: Uf | x, yi → | x, y ⊕ f (x)i .

(48)

Se presenta a continuaci´ on una compuerta l´ogica reversible conocida como compuerta de Toffoli y su implementaci´ on en un circuito cu´ antico. La importancia de esta compuerta radica en sus capacidades de computaci´ on universal, presentadas a continuaci´on. Las compuertas l´ ogicas and y not son llamadas compuertas l´ogicas universales, porque cualquier funci´ on f : {0, 1}n → {0, 1}m puede ser implementada en un circuito l´ogico que utilice s´olo estas compuertas. Por otro lado, no es posible obtener un conjunto de compuertas universales para funciones reversibles de la forma f : {0, 1}n → {0, 1}n con compuertas reversibles de 1-bit ni con compuertas reversibles de 2-bits; un conjunto de compuertas universales reversibles est´ a formado por una compuerta de 3-bits llamada la compuerta de Toffoli e ilustrada en la figura 7 (cf. [12], cap´ıtulo 6). x y z

Compuerta Toffoli

x y z ⊕ (x ∧ y)

Figura 7: Compuerta universal reversible: Compuerta de Toffoli.

Esta compuerta puede ser vista como un ejemplo de la aplicaci´on de la ecuaci´on (47) a la funci´on and entre dos bits, es decir: and : (x, y) → x ∧ y

99K

tof f oli : (x, y, z) → (x, y, z ⊕ (x ∧ y)).

(49)

El comportamiento de la compuerta de Toffoli es descrito por la tabla 3 y su caracter de compuerta universal es resumido por la ecuaci´ on (50) en donde se indica que dicha compuerta puede actuar como una compuerta and o una compuerta not o una compuerta xor o una compuerta identidad. 49

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

z ⊕ (x ∧ y) 0 1 0 1 0 1 1 0

Cuadro 3: Comportamiento compuerta Toffoli.

 x∧y    x ⊕ z z ⊕ (x ∧ y) =  ¬z    x

sii sii sii sii

z = 0 (compuerta and ), y = 1 (compuerta xor ), x = y = 1 (compuerta not), x = 0; y = 1 (compuerta identidad ).

(50)

La compuerta de Toffoli puede ser vista como un circuito cu´antico representado por la figura 8. A este circuito le corresponde la matriz unitaria dada por la ecuacion (51). | xi

r | xi

| yi

r

| zi ⊕

| yi | z ⊕ (x ∧ y)i

Figura 8: Circuito cu´antico de Toffoli.

UT of f oli

 1 0  0  0 = 0  0  0 0

0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1

 0 0  0  0  0  0  1 0

(51)

Aunque la compuerta cu´ antica de Toffoli es un compuerta de 3-qubits, ´esta puede ser implementada por un circuito cu´ antico que s´ olo utiliza compuertas cu´anticas de 1-qubit y de 2-qubits. En particular, la compuerta cu´ antica de Toffoli puede ser descompuesta en un circuito cu´antico formado con seis compuertas xor y ocho

50

compuertas de 1-qubit ; pero s´ı se es permitido un cambio de fase, la compuerta puede ser constru´ıda tal como lo indica la figura 9 (cf. [8], [2]), en la cual se han identificado cada una de las compuertas Ry (π/4) con los nombres de compuerta1 y compuerta2 , cada una de las compuertas Ry† (π/4) con los nombres compuerta3 y compuerta4 y cada una de las compuertas xor con los nombres xor1 , xor2 y xor3 . r r

Ry ( π4 )

⊕

r

Ry ( π4 )

⊕

Ry† ( π4 )

⊕

Ry† ( π4 )

compuerta1 xor1 compuerta2 xor2 compuerta3 xor3 compuerta4 Figura 9: Implementaci´ on de la compuerta de Toffoli con compuertas de 1-qubit y 2-qubits.

La implementaci´ on de la compuerta de Toffoli con compuertas cu´anticas de 1-qubits y 2-qubits, utiliza compuertas Ry ( Π4 ) cuya matriz unitaria fue descrita por la ecuaci´on (39), compuertas Ry† ( Π4 ) cuya matriz unitaria es la conjugada transpuesta de la matriz anterior y compuertas xor cu´anticas cuya matriz unitaria corresponde a la ecuaci´ on (42). La construcci´ on de la matriz unitaria se realizar´a para tres (| 0, 0, 0i , | 1, 0, 0i , | 1, 1, 1i) de los ocho posibles casos.

1. caso | 0, 0, 0i Paso 0: Los valores iniciales de los kets | xi , | yi y | zi est´an dados por | 0i , | 0i y | 0i respectivamente, con lo cual se forma el estado cu´ antico inicial: | 0i ⊗ | 0i ⊗ | 0i = | 0, 0, 0i .

(52)

Paso 1: La compuerta1 actua sobre el ket | zi = | 0i y el nuevo estado cu´antico es (ejemplo 3.3, ecuaci´on (31)): | 0i × | 0i ⊗ (cos(π/8) | 0i − sen(π/8) | 1i = cos(π/8) | 0, 0, 0i − sen(π/8) | 0, 0, 1i .

(53)

Paso 2: La compuerta xor1 efectua un xor entre el ket | yi = | 0i y el ket | zi = cos(π/8) | 0i − sen(π/8) | 1i y el nuevo estado cu´ antico es (ejemplo 3.6, ecuaci´on (43)):

| 0i × | 0i ⊗ (cos(π/8) | 0 ⊕ 0i − sen(π/8) | 0 ⊕ 1i) = cos(π/8) | 0, 0, 0i − sen(π/8) | 0, 0, 1i . 51

(54)

Paso 3: La compuerta2 actua sobre el ket | zi = cos(π/8) | 0i − sen(π/8) | 1i y el nuevo estado cu´antico es (ejemplo 3.3, ecuaci´ on (33)): | 0i × | 0i ⊗ (cos(π/4) | 0i − sen(π/4) | 1i) = cos(π/4) | 0, 0, 0i − sen(π/4) | 0, 0, 1i .

(55)

Paso 4: La compuerta xor2 efectua un xor entre el ket | xi = | 0i y el ket | zi = cos(π/4) | 0i − sen(π/4) | 1i y el nuevo estado cu´ antico es (ejemplo 3.6, ecuaci´on (43)):

| 0i × | 0i ⊗ (cos(π/4) | 0 ⊕ 0i − sen(π/4) | 0 ⊕ 1i) = cos(π/4) | 0, 0, 0i − sen(π/4) | 0, 0, 1i .

(56)

Paso 5: La compuerta3 actua sobre el ket | zi = cos(π/4) | 0i − sen(π/4) | 1i y el nuevo estado cu´antico es (ejemplo 3.4, ecuaci´ on (35)): | 0i ⊗ | 0i ⊗ (cos(π/8) | 0i − sen(π/8) | 1i) = cos(π/8) | 0, 0, 0i − sen(π/8) | 0, 0, 1i .

(57)

Paso 6: La compuerta xor2 efectua un xor entre el ket | yi = | 0i y el ket | zi = cos(π/8) | 0i − sen(π/8) | 1i y el nuevo estado cu´ antico es (ejemplo 3.6, ecuaci´on (43)):

| 0i ⊗ | 0i ⊗ (cos(π/8) | 0 ⊕ 0i − sen(π/8) | 0 ⊕ 1i) = cos(π/8) | 0, 0, 0i − sen(π/8) | 0, 0, 1i .

(58)

Paso 7: Finalmente, la compuerta matriz3 actua sobre el ket | zi = cos(π/8) | 0i − sen(π/8) | 1i y el nuevo estado cu´ antico es (ejemplo 3.4, ecuaci´on (36)): | 0i ⊗ | 0i ⊗ | 0i = | 0, 0, 0i .

(59)

Conclusi´ on: Con base en las transformaciones (52), (53), (54), (54), (55), (56), (57), (58) y (59), se afirma que la compuerta de Toffoli realiza la transformaci´on: UT of f oli | 0, 0, 0i → | 0, 0, 0i .

(60)

2. caso | 1, 0, 0i Este caso ilustra la transformaci´ on realizada por el xor cuando el primer qubit es uno, tal como lo indica el ejemplo 3.6, ecuaci´ on (43), pero de mayor importancia, este es el caso en donde se presenta 52

la diferencia de fase entre la compuerta de Toffoli representada por la figura 8 y su implementaci´ on indicada por la figura 9. Para ilustraci´on de este caso simplemente se indicaran las transformaciones realizadas por cada uno de los componentes del circuito indicado por la figura 9. | 1, 0, 0i

→ cos(π/8) | 1, 0, 0i − sen(π/8) | 1, 0, 1i

(61)

→ cos(π/8) | 1, 0, 0i − sen(π/8) | 1, 0, 1i

(62)

→ cos(π/4) | 1, 0, 0i − sen(π/4) | 1, 0, 1i

(63)

→ − sen(π/4) | 1, 0, 0i + cos(π/4) | 1, 0, 1i

(64)

→ − sen(3π/8) | 1, 0, 0i + cos(3π/8) | 1, 0, 1i

(65)

→ − sen(3π/8) | 1, 0, 0i + cos(3π/8) | 1, 0, 1i

(66)

→ − | 1, 0, 0i .

(67)

P aso 1

P aso 2

P aso 3

P aso 4 P aso 5

P aso 6

P aso 7

Conclusi´ on: Con base en las transformaciones (61), (62), (62), (63), (64), (65), (66) y (67), se afirma que la compuerta de Toffoli realiza la transformaci´on: UT of f oli | 1, 0, 0i → − | 1, 0, 0i ,

(68)

y este es el cambio de fase mencionado anteriormente. 3. caso | 1, 1, 1i Este caso ilustra uno de los dos casos (el otro caso es | 1, 1, 0i) en el cual la compuerta de Toffoli cambia el tercer qubit. | 1, 0, 0i

→ sen(π/8) | 1, 1, 0i + cos(π/8) | 1, 1, 1i

(69)

→ cos(π/8) | 1, 1, 0i + sen(π/8) | 1, 1, 1i

(70)

→ | 1, 1, 0i

(71)

→ | 1, 1, 1i

(72)

→ − sen(π/8) | 1, 1, 0i + cos(π/8) | 1, 1, 1i

(73)

→ cos(π/8) | 1, 1, 0i − sen(π/8) | 1, 1, 1i

(74)

→ | 1, 1, 0i .

(75)

P aso 1 P aso 2 P aso 3

P aso 4

P aso 5

P aso 6 P aso 7

Conclusi´ on: Con base en las transformaciones (69), (70), (70), (71), (72), (73), (74) y (75), se afirma que la compuerta de Toffoli realiza la transformaci´on: UT of f oli | 1, 1, 1i → | 1, 1, 0i . 53

(76)

4.2.

Estados enredados

Una de las caracter´ısticas particulares y no intuitivas de los sistemas cu´anticos es la relacionada con la existencia de estados enredados (entaglement). La existencia de estos estados cu´anticos permiten afirmar que la descripci´ on del estado de un sistema cu´antico no puede ser siempre realizada con base en la descripci´ on de los elementos que lo componen. Un estado cu´ antico de n qubits se dice enredado si este no puede ser expresado como el producto tensorial de los estados de cada uno de los n qubits que lo componen. Sean dos qubits | xi y | yi dados por: | xi = a | 0i + b | 1i ;

| yi = c | 0i + d | 1i ;

a, b, c, ∈ C

(77)

el producto tensorial de estos dos qubits est´a dado por: | xi ⊗ | yi = | x, yi = (a | 0i + b | 1i) ⊗ (c | 0i + d | 1i) = ac | 0, 0i + ad | 0, 1i + bc | 1, 0i + bd | 1, 1i ;

(78)

entonces, un estado de dos qubits es un estado enredado si no puede ser expresado en la forma de la ecuaci´ on (78). Ejemplo 4.1. El estado | ψi = 21 (| 0, 0i − | 0, 1i + | 1, 0i − | 1, 1i) es un estado no enredado, porque el sistema de ecuaciones ac = tiene la solucion a = b = c =

√1 ; d 2

1 ; 2

1 ad = − ; 2

1 ; 2

1 bd = − ; 2

= − √12 , es decir:

1 | ψi = (| 0, 0i − | 0, 1i + | 1, 0i − | 1, 1i) = 2 Ejemplo 4.2. El estado | ψi =

bc =

√1 (| 0, 1i 2

ac = 0;

1 1 √ | 0i + √ | 1i 2 2

! ⊗

! 1 1 √ | 0i − √ | 1i . 2 2

+ | 1, 0i) es un estado enredado, porque el sistema de ecuaciones 1 bc = √ ; 2

1 ad = √ ; 2

bd = 0;

no tiene solucion. El an´ alisis del comportamiento de un sistema cu´antico con relaci´on a la medida del mismo, permite observar si el sistema se encuentra o no en un estado enredado. Un sistema se encuentra en un estado enredado si la medida de uno de sus componentes afecta la medida de los otros, y el sistema se encuentra en un estado no enredado si esto no sucede. Se ilustra lo anterior con base en el estado no enredado y el estado enredado presentados en los ejemplos anteriores.

54

Ejemplo 4.3. Para el estado no enredado | ψi = 21 (| 0, 0i − | 0, 1i + | 1, 0i − | 1, 1i) presentado en el ejemplo 4.1, de acuerdo a la ecuaci´ on (21), se obtienen las siguientes probalidades de medida sobre el primer qubit (P1 ) y sobre el segundo qubit (P2 ): P1 (| 0i) = P1 (| 1i) = P2 (| 0i) = P2 (| 1i) =

1 . 2

(79)

De acuerdo al comportamiento de la medida indicado por las ecuaciones (22) y (23), s´ı el primer qubit es medido | 0i el estado del sistema viene a ser (una vez normalizado) | ψi = √12 (| 0, 0i − | 0, 1i) y si el primer qubit es medido | 1i el estado del sistema viene a ser (una vez normalizado) | ψi = √12 (| 1, 0i − | 1, 1i). En ambos casos, las probabilidades de medida sobre el segundo qubit son: P2 (| 0i) = P2 (| 1i) = 1/2. De donde se puede observar que la medida del primer qubit no afecta la medida del segundo qubit. Ejemplo 4.4. Para el estado enredado | ψi = √12 (| 0, 1i + | 1, 0i) presentado en el ejemplo 4.2, se obtienen las siguientes probalidades de medida sobre el primer qubit (P1 ) y sobre el segundo qubit (P2 ): P1 (| 0i) = P1 (| 1i) = P2 (| 0i) = P2 (| 1i) =

1 . 2

(80)

Si el primer qubit es medido | 0i el estado del sistema viene a ser (una vez normalizado) | ψi = | 0, 1i y las probabilidades de medida sobre el segundo qubit son: P2 (| 0i) = 0 y P2 (| 1i) = 1. Si por el contrario, el primer qubit es medido | 1i el estado del sistema viene a ser (una vez normalizado) | ψi = | 1, 0i y las probabilidades de medida sobre el segundo qubit son: P2 (| 0i) = 1 y P2 (| 1i) = 0. De donde se puede observar que la medida del primer qubit si afecta la medida del segundo qubit.

5.

Paralelismo cu´ antico

Como se mencion´ o en la introducci´ on, una de las caracter´ısticas principales que dota a la computaci´ on cu´ antica de su enorme poder de computaci´ on es el paralelismo impl´ıcito en las operaciones cu´anticas. Inicialmente se construye un ejemplo que hace uso del paralelismo cu´antico y despu´es se presenta este paralelismo en forma general.

5.1.

Problema de Deutsch

Es usual que las introducciones a la computaci´on cu´antica presenten como primer ejemplo de un problema que no tiene soluci´ on por los m´etodos de computaci´on cl´asica, pero que si la tiene por los m´etodos de la computaci´ on cu´ anticos, el problema de Deutsch (cf. [12], [5], [16]). Sin embargo, es necesario resaltar que la insolubilidad cl´ asica no es en t´erminos de computabilidad, sino que es en t´erminos de complejidad, y como se mencion´ o en la introducci´ on, es precisamente en el ´area de la complejidad algor´ıtmica, donde la computaci´ on cu´ antica es m´ as potente que la computaci´on cl´asica. Sea f : {0, 1} → {0, 1} una funci´ on cualesquiera. Se dice que f es una funci´on constante si f (0) = f (1), de lo contrario se dice que f es una funci´ on balanceada. ¿Ser´a posible determinar evaluando f una sola vez si ´esta es una funci´ on constante o balanceada?. Este problema es conocido como el problema de Deutsch.

55

An´ alisis cl´ asico: Existen cuatro posibles funciones de la forma f : {0, 1} → {0, 1} dadas por f1 (0) = 0,

f2 (0) = 0,

f3 (0) = 1,

f4 (0) = 1,

f1 (1) = 0,

f2 (1) = 1,

f3 (1) = 0,

f4 (1) = 1.

Las funciones f1 y f4 son contantes y las funciones f2 y f3 son balanceadas. No es d´ıficil construir una m´ aquina de Turing M1 tal que ( 1 sii x = y, M1 (x, y) = 0 sii x = 6 y; donde x representa el valor f (0) y y representa el valor f (1). Pero esta m´aquina no resuelve el problema de Deutsch porque expl´ıcitamente exige la evaluaci´on de la funci´on f dos veces. Una m´aquina de Turing M2 que resuelva el problema de Deutsch es una m´aquina tal que ( 1 sii x = y, M2 (x) = 0 sii x 6= y; pero esta m´ aquina es imposible de construir por la explicable raz´on de que el t´ermino y no hace parte de sus entradas. Es decir, el problema de Deutsch no tiene soluci´on desde la computaci´on cl´asica. An´ alisis cu´ antico: Desde el punto de vista cu´ antico el problema de Deutsch se soluciona con una compuerta cu´antica de dos qubits de entrada y de salida que realiza la transformaci´on: Udeutsch |x, yi → |x, y ⊕ f (x)i.

(81)

Para determinar el estado de entrada a la compuerta se definen los qubits |xi y |yi por (el an´alisis de esta compuerta se realizar´ a sobre estados no normalizados): |xi = |0i + |1i,

|yi = |0i − |1i,

(82)

de donde se obtiene el estado enredado (ver ejemplo 4.1) |x, yi = (|0i + |1i) ⊗ (|0i − |1i) = |0, 0i − |0, 1i + |1, 0i − |1, 1i = | ψentrada i .

(83)

La caracter´ıstica principal de este estado inicial es que es un estado superpuesto y esto posibilita la evaluaci´ on de la funci´ on f una sola vez, tal como se indica a continuaci´on.

56

Si se aplica la tranformaci´ on representada por (81) al estado representado por (83) se obtiene Udeutsch |ψentrada i = |0, 0i − |0, 1i + |1, 0i − |1, 1i = |0, 0 ⊕ f (0)i−

(84)

|0, 1 ⊕ f (0)i+

(85)

|1, 0 ⊕ f (1)i−

(86)

|1, 1 ⊕ f (1)i

(87)

= |ψsalida i.

(88)

El an´ alisis de los t´erminos (84) y (85) que componen el estado de salida |ψsalida i est´a dado por: 1. T´ermino |0, 0 ⊕ f (0)i a) Caso f (0) = 0 |0, 0 ⊕ f (0)i = |0, 0 ⊕ 0i = |0, 0i = |0, f (0)i. b) Caso f (0) = 1 |0, 0 ⊕ f (0)i = |0, 0 ⊕ 1i = |0, 1i = |0, f (0)i. Es decir, sin importar el valor de f (0) se obtiene que |0, 0 ⊕ f (0)i = |0, f (0)i.

(89)

2. T´ermino |0, 1 ⊕ f (0)i a) Caso f (0) = 0 ( |0, 1 ⊕ f (0)i = |0, 1 ⊕ 0i = |0, 1i = |0, f (0)i,

donde f (0) =

1 0

sii sii

f (0) = 0, f (0) = 1.

b) Caso f (0) = 1 |0, 1 ⊕ f (0)i = |0, 1 ⊕ 1i = |0, 0i = |0, f (0)i. Es decir, sin importar el valor de f (0) se obtiene que |0, 1 ⊕ f (0)i = |0, f (0)i.

(90)

Un an´ alisis similar se realiza para los t´erminos (86) y (87) y se obtiene |1, 0 ⊕ f (1)i = |1, f (1)i,

(91)

|1, 1 ⊕ f (1)i = |1, f (1)i.

(92)

57

Entonces, con base en los resultados (89), (90), (91) y (92), al aplicar la tranformaci´on (81) al estado (83) se obtiene Udeutsch |ψentrada i = |0, 0i − |0, 1i + |1, 0i − |1, 1i = |0, 0 ⊕ f (0)i − |0, 1 ⊕ f (0)i + |1, 0 ⊕ f (1)i − |1, 1 ⊕ f (1)i = |0, f (0)i − |0, f (0)i + |1, f (1)i − |1, f (1)i     = |0i ⊗ |f (0)i − |f (0)i + |1i ⊗ |f (1)i − |f (1)i

(93)

= |ψsalida i.

El lector podr´ a notar que el estado |ψsalida i representado por la ecuaci´on (93) todav´ıa exige la evaluaci´ on de f (0) y f (1), por lo tanto, a´ un no hemos resuelto el problema de Deutsch. El an´alisis de los dos posibles caso, f constante o f es variente es: 1. f es constante     |ψsalida i = |0i ⊗ |f (0)i − |f (0)i + |1i ⊗ |f (1)i − |f (1)i     = |0i ⊗ |f (0)i − |f (0)i + |1i ⊗ |f (0)i − |f (0)i = (|0i + |1i) ⊗ (|f (0)i − |f (0)i). | {z } | {z } primer qubit

(94)

segundo qubit

2. f es balanceada 



 |ψsalida i = |0i ⊗ |f (0)i − |f (0)i + |1i ⊗ |f (1)i − |f (1)i     = |0i ⊗ |f (0)i − |f (0)i − |1i ⊗ |f (0)i − |f (0)i = (|0i − |1i) ⊗ (|f (0)i − |f (0)i). {z } | {z } | primer qubit



(95)

segundo qubit

En este momento, el posible estado de salida (ecuaci´on (94) o ecuaci´on (95)) exige solamente la evaluaci´ on de f (0). Entonces, para determinar si la funci´on f es constante o balanceada se mide el primer qubit del estado de salida sobre la base {| 0i + | 1i , | 0i − | 1i}. Con base en la ecuaciones (19) y (20), s´ı el valor obtenido al medir el primer qubit es (|0i + |1i), la funci´on es constante y s´ı por el contrario se obtiene el valor (|0i − |1i), la funci´ on es balanceada. El ´exito de la soluci´ on cu´ antica al problema de Deutsch radica en la posibilidad de evaluar simult´ aneamente los valores de f (0) y f (1), est´ a evaluaci´on simult´anea es sustenda en el paralelismo cu´antico que es descrito a continuaci´ on. 58

5.2.

Descripci´ on del paralelismo cu´ antico

Para generalizar el problema de Deutsch, sea f una funci´on implementada por un circuito cu´antico Uf , tal que: Uf | x, yi → | x, y ⊕ f (x)i , (96) entonces, para obtener el valor de f (x) se realiza la computaci´on Uf | x, 0i → | x, 0 ⊕ f (x)i = | x, f (x)i .

(97)

Un aspecto importante en la soluci´ on al problema de Deutsch esta en la elecci´on de un estado inicial superpuesto dado por la ecuaci´ on (83). En el caso general, con base en las ecuaciones (12) y (13) un estado inicial superpuesto de n qubits se puede expresar por:   2n −1 1 X 1 √ √ | 01 , . . . , 0n−1 , 0n i + | 01 , . . . , 0n−1 , 1n i + | 01 , . . . , 1n−1 , 0n i + · · · + | 11 , . . . , 1n−1 , 1n i = | xi . 2n 2n x=0 (98) Dado que Uf es un operador lineal, cuando Uf es aplicado al estado superpuesto indicado por la ecuaci´ on (98) se obtiene:  Uf

 2n −1 2n −1 2n −1 1 X 1 X 1 X √ | x, 0i = √ Uf | x, 0i = √ | x, f (x)i . 2n x=0 2n x=0 2n x=0

(99)

Es decir, el operador Uf es aplicado simult´aneamente a todos los vectores bases que forman el estado superpuesto y en esto consiste el paralelismo cu´antico. Este paralelismo cu´antico tiene la propiedad de computar para un estado formado por n qubits 2n entradas, es decir, a partir de un crecimiento lineal del n´ umero de qubits, se obtiene un crecimiento exponencial en el espacio de computaci´on. Sin embargo, existe la dificultad de como extraer la informaci´ on de este espacio exponencial de computaci´on; una vez aplicada Uf al estado inicial superpuesto, se obtiene como salida un estado superpuesto de todos los posibles valores | x, f (x)i tal como lo indica la ecuaci´ on (99). La esencia de un algoritmo cu´antico est´a en la selecci´on de un estado superpuesto inicial que potencie la “manipulaci´on” del estado superpuesto final v´ıa la observaci´ on (medida) del mismo y as´ı poder obtener ventajas del paralelismo cu´antico.

6.

Transformada Cu´ antica R´ apida de Fourier (QFFT)

Finalmente, se presenta la QFTT, por ser uno de los mecanismos empleados por los algoritmos cu´anticos para obtener el estado superpuesto inicial, necesario para manipular adecuadamente el paralelismo cu´antico. No existe una definici´ on u ´nica y universalmente aceptada de la transformada de Fourier, algunos autores realizan una clasificaci´ on en transformada de Fourier de tiempo discreto y transformada de Fourier de Tiempo continuo (cf. [10]), otros autores por su parte, definen ciertas constantes que permiten manipular con base en ellas ciertos elementos que componen la transformada (en particular el signo de la exponencial) (cf. [13]). Con respecto a la transformada discreta de Fourier (DFT) ´esta es tambi´en presentada bajo ciertas restricciones 59

de las funciones, restricciones que est´ an relacionadas con la finitud del dominio de la funci´on (cf. [10], [9]), para algunos tama˜ nos n especiales del dominio de la funci´on, en particular cuando n es potencia de 2, existe un algortimo muy eficiente para implementar la DFT conocido como transformada r´apida de Fourier (FTT) (cf. [10]). En el caso particular de la computaci´on cu´antica, la FFT es presentada sobre funciones definidas de un grupo aditivo a los complejos ([4] la presentan para un grupo en especial) y entonces se habla de la transformada cu´ antica r´ apida de Fourier (QFFT). Se ha decidido, para esta presentaci´on seguir el enfoque presentado por [1]. ZQ representa un grupo aditivo de enteros m´odulo Q; sea f una funci´on definida por f : ZQ → C, la transformada discreta de Fourier para la funci´on f denotada por fe es una funci´on fe : ZQ → C definida por: Q−1 1 X f (b)e2πiab/Q fe(a) = √ Q b=0

(100)

Sea Q = 2m , con base en la ecuaciones (12) y (13) se puede expresar la QFFT por: m

2 −1 1 X 2πiab/2m e QF F T | ai = √ | bi . 2m b=0

(101)

Es posible implementar la QFFT por circuitos cu´anticos con diferente n´ umero y tipo de compuertas cua´ nticas, en particular [1] presenta un circuito cu´antico formado exclusivamente por dos tipos de compuertas de un qubit. Se presenta finalmente, un ejemplo para la QFFT. Ejemplo 6.1. Sea | ai = | 1, 0, 1i es decir a = 5 y m = 3, entonces 3

2 −1 1 X 2πi(5)b/23 e | bi QF F T | 1, 0, 1i = √ 23 b=0 3

2 −1 1 X 1 πib = √ e 4 | bi 2 2 b=0  π π 3π 1 = √ | 0, 0, 0i + e 4 i | 0, 0, 1i + e 2 i | 0, 1, 0i + e 4 i | 0, 1, 1i + 2 2  π 3π 3π eπi | 1, 0, 0i + e 4 i | 1, 0, 1i + e 2 i | 1, 1, 0i + e 4 i | 1, 1, 1i

1 1 i 1 = √ | 0, 0, 0i + (1 + i) | 0, 0, 1i + √ | 0, 1, 0i + (−1 + i) | 0, 1, 1i + 4 4 2 2 2 2 1 −i 1 −1 √ | 1, 0, 0i + (1 + i) | 1, 0, 1i + √ | 1, 1, 0i + (−1 + i) | 1, 1, 1i . 4 4 2 2 2 2

Referencias [1] Dorit Aharonov. Quantum computation. Eprint: arXiv.org/abs/quant-ph/9812037 (1998). 60

[2] Adriano Barenco, Charles H. Bennett, Richard Cleve David P. DiVincenzo, Norman Margolus Peter Shor Tycho Sleator, John Smolin y Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995). [3] Charles H. Bennett y Rolf Landauer. Limitaciones f´ısicas fundamentales de los procesos de c´ omputo. Investigaci´ on y Ciencia p´ aginas 8–19 (julio 1984). [4] Ethan Bersntein y Umesh Vazirani. Quantum complexity theory. SIAM J. Comput. 26(5), 1411– 1473 (octuber 1997). [5] Samuel L. Braunstein. Quantum computation: a tutorial. Eprint: chemphys.weizmann.ac.il/ ~schmuel/comp/comp.html (1995). [6] David Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97–117 (1985). [7] David Deutsch. Quantum computational networks. Proc. R. Soc. Lond. A 425, 73–90 (1989). [8] David P. DiVincenzo. Quantum gates and circuits. For the Proc. of the ITP Conference on Quantum Coherence and Decoherence, Dec., 1996, Proc. R. Soc. London A. Eprint: arXiv.org/abs/quant-ph/ 9705009 (1996). [9] Jack D. Gaskill. “Linear system, fourier transforms, and optics”. Wiley Series in Pure and Applied Optics. New York: John Wiley & Sons (1978). [10] Alan Oppenheim y Alan Willsky. “Se˜ nales y sistemas”. M´exico D.F.: Prentice-Hall Hispanoamericana, S.A. (1994). [11] Roger Penrose. “The emperor’s new mind concerning computers, minds and the laws of physics”. Oxford University Press (1989). [12] John Preskill. Advance mathematical www.theory.caltech.edu/ preskill/ph229 (1998).

methodos

of

physics:

notes

course.

[13] Robert T. Seeley. “Introducci´ on a las series e integrales de Fourier”. Editorial Revert´e S.A. (1970). [14] Peter W. Shor. Polinomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). [15] Mike Stannett. X-machines and the halting problem: building a super-Turing machine. Formal Aspects of Computing 2, 331–341 (1990). [16] Vlatko Vedral y Martin B. Plenio. Basics of quantum computation. Febrero 25, 1998 (1998).

61