PDF de programación - Un poco de computación cuántica: Algoritmos más comunes

Un poco de computación cuántica: Algoritmos más comunes

Guillermo Morales-Luna

Centro de Investigación y Estudios Avanzados del IPN

(CINVESTAV-IPN)

[email protected]

11 de diciembre de 2003

Resumen

El presente escrito constituye una introducción a la computación cuántica, es más bien un cursillo
“tutorial” y el único reclamo de originalidad es la de su presentación. De hecho, ha sido grande la
tentación de sutituir el adjetivo “cuántica” en “computación” por la frase adjetival “paralela basada en
álgebra exterior”. Nuestra presentación deja de lado la discusión sobre la plausibilidad de la computación
cuántica y las nociones inherentes de la física cuántica involucradas. Aquí sólo nos concentraremos en
presentar este paradigma como uno abstracto de cómputo y en él presentamos sus funciones primitivas,
los esquemas de composición y la codificación de entradas y salidas. Nos basamos en planteamientos
ortodoxos de álgebra exterior y utilizamos una notación más acorde con esta última.

Antes que nada presentamos las nociones básicas necesarias de álgebra exterior. Al iniciar el concepto
de computación cuántica propiamente presentamos a los espacios de Hilbert donde se realiza, la noción
de qubit e ilustramos el mecanismo de cómputo con el algoritmo ya clásico de Deutsch-Josza. Luego pre-
sentamos un algoritmo para calcular transformaciones discretas de Fourier en tiempo lineal. Finalmente,
presentamos el célebre algoritmo de Shor para la factorización de enteros en tiempo polinomial.

Contents

1 Productos tensoriales

1.1 Productos de vectores y espacios
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Productos de transformaciones lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Nociones básicas de Computación Cuántica

2.1 Postulado de medición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
qubits y palabras de longitud finita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
2.3 Compuertas cuánticas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Evaluación de funciones booleanas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Algoritmo de Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Algoritmo para el cálculo de la Transformada Discreta de Fourier

4 Algoritmo de Shor

4.1 Pequeño recordatorio de Teoría de Números . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Algoritmo cuántico para el cálculo de órdenes . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Elementos con orden potencia de 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Elementos con orden arbitrario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2

3
3
4
4
6
6

7

9
9
10
10
12

1

1 Productos tensoriales

1.1 Productos de vectores y espacios
Sea U un espacio vectorial sobre el campo C de los números complejos. Denotemos por L(U, V ) al espacio
de transformaciones lineales de U en V . El dual del espacio U es U∗ = L(U, C). Si u∗ ∈ U∗ escribimos, para
cada u ∈ U, u∗|u := u∗(u). ·|· : U∗ × U → C es una transformación bilineal.
Sea V otro espacio vectorial también sobre C. El producto tensorial de U con V es U ⊗ V = L(V ∗, U).

Se tiene:
Propiedad 1.1 U × V se identifica con un subconjunto de U ⊗ V .

En efecto, consideremos Φ : U × V → U ⊗ V tal que ∀(u, v) ∈ U × V , Φ(u, v) ∈ L(V ∗, U) es la
transformación Φ(u, v) : w∗ → w∗|vu. Claramente Φ es bilineal. Se tiene que Φ(u1, v1) = Φ(u2, v2) si y
sólo si existe k ∈ C tal que (u1, v1) = (ku2, k−1v2). Esta última condición define una relación de equivalencia
≡0 en U × V . Así pues, el espacio cociente (U × V )/ ≡0 se identifica con un subespacio de U ⊗ V . De hecho,
la aplicación Φ(u, v) ∈ L(V ∗, U) se denota como u⊗ v = Φ(u, v) y se dice ser el producto tensorial del vector
u con el vector v. Debido a la linealidad de los operadores involucrados se tiene que valen las relaciones
siguientes:

(zu) ⊗ v = z(u ⊗ v)
u ⊗ (zv) = z(u ⊗ v)

(u1 + u2) ⊗ v = (u1 ⊗ v) + (u2 ⊗ v)
u ⊗ (v1 + v2) = (u ⊗ v1) + (u ⊗ v2)

Resulta claro que el producto tensorial de vectores no es conmutativo, ni siquiera cuando U = V .
Propiedad 1.2 Si dim U = m y dim V = n entonces dim(U ⊗ V ) = mn.

dim(L(V ∗, U)) = nm.

En efecto, si V es de dimensión finita, entonces su dual V ∗ es de la misma dimensión, n, y obviamente
Así pues, si U = Cm y V = Cn entonces, prácticamente, U ⊗ V = Cmn.

Propiedad 1.3 Si BU = {u0, u1, . . . , um−1} es una base de U y BV = {v0, v1, . . . , vn−1} es una base
de V entonces (ui ⊗ vj)i<m,j<n es una base de U ⊗ V , donde, para cada i, j, ui ⊗ vj es la aplicación
w∗ =

j → wjui. Esta base se dice ser la base producto.

n−1

k=0 wjv∗

0, v∗

1, . . . , v∗

En efecto, BV ∗ = {v∗

n−1} es una base del dual V ∗, donde v∗

j1|vj2 = δj1j2. Ahora, respecto a
n−1
m−1
las bases BU y BV , la aplicación ui ⊗ vj se representa mediante la matriz Dij = (δi1j1ij)i1<m,j1<n, donde
δi1j1ij = 1 si y sólo si (i1, j1) = (i, j) y δi1j1ij = 0 si y sólo si (i1, j1) = (i, j). De manera un poco más
m−1
n−1
j=0 bjvj, también cada w∗ ∈ V ∗ como
general, escribamos cada u ∈ U como u =
i=0 aiui y v =
j=0 bjcj, y (u ⊗ v)(w∗) =
j . En consecuencia, w∗|v =
w∗ =

