# Interactive Proofs via Postselection?

Define the computational model MPostBQP to be identical to PostBQP except we allow polynomially many qubit measurements before the post-selection and final measurement.

Can we give any evidence indicating that MPostBQP is more powerful than PostBQP?

Define MPostBQP[k] to allow multiple rounds of measuring and postselection before we make the final measurement. Choose indexing so MPostBQP[1] = PostBQP and MPostBQP[2] = MPostBQP and so on. (Update: A formal definition is given below.)

Consider Arthur-Merlin games. Perhaps we can simulate them in this model of computation: Postselection can take Merlin's role of producing convincing messages and the intermediate measurements can take the role of Arthur's public coin tosses. This possibility makes me ask:

Do we have AM[k] $\subset$ MPostBQP[k]?

This is indeed known for $k=1$, which says MA $\subset$ PP. To show it for $k=2$ would mean MPostBQP = PP only if AM $\subset$ PP. Since there is an oracle relative to which AM is not contained in PP, this could give an affirmative answer for my first question.

Finally, for the polynomially many rounds case,

Do we have PSPACE $\subset$ MPostBQP[poly]? If so, is it equality?

This would be philosophically interesting (at least to me) because it would tell us that the "tractable" class of problems for a "postselecting sorcerer" includes (or is) all of PSPACE.

EDIT: I've been asked for a formal definition of MPostBQP. (I have updated what follows.)

MPostBQP[k] is the class of languages $L \subset \{0,1\}^*$ for which there exists a uniform family of polynomial-size quantum circuits $\{C_n\}_{n \geq 1}$ such that for all inputs $x$, the procedure below yields true with probability at least $2/3$ if $x \in L$, and with probability at most $1/3$ if $x \notin L$. The procedure, which allows for some choices which may depend on $L$ (but not $x$), is defined as follows:

Procedure: Step 1. Apply the unitary operator corresponding to $C_n$ to the input state $\left\vert 0\cdots 0\right> \otimes \left\vert x \right>$. Note the length of the first $\left\vert0\cdots 0\right>$ register is at most polynomial in the length of $x$. Step 2. For $i = 1 \cdots k$: If $i$ is even, then measure any desired number of qubits from the first register (at most polynomially many, given the size of the register). If $i$ is odd, then postselect so a chosen single qubit in the first register measures as $\left\vert 0 \right>$ (and have a guarantee that the probability is non-zero so the postselection is valid, of course). Step 3. Finally, measure a last qubit in the first register, and return true if we measure $\left \vert 1 \right>$ and false otherwise.

We have MPostBQP[0] = BQP, MPostBQP[1] = PostBQP, and MPostBQP := MPostBQP[2]. I'm trying to mirror the Arthur-Merlin classes where AM[0] = BPP, AM[1] = MA, and AM[2] = AM.

EDIT (3/27/11 5 PM): There seems to be debate about how postselection should be defined in this context. Obviously, I mean for a definition which does not trivialize my question! :) The definition I have assumed is the following: Postselecting on the kth bit means we project the state into the subspace in which the kth bit is $0$, and normalize. It turns out that in a scheme where we postselect before we do measurements, then we can obtain the final statistics by looking at conditional probabilities in a scheme where the postselections are replaced by measurements. However, I claim that this characterization breaks down when measurements and postselections are interspersed. I think the confusion stems from people using this "conditional probability definition" (which works in the special case which I am generalizing out of) as the definition of postselection, rather than the "forced measurement" definition I just gave, which clearly depends on order because of lack of commutativity. I hope this helps!

EDIT (3/27/11 9 PM): I defined postselection in the pure-state formalism already. Niel gave an analysis in the density matrix formalism that disagrees with mine for the 3-qubit example. The culprit is, again, the definition of postselection. Define postselection in the density matrix setting as follows. Given a density matrix $M$, rewrite it as a mixture of separable states $M = \sum p_i \left\vert a_i \right> \left< a_i \right\vert$. Let $\left\vert A_i \right>$ be the result of postselection (on some qubit) using the pure-state formalism I defined above. Define the result of the postselection on $M$ to be $\sum p_i \left\vert A_i \right> \left< A_i \right\vert$.

