Muy lejos, porque nadie ha demostrado ningún algoritmo para computadoras cuánticas que resuelva un problema de NP completo en tiempo polinómico. La mayoría de las personas en el campo, a diferencia del periodismo científico, creen que existe una separación entre BQP, la clase de problemas resueltos por las computadoras cuánticas en tiempo polinómico y NP-completo.
El algoritmo de Shor para factorizar, que no tiene NP completo, se ha ejecutado en computadoras cuánticas reales. El número más grande que se ha utilizado para factorizar (al que podría encontrar una referencia) es 56153: el nuevo número más grande factorizado en un dispositivo cuántico es 56,153 Y eso fue en 4 qubits.
El número de qubits necesarios para demostrar la “supremacía cuántica” en algún problema sigue siendo un tema de investigación, pero muchos investigadores creen que el objetivo es de unos 50 qubits. El dispositivo físico más grande hasta ahora es de aproximadamente 10 (aunque ahora podemos simular una computadora cuántica con hasta 56 qubits: Computación cuántica: Rompiendo la barrera de simulación de 49 Qubit)
- ¿Alguien puede mostrarme la relación de recurrencia?
- Cómo resolver el problema P versus NP
- ¿Qué es la notación de sintaxis abstracta uno?
- ¿Cuál es el mejor lenguaje de programación para un matemático?
- ¿Cuál es el significado del Lema Hardcore de Impagliazzo?
