Todo lo que puede calcular un ordenador cuántico se puede calcular mediante un ordenador (clásico), basta simularlo. Se acaba de publicar un problema con oráculo que se puede resolver de forma eficiente en un ordenador cuántico, está en la clase BQP, pero que no se puede resolver de forma eficiente en un ordenador (clásico), incluso bajo la hipótesis P=NP. Por supuesto, bajo la hipótesis de que P≠NP ya sabíamos que los ordenadores cuánticos son más eficientes, pues hay problemas en BQP que no están en P.