This is a more sensible definition, because it doesn't give us results which say that after we post-select, we alter the statistics of events (measurements) we already watched happen. That is, the $p_i$'s are probabilities of coins we've "already flipped". It doesn't make sense to me to say we are going to go back in time and bias a coin flip that already happened because that would make the current postselection more likely.

EDIT (3/28/11 1 PM): Niel concedes that with my definitions the problem makes sense and doesn't trivialize -- but with the stipulation that I shouldn't call it postselection. Given the amount of confusion, I have to agree with him. So let's call what I defined to be selection, which performs a "forced measurement". I should probably change the name of the complexity classes I defined as well (to not have "Post" in them) so let's call them QMS[k] (quantum-measure-select).

• Can you define MPostBQP more formally? If you just mean that this class has the power to post-select based on the outcome of several bits, then this class should be contained in PostBQP. – Robin Kothari Mar 26 '11 at 22:55
• The key idea isn't to post-select on many bits at once, because as Robin points out this doesn't help. It is to intersperse measurements and postselections. We can't commute these; the order matters. For example it wouldn't work in PostBQP to measure the answer, and then postselect. – Shaun Harker Mar 26 '11 at 23:13
• See the comment on Niel's answer; we can defer both measurements and post-selections until after the quantum evolution. I'm already doing that! The same argument doesn't seem to reorder the postselections after the measurements as well, however, because measurements aren't unitary. In particular, I'm saying the measurements and postselections are non-unitary operations on the quantum state which don't commute, so as far as I can tell we can't without loss defer all the postselections until after all measurements. – Shaun Harker Mar 27 '11 at 15:38
• @Shaun Harker: the fact that the measurements and postselections are non-unitary don't actually give us any more information about whether they will commute. Perhaps you could pinpoint why you think they do not commute? – Niel de Beaudrap Mar 27 '11 at 15:50
• Because of entanglement. Here is an example. Prepare the state $\alpha\left\vert 000 \right> + \sqrt{1/2 - \alpha^2} \left\vert 011 \right> + \sqrt{1/2 - \beta^2} \left\vert 101 \right> + \beta\left\vert 110 \right>$. Choose $0 < \alpha < \beta < 1$. If we first measure the first qubit and then postselect on the third qubit and then measure the second qubit for our outcome, then we obtain $0$ or $1$ with equal probability. If we first postselect on the third qubit, then measure the first qubit, and finally measure the second qubit for our outcome, we obtain $0$ less often than we get $1$. – Shaun Harker Mar 27 '11 at 16:23

It seems from the comments that Shaun has in mind something different from what is normally understood by post-selection. I now understand this to mean that the statistics for any measurements made prior to a particular postselection should not be altered by the subsequent postselection. This is akin to having a projection operator where the normalization is carried out over each branch of the wavefunction corresponding to a particular measurement resut, rather than over the wavefunction as a whole.

In this case, the arguments given in other answers by myself and Neil no longer hold. Indeed it is easily seen that $P^{PP[k]}\subseteq$ MPostBQP[k], since MPostBQP$[k]$ can be viewed as a BQP machine which can make $k$ queries to a PP oracle, and hence $P^{\# P}\subseteq$ MPostBQP.

So now we have a non-trivial lower bound, what about an upper bound? Well, clearly the problem is in PSPACE, but can we do better? Actually, I think we can.

We can write any computation in MPostBQP as a sequence of layers of the form: quantum computation followed by a postselection, followed by a single qubit measurement. Indeed, this might be an alternate way to formulate MPostBQP[k], as a computation composed of $k$ such layers (this is slightly different from Shaun's definition which I believe is intended to count only the number of post-selections), followed by a final layer of classical post-processing. I will use this definition of MPostBQP[k] in the following, as it leads to a more aesthetically pleasing result.

The below is updated from the original version to fix a hole in the proof.

First we wish to calculate the outcome of the measurement of the first qubit measured (not post-selected!). To do this we first note that any quantum computation can be expressed using only Hadamard gates and Toffoli gates, and the amplitude $\alpha_w$ of a particular computational basis state $|w\rangle$ in the output can be written as the sum of at most $2^{H}$ terms $a_{j,w}$, where $H$ is the total number of Hadamard gates, each of which corresponds to a unique computational path. Clearly, $a_{j,w} = \pm 2^{-H/2}$. The probability of obtaining a final state $|w\rangle$ is then given by $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$. We wish to calculate the total probability of measuring a 1. Let $S_0$ be the set of computational basis states which meet the post-selection criteria (i.e. the post-select qubit is 1) and result in 0 for the measured qubit, and let $S_1$ be the set of computational basis states which meet the post-selection criteria and result in 1 for the measured qubit. We can define $$\pi_0^\pm = \sum{w \in S_0} \pm \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}$$ and $$\pi_1^\pm = \pm \sum_{w \in S_1} \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}.$$

