or allowing intermediate postselection steps during the algorithm are equivalent. Here are three basic properties of PostBQP (which also hold for BQP via similar proofs): PostBQP is closed under complement. Given a language L in PostBQP and a corresponding deciding circuit family, create a new circuit family by flipping the output qubit after measurement, then the new circuit family proves the complement of L is in PostBQP. You can do probability amplification in PostBQP. The definition of PostBQP is not changed if we replace the 2/3 value in its definition by any other constant strictly between 1/2 and 1. As an example, given a PostBQP algorithm A with success probability 2/3, we can construct another algorithm which runs three independent copies of A, outputs a postselection bit equal to the conjunction of the three "inner" ones, and outputs an output bit equal to the majority of the three "inner" ones; the new algorithm will be correct with conditional probability , greater than the original 2/3. PostBQP is closed under intersection. Suppose we have PostBQP circuit families for two languages and , with respective postselection qubits and output qubits . We may assume by probability amplification that both circuit families have success probability at least 5/6. Then we create a composite algorithm where the circuits for and are run independently, and we set P to the conjunction of and , and Q to the conjunction of and . It is not hard to see by a union bound that this composite algorithm correctly decides membership in with (conditional) probability at least 2/3. More generally, combinations of these ideas show that PostBQP is closed under union and BQP truth-table reductions. = Scott Aaronson showed that the complexity classes (postselected bounded error quantum polynomial time) and PP (probabilistic polynomial time) are equal. The result was significant because this quantum computation reformulation of gave new insight and simpler proofs of properties of . The usual definition of a circuit family is one with two outbit qubits P (postselection) and Q (output) with a single measurement of P and Q at the end such that the probability of measuring has nonzero probability, the conditional probability Pr[Q = 1|P = 1] ≥ 2/3 if the input x is in the language, and Pr[Q = 0|P = 1] ≥ 2/3 if the input x is not in the language. For technical reasons we tweak the definition of