Introduccion A La Computacion Cuantica

Introducción a la computación cuántica
Salvador E. Venegas Andraca

Tecnológico de Monterrey Campus Estado de México
http://www.cem.itesm.mx/dia/escuelaverano
[email protected], [email protected] y [email protected]
Julio de 2007
1
1 Introducción
La mecánica cuántica es la rama de la fı́sica que describe el comportamiento de la naturaleza a es-
calas muy pequeñas (por ejemplo, el comportamiento de los átomos). La teorı́a de la computación
se encarga de estudiar si un problema es susceptible de ser resuelto utilizando una computadoa, ası́
como la cantidad de recursos (tiempo, energı́a) que se debe invertir en caso de existir solución. En
consecuencia, la computación cuántica hace uso de la mecánica cuántica con el objetivo de incremen-
tar nuestra capacidad computacional para el procesamiento de información y solución de problemas.
Por otra parte, la teorı́a de la información cuántica estudia los métodos, capacidades y lı́mites que las
leyes de la fı́sica imponen en la transmisión y recuperación de información.
El estudio formal de la computación cuántica comenzó con las preguntas que Richard Feynman
planteó sobre dos temas: 1) la posibilidad de simular sistemas cuánticos, y 2) las leyes de la fı́sica
que caracterizan al proceso de calcular [92, 93]. A partir de ese trabajo, la computación cuántica ha
avanzado a paso firme; por ejemplo, se ha definido formalmente la estructura de una computadora
cuántica [3], se han encontrado resultados espectaculares como el algoritmo de Shor [4] (capaz de
factorizar un número entero muy largo en tiempo razonable utilizando una computadora cuántica
[4, 7]) y el algoritmo de Grover [5] (este algoritmo encuentra elementos en conjuntos desordenados
de forma más eficiente que cualquier algoritmo posible ejecutado en computadoras convencionales
[5, 7]), y se ha diseñado una teorı́a y práctica de la criptografı́a usando las propiedades de la fı́sica
cuántica [6]. En el futuro mediato, la computación cuántica tendrá gran impacto en la industria de la
computación y el desarrollo de protocolos de criptografı́a y seguridad computacional [12–14].
La computación y la información cuánticas representan un reto teórico y experimental por la
cantidad y complejidad de problemas a resolver. A pesar de dichos retos, los avances realizados hasta
ahora permiten ya pensar en aplicaciones de esta disciplina en áreas del conocimiento tales como la
Inteligencia Artificial, el Reconocimiento de Patrones [16–23, 91] y la Bioinformática [24–26]. De
hecho, la computación cuántica ha dado ya sus primeros frutos en la industria pues desde 2003 hay
un sistema de criptografı́a cuántica disponible en el mercado [27, 30], y los experimentos realizados
en diversos laboratorios (por ejemplo [28, 29]) ofrecen resultados muy prometedores.
Universidades de prestigio internacional como Oxford [31], Cambridge [32], Harvard [33], Viena
[34], Caltech [35] y MIT [36] llevan a cabo investigación en estas disciplinas con financiamiento
público (Estados Unidos, Reino Unido, Alemania, Francia, Australia y Brasil, entre otros gobier-
nos) y privado (Lucent Technologies [37], Hewlett Packard [38], IBM [39] y Fujitsu [40], entre otras
empresas). La computación cuántica es importante para los gobiernos debido a que la creación de
computadoras cuánticas implicará la existencia de escenarios de alta vulnerabilidad (las computado-
ras cuánticas serán capaces de descifrar, en horas o minutos, los códigos de encriptación que hoy
tomarı́a mucho tiempo resolver. En consecuencia, la confidencialidad de mensajes electrónicos se
verá afectada). Por su parte, la industria del cómputo ha invertido recursos sustanciales en esta es-
pecialidad debido a las ventajas en rapidez y seguridad de datos que la tecnologı́a cuántica traerá
consigo, además de que la miniaturización de componentes electrónicos implica la aparición de efec-
tos cuánticos.
De lo anterior se deduce que las oportunidades de desarrollo profesional para cientı́ficos e inge-
nieros en estas disciplinas son amplias y prometedoras. Además, es importante subrayar que, dado
el alto impacto que la computación e información cuánticas tendrán en el quehacer cientı́fico y en la
2
vida diaria del ser humano, el trabajo desarrollado por algunos cientı́ficos en estas disciplinas ha sido
ya merecedor de premios internacionales como el Prı́ncipe de Asturias 2006 [41, 42].
En el ámbito nacional, la computación y la información cuánticas ha despertado el interés de
varios miembros de la vida cientı́fica e intelectual mexicana. Tanto en publicaciones académicas
[43, 44] como en medios de comunicación masivos [45–54], estos campos del conocimiento y su
posible impacto en nuestra sociedad han sido tratados desde distintas ópticas.
A pesar de contar con recursos humanos calificados en distintas universidades y centros de inves-
tigación (UNAM, INAOE y CINVESTAV, entre otras), y de que algunas instituciones han trabajado
en la formación de recursos humanos (por ejemplo, la primer escuela mexicana de verano en com-
putación cuántica, llevada a cabo en la UADY y el CINVESTAV-Mérida, organizada por los doctores
Luis Alberto Muñoz Ubando, Salvador Venegas Andraca, Romeo de Coss y Juan Luis Dı́az de León
[55, 56]), México no tiene grupos sólidos de investigación en computación e información cuánticas.
Como parte de la estrategia para integrar a México en este campo del conocimiento, el Tec-
nológico de Monterrey Campus Estado de México y la universidad de Leeds (Reino Unido) han
unido esfuerzos para organizar la Segunda Escuela Mexicana de Verano en Computación e Infor-
mación Cuánticas. El presente documento es un texto disenãdo para impartir un curso introductorio
a la computación cuántica durante la primera semana de nuestra escuela.
2 Álgebra lineal
El álgebra lineal es ampliamente utilizada en fı́sica. En particular, este campo de las matemáticas se
usa en la formulación de la mecánica cuántica y, en consecuencia, en la computación y la información
cuánticas.
En esta sección estudiaremos varios elementos del álgebra lineal necesarios para una introducción
seria a la computación cuántica. Para profundizar en los conceptos aquı́ revisados se recomienda
consultar las obras [7], [8], [9], [10] y [11].
2.1 Campo, espacio vectorial, producto interno y norma

Definición 2.1. Campo. Un campo es un conjunto F con dos operaciones, llamadas multiplicación y
adición, que satisface los axiomas siguientes:
1) ∀ x, y ∈ F ⇒ x + y ∈ F
2) ∀ x, y ∈ F ⇒ x + y = y + x
3) ∀ x, y, z ∈ F ⇒ x + (y + z) = (x + y) + z
4) ∃! 0 ∈ F tal que ∀ x ∈ F ⇒ x + 0 = 0 + x = x
5) Para cada x ∈ F ∃! − x ∈ F tal que x + (−x) = −x + x = 0
6) ∀ x, y ∈ F ⇒ xy ∈ F
7) ∀ x, y ∈ F ⇒ xy = yx
8) ∀ x, y, z ∈ F ⇒ x(yz) = (xy)z
9) ∃! 1 ∈ F tal que ∀ x ∈ F ⇒ x1 = 1x = x
10) Para cada x ∈ F − {0} ∃! x−1 ∈ F tal que xx−1 = x−1 x = 1
11) ∀ x, y, z ∈ F ⇒ x(y + z) = xy + xz
3
√
Ejercicio 2.1. Sea C = {a + bi | a, b ∈ R e i = −1} el conjunto de los números complejos.
Sean z1 = a + bi y z2 = c + di números complejos. Definimos entonces:
1) z1 + z2 = (a + bi) + (c + di) = (a + c) + (b + d)i
2) z1 z2 = (a + bi)(c + di) = (ac − bd) + (bc + ad)i
3) z1 ∗ = a − bi
Use 1) y 2) para demostrar que C es un campo.
Definición 2.2. Espacio vectorial. Sea V un conjunto cualquiera, asociado con un campo F (los
elementos de F son llamados escalares). En las siguientes lı́neas daremos las condiciones que debe
cumplir V para recibir el nombre de espacio vectorial, pero antes haremos del conocimiento del lector
algunas aclaraciones:
a) Denotaremos a los elementos de V con la nomenclatura |i, donde el punto es sustituido por
una letra del alfabeto griego o castellano. Además, denotaremos a los elementos de F con simples
letras del alfabeto castellano.
b) La notación generalmente utilizada para describir elementos de V es ~x. Sin embargo, en com-
putación cuántica se acostumbra escribir |xi en lugar de ~x por motivos que expondremos a lo largo
de las siguientes páginas. Baste decir por el momento que el sı́mbolo |xi forma parte de la notación
de Dirac.
Entremos entonces a la definición de un espacio vectorial. Definimos sobre V dos operaciones, la
adición y la multiplicación escalar.
- Por adición se entiende una regla que asocia a cada par de elementos |ui, |vi ∈ V con un objeto
|ui + |vi ∈ V, denominado suma de |ui y |vi.
- Por multiplicación escalar se entiende una regla que asocia a cada k ∈ F y cada objeto |ui ∈ V con
un objeto k|ui ∈ V, denominado múltiplo escalar de |ui por k.
Si ∀ |ui, |vi, |wi ∈ V y ∀ k, l ∈ F se satisfacen los axiomas 1 al 10 que se presentan enseguida

⇒ V se llama espacio vectorial y sus elementos vectores. V también puede recibir el nombre de
espacio vectorial lineal.
1) |ui, |vi ∈ V ⇒ |ui + |vi ∈ V

2) |ui + |vi = |vi + |ui
3) |ui + (|vi + |wi) = (|ui + |vi) + |wi
4) ∃ 0 ∈ V, llamado vector cero o elemento neutro aditivo, tal que |ui + 0 = 0 + |ui = |ui (observe
la notación atı́pica).
5) Para cada |ui ∈ V ∃! − |ui ∈ V tal que |ui + (−|ui) = −|ui + |ui = 0
6) ∀ |ui ∈ V, k ∈ F ⇒ k|ui ∈ V
7) (k + l)|ui = k|ui + l|ui
8) k(l|ui) = (kl)|ui
9) k(|ui + |vi) = k|ui + k|vi
10) 1|ui = |ui, siendo 1 el elemento neutro multiplicativo de F.
Nota. Si el campo en cuestión es C (R) entonces V recibe el nombre de espacio vectorial complejo
(real).
4
Ejercicio 2.2. Demuestre que:
a) Cn = {|ui = (u1 , u2, . . . , un )t | u1 , u2 , . . . , un ∈ C} es un espacio vectorial complejo.
b) Mn (C), el conjunto de las matrices de orden n y con entradas complejas, es un espacio vectorial
complejo.
Definición 2.3. Espacio vectorial complejo con producto interno. En la geometrı́a euclı́dea, las
propiedades que cuentan con la posibilidad de medir longitudes de segmentos rectilı́neos y ángulos
formados por rectas se llaman propiedades métricas. Además, en el estudio elemental de Rn se utiliza
el concepto de producto escalar para calcular longitudes y ángulos. Ahora extenderemos estas ideas
a espacios vectoriales generales a través de la definición del producto interno.
Sea V un espacio vectorial complejo. El espacio V se conoce como espacio vectorial complejo
con producto interno si es posible definir la función producto interno (·, ·) : V × V → C, la cual
obedece los axiomas plasmados en las siguientes lı́neas:
∀ |ui, |vi, |wi, |xi ∈ V, α, β ∈ C ⇒
1) (|ui, |ui) ≥ 0 y (|ui, |ui) = 0 ⇔ |ui = 0
2) (|ui, |vi) = (|vi, |ui)∗
3) (|ui, α|vi + β|wi) = α(|ui, |vi) + β(|ui, |wi) 1
Ejercicio 2.3. Sean |xi = (x1 , x2 , . . . , xn )t , |yi = (y1 , y2 , . . . , yn )t ∈ Cn ⇒ definimos el producto
interior en Cn de la siguiente manera:
(|xi, |yi) = (x∗1 y1 + x∗2 y2 + . . . + x∗n yn )1/2 = ( ni=1 x∗i yi )1/2 , donde x∗i es el conjugado de xi .
P
Demuestre que, con esta definición de producto interno, Cn es un espacio vectorial complejo con
producto interno. El espacio vectorial Cn , con el producto interno definido en este ejercicio, recibe el
nombre de espacio vectorial n-dimensional complejo con producto interno.
Definición 2.4. Espacio vectorial normado. Sea V un espacio vectorial complejo
p con producto
interno. Definimos la norma || |xi || de un elemento |xi ∈ V como || |xi || = (|xi, |xi), la cual
debe satisfacer las siguientes propiedades:
1) ∀|xi ∈ V ⇒ || |xi || ≥ 0, y || |xi || = 0 ⇔ |xi = 0
2) ∀|xi ∈ V y ∀α ∈ C ⇒ || α|xi || = |α| || |xi ||
3) || |xi + |yi || ≤ || |xi || + || |yi ||
Si para cada |xi ∈ V es posible calcular la norma correspondiente || |xi || ⇒ V recibe el nombre
de espacio vectorial normado.
Ejercicio 2.4. Demuestre que Cn es un espacio vectorial normado.
Definición 2.5. Normalidad, ortogonalidad y ortonormalidad. Sea V un espacio vectorial ⇒
- Dos elementos |xi, |yi ∈ V se llaman ortogonales si su producto interior es cero.
- Un subconjunto S ⊂ V es un conjunto ortogonal ⇔ ∀ |xi, |yi ∈ S, |xi = 6 |yi ⇒ (|xi, |yi) = 0.
- Un conjunto ortogonal se llama ortonormal si cada uno de sus elementos tiene norma igual a 1.
Observación. El elemento cero 0 ∈ V es ortogonal a todo elemento en V.

1
En textos de matemática pura es común que esta tercera regla se escriba ası́ :
(|ui, α|vi + β|wi) = α∗ (|ui, |vi) + β ∗ (|ui, |wi), donde α∗ y β ∗ son los conjugados de α y β respectivamente.
En computación cuántica se utiliza la definición 2.3.
5
2.2 Subespacios, combinación lineal, generación de espacios, independencia
lineal y bases
Dado el carácter elemental de los temas revisados en esta sección, se invita al lector interesado en
estudiar las demostraciones correspondientes, a consultar las obras [8], [9], [10] y [11].
Notación. En las siguientes lı́neas, el sı́mbolo V denotará a un espacio vectorial sobre un campo
F , i.e. V = V(F ).
Definición 2.6. Subespacio. Sea W un subconjunto de un espacio vectorial V. W se denomina

subespacio de V si W es un espacio vectorial bajo la suma vectorial y multiplicación escalar definidas
sobre V.
Teorema 1. Sea W un conjunto formado por uno o más vectores de un espacio vectorial V. W es un
subespacio de V ⇔ se cumplen las siguientes condiciones:
a) Si |ui, |vi ∈ W ⇒ |ui + |vi ∈ W

b) Si k ∈ F y |ui ∈ W ⇒ k|ui ∈ W
Ejercicio 2.5. Sean el espacio vectorial Mn (C) y S ={ A ∈ Mn (C)|A = At , i.e. A es igual a su transpuesta}.
Demuestre que S, el conjunto de las matrices simétricas, es un subespacio de Mn (C).
Definición 2.7. Combinación lineal. Sean V un espacio vectorial, S = {|vi i ∈ V, i ∈ {1, 2, . . . , n}}
un subconjunto de V y E = {ci , i ∈ {1, 2, . . . , n}} un subconjunto del campo F . Entonces, todo |xi
que se exprese en la forma
Xn
|xi = ci |vi i
i=1
se denominará combinación lineal de elementos de S.
Teorema 2. Sea V un espacio vectorial. Definimos a los conjuntos S = {|vii ∈ V|i ∈ {1, 2, . . . , n}} y
T = {|xi ∈ V | |xi = ni=1 ci |vi i, ci ∈ F, i ∈ {1, 2, . . . , n}}. Entonces, T es un subespacio de V.
P
Definición 2.8. Generación de espacios. Sean P V un espacio vectorial y los conjuntos S = {|vi i ∈
V|i ∈ {1, 2, . . . , n}} y T = {|xi ∈ V | |xi = ni=1 ci |vi i, ci ∈ F, i ∈ {1, 2, . . . , n}}. Entonces, T es
el conjunto generado por S.
Nota: Se acostumbra escribir a T de la siguiente forma: T = gen{|v1 i, |v2i, . . . , |vn i}.
Ejercicio 2.6. Los vectores ı̂ = (1, 0, 0)t, ̂ = (0, 1, 0)t y k̂ = (0, 0, 1)t , generan a R3 y a C3 .
Definición 2.9. Generación de un espacio vectorial. Sean V un espacio vectorial y S = {|vii ∈

V|i ∈ {1, 2, . . . , n}}. Se dice que S genera a V si y sólo si ∀ |xi ∈ V ⇒ |xi ∈ gen{S}.
6
Ejercicio 2.7. Espacios generadores.
1) S = {1, x1 , x2 , . . . , xn } genera a Pn (x).

