Epistemowikia
Revista «Hiperenciclopédica» de Divulgación del Saber
Segunda Época, Año IX
Vol. 8, Núm. 1: de enero a marzo de 2014
Epistemowikia es parte de
Logotipo de CALA Virtual
CALAALA | Communitas | Evolvere
Editio | Epistemowikia | Exercitatio | Fictor | Flor
Epistemowikia no se hace responsable ni se identifica necesariamente con el contenido ni las opiniones expresadas por sus colaboradores.
La Universidad de Extremadura no se hace en ningún caso responsable de los contenidos publicados en Epistemowikia.
La Asociación Conocimiento Comunal (CONOMUN) no se hace en ningún caso responsable de los contenidos publicados por terceros.

Inicio | La revista | Índex | Hemeroteca | Búsquedas | Quiénes somos | Contacto | Publica

Computación cuántica

De Epistemowikia

Tabla de contenidos

Introducción

¿Qué es la computación cuántica?

La computación cuántica nace con el objetivo de combinar las propiedades de la física y las ciencias computacionales para solucionar problemas de computación.

La base teórica de la computación tradicional está basada en saber usar unos y ceros para resolver problemas. Se utilizan los transistores como elemento principal, de forma que las diferencias de energía que existan en él son unos y ceros lógicos. Sin embargo, en la computación cuántica, se reduce la escala del elemento primario, lo que conlleva una serie de efectos cada vez más obvios.

Una parte básica de la computación cuántica es estudiar las consecuencias de dichos efectos en la computación tradicional. Dichos estudios fueron los que llevaron a los científicos a emplearlos para sacar provecho, de tal manera que físicos y computólogos (principalmente teóricos) comenzaron a crear diversas hipótesis basadas en la afirmación de que a partir de las leyes de la mecánica cuántica se podrían desarrollar nuevos planteamientos en la teoría y procesamiento de la información. Resulta obvio pensar que para poder aplicar estas teorías cuánticas necesitaremos obtener una computadora cuántica.

Hasta hoy día, los componentes de hardware han estado siendo miniaturizados hasta llegar a conseguir nano circuitos. Sin embargo, vamos a alcanzar un punto en el que esta miniaturización sea tal que no se pueda avanzar más en este aspecto. En ese momento tendrá que entrar en juego la mecánica cuántica.

Introducción histórica

En las décadas de 1970 y 1980, algunos teóricos como Richard Feynmann, (California Institute of Technology, de Pasadena); Paul Benioff, (Argonne National Laboratory, de Illinois); David Deutsch, (Universidad de Oxford, en Inglaterra), y Charles Bennett, (T.J. Watson Research Center de IBM en Nueva York), propusieron el concepto de las computadoras cuánticas, obteniendo como respuesta las dudas de muchos científicos respecto a que alguna vez ese tipo de computadoras pudieran llegar a resultar realmente prácticas.

Sin embargo, Peter Shor (AT & T Research) describió en 1994 un algoritmo cuántico, diseñado para realizar la factorización de números grandes, de una forma exponencialmente más rápida que las computadoras convencionales (hasta el punto de poder llegar a hacer saltar la seguridad de muchos criptosistemas de clave pública). Esto animó a muchos científicos a intentar explotar las capacidades de las computadoras cuánticas. Desde entonces, varios grupos de investigación de todo el mundo han logrado progresos realmente importantes en este ámbito.

Isaac L. Chiang (IBM y Gershenfeld), uno de los experimentalistas cuánticos más importantes del mundo, y Mark G. Kubinec (Universidad de Berkeley), se lanzaron a construir un ordenador cuántico simple que fuera capaz de ejecutar un algoritmo de búsqueda, denominado “de Grover�? en honor a su creador. En 1998, en la Universidad de California en Berkeley, consiguieron crear bits cuánticos a partir de átomos de hidrógeno y cloro procedentes del cloroformo. Tras alinear los núcleos, obligaban a las moléculas a comportarse como ordenadores, leyendo los resultados mediante resonancia magnética. Utilizaba 5 bits cuánticos (o qubits), y la factorización de dicho algoritmo es el algoritmo más complejo que se ha podido demostrar hasta el momento usando una computadora cuántica.

