El algoritmo de Shor a menudo se usa como argumento. Puede resolver el problema de factorización más rápido que cualquier algoritmo conocido para computadoras clásicas. Sin embargo, no tenemos pruebas de que las computadoras clásicas no puedan factorizar enteros de manera eficiente.
¿Existe alguna prueba real de que las computadoras cuánticas puedan resolver algunos problemas más rápido que las computadoras clásicas?
algorithms
efficiency
quantum-computing
MaiaVictor
fuente
fuente
Respuestas:
Sí, el algoritmo de Grover muestra que puede usar un algoritmo cuántico para encontrar un elemento en una base de datos desordenada de tamaño con alta probabilidad al consultar la base de datos solo veces. Cualquier solución clásica que tenga éxito con alta probabilidad requiere consultas a la base de datos.O ( √N Ω(N)O(N−−√) Ω(N)
fuente
Depende de lo que consideres una prueba real y de lo que quieres decir con "más rápido". Desde una perspectiva teórica de la complejidad, la respuesta es no: no tenemos esa prueba. BQP (la clase de problemas que una computadora cuántica puede resolver eficientemente) está contenida en PSPACE. Ser capaz de demostrar una separación entre BQP y PSPACE también implicaría una separación entre P y PSPACE, lo que no se conoce.
Tenga en cuenta que el algoritmo de Grover solo da una aceleración de raíz cuadrada, por lo que no hay contradicción.
fuente
preguntas acerca de la "prueba" que podría estar limitada a un nivel matemático, pero la pregunta básica es mucho más profunda que eso. los teóricos reconocerán que, en general, sigue siendo una pregunta abierta sobre el rendimiento relativo de los algoritmos cuánticos frente a los clásicos y probablemente no haya una respuesta simple / general, pero con algún consenso de expertos, el algoritmo Shors parece ser "inusualmente rápido en comparación con la mejor velocidad clásica esperada ". La factorización rápida en una computadora clásica romperá los supuestos de seguridad criptográfica ampliamente difundidos, como el sistema RSA .
algo de esto se captura formalmente en la pregunta de clase de complejidad abierta BPP =? Pregunta BQP . Estas son las clases clásicas y cuánticas análogas y la separación es desconocida y un área activa de investigación.
una pregunta estrechamente relacionada es si físicamente se pueden construir computadoras QM que cumplan con las especificaciones teóricas y algunos / una minoría de científicos (también conocidos como "escépticos") argumentan que puede haber leyes de ruido o escala que impiden la escala QM como se prevé en la teoría. en cierto sentido, la "prueba" definitiva de la velocidad de una computadora QM debe ser una implementación física. (Esto es similar a la forma en que la tesis de Church-Turing es teórica, pero parece vincularse en última instancia con una afirmación sobre implementaciones físicas). Algunos investigadores están hablando de los análogos de Church-Turing en la computación QM. ver, por ejemplo , la tesis de Church Turing en un mundo cuántico de Montanaro.
relevantes para / sobre esta pregunta / debate son continuos intentos sustanciales / "acalorados" (científicos) de comparar la computadora cuántica "más grande" actual del mundo por DWave. Este es un gran tema con una gran cantidad de material relacionado, pero para una descripción relativamente reciente, pruebe el estudio de referencia de disputas D-Wave que muestra una computadora cuántica lenta / el Registro
fuente