Barrapunto

La computación cuántica es apropiada para problemas de tipo NP y para problemas que no se haya demostrado o falsado que pertenezcan a P (creo que la factorización y el logaritmo discreto pertenecen a este último grupo). Hay un montón de problemas de optimización reales (en el sentido económico de la palabra) que hoy en día son imposibles de resolver porque son NP-completos. Un ejemplo es encontrar una interconexión cableada de una serie de estaciones que minimice la longitud total de los cables empleados (y por tanto el coste).

Ese es solo un ejemplo. Disponer de una forma de resolver problemas NP-completos permitiría ahorrar millones en muchos campos de la industria (minimización de circuitos lógicos, optimización de rutas, etc).

Si te refieres al problema de intercambio de claves se sesión (que ahora se resuelve con criptografía de clave pública), la criptografía cuántica también permite resolverlo (y, según creo, está mucho más adelantada que la computación cuántica).

No es probable: Según creo no se ha demostrado que esos problemas sean NP-completos (aunque tampoco se sabe si pertenecen a P). Por tanto una solución de los mismos no puede utilizarse para resolver cualquier problema NP. Lo más lógico sería disponer de una instrucción que resolviese algún problema NP-completo ya que con dicha instrucción se podría resolver cualquier otro problema, incluido el de factorización.

Disculpa, pero creo que has oido campanas y no sabes donde. "qubit" no es un término de complejidad computacional (no hay problemas de más o menos qubit). Por otro lado los problemas computacionales no "se implementan". Lo que se implementan son algoritmos o máquinas que los resuelven.

La computación cuántica es apropiada para problemas de tipo NP y para problemas que no se haya demostrado o falsado que pertenezcan a P (creo que la factorización y el logaritmo discreto pertenecen a este último grupo).

FALSO. Es apropiada para algunos problemas NP [wikipedia.org] que probablemente no son NP-completos [wikipedia.org]. Investigación y Ciencia publicó hace una buena temporada un artículo en que explicaba que el truco que hacía funcionar el algoritmo de Shor no es aplicable a problemas NP en general.

Por definición, si un algoritmo permite resolver un problema NP-completo con un tiempo de ejecución de orden polinomial, entonces dicho algoritmo permite resolver cualquier problema NP con un tiempo de ejecución de orden polinomial.

P.D. Disculpa, no era mi intención ofenderte.