Cheap and Secure Web Hosting Provider : See Now

# [Answers] Post-selection and complexity theory

, ,
Problem Detail:

I read about post-selection and didn't understand the meaning behind this thing. I didn't understand the Wikipedia article well, so what is a simple but understandable explanation of post-selection and how to use it in complexity?

###### Asked By : Fayez Abdlrazaq Deab

I went ahead and looked to see if there was a good resource that I could provide, but beyond some resources that Aaronson wrote, I could not find any good additional supplements. You should check out what he says and see if that helps. However, I'll do my best to provide a very quick and potentially hand wavy interpretation.

Basic Quantum Computing: (If Needed)

Consider a quantum computer with some number of quantum bits. Before we measure quantum bits, they are in a superposition of states. When measured, they collapse to a single state that is based on a probability distribution of states. Alternatively, some state is "chosen" randomly from all the possible ones with some more likely to be "chosen" than others. A computation takes these unmeasured bits and methodically applies quantum logic gates. Doing this influences that superposition. When done, we measure and look at the results. This is done multiple times to build up certainty.

Postselection in a Computation:

When computing a decision problem, let us just designate a single quantum bit, $q_1$, as our "answer" where $\lvert1\rangle$ and $\lvert0\rangle$ correspond to accept and reject.

Postselection introduces conditional probability into the mix. We say we want to postselect a quantum bit, $q_1$,for a specified outcome of a second bit, $q_2$. To simplify matters, let us assume that this is the last thing that we do before measuring. Without postselecting, our machine would accept with $\mathbb{P}\{q_1=\lvert1\rangle\}$. If we use post selection as described above, we are telling $q_1$ to only be in a superposition of states that work given that $q_2=\lvert1\rangle$. The probability that the computation accepts now becomes $\mathbb{P}\{q_1=\lvert1\rangle\mid q_2=\lvert1\rangle \}$. This essentially filters out all possible states that $q_1$ could be in if $q_2 = \lvert0\rangle$ (it can, but don't tell $q_1$ that). If $q_2$ happened to be an indicator of a "good" computation, then, by using postselection, we would have thrown out all the "bad" ones.

Note: $\mathbb{P}\{q_2=\lvert1\rangle\}$ must be $>0$ or else the conditional probability measure is not well defined.

So in short, postselection gives us the ability to force a quantum bits to think that another quantum bit is in a specific state we choose. This lets us filter out a lot of results that may be useless to us when we measure our bits. It provides a significant advantage as demonstrated in Aaronson's proof of $\text{PostBQP = PP}$.