1 0 0 1 0 0 0 0
2) , , , genera a M2 (F ).
0 0 0 0 1 0 0 1
3) Encuentre un conjunto generador para Mn (F ).
Definición 2.10. Independencia y dependencia lineal. Sean V un espacio vectorial, S un conjunto

definido por S = {|vii ∈ V|i ∈ {1, 2, . . . , n}} y c1 , c2 , . . . , cn ∈ F . La ecuación vectorial
n
X
ki |vi i = k1 |v1 i + k2 |v2 i + . . . + kn |vn i = 0 (1)
i=1
tiene por lo menos una solución, a saber:
k1 = k2 = . . . = kn = 0 (2)
Si la ecuación (2) es la única solución de la ecuación (1) ⇒ S es un conjunto linealmente indepen-

diente.
Si, además de la ecuación (1), existen otras soluciones para la ecuación (2) ⇒ S es un conjunto
linealmente dependiente.
Ejercicio 2.8. Demuestre que los vectores ı̂ = (1, 0, 0)t, ̂ = (0, 1, 0)t y k̂ = (0, 0, 1)t son linealmente
independientes.
Definición 2.11. Base. Sean V un espacio vectorial y S = {|vi i ∈ V, i ∈ {1, 2, . . . , n}}. El conjunto
S forma una base de V ⇔
a) {|v1 i, |v2 i, . . . , |vn i} es un conjunto linealmente independiente, y

b) {|v1 i, |v2 i, . . . , |vn i} genera a V.
Ejercicio 2.9. Bases vectoriales.
1) {ı̂,̂, k̂} es una base de R3 .
2) Sean Rn con campo R y B = {|e1 i, . . . , |en i | |ei i = (0, . . . , 0, 1, 0, ..., 0), con 1 en la i-ésima
entrada y 0 en las restantes, ∀i ∈ {1, 2, . . . , n}} Entonces, B es una base de Rn . La misma base
puede ser utilizada en Cn .
Teorema 3. Todo conjunto de n vectores en Rn linealmente independientes es una base de Rn .
Pn4. Sea {|v1 i, . . . , |vn i} una base de V y |vi ∈ V ⇒ ∃! conjunto {c1 , . . . , cn } ⊂ F tal que
Teorema
|vi = i=1 ci |vi i
Teorema 5. Si {|u1i, |u2i, . . . , |un i} y {|v1 i, |v2 i, . . . , |vm i} son bases de V ⇒ m = n, i.e. cua-
lesquiera dos bases en un espacio vectorial V poseen el mismo número de vectores.
7
Teorema 6. Sea B1 = {|u1i, . . . , |un i} una base de V. Supongamos además la existencia de n vec-
tores |x1 i, . . . , |xn i ∈ V expresados en la base B1 :
|x1 iB1 = (a11 , . . . , an1 )t , |x2 iB1 = (a12 , . . . , an2 )t , . . . , |xn iB1 = (a1n , . . . , ann )t
A partir de estos vectores |xi iB1 construyamos una matriz A:
 
a11 a12 . . . a1n
 a21 a2n . . . a2n 
A =  ..
 
.. .. .. 
 . . . . 
an1 an2 . . . ann
Entonces, |x1 i, |x2 i, . . . , |xn i son linealmente independientes ⇔ det(A) 6= 0.

Observación. Deseamos subrayar que la existencia de los elementos de un espacio vectorial
|xi ∈ V es independiente de cualquier base que uno escoja para representar al vector |xi. Lo único
que de |xi depende respecto de la base B que uno escogiese son las componentes del vector, y no el
vector en sı́ mismo ( o el número de componentes que deba tener en cualquier representación).
Definición 2.12. Dimensión de un espacio vectorial. Sea V un espacio vectorial y B una base de V
⇒ dimV = #(B), i.e. la dimensión de V es la cardinalidad de B.
2.3 Espacios de Hilbert

Definición 2.13. Estructura algebraica, homomorfismo e isomorfismo.
- Estructura algebraica. Conjunto cerrado sobre una o más operaciones, el cual satisface ciertos
axiomas.
- Homomorfismo. Un homomorfismo H : A → B es una función entre dos estructuras algebraicas
del mismo tipo (por ejemplo, dos espacios vectoriales) tal que H conserva/preserva la estructura de
A en B, por ejemplo elementos identidad, elementos inversos y operaciones binarias.
- Isomorfismo. La función f : A → B es un isomorfismo si tanto f como su inversa f −1 son
homomorfismos, i.e. mapeos que conservan la estructura de los conjuntos A y B.
La idea central en esta definición es la siguiente: si es posible contruir un isomorfismo entre dos
conjuntos A, B entonces dichos conjuntos son estructuralmente idénticos.
Definición 2.14. Espacio vectorial completo con producto interno. Sea V un espacio vectorial
con producto interno. V es completo si para cualquier sucesión {|ai i}∞ i=1 ∈ V que cumpla con
limi,j→∞ || |ai i − |aj i || = 0 también se cumple que ∃! |bi ∈ V tal que limj→∞ || |aj i − |bi || = 0.
Definición 2.15. Espacio de Hilbert (versión computación cuántica).
- Un espacio de Hilbert H es cualquier espacio vectorial completo con producto interno.
- Dos espacios de Hilbert H1 , H2 son isomórficos si los espacios vectoriales asociados son isomórficos
a su vez y dicho isomorfismo preserva el producto interno.
- En particular, cuando solamente se trata con espacios vectoriales complejos de dimensión finita,
un espacio de Hilbert se define como un espacio vectorial con producto interno (el requerimiento de
completitud es eliminado). Este es el tipo de espacios de Hilbert con los que generalmente se trabaja
en computación cuántica.
8
Observación. De acuerdo a lo establecido en la Def. (2.15), el espacio de Hilbert con el que
trabajaremos en computación cuántica es Cn (C), donde n es generalmente un múltiplo de 2.
Definición 2.16. Funcional. Sea V(F) un espacio vectorial. Un funcional lineal (también llamado
simplemente funcional) es una función lineal f : V → F.
Lema 1. Sea H un espacio de Hilbert. Definimos, para cada |ai ∈ H, la función f|ai : H → C con la
operación f|ai (|bi) = (|ai, |bi). Entonces, la función f|ai es una función lineal y, en consecuencia, es
un funcional.
Demostración. La definición del producto interno hace de f|ai una función. Sean ahora |bi, |ci ∈
Hyα∈C⇒
f|ai (|bi + |ci) = (|ai, |bi + |ci) = (|ai, |bi) + (|ai, |ci) = f|ai (|bi) + f|ai (|ci). Además,
f|ai (α|bi) = (|ai, α|bi) = α(|ai, |bi) = αf|ai (|bi), ambas deducciones de acuerdo a Def. (2.3).
Q.E.D.
Es posible demostrar que el conjunto de todos los funcionales de un espacio de Hilbert H forma,
a su vez, otro espacio de Hilbert, llamado espacio dual de Hilbert H∗ sobre C [8]. Más aún, es
también posible demostrar que existe una biyección entre H y H∗ ([8]) y, en consecuencia, H y H∗
son isomórficos. Este isomorfismo es la base de la muy famosa notación de Dirac.
Definición 2.17. Notación de Dirac. Sea H un espacio de Hilbert ⇒

- Un vector ψ~ ∈ H se denota con el sı́mbolo |ψi y recibe el nombre de ket.
- El funcional correspondiente f|ψi recibe el nombre de bra y se denota con el sı́mbolo hψ|.
- h·| puede ser visto como una función (operador) que mapea un estado arbitrario |ψi en el funcional
hψ| tal que f|ψi (|φi) = (|ψi, |φi) = hψ|φi.
- Luego, la notación h·|·i será utilizada, en el resto de este documento, para referirse al producto
interno de dos vectores en un espacio de Hilbert. Más aún, dicha notación es un standard en la
formulación y escritura de la mecánica cuántica.
- Por último, definimos |ψi† ≡ hψ|. El sı́mbolo † es ampliamente utilizado en computación cuántica
y su definición formal será estudiada en las siguientes páginas.
Definición 2.18. Representación de kets y bras en vectores columna y renglón. Sea H un espacio
de Hilbert, dimH = n y B una base de H ⇒
- Cualquier |ψi ∈ H se puede representar, usando la base B, como un vector columna con n compo-
nentes, i.e. |ψi = (ψ1 , ψ2 , . . . , ψn )t , donde ψi ∈ C, i ∈ {1, 2, . . . , n}.
-Más aún, el bra hψ| ∈ H∗ se puede representar como un vector renglón también de n componentes,
i.e. hψ| = (ψ1∗ , ψ2∗ , . . . , ψn∗ ), donde los ψ ∗ son los conjugados de ψi , i ∈ {1, 2, . . . , n}
- En consecuencia, si deseamos calcular el producto interno hψ|φi, donde |ψi, |φi ∈ H, y para ello
queremos usar las representaciones hψ| = (ψ1∗ , ψ2∗ , . . . , ψn∗ ) y |φi = (φ1 , φ2 , . . . , φn )t obtenidas me-
diante el uso de una base B de H ⇒
Xn
hψ|φi = (ψ1∗ φ1 + ψ2∗ φ2 + ...+ ψn∗ φn )1/2 =( ψi∗ φi )1/2
i=1
9
2.4 Operadores lineales
Uno de los objetivos del Análisis Matemático es estudiar ampliamente funciones cuyos dominios
y contradominios son subconjuntos de espacios vectoriales. Estas funciones reciben el nombre de
transformaciones u operadores. En particular, los resultados de la teorı́a de operadores lineales son de
mucho interés en la fı́sica cuántica y, por lo tanto, son un tema de estudio en la computación cuántica.
Definición 2.19. Operador lineal. Sean V y W espacios vectoriales. Un operador lineal
T̂ : V → W
es una función que asigna a cada vector |ψi ∈ V un único vector T̂ |ψi ∈ W tal que ∀ |ψi, |φi ∈ V y
∀ α ∈ F (el campo usado en la definición de V y W), se cumple que:
T̂ (|ψi + |φi) = T̂ |ψi + T̂ |φi
T̂ (α|ψi) = αT̂ |ui
Para cada |ψi ∈ V, T̂ |ψi se llama imagen de |ψi. La imagen del dominio V, T̂ (V), es el recorrido
de T̂ .
Ejercicio 2.10. Ejemplos de operadores lineales.
1) Sea T̂ : R2 → R3 definida por T̂ (x, y) = (x + y, x − y, 3y). Demuestre que T̂ es un operador
lineal.
2) Sea A ∈ Mm×n (R). Definamos a T̂ : Rn → Rm por T̂ |ψi = A|ψi. Demuestre que T̂ es un
operador lineal.
Observación 1. Si T̂ : V → V es un operador lineal y V es un espacio vectorial complejo de
dimensión n ⇒ T̂ tiene un conjunto infinito de representaciones matriciales, i.e. la acción de T̂ sobre
los elementos |ψi ∈ V se puede llevar a cabo de la siguiente manera: escoja una representación de
|ψi en una base dada, para después crear una matriz de orden n que permita calcular T |ψi en la base
vectorial correspondiente.
Este resultado no se extiende a espacios vectoriales infinito-dimensionales (por ejemplo, en estos
casos se requerirán representaciones de operadores integrales o diferenciales).
Observación 2. Sea T̂ : V → W un operador lineal. Deseamos subrayar que la acción de T̂ sobre
V y W es independiente de las bases que uno escoja para representar a los elementos de V y W. Un
operador lineal puede ser pensado como un procedimiento para transformar una entidad geométrica
en otra.
Teorema 7. El conjunto T̂ (V), el recorrido del T̂ , es un subespacio de W.
Demostración
Sean |ψi, |φi ∈ V tales que T̂ |ψi, T̂ |φi ∈ T̂ (V) ⊂ W. Como W es un espacio vectorial ⇒ T̂ |ψi +
T̂ |φi ∈ W. Dado que T̂ es un operador lineal ⇒ T̂ |ψi + T̂ |φi = T̂ (|ψi + |φi), i.e. T̂ (|ψi + |φi) =
T̂ |ψi + T̂ |φi es la imagen de |ψi + |φi. Por lo tanto, T̂ |ψi + T̂ |φi ∈ T̂ (V).
Ahora, sean |ψi ∈ V, α un escalar y T̂ |ψi ∈ T̂ (V) ⊂ W. Como W es un espacio vectorial
entonces αT̂ |ψi ∈ W y, dado que T̂ es un operador lineal, αT̂ |ψi = T̂ (α|ψi), esto es, existe un
elemento T̂ (α|ψi) ∈ W que es, por definición, la imagen de α|ψi, i.e. T̂ (α|ψi) ∈ T̂ (V).
Luego, de acuerdo al teorema (1), T̂ (V) es un subespacio de V.
Q.E.D.
10
Teorema 8. Sean V y W espacios vectoriales definidos sobre R y T̂ : V → W un operador lineal.
Entonces, ∀ |ψi, |φi, |ψii ∈ V y ∀ αi ∈ R se encuentra que:
1) T̂ (0V ) = 0W
2) T̂ (|ψi − |φi) = T̂ |ψi − T̂ |φi

X n X n
3) T̂ αi |ψi i = αi T̂ |ψi i
i=1 i=1
Demostración
1) Sea T̂ (0V ) = T̂ (0V + 0V ) = T̂ (0V ) + T̂ (0V ), de acuerdo a la Def. (2.19). Tenemos entonces
que T̂ (0V ) = T̂ (0V ) + T̂ (0V ), siendo T̂ (0V ) un elemento de W.
Esta suma nos obliga a concluir que T̂ (0V ) = 0W , pues 0W es el único elemento de W que, al ser
sumado al elemento T̂ (0V ), puede producir como resultado el mismo elemento T̂ (0V ).
2) Sean |ψi, |φi ∈ V. Sabemos que (−1)×|φi = −|φi ∈ V, ası́ que T̂ (|ψi−|φi) = T̂ |ψi+ T̂ (−|φi),
de acuerdo a la Def. (2.19).
Más aún, usando otra vez la Def. (2.19), encontramos que T̂ (−|φi) = T̂ ((−1) × |φi) = (−1)T̂ |φi =
−T̂ |φi. Luego, T̂ (|ψi − |φi) = T̂ |ψi − T̂ |φi.
3) La demostración se hace por inducción sobre el número de vectores y se deja al lector como ejer-
cicio (consejo: use la Def. (2.19) para formular el caso base).
Q.E.D.
Definición 2.20. Núcleo de un operador lineal. Sea T̂ : V → W un operador lineal. Definimos al

núcleo de T̂ , designado por N(T̂ ), de la siguiente manera:
N(T̂ ) = {|ψi ∈ V | T̂ |ψi = 0}
Teorema 9. Sea Sea T̂ : V → W un operador lineal ⇒ el núcleo de T̂ es un subespacio de V.
Demostración
1) Sean |ψi, |φi ∈ N(T̂ ) ⇒ T̂ |ψi = 0 y T̂ |φi = 0. Por una parte, tenemos que T̂ |ψi + T̂ |φi =
0+ 0 = 0. Además, dado que T̂ es un operador lineal, encontramos que T̂ |ψi + T̂ |φi = T̂ (|ψi + |φi),
lo que nos lleva a concluir que T̂ (|ψi + |φi) = 0, i.e. (|ψi + |φi) ∈ N(T̂ ).
2) Sean |ψi ∈ N(T̂ ) y α un escala ⇒ T̂ |ψi = 0 ⇒ αT̂ = α0 = 0. Dado que T̂ es lineal en-
tonces αT̂ |ψi = T̂ (α|ψi). En consecuencia, T̂ (α|ψi) = 0, i.e. α|ψi ∈ N(T̂ ).
Luego, de acuerdo al teorema (1), N(T̂ ) es un subespacio de V.
Q.E.D.
11
2.4.1 Acción de un operador lineal sobre una base
Sea T̂ : V → W un operador lineal, con V y W espacios vectoriales y B = {|e1 i, |e2 i, . . . , |en i} una
base de V. Por definición, para cada |ψi ∈ V ∃! |wi ∈ W tal que T̂ |ψi = |wi. En particular, vemos
que para cada |ei i ∈ B existe un único |uii ∈ W tal que T |ei i = |uii.
P bien, sea |xi un elemento arbitrario de V ⇒ podemos expresar a |xi como la sumatoria
Ahora
|xi = ni=1 αi |ei i (recuerde que el conjunto de escalares {αa , α2 , . . . , αn } es único).
Luego, si conocemos losP elementos |uii P ∈ W tales que T̂P|ei i = |ui i y usamos el Teorema (8),
encontramos que T̂ |xi = T̂ ( ni=1 αi |ei i) = ni=1 αi T̂ |ei i = ni=1 αi |ui i.
En otras palabras, si suponemos la existencia de un operador lineal T̂ : V → W, una base

