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 1 / 2 − n − c {\displaystyle {1/2}-{n^{-c}}} por um lado, ou exigindo um erro tão pequeno quanto 2 n − c {\displaystyle 2^{n^{-c}}} por outro lado, onde c {\displaystyle c} é qualquer constante positiva, e n {\displaystyle n} é o tamanho da entrada.