¿ Dónde es mejor una computadora clásica que una computadora cuántica ? ¿Hay algún dominio conocido en el que los algoritmos clásicos siempre superen a los cuánticos, digamos, tanto en términos de complejidad de tiempo como de espacio?
En caso afirmativo, ¿podría darme ejemplos?
Si no, ¿podría proporcionarme un enlace a la prueba?
Como respondió fs137, una computadora cuántica puede simular una computadora clásica y, por lo tanto, desde una perspectiva puramente de la teoría de la complejidad, la computadora clásica nunca es superior a la cuántica en un sentido asintótico (suponiendo que , actualmente una pregunta abierta).
Sin embargo, las computadoras cuánticas actualmente operan con un número muy bajo de qubits (descartando el control de calidad adiabático como D-Wave) en relación con las computadoras clásicas con bits clásicos. Por lo tanto, actualmente no estamos en un momento en el que las computadoras cuánticas puedan funcionar a una escala en la que estos asintóticos tomen el control. Dado que las computadoras cuánticas tienen una sobrecarga muy grande para realizar una operación que es comparativamente simple en una computadora clásica, tienen factores constantes muy grandes que dominan para cálculos pequeños. Cualquier operación individual que pueda realizar una computadora clásica, probablemente será mucho más lenta en una computadora cuántica.
Con esto en mente, las computadoras clásicas dominan en pequeñas cantidades de bits desde una perspectiva práctica. Sin embargo, a medida que comenzamos a escalar el número de bits y estamos resolviendo un problema con un algoritmo cuántico conocido que mejora el algoritmo clásico mejor conocido, veremos que una computadora cuántica puede terminar los cálculos más rápido porque está ejecutando un algoritmo completamente algoritmo diferente al de la computadora clásica.
Puede simular una computadora clásica en una computadora cuántica (esencialmente sin sobrecarga), pero no al revés. Aquí hay un enlace a una lista de puertas cuánticas que se han encontrado útiles: https://en.wikipedia.org/wiki/Quantum_gate Si miras cerca del final, puedes encontrar una implementación de la puerta cuántica de Toffoli.
También me gustaría señalar que la computadora cuántica no permite la copia de bits cuánticos. ( https://en.wikipedia.org/wiki/No-cloning_theorem ). Entonces, para almacenar datos, la computadora clásica es mejor.
Emilio Pisanty