B = {|e1 i, . . . , |en i} de V y el conjunto C = {T̂ |e1 i, . . . , T̂ |en i}, i.e. la acción de T̂ sobre B ⇒
siempre se puede calcular la acción de T̂ sobre un vector
P arbitrario |vi ∈ V para el cual conocemos
sus componentes respecto de la base B, i.e. |vi = ni=1 αi |ei i. Este razonamiento es un método
eficaz para calcular el efecto de un operador lineal sobre cualquier elemento de su dominio.
Veremos ahora un teorema que vincula la acción de un operador lineal inyectivo sobre las bases
de su dominio y contradominio. La demostración de este teorema es directa y se deja como ejercicio
al lector (en caso de necesitar guı́a, se recomienda consultar [9]).
Teorema 10. Sea T̂ : V → W un operador lineal con dimV = n entonces las siguientes proposiciones
son equivalentes:
1) T̂ es invertible y su inversa T̂ −1 : T̂ (V) → V es también un operador lineal.
2) si |e1 i, |e2 i, . . . , |en i ∈ V son vectores linealmente independientes ⇒ T̂ |e1 i, T̂ |e2 i, . . . , T̂ |en i ∈
T̂ (V) son también vectores linealmente independientes.
3) dimT̂ (V) = n
4) Si |e1 i, |e2i, . . . , |en i es una base de V ⇒ T̂ |e1 i, T̂ |e2 i, . . . , T̂ |en i es una base de T̂ (V).
2.4.2 Representaciones matriciales de operadores lineales

Mencionamos en el comienzo de este capı́tulo que un operador lineal cuyo dominio es un espacio
vectorial complejo n-dimensional tiene un conjunto infinito de representaciones matriciales. En esta
sección formalizaremos dicha noción.
Sea el operador lineal T̂ : V → W con dimV = n y dimW = m. De acuerdo a lo estudiado en
la sección anterior, el efecto de un operador lineal sobre su dominio está determinado por su acción
sobre una base {|ei i} de V. Puesto que los vectores T̂ |ei i ∈ W entonces podemos tomar una base
{|wi i} de W y construir n ecuaciones de la forma
m
X m
X m
X
T̂ |e1 i = αk1 |wk i; T̂ |e2 i = αk2 |wk i; . . . ; T̂ |en i = αkn |wk i
k=1 k=1 k=1
12
O, en su forma más general,
m
X
T̂ |ei i = αki |wk i
k=1
Escribamos ahora una matriz cuyas columnas sean los coeficientes de los vectores T̂ |ei i en
términos de la base {|wii}, i.e.
 
α11 α12 . . . α1n
 21 α22
α . . . α2n 
T̂ |e1 i{|wi i} T̂ |e2 i{|wi i} . . . T̂ |en i{|wii} = 

.. 
 . 
αm1 αm2 . . . αmn
Los coeficientes αij dependen de la base {|wii} que escojamos para W. Puesto que para un
espacio vectorial de dimensión m existe un conjunto infinito de distintas bases, entonces hay un
conjunto infinito de representaciones matriciales distintas para un mismo operador lineal T̂ .
Formalicemos ahora cómo una representación matricial de un operador lineal T̂ actúa sobre los
elementos del dominio de dicho operador.
Teorema 11. Sea T̂ : V → W un operador lineal con dimV = n y dimW = m. Además, suponga
la existencia de {|eii} y {|wii}, bases de V y W respectivamente, a partir de las cuales se calcula la
matriz T = (αij ) cuyos elementos están determinados por las ecuaciones
m
X
T̂ |ei i = αki |wk i (3)
k=1
Tomemos ahora un elemento cualquiera
n
X
|ψi = βp |ep i (4)
p=1
y apliquemos el operador
n
X m
X
T̂ |ψi = βp T̂ |ep i = γq |wq i (5)
p=1 q=1
Pm
Entonces los coeficientes γi tienen la forma γi = k=1 βk αik .
Demostración.
Combinando las Ecs. (5 y 3) encontramos que
T̂ |ψi = np=1 βp T̂ |ep i = β1 T̂ |e1 i + β2 T̂ |e2 i + . . . + βn T̂ |en i =

P
β1 k=1 αk1 |wk i + β2 m

Pm P Pm
k=1 αk2 |wk i + . . . + βn k=1 αkn |wk i =
β1 (α11 |w1 i + α21 |w2i + . . . + αm1 |wm i)+
β2 (α12 |w1 i + α22 |w2i + . . . + αm2 |wm i) + . . . +
βn (α1n |w1 i + α2n |w2 i + . . . + αmn |wm i).
13
Agrupando los sumandos en términos de los coeficientes de |wii, observamos lo siguiente
T̂ |ψi = np=1 βp T̂ |ep i

P
(β1 α11 + β2 α12 + . . . + βn α1n )|w1i+

(β1 α21 + β2 α22 + . . . + βn α2n )|w2i + . . . +
(β
P1nαm1 + β2 αm2 + P . . . + βn αmn )|wm i =
n Pn
k=1 βk α1k |w 1 i + k=1 βk α2k |w 2 i + . . . + k=1 βk αmk |wm i
Esto es,
T̂ |ψi = np=1 βp T̂ |ep i = m

P P
Pn Pn q=1 γq |wq i = Pn
k=1 βk α1k |w1 i + k=1 βk α2k |w2 i + . . . + k=1 βk αmk |wm i.
Pn
Del desarrollo anterior se observa que γi , el coeficiente de |wii, es igual a k=1 βk αik , con lo que
queda demostrado el teorema.
Q.E.D.
Dado que hay muchas representaciones matriciales para un operador lineal, es de interés del
investigador encontrar y caracterizar representaciones simples, esto es, matrices cuya manipulación
sea fácil de realizar.
Entre las representaciones matriciales que se usan comúnmente en computación cuántica, encon-
tramos las matrices diagonales. El siguiente teorema demuestra la existencia de este tipo de matrices,
y su demostración puede encontrarse en [9].
Teorema 12. Sean V y W espacios vectoriales de dimensión finita, con dimV = n y dimW = m.
Supongamos que T̂ : V → W y que r = dimT̂ (V) representa el rango de T̂ . Existe entonces una
base {|e1 i, |e2 i, . . . , |en i} de V y otra base {|w1 i, |w2i, . . . , |wn i} de W tales que
T̂ (|ei i) = |wi i, i ∈ {1, . . . , r}

T̂ (|ei i) = 0, i ∈ {r + 1, . . . , n}
Además, la matriz (αij ) relativa a estas bases tiene todos sus elementos iguales a cero excepto los
r elementos de la diagonal, cuyo valor es t11 = t22 = . . . = trr = 0.
14
2.4.3 Operadores lineales usando notación de Dirac
Definición 2.21. Producto externo: representación de un operador lineal en notación de Dirac.
Sean |ψi, |ai ∈ H1 y |φi ∈ H2 . Definimos entonces al producto externo (también conocido como
producto exterior) |φihψ| como el operador lineal con dominio H1 y contradominio H2 , el cual opera
de la siguiente manera:
(|φihψ|)(|ai) ≡ |φihψ|ai ≡ hψ|ai|φi
donde hψ|ai es el producto interno de |ψi y |ai.
Ejemplos de operadores en notación de Dirac y en representación matricial.
Comenzamos por definir los operadores de Pauli usando notación de Dirac:
σ̂x = |0ih1| + |1ih0| ; σ̂y = i|0ih1| − i|1ih0| ; σ̂z = |0ih0| − |1ih1| (6)

1 0
Si además definimos |0i = , |1i = , h0| = (1, 0) y h1| = (0, 1).
0 1
entonces podemos calcular representaciones matriciales de los operadores de Pauli:

0 1 0 −i 1 0
σx = ; σy = ; σz = . (7)
1 0 i 0 0 −1
El operador de Hadamard es otro operador lineal ampliamente usado en computación cuántica:
1
Ĥ = √ (|0ih0| = |0ih1| + |1ih0| − |1ih1|) (8)
2

1 1 1
H=√ (9)
2 1 −1
Los operadores de Pauli y Hadamard son ejemplos de dos tipos de operadores utilizados fre-
cuentemente en mecánica cuántica: operadores hermitianos y unitarios.
2.5 Operadores usados en computación cuántica

Suponga que Â : V → V es un operador lineal. Por una parte, sabemos que ∀ |ψi ∈ V ⇒ Â|ψi ∈ V
y que, para cada ket |ψi en V, existe un único bra hψ| en el espacio dual V∗ . Por extensión, si
Â|ψi = |ψ 0 i es un elemento de V entonces el bra hψ 0 | es un elemento de V∗ .
Dados estos elementos, procedemos a definir a Â† , el operador adjunto de Â, como el operador
capaz de generar al bra hψ 0 | a partir del bra hψ|, esto es,
Â|ψ 0 i = |ψ 0 i ⇔ hψ 0 | = hψ|Â†
Ahora bien, suponga que Â es un operador lineal y A una de sus representaciones matriciales.
Entonces, la representación matricial de Â† , basada en la matriz A, es la matriz (A∗ )t , esto es, la
matriz que representa a Â† es la transpuesta de la matriz conjugada de A.
15
Damos en el siguiente teorema algunas propiedades fundamentales de la operación †, cuya de-
mostración puede consultarse en varias fuentes, en particular en [57].
Teorema 13. Sean Â, B̂ operadores con dominio V, |uihv| un operador en notación de Dirac y α ∈ C.
Entonces
1) (Â† )† = Â
2) (αÂ)† = α∗ Â†
3) (Â + B̂)† = Â† + B̂ †
4) (ÂB̂)† = B̂ † Â†
5) (|uihv|)† = |vihu|
Usando el Teorema (13), podemos demostrar fácilmente el siguiente resultado
Teorema 14. Sean Âi : V → V, i ∈ {1, . . . , n} n operadores lineales y αi ∈ C n escalares ⇒
n n
X
†
X †
( αi Âi ) = αi∗ Âi
i=1 i=1
Definimos enseguida dos tipos de operadores muy usados en mecánica cuántica.
2.5.1 Operadores hermitianos

Definición 2.22. Operador hermitiano. Sea H un espacio de Hilbert de dimensión finita y Â : H →
H un operador lineal. Si Â = Â† entonces Â es un operador hermitiano. La definición se extiende
de forma natural a cualquier representación matricial de Â.
Ejercicio 2.11. Demuestre que los operadores de Pauli son hermitianos.
Una clase de operadores hermitianos fundamentales em mecánica cuántica son los proyectores.
Definición 2.23. Proyectores. Sea V un espacio vectorial y W un subespacio de V, con dimV = n
y dimW = m. Usando el procedimiento de Gram-Schmidt (ortonormalización de un conjunto de
vectores, consultar [9–11]), es posible construir una base ortonormal |u1i, |u2i, . . . , |un i para V tal
que |u1 i, |u2i, . . . , |uk i sea, a su vez, una base ortonormal para W. Definimos
k
X
P̂ = |uiihui | (10)
i=1
como el operador de proyección al subespacio W.
Observe que , de acuerdo a los Teoremas (13) y (14),

Xk k
X k
X
† † †
P̂ = ( |uiihui|) = (|uiihui|) = |uiihui| = P̂
i=1 i=1 i=1
Luego, P̂ es hermitiano de acuerdo a la Def. (2.22).
16
Ejemplo 2.1. El conjunto {|0i, |1i} es una base ortonormal de H2 . Luego,
|0ih0| es el operador de proyección al subespacio generado por |0i

|1ih1| es el operador de proyección al subespacio generado por |1i
Definición 2.24. Operador unitario. Sea H un espacio de Hilbert y Û : H → H un operador lineal.

ˆ donde Iˆ es el operador identidad. Como en el caso de los
Û es un operador unitario si Û Û † = I,
operadores hermitianos, la definición de matrices unitarias es una extensión natural de la definición
de un operador unitario.
Los operadores unitarios son muy importantes en mecánica cuántica porque preservan el valor del
ˆ = ha|bi.
producto interno: sean |αi = Û |ai y |βi = Û|bi ⇒ hα|βi = ha|Û † |Û|bi = ha|I|bi
Los operadores hermitianos y unitarios son ejemplos de operadores normales, los cuales se de-
finen a continuación.
Ejercicio 2.12. Demuestre lo siguiente:
1) Los operadores de Pauli (Ec. (6)) y Hadamard (Ec. (8)) son unitarios.
2) Las matrices de Pauli (Ec. (7)) y Hadamard (Ec. (9) )son unitarias.
Definición 2.25. Operador normal. Sea H un espacio de Hilbert y Â : H → H un operador lineal.

Â es normal si y sólo si ÂÂ† = Â† Â.
Los operadores normales tienen una propiedad matemática, la descomposición espectral, que
juega un papel fundamental en la formulación de la mecánica cuántica. Para poder revisar el teorema
de la descomposición espectral, antes es necesario recordar un tema: eigenvectores y eigenvalores.
17
2.6 Eigenvectores y eigenvalores
Definición 2.26. Eigenvectores y eigenvalores. Sea T̂ : V → V un operador lineal. Un escalar λ
recibe el nombre de eigenvalor de T̂ si existe un elemento no nulo |ψi ∈ V tal que
T̂ |ψi = λ|ψi (11)

El elemento |ψi recibe el nombre de eigenvector de T̂ perteneciente a λ. El escalar λ se llama
eigenvalor de T̂ .
Definición 2.27. Eigenespacio. Sea T̂ : V → V un operador lineal con un eigenvalor λ. Definimos
a E(λ) el eigenespacio de λ, de la siguiente manera:
E(λ) = {|ψi ∈ V | T̂ |ψi = λ|ψi}

1) Observe que E(λ) contiene al vector 0 y a todos los eigenvectores pertenecientes a λ.
2) Es fácil demostrar que E(λ) es un subespacio de V, pues si |xi, |yi ∈ V, α, β ∈ C ⇒
T̂ (α|xi + β|yi) = αT̂ |xi + β T̂ |yi = αλ|xi + βλ|yi = a|xi + b|yi, con a, b ∈ C.
2.6.1 Polinomio caracterı́stico

Sea T̂ : V → V un operador lineal. Tomemos la ecuación que define eigenvalores y eigenvectores:
ˆ
T̂ |ψi = λ|ψi ⇒ λ|ψi = T̂ |ψi ⇒ λI|ψi ˆ − T̂ |ψi = 0
= T̂ |ψi ⇒ λI|ψi (12)
Por definición, (f1 + f2 )(x) = f1 (x) + f2 (x), por ello es que
ˆ − T̂ |ψi = 0 ⇒ (λIˆ − T̂ )|ψi = 0

λI|ψi (13)
Puesto que (λIˆ − T̂ ) es un operador, podemos escribir la Ec. (13) de esta manera:
Â|ψi = λ|ψi (14)

Sea ahora A una representación matricial del operador Â. Ası́ las cosas, la Ec. (14) se puede
escribir de la siguiente manera:
A|ψi = λ|ψi, i.e.
(λI − T )|ψi = 0 (15)

donde T es una representación matricial de T̂ e I es la matriz identidad.
Sabemos de estudios elementales de álgebra lineal que la ecuación matricial A|xi = 0 sólo tiene
la solución trivial ⇔ det(A) = 0. Por otra parte, dado que la Def. (2.26) excluye al vector nulo, i.e.
|ψi =
6 0 entonces sólo nos queda concluir que, para que la Ec. (15) se cumpla, forzosamente se debe
cumplir la siguiente ecuación:
det(λI − T ) = 0 (16)
18
Definición 2.28. Sea T̂ : V → V un operador lineal y T una representación lineal de T̂ . Definimos
entonces la ecuación caracterı́stica
c(λ) = det(λI − T ) = 0
Observación. Puesto que det(kA) = k n det(A), donde A ∈ Mn (C) ⇒ c(λ) = det(λI − T ) =

det(T − λI) = 0.
Definición 2.29. Polinomio caracterı́stico. Al desarrollar c(λ) se obtiene un polinomio en λ, de-

nominado polinomio caracterı́stico de A.
Es posible demostrar que, si la matriz T es de orden n ⇒ su polinomio caracterı́stico es de grado

n. Por otra parte, el teorema fundamentalo del álgebra establece que todo polinomio de grado n tiene
exactamente n raı́ces, contando duplicidades. Por lo tanto,
Teorema 15. Sea A ∈ Mn (C). Si se consideran mutiplicidades A tiene exactamente n eigenvalores.
Un teorema más, cuya demostración es directa y se deja como ejercicio para el lector,
Teorema 16. Sea T ∈ Mn (C) y λ un eigenvalor de A. El conjunto E(λ), el eigenespacio de λ, es un

