No, no en el sentido de que la mayoría de los problemas algún día se beneficiarán de una computadora cuántica. (Eso nunca sucederá).
El campo de la teoría de la complejidad computacional es donde los científicos (¿matemáticos?) Estudian los recursos necesarios para resolver problemas, pero no para los problemas individuales, sino para las clases de problemas. Los recursos suelen ser el tiempo y el espacio necesarios para resolver un problema.
Hay problemas “agradables” o “fáciles” o “buenos” o “manejables”, como buscar un nombre en una guía telefónica. Abre la guía telefónica en el medio y el nombre que está buscando está delante o detrás de donde la abrió, por lo que ha reducido a la mitad el número de páginas que debe mirar con solo una “operación”. Continuaría subdividiendo las secciones restantes de la guía telefónica a medida que afina el nombre y el número que está buscando. Por lo tanto, una guía telefónica de 1,000 páginas solo necesita 10 operaciones, y una guía telefónica de 2,000 páginas solo necesita 11; una guía de 15,000 páginas solo necesita 14 operaciones.
- Cuál es la mejor revista para la investigación relacionada con la información cuántica: Phys. Rev. A o Información cuántica y computación?
- ¿Qué hace que la computación cuántica sea rápida? ¿Es simplemente la capacidad de ser 1 y 0 simultáneamente, o está relacionado con la velocidad física de las partículas en movimiento?
- ¿Qué es un salto cuántico?
- ¿Es la mecánica cuántica el tema más difícil de entender? Por lo tanto, ¿podemos decir con seguridad que quienes trabajan en mecánica cuántica son los más inteligentes?
- ¿Fue la motivación original de Quantum Computing hacer que los problemas de NP fueran realmente manejables?
Algunos problemas no son “agradables”, descritos como intratables . Si te di 10 canciones en un iPod y te hago la pregunta, “¿hay alguna manera de dividir estas 10 canciones en dos listas de reproducción con el mismo tiempo total de reproducción?”. Realmente no conocemos ninguna forma de verificar mucho mejor que solo sistemáticamente pasando por todas las combinaciones ([matemáticas] 2 ^ n [/ matemáticas] combinaciones). Para un pequeño número de canciones no es tan malo, pero cuando comenzamos a obtener hasta una docena de canciones, incluso nos abrumamos con la cantidad de combinaciones. Un iPod con 1000 canciones se vuelve tan difícil de manejar que, a menos que haya alguna información especial para explotar (si, por ejemplo, todas las canciones tienen la misma longitud), incluso convertir todo el universo en una gran computadora y ejecutar el cálculo para todo el futuro de En el universo, no afectarías mucho la cantidad de combinaciones posibles.
En la teoría de la complejidad computacional, los problemas se organizan en clases según los tipos de recursos que necesitan para ser “solucionables de manera eficiente”, es decir, sin ocupar todo el universo.
Las computadoras cuánticas aportan un recurso adicional que las computadoras clásicas no pueden simular de manera eficiente. (Nuevamente, significa eficientemente, en una cantidad de tiempo razonable). Los recursos cuánticos son enredos y superposición . Si solucionamos un problema correctamente, podemos obtener estos efectos para ayudarnos a encontrar respuestas a problemas que, sin estos recursos, no se sabe que se pueden resolver de manera eficiente. (Tenga en cuenta que dije que no se conocen , porque muchos de estos resultados en informática todavía son preguntas abiertas. Puede ser que las computadoras clásicas puedan resolver el mismo tipo de problemas (eficientemente) que las computadoras cuánticas, pero en este momento nosotros ‘ He pasado mucho tiempo buscando sin mucha mejora. Una idea errónea común sobre la computación cuántica es que todos los problemas se beneficiarán de ella, pero incluso el problema que describí, llamado suma de subconjuntos , no se sabe que tenga un algoritmo eficiente que use el cuántico especial recursos
Pero la razón por la que respondo que no es que hay muchos problemas que ya son tan eficientes que no hay ningún beneficio en tratar de mejorarlos, como el problema de la agenda telefónica. Y las computadoras ya son lo suficientemente rápidas para muchas de las cosas que las personas hacen con ellas (hojas de cálculo, navegación web, lectura, búsqueda, etc. ), que simplemente no hay razón para tratar de mejorarlas.
Las computadoras cuánticas usarán estos recursos, pero se aprovecharán de las computadoras clásicas, que continuarán manejando el tipo de tareas en las que son buenos. Probablemente habrá un poco de sobrecarga para organizar los recursos cuánticos para la informática y para obtener la respuesta, por lo que solo querrá invocarlo cuando brinde un beneficio real.
Echa un vistazo al Complexity Zoo, un catálogo de clases de complejidad. BQP, para el tiempo polinómico cuántico de error limitado, es importante para la computación cuántica, aunque no estoy seguro de si hay otras clases que usen recursos cuánticos.
El Algoritmo: Idioma de la Ciencia Moderna: aquí es donde obtuve el problema del iPod (¿y tal vez la agenda telefónica? No estoy seguro, han pasado años desde que lo leí).
Y Usuario: Silenciosamente tiene una lista de artículos interesantes de ciencias de la computación que encontré hace años (no he actualizado esa página en mucho tiempo).