Yeah, I know: PP has already been this weblog's complexity class of the week. But once you've seen how to define PP using super-powerful variants of quantum mechanics, you might never look at Probabilistic Polynomial-Time the same way again! (Then again, you might.)
- For all inputs x, the circuit's first qubit has a nonzero probability of being measured '1' at the end of the computation.
- If x is in L, the second qubit will be measured '1' with probability at least 2/3, conditioned on the first qubit being measured '1'.
- If x is not in L, the second qubit will be measured '1' with probability at most 1/3, conditioned on the first qubit being measured '1'.
Clearly PostBQP sits between BQP and PP. I became interested in PostBQP when I realized that the containment BQP/qpoly in EXP/poly (discussed earlier in this weblog) can be improved to BQP/qpoly in PostBQP/poly.
Exercise 1. Imagine that the gates of a quantum computer only needed to be invertible - not unitary. Since states might no longer be normalized, let's define the probability of measuring a basis state x with amplitude αx to be |αx|2 divided by the sum over all basis states y of |αy|2. Show that we could decide exactly the languages in PostBQP.
Exercise 2. Now imagine that the gates are unitary, but the probability of measuring a basis state x equals |αx|p divided by the sum over all basis states y of |αy|p, where p is a nonnegative real number not equal to 2. Show that we could decide all languages in PostBQP.
I was getting more and more excited about the fundamental new complexity class I'd discovered. Alas:
Exercise 3. Show that PostBQP equals PP.