A classe de problemas BQP (bounded-error quantum polynomial time) refere-se a problemas que podem ser resolvidos por um computador quântico em tempo polinomial, com uma probabilidade de erro limitada. Isso significa que, embora esses problemas não tenham uma solução eficiente em tempo polinomial usando algoritmos clássicos (ou seja, não pertencem à classe P), eles podem ser resolvidos de forma eficiente com a ajuda de algoritmos quânticos. Os problemas em BQP incluem, por exemplo, a fatoração de números inteiros e a simulação de sistemas quânticos, que são considerados difíceis para computadores clássicos. A relação entre BQP e NP é um tema de pesquisa ativo, pois ainda não se sabe se BQP é um subconjunto estrito de NP ou se BQP = NP.