La División de Investigación de IBM Research ha aportado además múltiples teorías cuánticas. Sus científicos, por ejemplo, fueron pioneros en criptografía y comunicaciones cuánticas, así como en metodologías de corrección de errores. Desde aquí se promulgaron los cinco criterios básicos para la realización de un computadora cuántica eficiente:

a) Un sistema físico de escala flexible con qubits bien caracterizados.

b) Capacidad de inicializar el estado de un qubit.

c) Tiempos de descoherencia más largos que el tiempo de operación de la puerta cuántica.

d) Un conjunto universal de puertas cuánticas.

e) La capacidad de medir qubits específicos.

Características

Mientras que en la computación que usamos hoy en día, cada bit puede presentarse en estados alternativos y discretos a la vez, en la computación cuántica cada bit llega a estar en múltiples estados en un mismo instante. Gracias a esto, podremos llegar a reducir exponencialmente el tiempo empleado por los algoritmos actuales.

Existe una arquitectura muy parecida a las que tenemos actualmente, que ha tenido mucho éxito en el ámbito teórico y cuya realización depende de la futura implementación de una computadora cuántica.

Los científicos cuánticos han logrado enormes avances teóricos al conseguir demostrar que es factible la reducción drástica de los recursos computacionales que se requieren en la ejecución de algoritmos, algunos de los cuales requieren muchísimo poder de cómputo en las computadoras más avanzadas que existen hoy en día. Algunos ejemplos desarrollados teóricamente con mucho éxito son la anteriormente mencionada búsqueda de factores de números primos, o la búsqueda en bases de datos no ordenadas.

La base teórica de la computación cuántica se basa en las interacciones del mundo atómico, así como en futuras implementaciones de computadoras cuánticas, obteniéndose por el momento resultados muy alentadores. Además, es uno de los métodos con mayor futuro debido a que ofrece una gama de prestaciones enormes, pudiendo llegar a duplicar los dispositivos de almacenamiento más avanzados.

Para entender esto último hemos de tener en cuenta que los qubits pueden representar cuatro números al mismo tiempo (en lógica binaria sólo se permite un 1 o un 0 para un único bit), de ahí esta duplicación de capacidad, no sólo de las memorias o dispositivos de almacenamiento secundario, sino también del resto de componentes como microprocesadores, tarjetas de sonido, de video… lo que conllevaría además un aumento de la velocidad de estos microprocesadores.

El qubit

Es el elemento básico de la computación cuántica. Su nombre viene dado por sus siglas: quantum bit, y representa ambos estados (0 y 1) simultáneamente, dos estados ortogonales de una subpartícula atómica. Un vector de n qubits representa a la vez 2n estados, de forma que un vector de dos qubits representaría los estados 00, 01, 10 y 11. Con dos estados discretos distintos, cualquier sistema cuántico puede servir como qubit, un spin de electrón que apunta arriba o abajo, o un spin de fotón con polarización horizontal o vertical.

Compuertas cuánticas

Las compuertas lógicas son semejantes a las que utilizamos en la actualidad, con la diferencia de que éstas trabajan sobre qubits.

Entanglement

Debido a este fenómeno, si dos partículas son generadas en el mismo proceso, permanecen relacionadas entre sí, (por ejemplo, la desintegración en un positrón y un electrón), de tal forma que no se pueden describir de forma aislada los subsistemas que forman. En el momento en el que una de las dos partículas cambia de estado, repercute en la otra. Esto se produce al intentar medir el estado de una de ellas.

Teletransportación cuántica

Fue descrita por Stean como “la posibilidad de transmitir qubits sin enviar qubits�?. Mientras que en la computación tradicional para transmitir bits estos son clonados/copiados y posteriormente enviados por diversos medios de transmisión… en la computación cuántica esto no es posible.

A la hora de enviar un qubit, el receptor no llegará a saber cuál era su estado anterior con certeza, pues como hemos comentado anteriormente, cualquier intento de medirlo produce una modificación en dicho estado, de tal manera que se pierde, siendo ya imposible recuperarlo. Sin embargo, podemos solucionar este problema a través del fenómeno del “entanglement�?. Para ello, lo que se hace es enredar los qubits del emisor y el receptor, de tal modo que el qubit del emisor se transmite desapareciendo del emisor, y llegando al receptor el qubit teletransportado.