subespacio de Cn .
En resumen, un camino para conocer los eigenvalores de un operador lineal T̂ es calcular una
representación matricial T de dicho operador. Acto seguido, sobre esta matriz T se calcula la función
caracterı́stica c(λ) y, a partir de esto último, el polinomio caracterı́stico correspondiente. Las raı́ces
son los eigenvalores del la matriz T y, por lo tanto, los eigenvalores del operador T̂ .
En el razonamiento anterior pareciera que existe un paso falso. Si un operador T̂ tiene muchas
representaciones matriciales, ¿cómo saber que los eigenvalores de una representación matricial deter-
minada son también los del operador T̂ ?
La respuesta a esta interrogante la dan los siguientes teoremas, cuyas demostraciones se re-
comienda consultar en [9]
Definición 2.30. Dos matrices A, B ∈ Mn (C) se llaman semejantes si existe una matriz no singular
C ∈ Mn (C), i.e. C −1 existe, tal que
B = C −1 AC
Teorema 17. Si dos matrices A, B ∈ Mn (C) representan el mismo operador lineal T̂ ⇒ ∃ una matriz
no singular C ∈ Mn (C) tal que B = C −1 AC. En otras palabras, si A, B representan al mismo
operador lineal si dichas matrices son semejantes.
El recı́proco del Teorema (17) también es cierto.
Teorema 18. Sean A, B, C ∈ Mn (C) dos matrices relacionadas por una ecuación de la forma B =
C −1 AC ⇒ A y B representan el mismo operador lineal.
Los teoremas (17,18) se resumen de la siguiente manera:
Teorema 19. Dos matrices son semejantes si y sólo si representan al mismo operador lineal.
19
El teorema (19), unido a la siguiente propiedad de la función determinante: det(C −1 AC) =
det(C −1 )det(A)det(C), son el fundamento del siguiente teorema, el cual establece que, si cua-
lesquiera dos representaciones matriciales de un operador lineal tienen los mismos autovalores.
Teorema 20. Las matrices semejantes tienen el mismo polinomio caracterı́stico y por tanto los mis-
mos eigenvalores.
Para terminar, enunciamos un teorema que relaciona la diagonalización de una matriz con sus
eigenvalores. Este resultado es fundamental en la estructura matemática de la mecánica cuántica.
Teorema 21. Sea T̂ : V → V un operador lineal, F el campo de definición del espacio vectorial
V y dimV = n. Además, supongamos que el polinomio caracterı́stico de T̂ tiene n raı́ces distintas
λ1 , λ2 , . . . , λn ⇒
a) Existe un conjunto de eigenvalores U = {|u1 i, |u2i, . . . , |un i}, que corresponden a λ1 , λ2 , . . . , λn
y que conforman una base para V.
b) la matriz T relativa a la base U es la matriz diagonal Λ que tiene a los eigenvalores λ1 , λ2 , . . . , λn
como elementos de la diagonal, i.e. T = diag(λ1 , λ2 , . . . , λn ).
c) Si A es la matriz de T̂ relativa a otra base {|e1 i, |e2 i, . . . , |en i} entonces la matriz diagonal Λ se
calcula de acuerdo a la fórmula
Λ = C −1 AC,
donde C es la matriz no singular que relaciona las dos bases {|ui i}, {|ei i} mediante la ecuación
U = EC.
2.7 Descomposición espectral

Teorema 22. Descomposici0́n espectral. Todo operador normal T̂ : V → V es diagonal respecto de
una base ortonormal de V.
P
Luego, una representación diagonal de T̂ tiene la forma T̂ = i λi |iihi|, donde {|ii} es un
conjunto ortonormal de eigenvectores de Â que corresponden a los eigenvalores λi .
2.8 Producto tensorial

Los conceptos matemáticos revisados hasta el momento serán utilizados para el análisis de sistemas
cuánticos individuales. En este apartado presentamos al lector un formalismo matemático usado para
representar sistemas cuánticos multipartitas.
Definición 2.31. Producto tensorial. Sean V(F) y W(F) espacios vectoriales de dimension m y n
respectivamente. Definimos a X como el producto tensorial de V y W, i.e. X = V ⊗ W.
- Los elementos de X son combinaciones lineales de vectores |ai ⊗ |bi, donde |ai ∈ V and |bi ∈ W.
- En particular, si {|ii} y {|ji} son bases ortonormales de V y W entonces {|ii ⊗ |ji} es una base 2
para X.
2
Un ejemplo concreto: sea {|0i, |1i} una base ortonormal de un espacio de Hilbert bidimensional H2 . Entonces, una
base para H4 = H2 ⊗ H2 es {|0i ⊗ |0i, |0i ⊗ |1i, |1i ⊗ |0i, |1i ⊗ |1i}.
20
Sean ahora Â, B̂ operadores lineales en V y W respectivamente ⇒ ∀ |ai1 , |ai2 ∈ V, |bi1 , |bi2 ∈ W,
α ∈ F se cumple que
1) α(|ai1 ⊗ |bi1 ) = (α|ai1 ) ⊗ |bi1 = |ai1 ⊗ (α|bi1 )

2) (|ai1 + |ai2 ) ⊗ |bi1 ) = |ai1 ⊗ |bi1 + |ai2 ⊗ |bi1
3) |ai1 ⊗ (|bi1 + |bi2 ) = |ai1 ⊗ |bi1 + |ai1 ⊗ |bi2
4) Â ⊗ B̂(|ai1 ⊗ |bi1 ) = Â|ai1 ⊗ B̂|bi1 P P
5) Sean |aii ∈ V, |bii ∈ W y αi ∈ F ⇒ Â ⊗ B̂( i αi |aii ⊗ |bii ) = i αi Â|aii ⊗ B̂|bii
El producto tensorial |ai ⊗ |bitambién se puede escribir |abi o |a, bi. Por otra parte, el producto
tensorial de |ai consigo mismo n veces |ai ⊗ |ai ⊗ . . . ⊗ |ai se puede escribir como |ai⊗n .
El producto de Kronecker es una representación matricial del producto tensorial. Sean A =
(aij ), B = (bij ) dos matrices de orden m × n y p × q respectively. Entonces A ⊗ B se calcula de la
siguiente manera:
 
A11 B A12 B . . . A1n B
 A21 B A22 B . . . A2n B 
A ⊗ B =  .. ..  .
 
.. ..
 . . . . 
Am1 B Am2 B . . . Amn B
A ⊗ B es de orden mp × nq.
21
3 Probabilidad elemental para computación cuántica
3.1 Discrete Random variables and distributions
Definición 3.1. Discrete Random Variable. An experiment is a situation with a set of possible
outcomes. Let us suppose we have an experiment with outcome space E.
A random variable (rv) is a real mapping X : E → R that is defined for all possible outcomes in S.
A discrete random variable (drv) takes only a finite or countable infinite number of distinct values,
i.e. X : E → A ⊂ R is a drv iff #(A) ≤ ℵ0 . The expression X = xi is shorthand for X(ei ) = xi , ∀
ei ∈ E, xi ∈ A.
Definición 3.2. Probability distribution for a drv. Let X : E → A be a drv. Since the outcomes of
an experiment are uncertain in general, we associate with each outcome xi ∈ A a probability p(xi ),
where p(xi ) = Pr(XP = xi ). The numbers p(xi ) are called a probability distribution of X iff i)
p(xi ) ≥ 0, and ii) xi ∈A p(xi ) = 1.
value and variance. The expectation value µ of a drv X, also known as

Definición 3.3. ExpectationP
mean, is defined as E[X] = Pi xi p(xi ). More generally, the expectation value of any function g(X)
of X is given by E[f (X)] = i f (xiP)p(xi ). The variance V [X] of a distribution, also written as σ 2 ,
is given by V [X] = E[(X − µ)2 ] = i (xi − µ)2 p(xi ). The square root of the variance is known as
the standard deviation and is denoted by σ.
If X, Y are two drv and a, b ∈ R, the following propositions can be proved ([58])
E[aX + bY ] = aE[X] + bE[Y ] (17)
V [X] = E[X 2 ] − (E[X])2 (18)
If X, Y are independent drvs ⇒ V [aX + bY ] = a2 V [X] + b2 V [Y ] (19)
Definición 3.4. Bernoulli distribution. The Bernoulli distribution, denoted B(θ), is used as a model
for experiments which have only two outcomes: success with probability θ, and failure with proba-
bility 1 − θ. If X is B(θ) then X = 1 if success and X = 0 if failure. It is a well known fact that if
X is B(θ) then µX = θ and σ 2 = θ(1 − θ).
Definición 3.5. Binomial distribution. The binomial distribution, denoted Bin(n, p), describes ex-
periments that consist of a number of independent identical trials with two possible outcomes: success
with probability p and failure with probability q = 1 − p. So, the random variable X =‘number of
successes’ can take any value from {1, 2, . . . , n} and its distribution is described by the binomial dis-
tribution. If X is Bin(n, p) then the probability p(r) of obtaining r successes from n trials is given by
p(r) = nr pr q n−r .
22
4 Postulados de la mecánica cuántica (versión computación cuántica)
La mecánica cuántica es una teorı́a sobre el comportamiento de la masa y la luz, en particular a escala
atómica [57, 59]. La historia de la mecánica cuántica (1900- circa 1930) incluye un conjunto de
resultados experimentales que pusieron en tela de juicio las ideas que sobre la Naturaleza se tuvieron
hasta el principio del siglo XX ([60], [61] and [62]). Gracias al trabajo de W. Heisenberg y E.
Schrödinger, el cual fue continuado por otros cientı́ficos como R. Feynman and M. Born, la mecánica
cuántica es hoy una teorı́a cientı́fica robusta, utilizada diariamente en la labor teórica y experimental.
En mecánica cuántica existen dos formalismos usados para describir un sistema fı́sico: vectores
de estado y operadores de densidad. Ambos formalismos son equivalentes [7] y, en consecuencia, el
uso de uno u otro depende los requerimientos del investigador. En este texto expresaremos los cuatro
postulados de nuestro interés usando el primer formalismo, el que corresponde a vectores de estado.
En esta capı́tulo nos concentraremos en el estudio de los postulados de la mecánica cuántica,
siguiendo la formulación que de los mismos se hace en [7]. Además, revisaremos varios resultados
presentados en las obras [57], [63], [59], [8] y [7]. Entre muchas obras y artı́culos, se recomienda al
lector interesado en profundizar en los temas aquı́ expuestos que consulte [64].
4.1 Espacio de estados

Este primer postulado consiste en la descripción matemática de sistemas fı́sicos aislados, esto es,
aquellos que no están en contacto con ningún otro sistema fı́sico.
Postulado 1. A cada sistema fı́sico aislado asociaremos un espacio de Hilbert H, el cual recibe
el nombre de espacio de estados.
La descripción total y absoluta de las caracterı́sticas que nos interesan del sistema fı́sico en
cuestión se encuentra contenida en su vector de estado, el cual es un vector unitario |ψi ∈ H. La
dimensión del espacio de estados H depende del número de grados de libertad de la propiedad fı́sica
en consideración.
Este primer postulado tiene una implicación muy importante: una combinación lineal de vectores
de estado es también un vector de estado [57]. Este es el principio de superposición y es una car-
acterı́stica fundamental de la descripción cuántica de sistemas fı́sicos. En particular, observe que
cualquier vector de estado |ψi se puede expresar
P como una superposición de vectores de estado
pertenecientes a una base de H, i.e. |ψi = i ci |ei i, ci ∈ C.
4.1.1 El qubit
En la teorı́a de la computación clásica la unidad fundamental de almacenamiento y manipulación
de información es el bit, cuya estructura matemática es bastante simple: basta con definir dos val-
ores tradicionalmente etiquetados como {0, 1} y con relacionar dichas etiquetas con dos resultados
posibles generados a través de una medición clásica. Un ejemplo de este procedimiento es tomar un
transistor TTL como el sistema fı́sico a medir y hacer la siguiente asignación:
- Si la diferencia de potencial entre colector y emisor se encuentra en el conjunto [0, 0.5]V entonces
hemos leı́do un ’0’ lógico.
23
- Si la diferencia de potencial entre colector y emisor se encuentra en el conjunto [4.5, 5]V entonces
hemos leı́do un ’1’ lógico.
Ası́ pues, es evidente que la descripción matemática de un bit clásico es un elemento de un espacio
escalar.
En computación cuántica, la unidad básica de almacenamiento, manipulación y medición de in-
formación es el qubit. Un qubit es un sistema fı́sico cuyo comportamiento se describe a través de las
leyes de la mecánica cuántica y que se puede representar matemáticamente como un vector unitario
en un espacio de Hilbert bidimensional, esto es
|ψi = α|pi + β|qi (20)

donde α, β ∈ C, |α|2 + |β|2 = 1 y {|pi, |qi} es una base cualquiera de H2 . Es común que la base
de elección sea {|0i, |1i}, la llamada base computacional o canónica de H2 .
Como se puede observar de la Ec. (20), un qubit |ψi es una superposición de los estados base |pi
y |qi, la cual se puede preparar en un número infinito de formas sólo con modificar los valores de los
coeficientes α, β ∈ C, siempre sujetos a la restricción de normalización.
La Ec. (20) también se puede escribir de la siguiente manera:
θ θ
|ψi = eiγ (cos |0i + eiϕ sin |1i) (21)
2 2
donde γ, θ, ϕ ∈ R. Puesto que eiγ no tiene efectos experimentales [7], podemos prescindir de este
factor. En consecuencia,
θ θ
|ψi = cos |0i + eiϕ sin |1i (22)
2 2
Los números θ y ϕ definen un punto en la esfera unitaria conocida como la esfera de Bloch (Fig.
(1)).
,0,
z
,ψ,
y
N
x
,1,
Figure 1: Un qubit como elemento de la esfera de Bloch |ψi = cos θ2 |0i + eiφ sin 2θ |1i.
24
4.2 Evolución de un sistema cuántico aislado
En este apartado estudiaremos la de la evolución de un sistema cuántico, esto es, el formalismo
matemático que describe el comportamiento temporal de un sistema fı́sico aislado, de acuerdo a las
leyes de la mecánica cuántica.
Postulado 2 (versión operador unitario).
Sea |Ψi el vector de estado de un sistema cuántico aislado. La evolución de |Ψi se describe me-
diante un operador unitario Û (Def. (2.24)), también conocido como operador de evolución. Luego,
el estado del sistema en el tiempo t2 dado el vector de estado del mismo sistema en el tiempo t1 es:
|Ψ(t2 )i = Û|Ψ(t1 )i. (23)

El postulado 2 sólo describe las caracterı́sticas matemáticas que debe cumplir un operador de
evolución cualquiera. Las propiedades particulares que debe tener Û a fin de reflejar la naturaleza de
la evolución de cierto sistema fı́sico dependen de este mismo sistema.
El postulado 2 también se puede escribir en una forma más tradicional, usando la famosa ecuación
de Schrödinger.
Postulado 2 (versión operador hermitiano). La evolución de un sistema cuántico aislado está

dada por la ecuación de Schrödinger:
d|ψi
i~ = Ĥ|ψi (24)
dt
donde ~ es la constante de Planck y Ĥ es un operador hermitiano (Eq. (2.22)) conocido como el
Hamiltoniano del sistema.
The Hamiltonian of particular physical systems must be determined and calculated for each case.
In general, figuring out the Hamiltonian of a particular physical system is a difficult task.
Nota aclaratoria. Tenga en mente que, a pesar de lo similar de la notación, Ĥ y Ĥ representan dos
cosas distintas: el primero es el hamiltoniano al que se hace referencia en el postulado 2, en tanto que
el último es el operador hadamard.
Veamos el efecto del operador Hadamard (Eq. (8)), usado como operador de evolución, sobre un
qubit.
1 1
Ĥ|0i = √ [|0ih0| + |0ih1| + |1ih0| − |1ih1|]|0i = √ (|0i + |1i)
2 2
1 1
Ĥ|1i = √ [|0ih0| + |0ih1| + |1ih0| − |1ih1|]|1i = √ (|0i − |1i)
2 2
Ejercicio 4.1. Sean los siguientes operadores unitarios:
1
σ̂x = |0ih1|+|1ih0|, σ̂y = i|0ih1|−i|1ih0|, σ̂z = |0ih0|−|1ih1|, y Ĥ = √ (|0ih0|+|0ih1|+|1ih0|−|1ih1|)
2
25
y los qubits con los siguientes estados cuánticos:
1
|ψi1 = |0i, |ψi2 = |1i, y |ψi3 = √ (|0i + |1i)
2
Aplique dos veces cada operador unitario a cada qubit.
4.3 Medición de un sistema cuántico

En la teorı́a de la mecánica cuántica, la medición de propiedades de sistemas fı́sicos es un proceso
alejado de la intuición debido a las siguientes razones:
1. La medición en mecánica cuántica es intrı́nsicamente probabilı́stica. Esto significa que, sin impor-
tar el detalle y control que tengamos sobre un experimento, la generación de los resultados obtenidos
en la medición de una propiedad fı́sica obedece una función de distribución (o función de densidad,
según sea el caso).
2. Además, al momento de llevar a cabo una medición, el estado del sistema fı́sico en cuestión se al-
tera, de forma inevitable, debido a la interacción que dicho sistema tiene con el aparato de medición.
Esto significa que, en general, el estado cuántico que describe al sistema antes de la medición es
distinto del estado que describe a este mismo sistema después de ser medido.
Las siguientes lı́neas contienen la versión del postulado de medición más frecuentemente usada
en computación cuántica.
Postulado 3. Medición proyectiva. Una medición proyectiva es descrita por un observable M̂ , el
cual es un operador hermitiano definido en el espacio de estados que se desea observar. El observable
M̂ se puede escribir, gracias al teorema de la descomposición espectral, de la siguiente manera:
X
M̂ = ri P̂ri
i
donde P̂ri es el proyector al eigenespacio E(ri ) definido por el eigenvalor ri . Los resultados posi-
bles de la medición corresponden a los eigenvalores ri del observable.
Este postulado provee de medios para cuantificar la función de distribución que determina las
frecuencias relativas correspondientes a las funciones de distribución de resultados.
Sea |ψi el vector de estado de un sistema cuántico inmediatamente antes de la medición. En-
tonces, la probabilidad de obtener el resultado ri se calcula usando la siguiente expresión:
p(ri ) = hψ|P̂ri |ψi (25)

