Los algoritmos clásicos pueden resolver 3-SAT en tiempo (aleatorizado) o 1.3303 n tiempo (determinista). (Referencia: Mejores límites superiores en SAT )
A modo de comparación, el uso del algoritmo de Grover en una computadora cuántica buscaría y proporcionaría una solución en , aleatorizado. (Esto aún puede requerir algún conocimiento de cuántas soluciones puede haber o no, no estoy seguro de cuán necesarias sean esas limitaciones). Esto es claramente significativamente peor. ¿Hay algún algoritmo cuántico que funcione mejor que los mejores algoritmos clásicos (o al menos, casi tan bueno?)
Por supuesto, los algoritmos clásicos podrían usarse en una computadora cuántica suponiendo suficiente espacio de trabajo; Me pregunto acerca de los algoritmos inherentemente cuánticos.
fuente
De hecho, como dijo wwjohnsmith1, puede obtener una aceleración de raíz cuadrada sobre el algoritmo de Schöning para 3-SAT, pero también de manera más general para el algoritmo de Schöning para k-SAT. De hecho, muchos algoritmos aleatorios para k-SAT se pueden implementar de forma cuadrática más rápida en una computadora cuántica.
fuente