Dicha teletransportación se produce por el denominado efecto EPR, mediante el cual tras enredar los dos qubits en el emisor (junto al bit cuántico original que deseamos transmitir) y receptor, y posteriormente separarlos, al realizar la lectura del estado original, estos cambian su estado a otro cualquiera, de tal manera que la información es enviada al receptor, que la utiliza para tratar su bit, de forma que éste acaba siendo idéntico al original.

El paralelismo cuántico

Gracias a la superposición cuántica, utilizando puertas lógicas cuánticas, podemos llegar a conseguir un paralelismo, en cálculos, exponencial. Esto es debido a que a diferencia de los bits convencionales, los bits cuánticos pueden existir en un estado de superposición.

Arquitectura cuántica

Límites de los circuitos electrónicos

Con el paso de los años, la densidad de los circuitos electrónicos ha aumentado de forma imparable sobre todo debido a la miniaturización del tamaño de los componentes. Esto ha llevado a los físicos a plantearse si existe un límite al proceso de miniaturización, viendo la solución a éste cuestión en la mecánica cuántica.

En los dispositivos actuales la corriente obedece a la física clásica. El gran torrente de electrones que la componen hace que se tienda a considerarla como un fluido homogéneo, más si tenemos en cuenta que las distancias entre corrientes son demasiado grandes para que suceda nada ajeno a la teoría newtoniana. Aun así, tras pasar un tamaño mínimo los electrones muestran su carácter individual y el comportamiento cuántico propio de las partículas atómicas de forma que, sin importar los aislantes que se utilicen, algunos electrones se moverán, gracias al "efecto túnel", entre las distintas líneas de corriente, dándose lugar a fugas que interfieren en el correcto funcionamiento del circuito. Esto hace que, de momento, el uso de la mecánica cuántica en los microcircuitos no sea muy productivo.

Por otra parte se habla de algunos dispositivos atómicos y moleculares basados en nuevas tecnologías: memorias basadas en átomos excitados individualmente y medidos por laser, nanomáquinas que actuan como pequeñas calculadoras agregadas a moléculas… La reducción de tamaño de estos dispositivos ofrece una mayor densidad de información y velocidad, aunque no son aquellos en los que se basa la computación cuántica.

El secreto de la computación cuántica radica en la lógica implementada en los dispositivos, no en su estructura física. Esta lógica no se basa en la física newtoniana clásica, sino que usa propiedades cuánticas. A fin de realizar una implementación cuántica correcta, se deben cumplir cinco preceptos:

• Es necesario un sistema de qubits.

• Estos deben ser direccionables individualmente, interactuando entre si para formar compuertas lógicas de propósito general.

• Se debe poder inicializar las compuertas.

• Se debe tener la posibilidad de extraer los resultados computacionales.

• Es necesario un tiempo de coherencia duradero.

La arquitectura de estos computadores es similar a la de las computadoress tradicionales, aunque incluyendo algunos elementos de la computación cuántica. Oskin et al propone una arquitectura formada por una ALU cuántica, memoria cuántica, y un planificador dinámico.

ALU cuántica

Sus funciones principales son la ejecución de operaciones cuánticas y la corrección de errores. Prepara los datos cuánticos antes de ejecutar cualquier compuerta lógica mediante la aplicación de varias transformaciones cuánticas básicas.

La ALU realiza la tarea de corrección de errores mediante esta secuencia de operaciones, consumiendo este proceso estados auxiliares adicionales empleados para la verificación de paridad. Además, la ALU utiliza hardware especializado que provee estados elementales a fin de producir los estados auxiliares adicionales.

Memoria cuántica

En el tipo de computadoras que tratamos, la memoria es un elemento vital. A fin de que su funcionamiento no de lugar a fallos, Oskin et al idearon una unidad especial situada en cada bando de memoria que se encarga de actualizarlo. Esta unidad actualiza periódicamente los bits individuales mediante algoritmos de detección y corrección de errores.

Tele transportadora de código

La teletransportadora de código de memoria a ALU ofrece nuevos usos a la teletransportación cuántica convencional, proporcionando un mecanismo general para ejecutar operaciones de forma simultánea a la vez que se transportan los datos cuánticos.