Y el estado de post-medición asociado al resultado ri es:
P̂r |ψi
|ψipm = p i (26)
p(ri )
26
Veamos un ejemplo. Suponga que tiene en su poder un fotón polarizado con orientaciones de
polarización vertical y horizontal. Simbolizamos a la polarización horizontal con el vector |0i y a la
polarización vertical con |1i. Luego, la polarización inicial de nuestro fotón se puede describir con la
expresión
|ψi = α|0i + β|1i
donde α, β ∈ C, |α|2 + |β|2 = 1 y {|0i, |1i} conforman la base computacional de H2 .
Ahora construyamos dos operadores de proyección P̂a0 = |0ih0| y P̂a1 = |1ih1|, los cuales
corresponden a los resultados a0 , a1 . Entonces, el observable utilizado en este experimento es
M̂ = a0 |0ih0| + a1 |1ih1|
Con esta información y de acuerdo al postulado 3, podemos decir lo siguiente:
1) Hay sólo dos resultados posibles en la medición de la polarización de nuestro fotón: a0 y a1 .
2) La probabilidad de obtener el resultado a0 es, de acuerdo a la Ec. (25):

p(a0 ) = hψ|P̂a0 |ψi = (h1|β ∗ + h0|α∗ )P̂a0 (α|0i + β|1i) = |α|2
3) Si la medición efectivamente arrojase el resultado a0 ⇒ el estado de postmedición serı́a, de
acuerdo a la Ec. (26)s:
P̂a |ψi |0ih0|(α|0i + β|1i)
p0 = p = |0i
p(a0 ) |α|2
4) De forma análoga, la probabilidad de obtener el resultado a1 es, de acuerdo a la Ec. (25):
p(a1 ) = hψ|P̂a1 |ψi = (h1|β ∗ + h0|α∗ )P̂a1 (α|0i + β|1i) = |β|2
5) Si la medición efectivamente arrojase el resultado a1 ⇒ el estado de postmedición serı́a dado
por la Ec. (26), esto es:
P̂ |ψi |1ih1|(α|0i + β|1i)
pa1 = p = |1i
p(a1 ) |β|2
Ejercicio 4.2. Sea
(|0i + |1i)
|ψi = √ ∈ H2
2
Definimos además dos bases de H2 :
B1 = {|0i, |1i}
y
1 1
B2 = |+i = √ (|0i + |1i), |−i = √ (|0i − |1i)
2 2
Ahora, definimos los siguientes proyectores:
P̂0 = |0ih0|, P̂1 = |1ih1|

P̂+ = |+ih+|, P̂− = |−ih−|
Calcule probabilidades y estados de postmedición de |ψi usando P̂0 , P̂1 y P̂+ , P̂−
27
4.4 Sistemas cuánticos multipartitas
We now focus on the mathematical description of a composite quantum system, i.e. a system made
up of several different physical systems.
Postulate 4. The state space of a composite quantum system is the tensor product of the component
system state spaces.
- If we have n quantum systems expressed as state vectors, labeled |ψi1, |ψi2 , . . . , |ψin then the joint
state of the total system is given by |ψiT = |ψi1 ⊗ |ψi2 ⊗ . . . ⊗ |ψin .
- Similarly, if we have n quantum systems expressed as density operators ρ1 , ρ2 , . . . , ρn then the joint
state of the total system is given by ρT = ρ1 ⊗ ρ2 ⊗ . . . ⊗ ρn (in the absence of any knowledge of
correlations).
As an advance of the operations we shall perform on the following chapters let us show the details
of applying an evolution operator to a composite quantum system. Let Ĥ ⊗2 be the tensor product of
the Hadamard operator (Eq. (8)) with itself and let |ψi = |00i. Then
1
Ĥ ⊗2 |ψi = (|00ih00| + |01ih00| + |10ih00| + |11ih00| + |00ih01| − |01ih01| + |10ih01| − |11ih01|
2
+ |00ih10| + |01ih10| − |10ih10| − |11ih10| + |00ih11| − |01ih11| − |10ih11| + |11ih11|)|00i
1
= (|00i + |01i + |10i + |11i) (27)
2
28
5 Theory of Computation
The purpose of this chapter is to present a concise introduction to the Theory of Computation, in
order to provide the necessary background and to motivate our further discussion on the importance
of classical random walks and quantum walks in computer science.
We begin by providing an overview of the theory of computation and deliver a succint historical
background of those ideas that led to its creation and development. We then formulate the essential
concepts of a basic and yet powerful model of computation: Finite Automata. We use these concepts
to introduce a formal definition of a model of computation that has played a most important role in
the development of Computer Science: Turing Machines. We extend our discussion by introducing
a third model of computation: Quantum Turing Machines. The previous concepts are followed by
key definitions and theorems from Complexity Theory and the definitions of P, NP and NP-complete
problem categories. This chapter is based on [65], [66], [67], [68] and [70].
5.1 What is the Theory of Computation?

The Theory of Computation is a scientific field devoted to understanding the fundamental capabilities
and limitations of computers, and it is divided into three areas:
1. Automata Theory. The study of different models of computation.
2. Computability Theory. This focuses on determining which problems can be solved by computers
and which cannot.
3. Complexity Theory. The objective in this area is to understand what makes some problems compu-
tationally hard and other easy.
The development of the theory of computation was driven in great part by several challenges
posed by D. Hilbert and other mathematicians on the foundations of mathematics at the beginning of
the 20th Century. A. Turing and other scientists, while working on the ideas required to formalize the
idea of computation, answered some of the questions posed by Hilbert et al.
5.2 Hilbert’s program and the Entscheidungsproblem

At the beginning of the 20th century D. Hilbert and other mathematicians were aware that the methods
of reasoning in mathematics could in some cases lead to contradictions. Hilbert believed that the
proper way to develop any scientific subject rigorously required an axiomatic approach. In providing
an axiomatic treatment, the theory would be developed independently of any need for intuition.
Hilbert’s first step towards a rigorous formulation of mathematics was undertaken in his lecture
at the International Congress of Mathematicians (Paris, 1900) [71], where he stated that “it shall be
possible to establish the correctness of the solution by means of a finite number of steps based upon
a finite number of hypotheses which are implied in the statement of the problem and which must
always be formulated . . . This conviction of solvability of every mathematical problem is a powerful
incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution.
You can find it by pure reason, for in mathematics there is no ignorabimus3”.
3
Short for ignoramus et ignorabimus: we do not know and will not know.
29
The second step towards a rigorous formulation of mathematics was taken in 1920-1921, when
Hilbert’s program was proposed [72]. Hilbert thought that, in order to formulate mathematics on
a solid and complete logical foundation, it would suffice to prove that “all of mathematics follows
from a correctly-chosen finite system of axioms, as well as that some such axiom system is provably
consistent.” Finally, Hilbert and Ackerman posed a challenge known as the Entscheidungsproblem
(Decision Problem) [73]. The Decision Problem is formulated in terms of first-order logic4 and can
be stated as follows
Definition 5.1. Entscheidungsproblem. Does there exist a procedure which can be followed for a
finite number of steps in order to determine the validity of a given first-order statement?
The idea of ‘finite procedure’ was deeply rooted in Hilbert’s proposals. A contemporary computer
scientist would immediately think of an ‘algorithm’ as an equivalent definition of ‘finite procedure’.
However, in Hilbert’s time the concept of algorithm did not exist yet.
Alan Turing published a most influential paper in 1936 [69] in which he pionereed the theory of
computation, introducing the famous abstract computing machines now known as Turing Machines.
In [69], Turing explained the fundamental principle of the modern computer, the idea of controlling
the machine’s operation by means of a program of coded instructions stored in the computer’s mem-
ory, i.e. Turing showed that it was possible to build a “Universal Turing Machine”, that is, a Turing
machine capable of simulating any other Turing machine (the Universal Turing Machine being the
actual digital computer and the simulated Turing machine the program that has been encoded in the
digital computer’s memory). In addition, Turing proved that not all precisely stated mathematical
problems can be solved by computing machines, in particular the Entscheidungsproblem.
In the following section we deliver a brief summary of ideas and main results from [69].
5.3 On Computability
When Turing wrote [69], a computer was not a machine at all, but a human being. A computer
was a mathematical assistant who calculated by rote, in accordance with a systematic method. The
method was supplied by an overseer prior to the calculation. It is in that sense that Turing uses the
word ‘computer’ in [69] and a Turing machine is an idealized version of this human computer. What
Turing did in [69] was to propose a mathematical formalism for the idealization of a human computer
as well as to study the calculation capabilites and limitations of that mathematical model.
Turing meant by a systematic method (sometimes called an effective method and a mechanical
method) any mathematical method for which all the following are true:
1. The method can, in practice or in principle, be carried out by a human computer working with
paper and pencil.
2. The method can be given to a human computer in the form of a finite number of instructions.
3. The method demands neither insight nor ingenuity on the part of the human being carrying it out.
4. The method will definitely work if carried out without error.
4
First-order logic or First Order Predicate Calculus (FOPC) is a formalisation of deductive logical reasoning. A
concise tutorial on FOPC can be found in [65].
30
Turing’s definition of a systematic method is the definition of an algorithm. Also, Turing proved
that it was possible to build a particularly powerful machine called Universal Turing Machine
(UTM) that could simulate any other Turing machine in reasonable time. Furthermore, Turing stated
a conjecture now known as the Church-Turing Thesis, in which he established an equivalence corre-
spondence between the existence of Turing machines and that of systematic methods. If the Church-
Turing thesis is correct, then the existence or non-existence of systematic methods can be replaced
throughout mathematics by the existence or non-existence of Turing machines. For instance, one
could establish that there is no systematic method for doing a certain task by proving that no Turing
machine can do the task in question.
5.1. The Church-Turing Thesis. Three ways to express the thesis are:
1. The UTM can perform any calculation that any human computer can carry out.
2. Any systematic method can be carried out by the UTM.
3. Every function which would be naturally regarded as computable can be computed by the Universal
Turing Machine.
Turing proved that it was not possible to build a Turing machine capable of solving problem from
Def. (5.1), i.e. the Entscheidungsproblem is undecidable. If the Church-Turing thesis is true that
means that the problem posed in Def. (5.1) cannot be solved by any algorithm, i.e. any finite method,
as required by Hilbert. In this thesis we shall focus only on decidable problems, that is, problems for
which it is possible to build Turing machines to solve them.
In the following section we deliver some general properties of problems suitable to be solved by
Turing machines, along with two relevant problems in Computer Science.
5.4 Definition of a Problem and two examples

We define a problem as a general question, usually possessing several parameters. A problem is
specified by giving a general description of all its parameters, and a statement of what properties the
solution is required to satisfy. An instance of a problem is obtained by specifying particular values
for all the problem parameters. In general, we are interested in finding the “most efficient” algorithm
for solving a problem, i.e. the fastest algorithm.
The description of a problem instance is a finite string of symbols under a particular and reasonable
encoding scheme, which maps problem instances into the strings describing them. To do this mapping
we use the concept of language:
Definition 5.2. Language. For any finite set of symbols Σ, we denote Σ∗ the set of all finite strings
of symbols from Σ. If L ⊂ Σ∗ then L is a language over the alphabet Σ.
For example, let Σ = {0, 1}. Then, Σ∗ = {φ, 0, 1, 00, 01, 10, 11, 000, 001, . . .} where φ is the
empty string. Thus, L = {01, 001, 111, 10100101, 1111, 0001} is a language over Σ, as is the set of
all binary representations of integers that are perfect cubes.
The input length for an instance I of a problem ζ is the number of symbols in the description of
I obtained from the encoding scheme of ζ. An algorithm solves a problem ζ if that algorithm can be
applied to any instance I of ζ and is guaranteed always to produce a solution for that instance I. Two
important problems in Computer Science are:
31
Definition 5.3. The Traveling Salesman Problem
INSTANCE: A finite set C = {c1 , c2 , . . . cm } of “cities” and a “distance” d(ci, cj ) ∈ N, the set of
natural numbers.
QUESTION: Which is the shortest “tour” of all the cities in C, that is, an ordering [cΠ(1) , cΠ(2) , . . . , cΠ(m) ]
of C such that [ m−1
P
i=1 d(cΠ(i) , cΠ(i+1) )] + d(cΠ(m) , cΠ(1) ) is minimum?
Definition 5.4. The Satisfiability (SAT) Problem

Let S = {x1 , x2 , . . . , xn } be a set of Boolean variables. A truth assigment for S is a function t : S →
{T, F }, for which if t(xi ) = T we say that xi is TRUE under t, and FALSE if t(xi ) = F . If xi is
a variable under S then xi and x̄i are literals over S. A clause over S is the disjunction of a set of
literals over S (such as x1 ∨ x2 ∨ x̄4 ) and it is satisfied by a truth assignment iff at least one of its
members xi is true under that assignment.
A collection C of clauses over S is satisfiable iff there exists some truth assignment V forWS that
simultaneously satisfies all the clauses in C, i.e. C is a conjunction of disjunctions C = i [( j xj )].
Such a truth assigment is called a satisfying truth assignment for C.
INSTANCE: A set S of variables and a collection C of clauses over S.
QUESTION: Is there a satisfying truth assignment for C?
In the theory of computation we usually work with decision problems, the reason being the need
to build operational definitions of relevant problems. It is a matter of ingenuity to design a decision-
problem version of a problem and it is not always the case that totally equivalent versions are obtained.
Let us provide a decision-version of problem 5.3 as an example (note that the SAT problem (5.4) is
already a decision problem).
Definition 5.5. The Traveling Salesman Problem (Decision problem version)

INSTANCE: A finite set C = {c1 , c2 , . . . cm } of “cities” a “distance” d(ci , cj ) ∈ N and a bound
B ∈ N.
QUESTION: Is there a “tour” of all the cities in PCm−1
having total length no more than B, that is, an
ordering [cΠ(1) , cΠ(2) , . . . , cΠ(m) ] of C such that [ i=1 d(cΠ(i) , cΠ(i+1) )] + d(cΠ(m) , cΠ(1) ) ≤ B?
We restrict ourselves to work with decision problems because languages, as defined in Def. (5.2),
are their natural counterpart, suitable to study in a mathematical fashion. The correspondence between
decision problems and languages is brought about by the encoding schemes used to specify problem
instances. An encoding scheme used describe each instance of a problem ζ partitions language Σ∗
into three classes of strings: strings that are not encoding of instances of ζ, those that encode instances
of ζ for which the answer is ‘no’ and those that encode instances of ζ for which the answer is ‘yes’.
Since we work with decidable problems, we are interested in the third class of strings.
In the following section we present definitions and main results of three models of computation:
Finite Automata, Turing Machines and Quantum Turing Machines.
32
5.5 Models of Computation and Algorithmic Complexity
Finite Automata, Turing Machines and Quantum Turing Machines are three models of computation.
In this chapter, Finite Automata are presented and its results are used to introduce Turing machines;
both models of computation are presented in their deterministic and nondeterministic versions. Quan-
tum Turing machines are introduced along with a physics-oriented version of the Church-Turing the-
sis. Before introducing the above mentioned models, we will provide some concepts to quantify the
amount of resources required to find an algorithmic solution to a problem.
5.5.1 Asymptotic Notation

The performance of models of computation in the execution of an algorithm is a fundamental topic
in the theory of computation. Since the quantification of resources (in our case, we focus on time)
needed to find a solution to a problem is usually a complex process, we just estimate it. To do so,
we use a form of estimation called Asymptotic Analysis in which we are interested in the maximum
number of steps Sm that an algorithm must be run on large inputs. We do so by considering only the
highest order term of the expression that quantifies Sm . For example, the function F (n) = 18n6 +
8n5 − 3n4 + 4n2 − π has five terms, and the highest order term is 18n6 . Since we disregard constant
factors, we then say that f is asymptotically at most n6 . The following definition formalises this idea.
Definition 5.6. Big O Notation. Let f, g : N → R+ . We say that f (n) = O(g(n)) if ∃ α, no ∈ N

such that ∀ n ≥ no
f (n) ≤ αg(n)
So, g(n) is an asymptotic upper bound for f (n) (“f is of the order of g”). Bounds of the form nβ ,
γ
β > 0 are called polynomial bounds, and bounds of the form 2n , γ ∈ R+ are called exponential
bounds. f (n) = O(g(n)) means informally that f grows as g or slower.
Big O notation says that one function is asymptotically no more than another. To state that one
function is asymptotically no less than another we use the Ω notation.
Definition 5.7. Ω Notation. Let f, g : N → R+ . We say that f (n) = Ω(g(n)) if ∃ α, no ∈ N such

