¿Cuáles son algunos problemas que, incluso teóricamente, una computadora cuántica encontrará difícil o imposible de hacer?

1) Las computadoras Quantum no pueden copiar información. Una vez que mides qubits, los destruyes. Sin clonación ¡Imposible, no difícil!

2) No se pueden rastrear los paquetes de computadora Quantum. Misma razón. Sin clonación ¡Olvídate de monitorear redes o contar clics para el ranking de páginas de Google en el espacio cuántico!

3) Difícil: la memoria cuántica (Oracle) es realmente muy muy difícil. En Quantum no puedes acceder a una celda de memoria. Debe acceder a todas las celdas de memoria posibles en superposición (es decir, en paralelo). Esto es lo que otorga poderes increíbles a estas bestias, pero también es una gran limitación.

4) Imposible: encontrar la raíz cuadrada de un número irracional en tiempo y memoria finitos

Como he dicho en otras partes, las computadoras cuánticas, si alguna vez las hacemos funcionar, será como si el fuego fuera para las mujeres de las cavernas de antaño. ¡Las computadoras cuánticas no son “simplemente mejores computadoras” como el fuego es “solo una mejor piel de animal para mantenerse caliente”!

Cualquier problema que sea imposible de resolver para una computadora ordinaria también lo es para una cuántica. Las computadoras cuánticas pueden (¡tal vez!) Hacer ciertas cosas especializadas más rápido, pero no hay nada indiscutible que puedan calcular. La computación cuántica afecta la complejidad , no la computabilidad , y ni siquiera estamos realmente seguros de lo primero.

Ejemplos concretos de problemas inconfesables son decidir si un programa determinado se detendrá en una entrada determinada, o determinar si un conjunto de ecuaciones polinómicas con coeficientes enteros tiene una solución en enteros.

Con nuestro conocimiento actual, en realidad no hay tantos problemas que una computadora cuántica pueda hacer mejor que nuestras computadoras actuales. Sabemos que una computadora cuántica puede simular la física cuántica y factorizar grandes números (algoritmo de Shor) más rápidamente, pero más allá de eso, hay algunos otros algoritmos que realmente aprovechan tener qbits.

De hecho, los problemas que se pueden resolver usando una computadora cuántica también se pueden resolver usando una computadora clásica; La diferencia es que una computadora cuántica nos permite resolver estos problemas más rápidamente. Del mismo modo, como se ha dicho, cualquier problema que sea indecidible también lo será usando una computadora cuántica (problema de detención).

Si bien en general estoy de acuerdo con las respuestas más votadas, albergan una falla importante: todas asumen el análisis del peor de los casos de los problemas respectivos. Tome un problema indecidible, como mirar un programa y decir si siempre termina; tengo que resolver este problema muchas veces por hora al calificar los exámenes en mi curso de algoritmo. Entonces, muchos casos de tales problemas pueden resolverse en la práctica. ¿Puede una computadora cuántica ayudar aquí? Realmente no lo sabemos, y ni siquiera tenemos buenas técnicas para explicar lo que pueden hacer las computadoras convencionales.

Las computadoras cuánticas de tipo extraño son solo hardware. Ves cosas como que el problema de detención no se resuelve con hardware resuelto por software. Escribir en los requisitos previos de los programas que anulan los cálculos continuos. Un programa de inteligencia artificial que se ejecuta en una computadora cuántica puede resolver cualquier cosa, dada la preprogramación correcta en su concepción y la capacidad de recopilar nuevas entradas y / o datos.

Los problemas que pueden ser más difíciles de responder para una computadora cuántica son los principales, por ejemplo

¿En qué debería trabajar después?
¿Es hermosa esta prueba?
¿Cómo puedo hacer esta prueba más bella?
¿Cómo puedo generalizar, especializar, ampliar los resultados que he obtenido?
¿Por qué mi corazón canta cuando miro una prueba?

Procesamiento de textos. Seriamente. Sería una solución terrible.

NP-Hard. Problemas