Existe, sin embargo, un algoritmo para computación cuántica, propuesto por Peter Shor, capaz de encontrar la factorización de un entero en sus factores primos en tiempo polinomial con error acotado, es decir, de clase BQP.