Una computadora cuántica puede resolver cualquier “problema de búsqueda”, incluidos muchos problemas NP-hard, como SAT, en [math] O (\ sqrt {N}) [/ math] “cheques”, donde N es el tamaño del espacio de búsqueda . Esto es con un algoritmo de búsqueda general llamado algoritmo de Grover.
Por ejemplo, para una instancia SAT con n variables, hay [matemática] 2 ^ n [/ matemática] formas posibles de establecer todas las variables. Para verificar cada uno requeriría [matemática] O (n 2 ^ n) [/ matemática]. Ese factor de [math] n [/ math] se debe a que toma [math] O (n) [/ math] tiempo para evaluar el circuito booleano para un ajuste dado de las variables. No se conoce ningún algoritmo clásico que pueda mejorar. Tal vez pueda eliminar el factor de n, no estoy seguro. Pero ciertamente no se sabe cómo hacer [matemáticas] O ((2- \ epsilon) ^ n) [/ matemáticas].
Con el algoritmo de Grover cuántico, puede hacer esto a tiempo [matemática] O (n \ sqrt {2 ^ n}) = O (n 2 ^ {n / 2}) [/ matemática] que es mucho más rápido. Todavía no es tiempo polinómico, pero aún es mucho mejor.
- ¿Fue la motivación original de Quantum Computing hacer que los problemas de NP fueran realmente manejables?
- ¿El lenguaje Python necesita cambiar para reflejar la computación cuántica?
- Cómo calcular resultados con los qubits cuánticos
- ¿El desarrollo de computadoras cuánticas personales comerciales aumentaría o disminuiría el valor del bitcoin?
- ¿Es cierto que la computación cuántica puede revolucionar todos los campos de la ciencia?