The in this case the probability of measuring a 1 conditioned on a 1 for the post-selected qubit is given by $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$. As we can determine this with 4 calls to a #P oracle. We use this to produce a random bit $b_1$ which is 1 with probability $X_1$, the same as the quantum measurement. Thus MPostBQP[1] is in $BPP^{\# P[4]}$.

Next we calculate the measurement result of the second qubit. To do this, we run the same #P queries as for the first layer, but on the circuit obtained by composing the first two layers, and where we postselect on 1 for each of the post-selected qubits, but also on $b_1$ for the output of measurement 1. Note that although this is postselecting on the states of 3 qubits rather than 1, this is a trivial modification to the $\# P$ queries, by simply adding an ancilla which is set only if all 3 qubits meet the conditions required and post-selecting instead on this ancilla. This then generates the correct conditional output probabilities for the result of the second measured qubit, which we label $b_2$. Note that we have now used 8 calls to the #P oracle.

We repeat this process iteratively, so that at a layer $j$ we postselect on 1 for all the $j$ preceeding post-selected qubits and on $b_{i<j}$ for all the previous measurement, and label the outcome of the corresponding $P^{\# P}$ machine $b_j$. In total this has required $4j$ oracle queries.

Thus we have MPostBQP[k] $\subseteq P^{\# P[4k]}$, which combined with the previous result that $P^{PP[k]}\subseteq$ MPostBQP$[k]$, implies that $P^{PP[k]} \subseteq$ MPostBQP[k] $\subseteq BPP^{\# P[4k]}$, and hence MPostBQP $= P^{\# P}$.

[Revised.] I have revised my response based on your revisions to your question, I've retained the content of my original response, but made it shorter. The more elaborate description of the "simulation" process has been replaced, but I suppose that it can be seen by viewing the edit history of this post.

Most people will understand "postselection" in the sense of a conditional probablity. Indeed, the current version of the Wikipedia article on PostBQP describes it that way; and viewed as an operation on density operators (in which one applies a completely-positive trace-non-increasing map Φ, such that Φ2 = Φ, and then renormalizes the trace) one recovers this definition.

Given this definition of postselection, your defintion of an MPostBQP[k] algorithm can be simulated by a PostBQP algorithm, by deferring the post-selections and performing them simultaneously, in a suitable way. This is noted more-or-less explicitly on page 3 of Aaronson's paper Quantum Computing, Postselection, and Probabilistic Polynomial-Time which introduces the class PostBQP.

This can be shown explicitly by noting that, for a sequence of bits P1 ,  P2 ,  ... to be postselected (e.g. in the 1 state, which is usual), there is no difference between conditioning on them being 1 in the middle of the computation and conditioning on them being 1 at the end of the computation, so long as the values of these bits are not changed in the interim. Then, rather than post-selecting on each of them individually being 1, we can compute their logical AND before post-selection and then postselect on that conjunction being 1. Furthermore, computing the AND can be performed at any point between the last transformation of the bit and its post-selection. This will in no way affect the joint statistics of any of the properties of the state.

Thus, using the common definition of postselection in terms of conditional probabilities, we would have MPostBQP[k] = PostBQP for all k > 0.

As I have noted in the comments above, I do not think that the operation which you describe on state vectors — specifically, involving renormalization of state-vectors independently in each branch of the probability distribution over measurement outcomes — corresponds to post-selection, as many people in the field (epsecially experimentalists) would describe the concept. It may even give rise to some 'unphysical' properties, if extended to a mapping on density operators. However, it is a possible means of constructing something like decision trees whose nodes are labelled by state-vectors, and so it is in principle a reasonable process of study in its own right. I just wouldn't call that process 'postselection'.

[Edit.] For the sake of tidiness, I have removed the computed example. I suppose that it can be seen by viewing the edit history of this post.

• The argument appears incomplete. The comment in Aaronson's paper points out we gain no power by interspersing postselections with the unitary evolutions, just as it does not help to intersperse measurements with unitary evolutions. But I'm doing neither; I'm interspersing postselection and measurement. To answer my question in the negative in this fashion would require proving we can always order the post-selections after the measurements without loss of power. (Not obvious to me at all.) The rest of the answer only explains why I defined the class to only postselect on one bit each round. – Shaun Harker Mar 27 '11 at 15:04
• @Shaun Harker: Regardless of whether Aaronson's paper answers your question, my response above should. The effect of postselection is essentially to allow measurements to realize conditional probabilities rather than "non-conditional" probabilities. Post-selecting on the bits $C_j$ is essentially the same as selecting for conjunctions of conditions for conditional probabilities. Those conditional probabilities on the bits $C_j$ do not change, just by deferring the evaluation of whether the condition holds, so long as the bits $C_j$ are left unmolested. – Niel de Beaudrap Mar 27 '11 at 15:41
• It seems you are arguing we get the same statistics if we reorder the postselections and measurements. But if we measure some bits before a postselection, then we measure from a different distribution then we would have if we measured those same bits after the postselection. So the statistics aren't the same. – Shaun Harker Mar 27 '11 at 16:02
• For the purpose of gathering statistics, a postselection can be implemented physically (albeit inefficiently) by simply rejecting trials in which the desired postcondition does not hold. The status of whether a postcondition holds (e.g. "this single bit is in the state |1⟩" or "these five bits are all in the state |1⟩") is not affected by the measurement order, so long as operations are not applied to change bits storing the results. As the fact of whether a trial will be rejected or not is independent of measurement order in PostBQP, we may defer postselection to the end. – Niel de Beaudrap Mar 27 '11 at 18:28
• This characterization of postselection only applies when we perform the postselection before the measurements. The three qubit example I gave already demonstrated this. If I am wrong about this, then please respond by directly refuting this example which gives different statistics depending on the ordering of measurements and postselections. – Shaun Harker Mar 27 '11 at 20:00

It would seem from you definition of MPostBQP, that this is simply PostBQP in fancy dress. Rather than trying to convince you that the measurements can be reordered, perhaps you would find it more convincing to prove MPostBQP = PP, since it is known that PostBQP = PP (see quant-ph/0412187). To prove this, we separate it into two tasks:

1. proving that PP $\subseteq$ MPostBQP and
2. proving that MPostBQP $\subseteq$ PP

The first task is trivial, since PP=PostBQP=MPostBQP[1] $\subseteq$ MPostBQP. The second task is is really the main question here, but is answerable by making a simple adaptation to the proof that PostBQP = PP, given in quant-ph/0412187 (see the Wikipedia page on PostBQP for an outline of the proof).

The following is adapted from the Wikipedia proof sketch for PostBQP = PP.

We can write out the circuit corresponding to any MPostBQP computation as a series of unitary gates and post-selections. Without loss of generality we can assume that once a qubit is post-selected, it is never again acted upon. Thus, the quantum state obtained at the end of the computation is given by $|\psi\rangle = \prod_i (P_i^1 \prod_j A^{ij}) |x\rangle$, where $P_i^1$ denotes the projector for qubit $i$ onto the $|1\rangle$ subspace and $A^{ij}$ are the matrices corresponding to elementary gates. Note that without loss of generality we can assume that all the entries in $A^{ij}$ are real at the expense of an additional qubit.

Now, let $\{p_i\}$ be the set of qubits which are post-selected upon, and let $q$ be the output qubit. We define $\pi_0 = \sum_{w \in S_0} \psi_w^2$ and $\pi_1 = \sum_{w \in S_1} \psi_w^2$, where $S_0$ ($S_1$) is the set of computational basis states for which $p_i = 1 \forall i$ and $q=0$ ($q=1$). The definition of MPostBQP then ensures that either $\pi(1) \geq 2\pi(0)$ or $\pi_0 \geq 2\pi_1$. The idea is then to construct a PP machine to compare $\pi_0$ and $\pi_1$. Expressing $\psi_w$, the part of the final wavesfunction $\psi$ corresponding to a particular computational basis state $w$, as a sum over paths and replacing the indices $i$ and $j$ on $A^{ij}$ with a single index $k$ running from 1 to $G$, we obtain $\psi_w = \sum_{\alpha_1 ... \alpha_G} A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$.

The idea, then, is to construct a PP machine which accepts with probability $\frac{1}{2}(1+C(\pi_1-\pi_0))$ for some $C>0$, since then $x \in L$ would imply that $\frac{1}{2}(1+\pi_1-\pi_0)> \frac{1}{2}$ and $\frac{1}{2}(1+\pi_1-\pi_0) < \frac{1}{2}$ if $x \notin L$.

Now let $\alpha = \{\alpha_i\}$ and $F(A,w,\alpha,X) = A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$. Then $\pi_1 - \pi_0 = \sum_{w \in S_1} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X) - \sum_{w \in S_0} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X)$.