that ∀ n ≥ no
g(n) ≤ αf (n)
Finally, to say that two functions grow at the same rate we use the Θ notation.
Definition 5.8. Θ Notation. Let f, g : N → R+ . We say that f (n) = Θ(g(n)) if f (n) = O(g(n))
and f (n) = Ω(g(n)). Thus, f (n) = Θ(g(n)) means that f and g have the same rate of growth.
5.5.2 Deterministic Finite Automata

Deterministic Finite Automata is a model for computers with an extremely limited amount of memory.
An example of a Deterministic Finite Automaton (DFA) is a machine R used to determine the parity
of a sequence of characters like the one shown in Fig. (2).
33
Suppose that R is at one of the ends of a wireless communication system. R can receive as valid
input the characters ‘0’ and ‘1’, and, since any communication system is subject to errors, R can
receive a third character ‘#’ which is used to state that an error has occurred in the transmission of
the data stream. So, the input for R is an arbitrarily long set of characters (also known as a string)
taken from the alphabet Σ = {0, 1, #}. The parity of a sequence of 0s and 1s is defined as follows: a
sequence of 0s and 1s is odd if its number of 1s is odd, and it is even if its number of 1s is even.
Let us now elaborate on the properties R must have. First, we state that only strings with no errors
will be suitable for parity computation. Thus, only sequences of 0s and 1s will be accepted and any
string has at least one error character must be rejected. Second, an empty set of characters has no 1s,
thus we set the initial parity of a string as even.
Let us show the behaviour of R with an example. Suppose that R receives as input the string
100110001 (read from left to right). The first input character is ‘1’ thus R goes from state ‘Even’ to
state ‘Odd’. We then read ‘0’ and therefore we stay in state ‘Odd’. The third input character is again a
‘0’ and we remain in state ‘Odd’. As fourth input we receive a ‘1’ and then we move from state ‘Odd’
to state ‘Even’ as now we have an even number of ‘1’s in our account. The fifth input is a ‘1’ and
consequently we move from state ‘Even’ to state ‘Odd’ as the total number of ‘1’s we have received
so far is odd. The 6th , 7th and 8th characters are ‘0’ thus the current state of machine R remains being
‘Odd’. Finally, the last input character is ‘1’ and therefore R goes from state ‘Odd’ to state ‘Even’.
The final outcome of the computation is the accept state ‘Even’.
1
0 0
Start Even Odd

0 1
# #
Error
0,1,#
Figure 2: A finite automaton R for parity computation. Double-circled states are accept states and single-
circled state is a reject state. Input strings for R are taken from the set of any combination of characters taken
from the alphabet Σ = {0, 1, #}.
Formally speaking, a DFA is a list of five objects: set of states, input alphabet, rules for moving,
start state, and accept states. We use a transition function to define the rules for moving. If the
DFA has an arrow from state x to a state y labeled with the input symbol 1, that means that, if the
automaton is in state x when it reads a 1, it then moves to state y. We can indicate the same thing
with the transition function by saying that δ(x, 1) = y.
34
Definition 5.9. Deterministic Finite Automaton. A DFA R is a 5-tuple (Q, Σ, δ, qo , F ), where
1. Q is a finite set called the states,
2. Σ is a finite set called the alphabet,
3. δ : Q × Σ → Q is the transition function,
4. q0 ∈ Q is the start date, and
5. F ⊂ Q is the set of accept states.
The formal description of the DFA R depicted in Fig. (2) is as follows: Q = {Even, Odd, Error},
Σ = {0, 1, #}, q0 = Even, F = {Even, Odd} and L(R) = {x ∈ {0, 1}n }. The transition function is
given in Table 1.
Table 1. Transition Function δ
δ(Even, 0) = Even δ(Even, 1) = Odd δ(Even, #) = Error
δ(Odd, 0) = Odd δ(Odd, 1) = Even δ(Odd, #) = Error
δ(Error, 0) = Error δ(Error, 1) = Error δ(Error, #) = Error
Definition 5.10. Computation with a Deterministic Finite Automaton. Let R = (Q, Σ, δ, qo , F )

be a DFA and let w = w1 w2 . . . wn be a string where each wi is a member of the alphabet Σ. Then R
accepts w if a sequence of states r0 , r1 , . . . , rn in Q exists with three conditions:
1. ro = q0 ,
2. δ(ri , wi+1 ) = ri+1 , for i = 0, 1, . . . , n − 1, and
3. rn ∈ F .
Condition 1 means that the machine starts in the start state. Condition 2 states that the machine
goes from state to state according to the transition function. Condition 3 says that the machine accepts
its input if it ends up in an accept state. We say that R accepts language A if A = {w|R accepts w},
i.e. A is the set of all strings accepted by R.
5.5.3 Nondeterministic Finite Automata

When every step of a computation follows in a unique way from the preceding step (as in a DFA)
we are doing deterministic computation. In a nondeterministic machine, several choices may exist
for the next state at any point. Non determinism is a generalization of determinism, so every DFA is
automatically a Nondeterministic Finite Automaton (NFA).
How does an NFA compute? Suppose that we are running an NFA on an input string and come to
a state with multiple states to proceed. For example, say that we are in state qi in NFA N1 and that
the next input symbol is 1. After reading that symbol, the machine splits into multiple copies of itself
and follows all the possibilities in parallel. Each copy of the machine takes one of the possible ways
to proceed and continues as before. If there are subsequent choices, the machine splits again. If the
next input symbol does not appear on any of the arrows exiting the state occupied by a copy of the
machine, that copy of the machine dies, along with the branch of the computation associated with it.
Finally, if any one of these copies of the machine is in an accept state at the end of the input, the NFA
accepts the input string.
35
Deterministic Computation Non−deterministic Computation
111
000
000
111 00
11
Start 000
111 00
11
00000000
11111111
000
111 111111111
000000000
0
1 0000000 11111111
1111111 00000000
0
1
0
1 0000000 11111111
1111111
0000000
1111111
00000000
0
1
00000000
11111111
0
1
1
0 0000000
1111111 00000000
11111111
0
1
0
1 000
111 000
111
0000000
1111111 0
1 000
111
00000000
11111111
0
1 000
111
00
1100
11 000
111 000
11100000000
11111111
0011
1100
0
1 000
111
00
1100
11 000
111 000
11100000
11111
00000000
11111111
0011
1100
0
1 0011
1100 0
1 00
11 00000
11111
00000000
11111111
00
11
0
1
0
1 0011
1100 0
1 11 00000
11111
00000000
11111111
0011
00
00
11 0
1 00000
11111
00000000
11111111
0
1
00
11 0011
1100 0
1
000
111 0011
11
000
111 00
00000
1111100
11
00000000
11111111
0
1
00
11
00
11 0011
11
00
11 00
00
11 0
1
000
111
000
111
000
111 11
0011
1100
00000
11111
111
00
000 111
111 00
11
00000000
11111111
000 00
11
00
11
00
11 Reject 00
11 00
11 000
111 000
000 111
111 0
1 00
11 00
11
0
1
0
1 00
11 00
11 000
0
1 00
11 00
11
0
1
0
1 0
1 0
1
0
1
0
1 . 0
1 0
1
0
1 . 0
1 0
1
0
1
0
1
. .. 0
1
00
11
00
11
0
1
0
1
0
1
0
1
. 00 Reject
11
00
11
0
1
00
11
00
11 1
0
00
11
0
1 0
1
0
1 0
1
0
1
0
1 000
111
0
1
0
1 .
0
1
0
1 000
111
000
111
0
1 .
.. 000
111
00 11
11
00
11
00 .
00 11
11 00
00
11
. 00 111
11
000
111
000
111
00
11
00 000
11 00
11
000
111 111
000
00
11
00
11
0000
1111
1
0 000
111
Accept 111 000
111 000
11100
11
0000
1111
0
1 000 000
111 0001111
1110000
0
1 0001111
1110000
1111
0
1 000
1110000
0
1
00
11 0001111
1110000
00
11
0
1 000
111
00
11 0000
1111
000
111 000
111
00
11
0
1 Accept 00 111
11 000 111
000
0
1 00 111
11 000 111
000
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
00
11
Accept 00
11
00
11
or
Reject
Figure 3: In a DFA, every single step is fully determined by the previous step. In an NFA, a step may be
followed by n new steps or, equivalently, an NFA makes n copies of itself, one for each possibility.
Another way to think of a nondeterministic computation is as a tree of possibilities. The root of

the tree corresponds to the start of the computation. Every branching point in the tree corresponds to
a point in the computation at which the machine has multiple choices. The machine accepts if at least
one of the computation branches ends in an accept state. A graphical illustration of a nondeterministic
computation is given in Fig. (3).
An NFA is not a fully realistic model of computation as it assumes the capability of producing
several instances of NFAs to run in parallel (it would be like suddenly producing as many computers
as instances for each computation step). However, nondeterminism may be viewed as a kind of
parallel computation wherein multiple independent processes can be running concurrently, and this
view does prepare the grounds for introducing the concept of probabilistic computation, which will
be reviewed in the following pages of this chapter.
Definition 5.11. Nondeterministic Finite automaton. An NFA RN is a 5-tuple (Q, Σ, δ, qo , F ),

where 1) Q is a finite set of states; 2) Σ is a finite alphabet; 3) δ : Q × Σ → P(Q) is the transition
function; (P is the power set of set Q); 4) q0 ∈ Q is the start state, and 5) F ⊆ Q is the set of accept
states.
Definition 5.12. Computation on a Nondeterministic Finite Automaton. Let RN = (Q, Σ, δ, q0 , F )

be an NFA and w a string over the alphabet Σ. Then we say that RN accepts w if we can write w as
w = y1 y2 . . . ym , where each yi is a member of Σ and a sequence of states r0 , r1 , . . . , rm exists in Q
with three conditions:
1. r0 = q0 ,
2. ri+1 ∈ δ(ri , yi+1 ), for i = 0, . . . , m − 1, and
3. rm ∈ F .
36
Condition 1 states that the machine starts out in the start state. Condition 2 means that state ri+1
is one of the allowable next states when N is in state ri and reading yi+1 . Observe that δ(ri , yi+1 )
is the set of allowable next states and so we say that ri+1 is a member of that set. Finally, condition
3 establishes that the machine accepts its input if the last state is an accept state. We say that RN
accepts language A if A = {w|RN accepts w}, i.e. A is the set of all strings accepted by RN .
It can be proved that DFAs and NFAs recognize the same class of languages [68]. However,
the number of states of a deterministic counterpart of an NFA can be exponential in the number
of branches of such an NFA and this is a very important difference between these two models of
computation.
5.5.4 Deterministic Turing Machines

Similar to a DFA but with an unlimited and unrestricted memory, a Deterministic Turing Machine
(DTM) is a much more accurate model of a general purpose computer. A DTM, pictured schemati-
cally in Fig. (4), can do everything a real computer can do.
Finite State Control
Read−Write Head
00000000000000000000000000000000000000
11111111111111111111111111111111111111
0
1 0
1 0
1 0
1 0
1 0
1 11111
00000
0
1
0
1 0
1 0
1 0
1 0
1 0
1 0
1
0
1 0
1 0
1 0
1 0
1 0
1 0
1
0
1 0
1 0
1 0
1 0
1 0
1 0
1
0
1 0
1 0
1 0
1 0
1 0
1 0
1
... 0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
...
0
1 0
1 0
1 0
1 0
1 0
1 0
1
0
1 0
1 0
1 0
1 0
1 0
1 0
1
0
1 0
1 0
1 0
1 0
1 0
1 0
1
11111111111111111111111111111111111111
00000000000000000000000000000000000000
11111
00000
−3 −2 −1 0 1 2 3
Figure 4: The ‘hardware’ elements of a Deterministic Turing Machine (DTM) are a limitless memory-type
(the tape is divided into squares or cells), and a scanner which consists of read-write head plus a finite state
control system. The scanner has two purposes: to read and write information on the cells of the tape as well as
to control the state of the DTM.
A DTM consists of a scanner and a limitless memory-tape that moves back and forth past the
scanner. The scanner is composed of a read-write head as well as a finite state control system. The
scanner does two tasks: it controls the state of the DTM through the finite state control system, and
reads and writes information on the memory cells through the read-write head. The tape is divided
into squares. Each square may be blank (t) or may bear a single symbol (0 or 1, for example). The
scanner is able to examine only one square of tape at a time (the ‘scanned square’). The scanner has
mechanisms that enable it to write and erase the symbol on the scanned square, and to move the tape
to the left or right, one square at a time. Also, the scanner is able to alter the state of the machine:
a device within the scanner is capable of adopting a number of different states, and the scanner is
able to alter the state of this device whenever necessary. The operations just described - erase, print,
move, and change state - are the basic operations of a DTM. Complexity of operation is achieved by
chaining together large numbers of these simple basic operations.
37
Note that according to the definitions of effective procedure and Turing machines, and under the
assumption that the Church-Turing thesis holds, the concepts of Turing machine and algorithm are
interchangeable.
Definition 5.13. Deterministic Turing Machine. A Deterministic Turing Machine (DTM) is a 7-

tuple M = (Q, Σ, Γ, δ, q0 , qaccept , qreject ), where Q, Σ, Γ are all finite sets and
1. Q is the set of states
2. Σ is the input alphabet not containing the blank symbol t,
3. Γ is the tape alphabet, where t ∈ Γ and Σ ⊂ Γ
4. δ : Q × Γ → Q × Γ × {L, R} is the transition function,
5. q0 ∈ Q is the start state,
6. qaccept ∈ Q is the accept state, and
7. qreject ∈ Q is the reject state, where qaccept 6= qreject .
Definition 5.14. Computation with a Deterministic Turing Machine.

Let M = (Q, Σ, Γ, δ, q0 , qaccept , qreject ) be a DTM.
Initially M receives its input w ∈ Σ∗ on the leftmost n squares of the tape, and the rest of the tape
is filled with blank symbols. The head starts on the leftmost square of the tape (Σ does not contain
the blank symbol, so the first blank appearing on the tape marks the end of the input.) Once M has
started, the computation proceeds according to the rules described by δ. The computation continues
until it enters either the accept or reject states at which point it halts. If neither occurs, M just does
not stop.
As a DTM computes, changes occur in the current state, the current tape contents, and the current
head location. A setting of these three items is called a configuration of the DTM. A configuration
C1 yields configuration C2 if the Turing machine can legally go from C1 to C2 in a single step. In an
accepting configuration the state of the configuration is qaccept . In a rejecting configuration the state
of the configuration is qreject . Accepting and rejecting configurations are halting configurations and
do not yield further configurations.
A DTM M accepts input w if a sequence of configurations C1 , C2 , . . . Ck exists, where
1. C1 is the start configuration of M on input w,
2. each Ci yields Ci+1 , and
3. Ck is an accepting configuration.
We say that M accepts language A if A = {w|M accepts w}, i.e. A is the set of all strings
accepted by M. We now show how to use a DTM to recognize all numbers divisible by 4.
Example 5.1. Running a program in a Deterministic Turing Machine. The program specified by
Γ = {0, 1, t} (t is the blank symbol), Q = {q0 , q1 , q2 , q3 , qaccept , qreject } and δ, provided in Table 1,
is used in a deterministic Turing machine M to determine whether a number can be divided by 4
or, equivalently, whether the last two digits of a binary number, reading from left to right, are two
consecutive zeros.
38
Table 1. Example of a deterministic Turing machine.
Q/Γ 0 1 t
q0 (q0 , 0, R) (q0 , 1, R) (q1 , t, L)
q1 (q2 , t, L) (q3 , t, L) (qreject , t, L)
q2 (qaccept , t, L) (qreject , t, L) (qreject , t, L)
q3 (qreject , t, L) (qreject , t, L) (qreject , t, L)
The program works as follows. For a state qi ∈ {q0 , q1 , q2 , q3 } specified in the LHS column and
a given alphabet symbol sj ∈ {0, 1, t} specified in the top row, the box that corresponds to row qi
and column sj and contains three symbols: the first symbol is the new state of M, the second symbol
is the new alphabet symbol that will be written in the current cell (substituting symbol si ) and the
third symbol specifies the motion direction of the read-write head. So, row qi and column sj are the
current configuration of M and the symbols contained in the box corresponding to row qi and column
sj are the next configuration of M.
For example, let X = 10100 be an input binary string (we shall read the input string from left to
right). The initial state of M is q0 and M’s tape reads as t 1 0 1 0 0 t where our first
input symbol (in bold face) is the leftmost 1. So,the initial configuration of M is q0 , 1.
The transition function specifies that for a state q0 and input symbol 1, M must take q0 as new
state, write the value 1 in the cell where its read-write head is now located (1) and take its read-write
head one cell forward, i.e. to the right. So, M is now in the configuration q0 , 0 and its tape reads as
t 1 0 1 0 0 t .
The full run of this program is given in the following sequence

Step 1: q0 , t10100t → q0 , t10100t
Step 2: q0 , t10100t → q0 , t10100t
Step 3: q0 , t10100t → q0 , t10100t
Step 4: q0 , t10100t → q0 , t10100t
.
Step 5: q0 , t10100t → q0 , t10100t
Step 6: q0 , t10100t → q1 , t10100t
Step 7: q1 , t10100t → q2 , t1010 t t
Step 8: q2 , t1010bt → qy , t101 t tt
We have said that DTMs can do everything a real computer can do, and real computers compute
values of functions. Transducer Machines, a DTM variant, are capable of those computations.
Definition 5.15. Transducer Machines. A transducer machine T is used to compute functions. T

has a string w ∈ Σ∗ as input and produces another string y as output. Output y is stored in a special
tape called the output tape. Given a function f , a transducer T computes f if the computation T (w)
reaches a final state containing f (w) as output whenever f (w) is defined (if f is not defined, T never
reaches a final state). A function f is computable if a Turing Machine T exists capable of computing
it.
39
5.5.5 Algorithmic Complexity for DTMs
A DTM can be used to find a solution to a problem, so how efficiently can such a solution be found?
As stated previously, we shall be interested in finding the fastest algorithms. Let us now introduce a
few concepts needed to quantify the efficiency of an algorithm.
The time complexity of an algorithm A expresses its time requirements by giving, for each input
length, the largest amount of time needed by A to solve a problem instance of that size.
Definition 5.16. Time Complexity Function for a DTM. Let M be a DTM. We define f : N → N
as the time complexity function of M, where f (n) is the maximum number of steps that M uses on
any input of length n.
Definition 5.17. Time Complexity Class for DTMs. Let t : N → R+ be a function. We define the
time complexity class TIME(t(n)), as the collection of all languages that are decidable by an O(t(n))
time DTM.
Definition 5.18. Class P. The class of languages that are decidable in polynomial time on a deter-
ministic single-tape Turing machine is denoted by P and is defined as
[
P= TIME(nk )
k
The language of Ex. (5.1) is in P.
A polynomial time or tractable algorithm is defined to be one whose time complexity function is
O(p(n)) for some polynomial function p, where n is used to denote the input length. Any algorithm
whose time complexity function cannot be so bounded is called an exponential time or intractable
algorithm. Tractable algorithms are considered as acceptable, as a sign that a satisfactory solution
for a problem has been found. Finding a tractable algorithm is usually the result of obtaining a deep
mathematical insight into a problem. In contrast, intractable algorithms are usually solutions obtained
by exhaustion, the so called brute-force method, and are not considered satisfactory solutions.
For example, no tractable algorithm for the Travelling Salesman Problem (5.3) is known so far
([67] and [74]). All solutions proposed so far are based on enumerating all possible solutions. Why is
the Travelling Salesman problem intractable? Nobody knows for sure. It could be either that we need
a deeper knowledge of the characteristics of this problem or, simply, that the Travelling Salesman
problem is inherently intractable. However, no proof for neither of these two alternatives has been
supplied so far.
DTMs are powerful machines. However, there are many decidable problems that require an un-
reasonable amount of resources from a DTM to be solved. In the following lines we introduce another
model of computation used to tackle some of those problems.
We shall study two of those problems in detail in the last part of this chapter, but before doing
so we must introduce some formal definitions in order to have the tools required to define and attack
those problems.
40
5.5.6 Nondeterministic Turing Machines
The definition of a Nondeterministic Turing Machine (NTM) is similar to that of an NFA. The com-
putation of an NTM is a tree whose branches correspond to different possibilities for the machine (see
Fig. (3)). If some branch of the computation leads to the accept state qaccept then the machine accepts
its input.
Definition 5.19. Nondeterministic Turing Machine. A Nondeterministic Turing Machine is a 7-
tuple MN = (Q, Σ, Γ, ∆, q0 , qaccept , qreject ), where Q, Σ, Γ are all finite sets, P(Q × Γ × {L, R}) is the
power set of Q × Γ × {L, R}, and
3. Γ is the tape alphabet, where t ∈ Γ and Σ ⊂ Γ,
4. ∆ : Q × Γ → P(Q × Γ × {L, R}) is the transition relation,
7. qreject ∈ Q is the reject state, where qaccept 6= qreject
Notice that ∆ is not a function anymore but a relation, reflecting the fact that an NTM does not
have a single, uniquely defined next action but a choice between several next actions. In other words,
for each state and symbol combination, there may be more than one appropriate next step, or none at
all.
Definition 5.20. Computation with an NTM. An NTM MN accepts input w ∈ Σ∗ if at least one
branch of its computation tree is a sequence of configurations C1 , C2 , . . . Ck such that
1. C1 is the start configuration of MN on input w,
2. each Ci yields Ci+1 , and
3. Ck is an accepting configuration.
MN accepts language A if A = {w|MN accepts w}, i.e. A is the set of all strings accepted by MN .
NTMs are powerful because of the assymetrical input-output relation found in the way these
machines compute. In order to have an NTM MN accept one string w it suffices to find just one
branch b in the computation tree that accepts w.
It can be shown that an NTM can be simulated by a DTM, i.e. that every NTM has an equivalent
DTM ([68] and next section). However, simulating an NTM by a DTM may be at the cost of an
exponential loss of efficiency [67]. Whether this loss is inherent to this ‘translation’ between models
?
or is just a consequence of our limited understanding of nondeterminism is the famous P = NP
problem [67].
5.5.7 Algorithmic Complexity for NTMs

We start by offering the definitions of time complexity function and time complexity class for NTMs.
Definition 5.21. Time Complexity Function for an NTM. Let MN be an NTM. We define g : N → N
as the time complexity function of MN , where g(n) is the maximum number of steps that MN uses on
any branch of its computation on any input length n.
41
Definition 5.22. Time Complexity Class for NTMs. Let t : N → R+ be a function. We define
the time complexity class NTIME(t(n)), as the collection of all languages that are decidable by an
O(t(n)) time nondeterministic Turing machine.
For an NTM to accept string w it is enough to find just one branch b in its computation tree that
accepts w. However, a practical problem with this definition is to find b as an NTM can have an infinite
(or exponentially big) number of different branches. Therefore, a more operational method for doing
nondeterministic computation is needed. An important discovery in the theory of computation is the
fact that the complexities of many problems are linked by means of a concept called verifiability.
For example, let us suppose we have a proposed solution for the Travelling Salesman problem
(5.5) and another solution for the SAT problem (5.4). In both cases, we could easily check whether
each proposal is indeed a solution, all we need is a DTM that verifies whether proposed solutions are
right or not. Let us formalize these concepts.
Definition 5.23. Verifier. A verifier for a language A is an algorithm V , where
A = {w|V accepts (w, c) for some string c}

We measure the time of a verifier only in terms of the length of w, so a polynomial time verifier runs
in polynomial time in the length of w. A language A is polynomially verifiable if it has a polynomial
time verifier. The string c, a certificate, is additional information needed by the verifier. For example,
in the case of problem (5.5), c is the set of cities and distances, along with the bound B. In the case
of the SAT problem (5.4), c is the actual clause collection to be tested.
Note that a fundamental difference between an NTM (Def. (5.19)) and a verifier is that an NTM
finds solutions, while a verifier only checks whether a proposal is a solution or not.
We now proceed to define a most important class of languages in Computer Science:
Definition 5.24. Class NP. The class of languages that have polynomial time verifiers is known as
NP.
What is the relation between the abstract model of an NTM and the concepts of verifiers and NP
languages class? The answer is given in Theorem (1) and its proof can be found in [68].
Theorem 1. A language is in NP if and only if it is decided by a nondeterministic polynomial time

Turing machine.
?
5.5.8 P = NP and NP-complete problems
?
The problem P = NP is a fundamental topic in the theory of computation. It is known that P ⊂ NP
as any polynomial language can be checked with a polynomial verifier. Also, it can be proved [66]
that
Theorem 2. If a problem ζ ∈ NP then ∃ a polynomial p such that ζ can be solved by a deterministic

algorithm having time complexity O(2p(n)).
42
Due to theorem (2) there is a widespread belief that P 6= NP although no proof has been delivered
?
and therefore P = NP remains an open problem.
There is a particular set of problems in NP that plays a key role in the theory of computation:
NP-complete problems. In order to characterise this important set of problems we shall introduce the
notion of polynomial transformations.
Definition 5.25. Polynomial Transformation. A polynomial transformation from a language L1 ⊂

Σ∗1 to a language L2 ⊂ Σ∗2 , denoted by L1 ∝ L2 , is a function f such that
1. There is a polynomial time DTM that computes f .
2. ∀ x ∈ Σ∗1 , x ∈ Li ⇔ f (x) ∈ L2
Definition 5.26. NP-Complete Languages and Problems. A language L is NP-complete if L ∈ NP

and, for all other languages Li ∈ NP we find that Li ∝ L.
Due to our capacity to go from problem instances to languages by means of encoding schemes, we
can also say that a decision problem ζ is NP-complete if ζ ∈ NP and, for all other decision problems
ζi ∈ NP we find that ζi ∝ ζ.
There is a plethora of NP-complete problems. The first NP-complete problem (chronologically

speaking) was found by Stephen Cook ([75]) and it is stated in the following theorem (its proof can
be found in [75] and [66]).
Theorem 3. NP-Completeness of SAT problem. SAT problem is NP-complete.
Therefore, studying the properties of SAT is an important and active area of research, not only
because a polynomial-time solution to SAT would imply P = NP, but also because SAT is used to
model problems and procedures in several areas of applied computer science and engineering like
Artificial Intelligence (e.g. [76]) and hardware verification (e.g. [77] and [78]), using the following
approach ([79]):
1. Represent the problem in propositional logic

2. Identify the proposition to be decided by satisfiability
3. Solve the SAT problem
4. Interpret the result in the original domain
Surveys of algorithms for solving several variations and instances of SAT can be found in [76], [80]
and [79] . Also, good introductions to the vast field of computational complexity can be found in [81],
[82], [74], [83], and [68].
43
6 Physics and the Theory of Computation
Considerations about the physical properties of systems used to do computation and/or transmission
of information have been studied for several decades. Consequently, physics and computer science
have cross-fertilised each other for long time. As early as in the 1940s, in the beginning of the digital
computer era, scientists wondered about the existence and quantification of the minimum amount of
energy required to perform a computation. J. von Neumann, in a set of lectures delivered in 1949 [?],
showed that “a minimum amount of energy required per elementary decision of a two-way alternative
and the elementary transmittal of one unit of information” was close to kT , where k is Boltzmann’s
constant and T is the temperature of the system. Later on, R. Landauer studied the relationship be-
tween energy comsumption and reversible computation (a computational step is reversible iff given
the output of that step, its input is uniquely determined5 .) Among those results published by Landauer
in [?] we have the following principle.
Landauer’s principle. Suppose a computer erases a single bit of information. The amount of energy
dissipated into the environment is at least kT ln 2, where k is Boltzmann’s constant, and T is the
temperature of the environment of the computer.
Landauer’s principle became a big motivation to do research in reversible computation. Among

those works about reversible models of computation we find [84], [86] and [85].
Since evolution in quantum mechanics is reversible due to the use of unitary operators, the next
step in the cross-fertilisation between computer science and physics was to link quantum mechanics
and computer science. Benioff introduced the notion of Quantum Turing Machines and proposed
a quantum mechanical model for the simulation of a classical computer ([87], [90], [89], [88] and
chapter 6 of [93]). Additionally, R. Feynman, in his traditional and celebrated style, lectured at MIT
in 1981 [92] about the fundamental capabilities and limitations of classical computers to simulate
quantum systems. A gentle and concise introduction to this blend of physics, computer science and
information theory, as well as Feynman’s main ideas behind physics and computation can be found
in [93].
In 1985 D. Deutsch made two key contributions in [3]: a design of a Universal Quantum Turing
Machine, and a physics-oriented version of the Church-Turing thesis which he called ‘Church-Turing
principle’:
The Church-Turing principle [3]. Every finitely realizable physical system can be perfectly simu-
lated by a universal model computing machine operating by finite means.
In Deutsch’s words, the rationale behind the Church-Turing priciple was “to reinterpret Turing’s
‘functions which would be naturally regarded as computable’ as the functions which may in principle
be computed by a real physical system. For it would surely be hard to regard a function ‘naturally’ as
computable if it could not be computed in Nature, and conversely”. The Universal Quantum Turing
machine proposed in [3] was further developed and improved by Yao [95] and Bernstein and Vazirani
[96].
5
For example, the logical operation OR is not reversible, while the operation NOT is indeed reversible.
44
We now define a Probabilistic Turing Machine and a Quantum Turing Machine.
Definition 6.1. [8] Probabilistic Turing Machine. A Probabilistic Turing Machine (PTM) is a
Nondeterministic Turing Machine which randomly chooses between the available transitions at each
point according to a probability distribution. Thus, a PTM MN = (Q, Σ, Γ, ∆, q0 , qaccept , qreject ), is a
7-tuple where Q, Σ, Γ are all finite sets, P(Q × Γ × {L, R}) is the power set of Q × Γ × {L, R}, and
7. The transition relation is given by ∆ : Q × Γ → P(Q × Γ × {L, R} × [0, 1]), so that for a
given configuration C0 , each of its successor configurations C1 , C2 , . . . , Cn isPassigned a probability
p1 , p2 , . . . , pn , where n is the cardinality of P(Q × Γ × {L, R} × [0, 1]) and ni=1 pi = 1.
Definition 6.2. [8] Quantum Turing Machine. A Quantum Turing Machine is defined analogously
to a PTM but with a different transition relation. The transition relation includes the use of complex
numbers which are the corresponding amplitudes of quantum states used for computation. A QTM is
a 7-tuple MN = (Q, Σ, Γ, ∆, q0 , qaccept , qreject ), where Q, Σ, Γ are all finite sets, P(Q × Γ × {L, R})
is the power set of Q × Γ × {L, R}, and
7. The transition relation is given by ∆ : Q × Γ → P(Q × Γ × {L, R} × C[0,1] ), where C[0,1] ) = {z ∈
C| |z|2 ≤ 1}. So, for a given configuration C0 , each of its successor configurations C1 , C2 , . . . , Cn is
assigned an amplitude z1 , z2 , . . . , zn , where n is the cardinality of P(Q × Γ × {L, R} × C[0,1] ) and
P n 2
i=1 |zi | = 1.
Quantum computation can be regarded as the study and development of methods that, by using
quantum mechanical properties, solve problems in finite time (from a different computational point of
view, quantum computation is a sub-field of unconventional models of computation [94]). Quantum
information can be defined as the field devoted to understanding how information is represented
and communicated using quantum states. Due to the advances made over the last few years, both
disciplines are now huge areas of research where diverse interests of several scientific communities
can be found. Quantum walks is one of those interests, mainly contained in the sub-field of quantum
algorithms.
45
7 Algoritmos cuánticos
Con el objetivo de adquirir práctica en el uso de sı́mbolos y operaciones propios del cómputo cuántico,
los trabajos de esta sección se harán en el pizarrón. Los temas que se estudiarán son:
7.1 Una mala noticia: the no cloning theorem

7.2 Si los qubits no pueden ser copiados, ¿cómo calcular?
7.3 Circuitos cuánticos
7.3.1 Compuertas controladas
7.3.2 Circuito cuántico para la generació de estados de Bell
7.4 Paralelismo cuántico

7.5 El algoritmo de Deutsch
46
References
[1] Richard P. Feynman. Simulating Physics with Computers. International Journal of Theoretical
Physics 21(6/7), pp. 467-488, 1982.
[2] Richard P. Feynman. Feynman Lectures on Computation. Penguin Books, 1999.

[3] David Deutsch. Quantum Theory, the Church-Turing Principle and the Universal Quantum Com-
puter. En Proceedings of the Royal Society of London, series A, Mathematical and Physical Sci-
ences, Volume 400, Issue 1818, pp. 97–117, 1985.
[4] Peter Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Algorithms on a
Quantum Computer. En Proceedings of the 35th Annual Symposium on Foundations of Computer
Science, pp. 124–134, 1994. IEEE Computer Society Press.
[5] Lov K. Grover. A fast quantum mechanical algorithm for database search. En Proceedings of the
28th annual ACM symposium on the Theory of Computing, pp. 212–219, 1996.
[6] Dirk Bouwmeester, Artur Ekert y Anton Zeilinger (Comps.). The Physics of Quantum Informa-
tion. Springer, 2001.
[7] Michael A. Nielsen e Isaac L. Chuang. Quantum Computation and Quantum Information. Cam-
bridge University Press, 2000.
[8] Josef Gruska. Quantum Computing. McGraw-Hill, 1999.

[9] Tom Apostol. Calculus vol. II. Editorial Reverté, 1980.
[10] K.F. Riley, M.P. Hobson y S.J. Bence. Mathematical Methods for Physics and Engineering.
Cambridge University Press, 1998.
[11] H. Ted Davis y Kendall T. Thomson. Linear Algebra and Linear Operators in Engineering.
Academic Press, 2000.
[12] Head and Tails. Quantum Computers are another step closer. Technology Quarterly, The
Economist, 2 de enero de 2003.
[13] Dream code. Programming languages for quantum computers are now being written. Technol-
ogy Quarterly, The Economist, 3 de abril de 2003.
[14] Quantum computing. Computing is driving the philosophical understanding of quantum theory.
Technology Quarterly, The Economist, 1 de abril de 2004.
[15] Paul A. Benioff, Space searches with a quantum robot. En Quantum Computation and Quantum
Information: A millenium volume. S. Lomonaco y H.E. Brandt (Comps.), AMS Contemporary
Mathematics (305), 2002.
[16] Carlo Trugenberger. Probabilistic Quantum Memories. Physical Review Letters, 87:067901,
2001.
47
[17] Carlo Trugenberger. Phase Transitions in Quantum Pattern Recognition. Physical Review Let-
ters, 89:277903, 2002.
[18] Carlo Trugenberger. Quantum Pattern Recognition. Quantum Information Processing, 1(6), pp.
471-493, 2002.
[19] M. Cristina Diamantini y Carlo Trugenberger. Quantum Pattern Retrieval by Qubit Networks
with Hebb Interactions. quant-ph/0609117
[20] Salvador E. Venegas-Andraca y Sougato Bose. Quantum Computation and Image Processing:
New Trends in Artificial Intelligence. En Proceedings of the International Conference on Artificial
Intelligence IJCAI-03, pp. 1563-1564, 2003.
[21] Salvador E. Venegas-Andraca y Sougato Bose. Storing, processing and retrieving an image
using Quantum Mechanics. En Proceedings of the SPIE Conference Quantum Information and
Computation, pp. 137-147, 2003.
[22] Salvador E. Venegas-Andraca y Jonathan L. Ball. Storing Images in Entangled Systems. Enviado
a la revista Journal of Electronic Imaging, SPIE, 2006.
[23] Sanjay Gupta. Quantum Neural Networks. Journal of Computer and System Sciences, 63, pp.
355-383, 2001.
[24] Chun-Yang Zhang, Hsin-Chih Yeh, Marcos T. Kuroki y Tza-Huei Wang. Single Quantum-Dot-
Based DNA nanosensor. Nature materials (4) pp. 826-831, 2005.
[25] Yaakov S. Weinstein, C. Stephen Hellberg y Jeremy Levy. Quantum-Dot Cluster-State Comput-
ing with Encoded Qubits. Physical Review A 72(2): 020304, 2004.
[26] Lloyd C.L. Hollenberg. Fast Quantum Search Algorithm in Protein Sequence Comparison-
Quantum Biocomputing. Physical Review E 62, pp. 7532-7535 (2000).
[27] Uncrackable beams of light. Quantum Cryptography is finally going commercial. Technology
Quarterly, The Economist, 4 de septiembre de 2003.
[28] http://www.quantum.univie.ac.at/zeilinger/
[29] http://ultrafast.physics.ox.ac.uk/
[30] http://www.magiqtech.com/
[31] http://www.qubit.org
[32] http://cam.qubit.org
[33] http://aspuru.chem.harvard.edu/
[34] http://www.quantum.univie.ac.at/
48
[35] http://www.iqi.caltech.edu/
[36] http://www-math.mit.edu/ ˜ shor/
[37] http://www.bell-labs.com/org/physicalsciences/
[38] http://www.hpl.hp.com/research/qsr/
[39] http://www.research.ibm.com/quantuminfo/
[40] http://jp.fujitsu.com/group/labs/en/business/activities/activities-3/ (apartado Nanotecnologı́a).
[41] Gana fı́sico español Asturias de ciencia. Periódico Reforma, 24 de mayo de 2006.
[42] El fı́sico español Cirac Sasturain, Premio Prı́ncipe de Asturias de investigación. Periódico El
Paı́s, 24 de mayo de 2006.
[43] Oscar Rosas-Ortiz. Manipulando el mundo cuántico: ingenierı́a cuántica. Avance y Perspectiva
(CINVESTAV), octubre-diciembre 2004.
[44] Isaac Hernández Calderón. Los semiconductores: de los transistores a las nanoestructuras y la
computación cuántica. Avance y Perspectiva (CINVESTAV), abril-junio 2005.
[45] Carlos Fuentes. Tecnologı́a mexicana: noticias desde Londres. Periódico Reforma, 27 de oc-
tubre de 2003.
[46] José Galán. Explora mexicano los alcances de la computación cuántica. Entrevista con Salvador
Venegas Andraca. Periódico La Jornada, 20 de mayo de 2005.
[47] Salvador Elı́as Venegas Andraca. Un vistazo a la tecnologı́a del futuro I: ¿qué es la computación
cuántica? Periódico Milenio, 3 de enero de 2006.
[48] Salvador Elı́as Venegas Andraca. Un vistazo a la tecnologı́a del futuro II: caminatas cuánticas
Periódico Milenio, 10 de enero de 2006.
[49] Ariadne Gallardo. La mecánica cuántica al servicio de la computación. Entrevista con Salvador
Venegas Andraca. Periódico en lı́nea Casanchi. Enero de 2005.
[50] Shahen Hacyan. Teleportación cuántica. Periódico Reforma, 1 de julio de 2004.
[51] Shahen Hacyan. Criptogramas cuánticos. Periódico Reforma, 9 de septiembre de 2004.
[52] Teletransportan fotones. Periódico Reforma, 19 de agosto de 2004.
[53] Olivia Aguayo. Teletransportación: Mito o realidad? Periódico Reforma, 20 de febrero de

2006.
[54] Cómo construir una computadora cuántica. Periódico La Jornada (The Economist Intelligence
Unit), 18 de mayo de 2006.
49
[55] Computation Summer School in Yucatán. Mexico Update, revista de comunicación oficial de la
embajada de México en el Reino Unido. octubre de 2004.
[56] Resumen de actividades de la primer escuela mexicana de verano en computación cuántica,

http://www.cem.itesm.mx/dia/escuelaverano y escoger la opción “Escuela de verano 2004”.
[57] C. Cohen-Tannoudji and B. Diu and F. Laloe. Quantum Mechanics, Vols. 1 & 2. Wiley-
Interscience, 1977.
[58] R. Coleman. Stochastic Processes. George Allen & Unwin, Ltd., 1974.
[59] R.P. Feynman and R.B. Leighton and M. Sands. The Feynman Lectures on Physics, vol. III.
Addision-Wesley Publishing Co., 1965.
[60] A. Einstein. Ideas and Opinions. Wing Books, 1954.
[61] W. Heisenberg. Physics and Philosophy. Penguin Group, 1962.
[62] D. Preston. Before the Fall-out: From Marie Curie to Hiroshima. Doubleday, 2005.
[63] P.A.M. Dirac. The Principles of Quantum Mechanics. Oxford University Press, 1930.
[64] E. Rieffel y W. Polak. An introduction to quantum computing for non-physicists. ACM Comput-
ing Surveys, vol. 32(3)”, pp. 300–335, 2000.
[65] B.J. Copeland. The essential Turing. Oxford University Press, 2004.
[66] M.R. Garey y D.S. Johnson. Computers and Intractability. A Guide to the Theory of NP-
Completeness. W.H. Freeman and Co., NY, 1979.
[67] C.H. Papadimitriou. Computational Complexity. Addison Wesley Publishing Co., 1995.
[68] Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Co., 2005.
[69] Alan M. Turing. On Computable Numbers, with an application to the Entscheidung problem.
Proceedings of the London Mathematical Society, vol. 42, pp. 230-265, 1936-37.
[70] . Richard Zach. Hilbert’s Program. The Stanford Encyclopedia of Philosophy, Edward N. Zalta,
http://plato.stanford.edu/archives/fall2003/entries/hilbert-program/, Fall 2003.
[71] David Hilbert. Mathematische Probleme. Archiv der Mathematik und Physik 1 (1901) 4463,
213237. English translation by M.W. Newson in Bulletin of the American Mathematical Society 8
(1902), 437-479, url = ”http://aleph0.clarku.edu/ djoyce/hilbert/problems.html
[72] David Hilbert. Neubegrundung der Mathematik: ErsteMitteilung. Series of talks given at the
University of Hamburg. English translations given by Mancosu, Paolo (ed.), 1998a, From Brouwer
to Hilbert. The Debate on the Foundations of Mathematics in the 1920s, Oxford. Oxford University
Press, 1922.
50
[73] D. Hilbert y W. Ackerman. Grundzuge der theoretischen Logik. Springer-Verlag, 1928. English
translation of the second edition Principles of Mathematical Logic, by L. M. Hammond et al.,
Chelsea, New York, 1950.
[74] Stephan Mertens. Computational Complexity for Physicists. Computing in Science and Engi-
neering, IEEE, pp. 31-47, May-June 2002.
[75] Stephen A. Cook. The Complexity of Theorem-Proving Procedures. Proc. 3rd Ann. ACM Sym-
posium on the Theory of Computing, pp. 151-158, 1971.
[76] I. Gent y T. Walsh. The search for Satisfaction. Internal report, department of computer science,
University of Strathclyde, 1999.
[77] P. Bjesse, T. Leonard y A. Mokkedem. Finding bugs in an alpha microprocessor using satisfia-
bility solvers. Proc. 13th International Conference on Computer Aided Verification, 2001.
[78] M.N. Velev y R.E. Bryant. Effective use of Boolean satisfiability procedures in the formal verifi-
cation of superscalar and vliw microprocessors. Proc. 38th Design Automation Conference (DAC
’01), pp. 226-231, 2001.
[79] H. Rantanen. Analyzing the random-walk algorithm for SAT. Master’s thesis, Helsinki Univer-
sity of Technology, 2004.
[80] H. Kautz y B. Selman. The state of SAT. Preliminary version in Proc. of CP-2003. To appear in
Discrete and Applied Mathematics, 2005.
[81] Stephen A. Cook. An overview of computational complexity. Turing award lecture 1983, Asso-
ciation for Computing Machinery, 1983.
[82] L. Fortnow y S. Homer. A Short History of Computational Complexity. D. van Dalen, J. Dawson,
y A. Kanamori (Eds.), The History of Mathematical Logic. North-Holland, Amsterdam, 2003.
[83] C.H. Papadimitriou. On selecting a satisfying truth assignment. Proceedings 32nd IEEE Sym-
posium on the Foundations of Computer Science, pp. 163 - 169, 1991.
[84] C.H. Bennett. Logical Reversibility of Computation. IBM Journal of Research and Development,
vol. 17, pp. 525-532, 1973.
[85] Y. Lecerf. Logique Mathématique : Machines de Turing réversibles. Comptes rendus des
séances de l’académie des sciences, vol. 257, pp. 2597-2600, 1963.
[86] E. Fredkin y T. Toffoli. Conservative Logic. International Journal of Theoretical Physics, vol.
21, pp. 219-253, 1982.
[87] P.A. Benioff. The computer as a physical system: a microscopic quantum mechanical Hamil-
tonian model of computers as represented by Turing Machines. Journal of Statistical Physics, vol.
22(5), p. 563, 1980.
51
[88] P.A. Benioff. Quantum Mechanical models of Turing Machines that Dissipate no energy. Phys.
Rev. Lett., vol. 48, pp. 1581–1585, 1982.
[89] P.A. Benioff. Quantum mechanical Hamiltonian models of Turing machines. Journal of Statisti-
cal Physics, vol. 3(29), pp. 515–546, 1982.
[90] P.A. Benioff. Quantum Mechanical Hamiltonian Models of Discrete Processes That Erase Their
Own Histories: Application to Turing Machines. International Journal of Theoretical Physics, vol.
21, pp. 177-201, 1982.
[91] P.A. Benioff. Space searches with a quantum robot. In Quantum Computation and Quantum
Information: A millenium volume. S. Lomonaco and H.E. Brandt (Eds.), AMS Contemporary
Mathematics (305), 2002.
[92] R.P. Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics,
vol. 21(6/7), pp. 467-488, 1982.
[93] R. P. Feynman. Feynman Lectures on Computation. Penguin Books, 1999.
[94] C.S. Calude, J. Casti y M.J. Dineen (Eds.). Unconventional Models of Computation. Springer-
Verlag, 1998.
[95] A. C. Yao. Quantum Circuit Complexity. Proceedings of Thirty-fourth IEEE Symposium on

Foundations of Computer Science, pp. 352–361, 1993.
[96] E. Bernstein y U. Vazirani. Quantum complexity theory. SIAM Journal of Computing, vol. 5(26),
pp. 1411–1473, 1997.
52

Introduccion A La Computacion Cuantica

Cargado por

Copyright:

Formatos disponibles

Introduccion A La Computacion Cuantica

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Introduccion A La Computacion Cuantica

Cargado por

Copyright:

Formatos disponibles

Introducción a la computación cuántica

Salvador E. Venegas Andraca

2.1 Campo, espacio vectorial, producto interno y norma

Si ∀ |ui, |vi, |wi ∈ V y ∀ k, l ∈ F se satisfacen los axiomas 1 al 10 que se presentan enseguida

1) |ui, |vi ∈ V ⇒ |ui + |vi ∈ V

