A quantum computer can efficiently solve problems lying in the complexity class BQP. I have seen a claim the one can (potentially, because we don't know whether BQP is a proper subset or equal to PP) increase the efficiency of a quantum computer by applying postselection and that the class of efficiently solvable problems becomes now postBQP = PP.

What does postselection mean here?

  • 3
    You say "I have seen a claim". Where did you see that claim? Are you able to retrieve the original source and link us to it? – nbro Mar 13 at 12:33
  • 1
    I will remove my downvote if you show us the source of that claim. – nbro Mar 13 at 12:44

"Postselection" refers to the process of conditioning on the outcome of a measurement on some other qubit. (This is something that you can think of for classical probability distributions and statistical analysis as well: it is not a concept special to quantum computation.)

Postselection has featured quite often (up to this point) in quantum mechanics experiments, because — for experiments on very small systems, involving not very many particles — it is a relatively easy way to simulate having good quantum control or feedforward. However, it is not a practical way of realising computation, because you have to condition on an outcome of one or more measurements which may occur with very low probability.

Actually 'selecting' a measurement outcome is nothing you can do easily in quantum mechanics — what one actually does is throw away any outcome which does not allow you to do what you want to do. If the outcome which you are trying to select has probability $0 < p < 1$, you will have to try an expected number $1/p$ times before you manage to obtain the outcome you are trying to select. If $p = 1/2^n$ for some large integer $n$, you may be waiting a very long time.

The result that postselection 'increases' (as you say) the power of bounded-error quantum computation from BQP to PP is a well-liked result in the theory of quantum computation, not because it is practical, but because it is a simple and crisp result of a sort which is rare in computational complexity, and is useful for informing intuitions about quantum computation — it has led onward to ideas of "quantum supremacy" experiments, for example. But it is not something which you should think of as an operation which is freely available to quantum computers as a practical technique, unless you can show that the outcomes which you are trying to postselect are few enough and of high-enough probability (or, as with measurement-based computation, that you can simulate the 'desirable' outcome by a suitable adaptation of your procedure if you obtain one of the 'undesirable' outcomes).

As the other answer conveyed (and to which I am just trying to provide some clarification), post-selection is about just looking at a subset of possible measurement outcomes. To my mind, this falls into two different cases, as below. Yes, they are different aspects of the same thing, but they are used very differently by two different communities.

Experimental Post-selection

You do some experiments, but you only gather data when certain conditions are fulfilled. Generally it's used to compensate for heralded experimental imperfections (i.e. something is triggered that tells us we've had a undesired result before proceeding with another part of the experiment). For example, you might be using a pair of photons as information or entanglement carriers, but sometimes those photons get lost on the way. If you only do things when both photons are detected, you are post-selecting on their successful arrival.

Theoretical Post-selection

This is a thought experiment of "how much more powerful could my computer be if I could choose the outcomes of measurements?" and is not a practical proposition.

As a simple example, think about quantum teleportation. In the normal scenario, Alice and Bob share a Bell pair, and Alice has a qubit in an unknown state that she wants to teleport to Bob. She performs a Bell measurement on her two qubits, and sends her measurement outcome to Bob. If Bob is far away from Alice, the information on the measurement result takes a finite time to get there, and it's after that time that he can be thought of as having received the qubit (because he has to compensate for effects of the different results on the qubit he holds).

However, if Alice can post-select on the measurement result as always being one particular result, and Bob knows that she's going to select that one, then Alice doesn't need to send the measurement result to Bob. He can use the qubit he holds immediately. Even stronger, he can use it before Alice has made the measurement, secure in the knowledge that she will! So, not only are you achieving faster-than-light communication, you're actually communicating backwards in time! You can start to imagine how immensely powerful that could be for a computer (compute for an arbitrarily long time and then send the answer back in time to the moment the question was asked).

  • I don't get the last paragraph: Even if Alice post-selects on a certain outcome of a Bell measurement, there are measurements that she has to discard because they didn't give the correct outcome and Alice needs to communicate the fact whether she has accepted or discarded the experimental outcome. – jknappen Apr 11 at 14:17
  • @jknappen That's the difference between theory and experiment. Experiments discard the false results. The theory version posits that you can force it to always give the right result. There's nothing to discard. – DaftWullie Apr 11 at 14:19
  • I don't think so, even in theory you have to discard some computations. In classical computation, the same holds for well-known zero-knowledge proof protocols. – jknappen Apr 11 at 14:22
  • @jknappen I have to admit I was reconstructing this argument from my memory of a paper that, now I come to look for it, I can't immediately lay my hands on to verify the details. However, this one talks about doing just the same. – DaftWullie Apr 11 at 14:32
  • @jknappen In the last paragraph, DaftWullie is referring to a hypothetical world where you could really truly do a post-select operation (e.g. apply the non-unitary single-qubit operation [[1,0],[0,0]] followed by a normalization of the wavefunction, as can be done in a simulator). – Craig Gidney May 28 at 1:45

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.