Esto se usa para corrección de errores en los codificadores de código de origen y destino. En ese momento. el emisor y el receptor ejecutan qubits lógicos equivalentes en la operación de teletransportación en cada terminal del par "enredado" (entangled).

Planificador dinámico

Un procesador clásico dedicado, el elemento principal del planificador dinámico, fue propuesto por Oskin et al. Su funcionamiento comienza con la ejecución de un algoritmo de planificación dinámico, parte de operaciones cuánticas lógicas junto con construcciones clásicas de control de flujo y las traduce dinámicamente a operaciones individuales de qubits físicos. La definición de computadoras cuánticas con un mayor nivel de aceptación es la expuesta por Beth, acogida de forma positiva por la mayoría de la comunidad científica. Este la concibe como un sistema de circuitos cuánticos que actua en un espacio complejo 2n-dimensional de Hilbert, un espacio de estados. El circuito es una secuencia de conversiones unitarias seguido por una medición. Las conversiones, denominadas compuertas cuánticas, son controladas por un computador convencional. El espacio de estados de una computadora cuántica posee una estructura similar a aquella de los espacios de un vector Hermitian. Esto permite la superposición simultánea de estados básicos ortogonales (los cuales corresponden a estados clásicos "0" y "1") con posibilidad de interferencia constructiva y destructiva entre diferentes rutas de computación. Este principio permite el uso de los estados entrelazados.

Problemas e invonvenientes

La implementación de un sistema que realice cálculos cuánticos es una tarea complicada, independientemente del sistema físico que usemos. Tenemos en contra la influencia del medio ambiente alrededor del sistema, sobre todo debido a dos efectos, el decaimiento y la decoherencia. El primero consiste en la fuga de energía desde el sistema al medio, forzando a los estados de energía más alta a evolucionar emitiendo energía hacia los estados de mínima energía, produciéndose la mezcla inicial de estados y convirtiéndose en una mezcla de sólo los estados de menor energía. El segundo efecto, la decoherencia, es un fenómeno más sutil que no implica intercambio de energía con el medio ambiente, sino perdida de información. Este efecto es la razón de que los objetos macroscópicos a nuestro alrededor no presenten el comportamiento dictado por la mecánica cuántica, ya que el medio elimina la mezcla de estados típica de la física cuántica como si se realiza continuamente una serie de medidas sobre el sistema. Debido a que la mezcla de estados es la que da potencia a la computación, cualquiera de estos dos procesos son nefastos para la consecución del cálculo. La solución a estos problemas pasa por mantener el sistema tan aislado de la influencia externa como sea posible mientras dure el cálculo.

Algoritmos y aplicaciones

Clasificación de problemas

La definición que le podríamos asignar a la ciencia de la computación es: disciplina que se encarga de la búsqueda de algoritmos para la resolución de problemas, con independencia del hardware en el que se implementen estos algoritmos. Ya intentamos darle una definición a algoritmo en una de las clases de Lógica y Computabilidad, fundamentalmente lo podemos ver como una receta (una serie de pasos ordenados y concretos) con la que cocinamos los datos de entrada con el fin de obtener una solución a nuestra pregunta.

Para comprender las ventajas que proporciona la computación cuántica, debemos partir de si el problema que nos estamos planteando es posible hacerlo y cuánta dificultad conlleva, antes de pasar a cómo hacer las cosas. Primeramente realizaremos una clasificación basada en el proceso de resolución, de tal forma que obtendremos la solución en un número variable de pasos, dependiendo de la dificultad del problema. En cuanto al tiempo que le llevará no dependerá únicamente de la dificultad del problema, sino también de la información que proporcionan los datos de entrada. Veamos a continuación dos algoritmos expresados mediante una fórmula que calcula el número de pasos necesarios para la obtención de la solución mediante la información proporcionada por los datos iniciales.

El primer algoritmo que comentaremos es el de multiplicación de dos números (algoritmo de tipo polinómico). Donde utilizando el paso base de multiplicación de números de una cifra, cuando tenemos una entrada de C cifras, el número de pasos necesarios para calcular la solución será de C2, T(C) = C2, como la fórmula es un polinomio decimos que este es un problema de tipo Polinómico o de tipo P.