Observación. El elemento cero 0 ∈ V es ortogonal a todo elemento en V.

Definición 2.6. Subespacio. Sea W un subconjunto de un espacio vectorial V. W se denomina

a) Si |ui, |vi ∈ W ⇒ |ui + |vi ∈ W

se denominará combinación lineal de elementos de S.

Definición 2.9. Generación de un espacio vectorial. Sean V un espacio vectorial y S = {|vii ∈

1) S = {1, x1 , x2 , . . . , xn } genera a Pn (x).

Definición 2.10. Independencia y dependencia lineal. Sean V un espacio vectorial, S un conjunto

tiene por lo menos una solución, a saber:

Si la ecuación (2) es la única solución de la ecuación (1) ⇒ S es un conjunto linealmente indepen-

a) {|v1 i, |v2 i, . . . , |vn i} es un conjunto linealmente independiente, y

Entonces, |x1 i, |x2 i, . . . , |xn i son linealmente independientes ⇔ det(A) 6= 0.

2.3 Espacios de Hilbert

Definición 2.17. Notación de Dirac. Sea H un espacio de Hilbert ⇒

2) T̂ (|ψi − |φi) = T̂ |ψi − T̂ |φi

Definición 2.20. Núcleo de un operador lineal. Sea T̂ : V → W un operador lineal. Definimos al

