PDF de programación - Brevísima Introducción a la Computación Cuántica

Brevísima Introducción a la Computación Cuántica

Alejandro Díaz Caro†, Julián Samborski Forlese‡

Departamento de Ciencias de la Computación - FCEIA - UNR

†[email protected], ‡[email protected]

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 1

Introducción

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 2

¿Qué es?

La computación cuántica es un paradigma de computación
distinto al de la computación clásica.
Se basa en el uso de qubits en lugar de bits, y da lugar a
nuevas puertas lógicas que hacen posibles nuevos
algoritmos.
Una misma tarea puede tener diferente complejidad en
computación clásica y en computación cuántica, lo que ha
dado lugar a una gran expectación, ya que algunos
problemas intratables pasan a ser tratables.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 3

Algo habrán hecho...

• 1936 Alan Turing inventa la MT para demostrar que

existían problemas matemáticos que no eran computables.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 4

Algo habrán hecho...

• 1936 Alan Turing inventa la MT para demostrar que

existían problemas matemáticos que no eran computables.
Ley de Moore ⇒ Dismunición en tamaño, mayor poder de
cómputo. Sin embargo, los problemas que requieren
recursos exponenciales siguen causando problemas.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 4

Algo habrán hecho...

• 1936 Alan Turing inventa la MT para demostrar que

existían problemas matemáticos que no eran computables.
Ley de Moore ⇒ Dismunición en tamaño, mayor poder de
cómputo. Sin embargo, los problemas que requieren
recursos exponenciales siguen causando problemas.
• 1982 Richard Feynman sugiere que simular sistemas

cuánticos necesariamente requiere recursos
exponenciales. Sin embargo la naturaleza es capaz de
simularlo de manera eficiente!

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 4

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

Algo habrán hecho...

• 1936 Alan Turing inventa la MT para demostrar que

existían problemas matemáticos que no eran computables.
Ley de Moore ⇒ Dismunición en tamaño, mayor poder de
cómputo. Sin embargo, los problemas que requieren
recursos exponenciales siguen causando problemas.
• 1982 Richard Feynman sugiere que simular sistemas

cuánticos necesariamente requiere recursos
exponenciales. Sin embargo la naturaleza es capaz de
simularlo de manera eficiente!

• 1985 David Deustch describe el primer modelo para una

Quantum Turing Machine basada en la utilización de datos
y control cuánticos.

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 4

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

Algo habrán hecho...

• 1936 Alan Turing inventa la MT para demostrar que

existían problemas matemáticos que no eran computables.
Ley de Moore ⇒ Dismunición en tamaño, mayor poder de
cómputo. Sin embargo, los problemas que requieren
recursos exponenciales siguen causando problemas.
• 1982 Richard Feynman sugiere que simular sistemas

cuánticos necesariamente requiere recursos
exponenciales. Sin embargo la naturaleza es capaz de
simularlo de manera eficiente!

• 1985 David Deustch describe el primer modelo para una

Quantum Turing Machine basada en la utilización de datos
y control cuánticos.

• 1993 Charles Bennet y otros cieníficos de IBM diseñaron el

experimento de Teleportación.

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 4

Algo habrán hecho... (cont.)

• 1994 Peter Shor describe un algoritmo cuántico para

factorizar números que es exponencialmente más rápido
que cualquier algoritmo clásico conocido. El potencial de
ese algoritmo atrajo mucha inversión de entes estatales y
privados.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 5

Algo habrán hecho... (cont.)

• 1994 Peter Shor describe un algoritmo cuántico para

factorizar números que es exponencialmente más rápido
que cualquier algoritmo clásico conocido. El potencial de
ese algoritmo atrajo mucha inversión de entes estatales y
privados.

• 1998 Isaac Chuang dirige el grupo de Berkeley que

desarrolla la primera computadora cuántica de 1 qubit.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 5

Algo habrán hecho... (cont.)

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

• 1994 Peter Shor describe un algoritmo cuántico para

factorizar números que es exponencialmente más rápido
que cualquier algoritmo clásico conocido. El potencial de
ese algoritmo atrajo mucha inversión de entes estatales y
privados.

• 1998 Isaac Chuang dirige el grupo de Berkeley que

desarrolla la primera computadora cuántica de 1 qubit.

• 2001 Un grupo de IBM desarrolla una computadora

cuántica capaz de controlar 7 qubits, con ella prueban el
algoritmo de Shor factorizando el número 15.

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 5

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

Algo habrán hecho... (cont.)

• 1994 Peter Shor describe un algoritmo cuántico para

factorizar números que es exponencialmente más rápido
que cualquier algoritmo clásico conocido. El potencial de
ese algoritmo atrajo mucha inversión de entes estatales y
privados.

• 1998 Isaac Chuang dirige el grupo de Berkeley que

desarrolla la primera computadora cuántica de 1 qubit.

• 2001 Un grupo de IBM desarrolla una computadora

cuántica capaz de controlar 7 qubits, con ella prueban el
algoritmo de Shor factorizando el número 15.

• Diciembre de 2005 Rainer Blatt y su grupo de Innsbruck

realizan una computadora cuántica de 8 qubits (1 qubyte) y
Daniel Stick y su grupo de Michigan logran el primer chip
capaz de controlar un qubit.

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 5

Algunos conceptos

Unidad mínima de información clásica: BIT.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 6

Algunos conceptos

Unidad mínima de información clásica: BIT.

Unidad mínima de información cuántica: QuBIT.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 6

Algunos conceptos

Unidad mínima de información clásica: BIT.

Unidad mínima de información cuántica: QuBIT.

Un qubit puede existir como 0, como 1 o como una
superposición de 0 y 1. Esto permite que se puedan
realizar cómputos sobre ambos valores a la vez.

Introducción
• ¿Qué es?
• Algo habrán hecho...
• Algo habrán hecho...

(cont.)

• Algunos conceptos
• ¿Cómo se piensa

cuánticamente?

• Algoritmos Cuánticos
• Algoritmos Cuánticos

(cont.)

• Implementaciones???
• Lenguajes Cuánticos

Qubits

Algo de Criptografía

A Díaz Caro, J. Samborski Forlese

Introducción a la Computación Cuántica sn - p. 6

Algunos conceptos

Unidad mínima de información clásica: BIT.

Unidad mínima de información