¿Qué tipo de algoritmos son más rápidos con una computadora cuántica?

Soy un estudiante principiante de CS y estoy aprendiendo algoritmos. Escuché que incluso con las computadoras cuánticas, los algoritmos generales de clasificación nunca pueden ser mejores que time. Sin embargo, también sé que los algoritmos de factorización serían mucho más rápidos. En términos generales, ¿qué tipo de algoritmos serían mucho más rápidos con las computadoras cuánticas?$n\log n$

• El algoritmo de Shor que pone FACTORING en BQP ( tiempo polinómico cuántico de error acotado , efectivamente el equivalente cuántico de P) también se puede utilizar para resolver el problema DISCRETO LOGARITHM , donde queremos encontrar un número entero tal que donde y se dan, en (quantum) tiempo polinómico. El problema del LOGARITMO DISCRETO tiene el mismo estado que el problema de FACTORACIÓN en que no sabemos si son solucionables en tiempo polinómico, por lo que esto podría no ser una aceleración.$k$$a^{k} = b$$a$$b$
• El algoritmo de Grover proporciona una velocidad cuadrática en la búsqueda de listas sin clasificar (que se puede usar como una velocidad para muchos algoritmos).
• Simular sistemas cuánticos también está en BQP, pero exponencialmente más lento en una TM clásica.
• Resolver la ecuación de Pell (no realmente una ecuación) está en BQP, otra aceleración exponencial.
• También hay una serie de otros problemas más oscuros que están en BQP, pero parecen no estar en P. Wocjan y Zhang dan un buen punto de partida para desenterrarlos.