N(T̂ ) = {|ψi ∈ V | T̂ |ψi = 0}

Teorema 9. Sea Sea T̂ : V → W un operador lineal ⇒ el núcleo de T̂ es un subespacio de V.

Luego, de acuerdo al teorema (1), N(T̂ ) es un subespacio de V.

En otras palabras, si suponemos la existencia de un operador lineal T̂ : V → W, una base

2.4.2 Representaciones matriciales de operadores lineales

Combinando las Ecs. (5 y 3) encontramos que

T̂ |ψi = np=1 βp T̂ |ep i = β1 T̂ |e1 i + β2 T̂ |e2 i + . . . + βn T̂ |en i =

β1 k=1 αk1 |wk i + β2 m

T̂ |ψi = np=1 βp T̂ |ep i

(β1 α11 + β2 α12 + . . . + βn α1n )|w1i+

T̂ |ψi = np=1 βp T̂ |ep i = m

T̂ (|ei i) = |wi i, i ∈ {1, . . . , r}

Ejemplos de operadores en notación de Dirac y en representación matricial.

Comenzamos por definir los operadores de Pauli usando notación de Dirac:

2.5 Operadores usados en computación cuántica

Definimos enseguida dos tipos de operadores muy usados en mecánica cuántica.

2.5.1 Operadores hermitianos

Ejercicio 2.11. Demuestre que los operadores de Pauli son hermitianos.

Observe que , de acuerdo a los Teoremas (13) y (14),

Luego, P̂ es hermitiano de acuerdo a la Def. (2.22).

|0ih0| es el operador de proyección al subespacio generado por |0i

Definición 2.24. Operador unitario. Sea H un espacio de Hilbert y Û : H → H un operador lineal.

Ejercicio 2.12. Demuestre lo siguiente:

Definición 2.25. Operador normal. Sea H un espacio de Hilbert y Â : H → H un operador lineal.

T̂ |ψi = λ|ψi (11)

E(λ) = {|ψi ∈ V | T̂ |ψi = λ|ψi}

2.6.1 Polinomio caracterı́stico

ˆ − T̂ |ψi = 0 ⇒ (λIˆ − T̂ )|ψi = 0

Â|ψi = λ|ψi (14)

A|ψi = λ|ψi, i.e.

(λI − T )|ψi = 0 (15)

Observación. Puesto que det(kA) = k n det(A), donde A ∈ Mn (C) ⇒ c(λ) = det(λI − T ) =

Definición 2.29. Polinomio caracterı́stico. Al desarrollar c(λ) se obtiene un polinomio en λ, de-

Es posible demostrar que, si la matriz T es de orden n ⇒ su polinomio caracterı́stico es de grado

Teorema 15. Sea A ∈ Mn (C). Si se consideran mutiplicidades A tiene exactamente n eigenvalores.

Teorema 16. Sea T ∈ Mn (C) y λ un eigenvalor de A. El conjunto E(λ), el eigenespacio de λ, es un

El recı́proco del Teorema (17) también es cierto.

Los teoremas (17,18) se resumen de la siguiente manera:

2.7 Descomposición espectral