El segundo algoritmo es el de factorización de un número (algoritmo de tipo no polinómico). Cuya objetivo es la de encontrar todos y cada uno de los factores primos de un número (útil para la fabricación de claves y métodos criptográficos). Para ello, dado un número N dividiremos por todos los enteros entre 2 y la raíz del número (N1/2). Esta estrategia, que es la más directa pero no la mas rápida, implica realizar un número de pasos igual a T=N1/2. Expresándolo en función de la cantidad de cifras C del número N, y usando el hecho de que N≈10C, obtenemos por tanto, T(C)=10C/2. Donde podemos observar una diferencia fundamental respecto al algoritmo anterior, la función encargada de expresar el número de pasos necesarios es una exponencial, por ello decimos que este tipo de problemas se denomina no polinómico o exponencial (tipo NP o EXP).

La propiedad que diferencia a los polinomios y las exponenciales la usaremos como criterio de clasificación, es decir, la velocidad con la que crecen, siempre es mucho más rápida en una exponencial que una potencia, sin importar lo grande que sea el exponente. Aunque puede que inicialmente los valores de una potencia sean mayores que los de una exponencial, llegará un punto en que esta tendencia cambiará.

Por tanto, ante la entrada de datos suficientemente grandes, un algoritmo P requerirá menos tiempo que uno NP, considerando que el problema resuelto por éste último es de mayor dificultad. Podríamos llegar a pensar que esto no es tan grave en estos tiempos de potentes ordenadores de procesamiento en paralelo. Pero esto no es suficiente ya que el uso de varios procesadores solamente lograría reducir el tiempo en un factor igual al número de procesadores. ¿Qué beneficios podemos obtener tratando este problema mediante la física cuántica? Como se ha comentado anteriormente, al basarnos en el concepto de qubit no se restringe a que esté en un estado único y definido como lo haría el bit, puede estar a la vez en el estado 1 y en el 0, contribuyendo cada uno de ellos con un factor distinto. Un sistema que conste de n qubits (registro cuántico), tendremos una mezcla de 2n estados clásicos. De tal forma que cuando se realice una operación sobre este registro, se operará simultáneamente sobre todos esos estados clásicos de los que se compone. Este paralelismo masivo es lo que permite la potencia de la computación cuántica. Los algoritmos que hacen uso de esta característica se denominan QP (Quantum Polynomical o polinómico cuántico).

Algoritmos cuánticos

Los primeros problemas que se intentaron dar solución mediante la computación cuántica, aunque sencillos, permitieron comprobar las diferencias que existen entre los modelos de computación clásico y cuántico. Posteriormente aportaron técnicas algorítmicas que permitieron obtener algunos algoritmos importantes como el de Shor o el de Grover. Comentemos cada uno de ellos.

Algoritmo de Shor

La computación cuántica ofrece, además de su enorme potencial operativo, una nueva forma de cálculo basada en principios cuánticos. En el año 1994, Peter Shor ideó un nuevo algoritmo destinado a computadores cuánticos que permitía factorizar numeros grandes en factores primos en un tiempo mucho menos que los computadores tradicionales. El algoritmo de Shor puede ser estructurarlo en dos fases, la primera que explota el paralelismo masivo de la computación cuántica para calcular en una sola iteración todas las potencias modulares, y la segunda, realizando interferencias destructivas para hallar el periodo. Si desea ver una descripción mas formal de los pasos a seguir diríjase a Algoritmo de Shor

Algoritmo de búsqueda de Grover

En 1997, Lov K. Grover presentó otro algoritmo de especial interés orientado en el camo de las rutinas de ordenación. Se trata de un algoritmo muy interesante, ya que puede ser empleado para localizar de manera eficiente un determinado elemento en una base de datos no estructurada, como para resolver problemas en los que es muy complicado encontrar una solución, pero a la vez muy sencillo probar posibles candidatas. Aclaremos el concepto de “base de datos no estructurada�?. Una base de datos estructurada la podemos ver como una guía telefónica en la que dado el nombre del titular de la línea telefónica, y haciendo uso de la organización alfabética de la guía, obtenemos el número de teléfono. Una base de datos no estructurada, siguiendo con el mismo ejemplo, sería aquella en la que quisiéramos encontrar el nombre del titular de la línea a través del número de teléfono. Dicha tarea llevaría a un algoritmo clásico evaluar una media de N/2 veces (N en el peor de los casos), mientras que al algoritmo de Grover solamente le requeriría (N1/2). Por último comentar que el algoritmo de Grover es un algoritmo óptimo, esto es, no existe ningún otro algoritmo cuántico de menor orden que pueda resolver el problema.

