Scott Aaronson

The Amazing Power of Postselection

Suppose you killed yourself in all universes where your quantum computer didn't produce a desired output. Conditioned on remaining alive, what could you do? It turns out that you could solve exactly the problems in the complexity class PP, and that this implies an extremely simple, quantum computing based proof of the celebrated Beigel-Reingold-Spielman result that PP is closed under intersection. You could also simulate BQP with quantum advice using only classical advice. Finally, for every fixed k, you could solve a problem that does not have quantum circuits of size n^k (even circuits with quantum advice).