Post-selection and complexity theory [closed]

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?

• What did you understand? Are you familiar with complexity-theory basics?
– Raphael
Sep 17 '13 at 8:33
• @Raphael I am familiar with the basics ... Sep 17 '13 at 8:47
• Then you should be able to formulate a more specific question than "Please explain all of X [in plain English]!"
– Raphael
Sep 17 '13 at 8:50

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 many possible output states. When measured, they collapse to a single state that is sampled from a probability distribution of states. In other words, during measurement, some state is "chosen" randomly from all possible states, with some more likely than others to be "chosen".

A quantum computation takes these unmeasured qbits and methodically applies quantum logic gates. Doing this influences that superposition (the probability distribution of final states). When we are done applying quantum gates, we perform a measurement on the entangled qbits (final quantum state). This gives us a result we can use, but all the underlying quantum information is lost, preventing us from measuring again. The quantum computation would have to be repeated from scratch in order to perform another measurement. To account for errors, quantum computations are usually performed multiple times to build up additional confidence in the final result.

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}\left[q_1=\lvert1\rangle\right]$$. 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}\left[q_1=\lvert1\rangle\mid q_2=\lvert1\rangle \right]$$. This essentially filters out all possible states that $$q_1$$ could have been in if $$q_2 = \lvert0\rangle$$.

If $$q_2$$ happened to be defined as an indicator of a "good" computation in our experiment, then, by using postselection, we would have thrown out all the "bad" computations.

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

So in short, postselection gives us the ability to force 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 we consider to be useless to us when we measure our quantum state. As demonstrated in Aaronson's proof of $$\text{PostBQP = PP}$$, the ability to postselect provides significant computational advantage over vanilla models of quantum computation.

• ok, so this means that post-selection is to condition some computation path by another one that may help us to get rid of unnecessarily computations ? Sep 17 '13 at 9:02
• @FayezAbdlrazaqDeab Not exactly. You would condition a quantum bit in order to get rid of unnecessary "computation paths" (or more accurately, lessen the probability of some undesired superpositions). In quantum computing, it is better to think of a single execution as an experiment (it is repeated many times to build up confidence). Postselection allows us to take a set of experiments out of the picture, effectively preventing them from being considered in the final measurement (result).
– mdxn
Sep 18 '13 at 1:33
• Hello! Thank you for a clear answer. The thing I still don't get is the following: If post selection happens after you run your algorithm, then how is it helping us to get rid of undersired calculations? We already did the calculation, the only thing that's happening is that we are throwing the result because it represents a "bad calculation". Dec 1 '18 at 16:46
• @P.C.Spaniel We apply quantum logic gates, post select, and obtain a final measurement in that order. The post-selection step happens before (or immediately during) the measurement phase, so it occurs before the explicit calculation (result of a measurement) has completed.
– mdxn
Dec 2 '18 at 23:30