Criptografía cuántica

La criptografía (del griego κ�?υπτός (kryptos), "oculto", y grafía, "escribir", escritura oculta) y según la R.A.E: arte de escribir con clave secreta o de un modo enigmático. Actualmente son varios de los métodos criptográficos usados que requieren que los comunicantes se proporcionen entre sí varias claves de forma segura, siendo en este intercambio donde existe mayor vulnerabilidad.

Nacida en los años 80, la criptografía cuántica realiza el intercambio de claves mediante fotones individuales enviados de emisor a receptor por fibra óptica. En este punto, señalamos la diferencia respecto a los sistemas actuales, ya que mediante el teorema de no-clonación, nos es imposible clonar la información transmitida sin conocer a priori el estado cuántico de la luz. De tal forma que ante una intrusión que trate de capturar el mensaje enviado, solamente lo podrá destruir, sin posibilidad de reproducirlo, perturbando la comunicación y dando a conocer a los interlocutores dicha intrusión.

Un ejemplo de lo que sería la vulnerabilidad de los sistemas criptográficos actuales ante las ventajas que ofrece la computación cuántica, sería el sistema criptográfico de clave pública RSA; los donde los mensajes son enviados usando el algoritmo RSA, cuyo funcionamiento se basa en el producto de dos números primos grandes elegidos al azar que forman la clave de descifrado. De tal forma que la seguridad de dicho algoritmo radica es que no existen métodos de resolución rápidos para la factorización de dichos números, cosa que mediante la computación cuántica este cálculo podría realizarse en segundos.

Proyección de futuro

El conocimiento cada vez mejor de los sistemas cuánticos produce cada vez más beneficios, haciendo que poco a poco veamos más cercano el momento en que podamos crear computadores cuánticos al mismo ritmo que los convencionales. Existen diversas propuestas para ello, aunque la mayoría sólo son teorías sin evidencia experimental. Una propuesta que cuenta ya con el respaldo de la experiencia es la de un conjunto de iones atrapados en una trampa electromagnética. Cada ión almacena un qubit y las operaciones aritméticas se realizan iluminando selectivamente los iones con luz láser. Otra propuesta trata de utilizar propiedades magnéticas de los espines nucleares de los átomos de una molécula. La tecnología actual no permite realizar experimento alguno de esta propuesta, por lo que se seguirá desarrollando sobre papel. Otra corriente de experimentos esta encaminada a construir puertas lógicas con fotones.

El hecho experimental que más esperanzas ha dado a la computación cuántica se produjo cuando un grupo de investigadores, Isaac L. Chiang de IBM, y Gershenfeld y Kubinec de la Universidad de Berkeley, consiguieron crear qubits a partir de los núcleos de átomos de hidrógeno y cloro del cloroformo. Con esta estructura lograron implementar una búsqueda (algoritmo de Grover de búsqueda), utilizando técnicas de resonancia magnética nuclear. El hecho de que esa búsqueda fuese realizada por un ordenador cuántico basado en qubits incrementa enormemente su eficiencia, debido a la estructura implícita en paralelo de la computación cuántica.

Para terminar, los últimos estudios en el mundo de las partículas mesoscópicas (situadas entre las microscópicas y las macroscópicas) relevan que una molécula, el Mn-12-acetato, puede llegar a ocupar un lugar importante en la creación de un ordenador cuántico. Peter Shor, experto de los laboratorios AT&T, opina que será posible construir un ordenador de 30 qubits dentro de una década. Esto supondría un paso importante para crear ordenadores más avanzados con potencias altísimas.

Autores

Trabajo realizado por:

  • Eduardo Alvarado Sánchez
  • Javier Corral García
  • Eduardo de la Montaña Gutiérrez

Artículos Relacionados

Teoría de la computación cuántica

Licencia





Los contenidos de esta página están publicados bajo los términos de la licencia Atribución, compartir bajo la misma licencia 2.5 de Creative Commons, conocida como CC-By-Sa.
El texto legal puedes verlo pinchando aquí
y un resumen en castellano pinchando aquí.


Herramientas personales