Esta es una pregunta natural con una respuesta un poco decepcionante. Tal vez te preguntes esto porque has oído hablar de algún algoritmo cuántico elegante, digamos el algoritmo de Shor, que resuelve un problema de NP (en este caso, factorización de enteros) en tiempo P (Shor’s se ejecuta en un tiempo poliligarítmico extraño, específicamente [matemática] O ((\ log n) ^ 2 (\ log \ log n) (\ log \ log \ log n) [/ math], donde [math] n [/ math] es el número de dígitos en la entrada.
Esta es claramente una clase (sub) polinómica de soluciones a un problema de NP, entonces P = NP resuelto, ¿verdad?
No Desafortunadamente. Ciertos problemas caen en una clase particular de dificultad llamada BQP, o tiempo polinómico cuántico de error acotado, que se describe como tiempo polinómico para una computadora cuántica con una probabilidad máxima de [error matemático \ \ frac13 [/ matemático] (si usted no son conscientes, debido a su naturaleza probabilística, los algoritmos cuánticos tienen la posibilidad de contener un error).
- Cómo formular matemáticamente para seleccionar los mejores valores de N de una matriz
- ¿Debo leer matemáticas y algoritmos discretos primero antes de comenzar la programación competitiva?
- ¿Por qué algunas funciones hash usan un número primo como base? ¿Cuál es el significado de usar un número primo? ¿Es para asignar unicidad y minimizar la colisión de valores hash?
- ¿Cuál es la forma más sencilla de entender las máquinas de Turing y el problema del castor ocupado?
- ¿Cuáles son las diferencias entre autómatas finitos y sistema de transición?
No se sabe con certeza, pero esta es una relación sospechosa entre BQP y otras clasificaciones de dificultad:
