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.
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.
No hay comentarios:
Publicar un comentario