PostBQP
Em teoria da complexidade computacional, PostBQP é uma classe de complexidade que consiste de todos os problemas computacionais solúveis em tempo polinomial em uma Máquina de Turing quântica com pós-seleção e erro limitado (no sentido de que o algoritmo é correto ao menos em 2/3 das vezes para todas as entradas).

Pós-seleção não é considerada uma funcionalidade que um computador realístico (mesmo um quântico) iria conter, mas ainda assim, máquinas pós-seletivas são interessantes sob uma perspectiva teórica.

Remover qualquer uma dessas duas funcionalidades (quanticidade e pós-seleção) de PostBQP resulta em uma das duas seguintes classes, sendo as duas subclasses de PostBQP:
* BQP é a mesma que PostBQP apenas sem pós-seleção
* BPPpath é a mesma que PostBPP exceto que ao invés de quântico, o algoritmo é randômico clássico (com pós-seleção)

Adicionar pós-seleção parece fazer com que Máquinas de Turing Quântica fiquem muito mais poderosas: Scott Aaronson provou que PostBQP é equivalente a PP, uma classe que se acredita ser relativamente poderosa, enquanto que BQP não se sabe se até mesmo contém a classe aparentemente menor NP. Utilizando técnicas similares, Aaronson também provou que pequenas mudanças nas leis da computação quântica teriam efeitos significativos. Como exemplos específicos, sob quaisquer das duas seguintes mudanças, a "nova" versão de BQP se tornaria equivalente a PP:
* se nós ampliarmos a definição de 'porta quântica' para incluir não apenas operações unárias mas também operações lineares, ou
* se a probabilidade de medição de um estado base formula_1 for proporcional a formula_2 no lugar de formula_3 para qualquer inteiro ímpar "p > 2".
Q5157286
teoria da complexidade computacional
Concept
Q908207
classe de complexidade
Concept
Q3435924
problemas computacionais
Concept
Q2393193
tempo polinomial
Concept
Q765620
Máquina de Turing quântica
Concept
None
pós-seleção
UNK
Q601325
BQP
MISC
None
pós-seleção
UNK
None
Scott Aaronson
UNK
Q601325
BQP
MISC
Q628036
NP
MISC
Q1563053
PP
MISC
Q7233606
PostBQP
MISC
Q7233606
PostBQP
MISC
Q7233606
PostBQP
MISC
Q7233606
PostBQP
MISC
Q7233606
PostBQP
MISC
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
instance of
subclass of
said to be the same as
has quality
has quality
has quality
subclass of