Home > Resumen > Computación cuántica: solución milagrosa?

Computación cuántica: solución milagrosa?

A pesar de lo que muchas personas creen la computación cuántica promete grandes soluciones, pero solo es eso -promesas- por ahora. La única manera de poder ver realmente lo que QC ofrece es estudiar las clase de complejidad en la que se encuentra.

La teoría de la complejidad computacional se encarga de estudiar los recursos (tiempo y espacio) necesarios para la solución de los problemas, tanto en el modelo clásico como en el cuántico, y como clasificarlos. Una clase de complejidad es el conjunto de problemas con características similares en cuanto al consumo de recursos para su resolución.

A pesar que se tienen sospechas que la computación cuántica es mucho más poderosa que la computación clásica por algunos ejemplos, como el algoritmo de factorización de Shor, estas aún son suposiciones. Ya que es posible que las computadoras cuánticas no sean más poderosas que las clásicas, de manera que cualquier problema que se pueda resolver en una computadora clásica se puede resolver en una computadora cuántica (esto también se ve por la implicación de la máquina de Turing cuántica, ya que puede emular una máquina Universal de Turing por lo que puede resolver cualquier problema que una computadora clásica pueda resolver).

Las clases más importantes son las denominadas P y NP. La clase P es el conjunto de problemas que se pueden resolver en tiempo polinomial en una computadora clásica (Máquina universal de Turing). Y la clase NP es el conjunto de problemas que se pueden revisar en una computadora clásica, pero no encontrar las soluciones. Existen subclases de la clase NP, por ejemplo esta el NP-completo que son aquellos problemas que no tienen solución en una computadora clásica.

Se puede ver que P esta contenido en NP, ya que cualquier problema que se pueda resolver puede también verificar las soluciones para el problema. Uno de los grandes problemas que han tenido los científicos es identificar si P y NP son distintos, es decir, si existen problemas en NP que no puedan estar en P. Si existe un algoritmo para resolver problemas NP-completos entonces podriamos utilizar alguna variante de este para resolver cualquier otro problema de la misma naturaleza. Por consiguiente, si en realidad P es un subconjunto de NP, entonces no existiría solución alguna en P para los problemas que sean NP-completos.

Es por esto que se cree que la computación cuántica puede ser más poderosa que la computación clásica. Como existe una solución eficiente a un problema que se cree es NP-completo, el algoritmo de factorización de Shor, entonces se tendrían soluciones a cualquier otro problema. Sin embargo, nadie a demostrado que la factorización de algún número sea un problema NP, pero nadie tampoco a demostrado lo contrario, por lo que existen personas que creen que es posible que la computación cuántica tiene esperanzas.

Clases de complejidad

Fuente: [1] pag. 42

Otra clase importante es la llamada PSPACE, esta clase contiene a los problemas que requieren poco espacio para resolver el problema pero muchisimo tiempo para poder hacerlo. Además, se cree que es mucho más grande que P y NP. Entonces, se crea una clase para los problemas que pueden ser resueltos a través de una computadora cuántica llamada BQP. Se sospecha, por todo lo que he expuesto, que podría contener a P y a NP, sin embargo al momento de trabajar este tipo de problemas pueden surgir otros que no se encuentren en NP, de modo que existiran problemas que aún no podrán ser resueltos eficintemente con una computadora cuántica por lo que tendremos que buscar y cambiarnos de paradigma nuevamente!!!.

Referencias

  1. M.A. Nielsen, I.L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press ( 2001 )
  2. E. Kashefi, C. Moura, On The Complexity of Quantum Languages, Oxford University ( 2008 )
  1. April 15, 2008 at 8:34 pm

    Interesante lo de las maquinas de turing.

  2. August 25, 2010 at 12:40 am

    creo que la comunidad cientifica, y la humanidad en general, deben enfocarse en este campo. Cuando la ciencia descubra los secretos acerca de como funciona la paradoja EPR, el mundo que conocemos va a cambiar definitivamente, será un antes y un despues.
    Al margen de las nuevas y extremadamente formidables aplicaciones que le darán al uso de la teletransportación de información, surgirán nuevos descubrimientos relacionados que abrirán un nuevo horizonte a la raza humana.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: