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.)

Let's define PostBQP (or BQP with postselection) as the class of languages L for which there exists a uniform family of polynomial-size quantum circuits such that

- 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'.

_{path}(another previous CCW).

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.

The moral is that when you make a quantum class too powerful, it turns into a classical class! (Another example of this is NQP = coC=P.)

## No comments:

## Post a Comment