BQP

Em Teoria da Complexidade Computacional, BQP (do inglês bounded error quantum polynomial time) é a classe de problemas de decisão solúveis por um computador quântico em tempo polinomial, com uma probabilidade de erro de até 1/3 para todas as instâncias. É a classe quântica análoga da classe de complexidade BPP.

Em outras palavras, existe um algoritmo para um computador quântico (um algoritmo quântico) que resolve o problema de decisão com alta probabilidade e é garantido de executar em tempo polinomial. Em qualquer dada execução do algoritmo, ele tem uma probabilidade de até 1/3 de que vai dar uma resposta errada.

Similarmente a outras classes probabilisticas "de erro limitado", a escolha de 1/3 na definição é arbitrária. Pode-se executar o algoritmo um número constante de vezes e tomar uma maioria para alcançar qualquer probabilidade de corretude menor que 1 desejada, utilizando o limitante de chernoff. Análises detalhadas mostram que a classe de complexidade é inalterada admitindo um erro tão alto quando ${\displaystyle {1/2}-{n^{-c}}}$ por um lado, ou exigindo um erro tão pequeno quanto ${\displaystyle 2^{n^{-c}}}$ por outro lado, onde ${\displaystyle c}$ é qualquer constante positiva, e ${\displaystyle n}$ é o tamanho da entrada.