Such a PP machine can then be defined as follows:

1. Pick a computational basis state $w$ uniformly at random.
2. If $w \notin S_0 \cup S_1$, then stop and accept with probability $1/2$, and reject otherwise.
3. Pick two sequences $\alpha$ and $\alpha'$ of $G$ computational basis states uniformly at random.
4. Compute $X = F(A,w,\alpha,x)F(A,w,\alpha',x)$.
5. If $w\in S_1$ then accept with probability $\frac{1+X}{2}$, and reject otherwise. Alternatively, if $w\in S_0$ then accept with probability $\frac{1-X}{2}$, and reject otherwise.

This then puts MPostBQP[k] $\subseteq$ PP, for all $k$, and hence MPostBQP is no more powerful than PostBQP.

• This argument shows that interspersing multiple postselections with unitary evolutions doesn't give us anything more than PP. I totally agree. We can without loss of power defer them to the end and we only need one. I don't see that this argument tells me anything more than that. But my question asks something different; it regards unitary evolution followed by rounds of measurement and selection (with final probabilities reckoned via this decision tree method). So I don't see that this addresses my question. – Shaun Harker Apr 10 '11 at 17:52
• Not to say I don't (extremely) appreciate the effort you put into your response. I just don't see that it addresses what I was really try to get at, which I admittedly didn't do too great of a job of explaining. – Shaun Harker Apr 10 '11 at 17:58
• @Shaun: I don't see the distinction. Are you suggesting that adding measurements changes the power? This is certainly not the case, as measurements are always equivalent to unitary evolution on a larger Hilbert space. – Joe Fitzsimons Apr 10 '11 at 17:59
• @Shaun: My point is that mathematically the situation with measurements and the situation without (but with a suitably enlarged Hilbert space) are identical. I'm not trying to make any kind of philosophical point, or favoring one interpretation of quantum mechanics, I'm simply pointing out that adding measurements makes no difference to the computational power due to a well established (mathematical) result. – Joe Fitzsimons Apr 10 '11 at 18:39
• @Shaun: It seems to me that you are implementing post-selection incorrectly. If you implement it in the normal way (i.e. considering what statistics you get if you consider only those results which fit a particular criteria), then you get PostBQP = MPostBQP, as both Niel and I have shown. You also get identical statistics independent of the ordering for the measurements of the state you gave in the comments. Importantly the first qubit does not give 0 and 1 with equal probability. (to be continued) – Joe Fitzsimons Apr 10 '11 at 19:55