n−1

n−1

j=0 cjv∗

j=0 bjcj

i=0 ai



ui.

1.2 Productos de transformaciones lineales
Supongamos que U1, U2, V1, V2 son espacios vectoriales, de dimensiones respectivas m1, m2 y n1, n2, y que
K : U1 → U2 y L : V1 → V2 son sendas transformaciones lineales. Las transformaciones lineales duales
K∗ : U∗

1 y L∗ : V ∗

2 → V ∗

2 → U∗

1 están definidas mediante las relaciones
2)|u1 = u2|K(u1)
2)|v1 = v2|L(v1)

K∗(u∗
L∗(v∗

Propiedad 1.4 Si K se representa, respecto a bases BU1 y BU2, mediante una matriz MK ∈ Cm2×m1
entonces K∗ se representa, respecto a las bases duales, mediante la matriz traspuesta M T

K ∈ Cm1×m2.

2

Ahora definamos una transformación K⊗L : U1⊗V1 → U2⊗V2 haciendo (K⊗L)(u1⊗v1) = K(u1)⊗L(v1).
Propiedad 1.5 Si K se representa, respecto a bases BU1 y BU2, mediante la matriz MK ∈ Cm2×m1 y L se
representa, respecto a bases BV1 y BV2, mediante la matriz ML ∈ Cn2×n1 entonces (K ⊗ L) se representa,
respecto a las bases productos, mediante la matriz producto tensorial MK ⊗ ML ∈ Cm2n2×m1n1 siguiente:



MK ⊗ ML =

m(K)
00 ML
m(K)
10 ML
...

m(K)
01 ML
m(K)
11 ML
...

···
···
...

m(K)

m2−1,0ML m(K)

m(K)
m(K)

0,m1−1ML
1,m1−1ML

...

m2−1,m1−1ML



m2−1,1ML ··· m(K)




Ahora bien, si U es un espacio vectorial de dimensión m y K : U → U es lineal, definimos recursivamente:
K⊗1 = K, K⊗n = K⊗(n−1) ⊗ K. Naturalmente, K⊗n es la n-ésima potencia tensorial de K. Si MK =
(mij)i,j<m es la matriz cuadrada de orden m que representa a K respecto a una cierta base BU , se tiene que
K⊗n quedará representada por la matriz MK⊗n =

n−1
Cada índice entero i < mn se escribe en base m como una palabra de n dígitos 0, . . . , m − 1, i =
ι=0 ξιmι = (ξn−1 ··· ξ1ξ0)m = ξ(i). Para una tal palabra ξ = ξn−1 ··· ξ1ξ0, definamos car(ξ) = ξ0 y
cdr(ξ) = ξn−1 ··· ξ1. Evidentemente, vistas las palabras como representaciones de números en base m:
(ξ)m = m(cdr(ξ))m + car(ξ), car(ξ) = ξ mod m y cdr(ξ) = (ξ − car(ξ))/m.

determinada como sigue:

m(n)
ij

i,j<mn

Debido a la propiedad 1.5, se tiene la recurrencia

ξ(i),ξ(j) = m(n−1)
m(n)

cdr(ξ(i)),cdr(ξ(j)) · mcar(ξ(i)),car(ξ(j))

(1)

con la cual es posible calcular las entradas de la matriz MK⊗n siguiendo las representaciones en base m de
los índices correspondientes.

2 Nociones básicas de Computación Cuántica





mH
ji

2.1 Postulado de medición
En [2] se presentó la base de la computación cuántica.
Sea C el campo de los números complejos, y para cada m, n sea Cm×n el espacio de matrices de orden
m × n, es decir, de matrices con m renglones y n columnas, con entradas números complejos. Para cada
∈ Cn×m donde para cada pareja
matriz M = (mij)i,j ∈ Cm×n su transpuesta hermitiana es M H =
de índices (i, j) ∈ [[0, m − 1]] × [[0, n − 1]], mH
ji = mij (si z = a + ib ∈ C es un número complejo, naturalmente
z = a − ib ∈ C es su conjugado). Una matriz M = (mij)i,j ∈ Cm×n se dice ser unitaria si M H M = 1nn,
donde 1nn denota a la matriz identidad de orden n × n.
Al subconjunto consistente de los vectores columnas unitarias en Cm×1 (es decir, el espacio de vectores
columnas de dimensión m) se le llama conjunto de estados de un sistema físico cerrado, y la dimensión m
se conoce como el grado de libertad del sistema. En Cm×1 se tiene que cada estado es un vector en la esfera
euclidiana unitaria de Cm. Sea pues Em = {v ∈ Cm|1 = vHv =: v|v} el conjunto de estados.

Sea ej = (δij)i<m el j-ésimo vector de la base canónica de Cm. Se tiene que todo vector de la base
canónica es un estado. Se dice que un estado v = (vi1)i<m produce la salida i con una probabilidad
|vi1|2 = Re(vi1)2 + Im(vi1)2. Se tiene el siguiente
Postulado de Medición: Si el estado actual es v = (vi1)i<m entonces, para cada i < m, con probabilidad
|vi1|2 se realiza lo siguiente: Se emite la respuesta i y se transita al estado ei; es decir este último será
el estado actual en el paso siguiente.

ji

De hecho el proceso de medición se realiza al final de cualquier algoritmo cuántico, así que el último estado
actual al que se refiere en su enunciado es el estado final.
Ahora, sea U ∈ Cm×m una matriz unitaria cuadrada de orden m × m. U determina una transformación
ortogonal Cm → Cm: v → Uv. De hecho, al restringirla a Em se tiene una transformación Em → Em.
U se dice ser una compuerta cuántica. Un algoritm