Interactive Proofs via Postselection?

Question

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).

Answer 1

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}$.

Answer 2

[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 Φ² = Φ, 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 P₁ ,  P₂ ,  ... 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.

Answer 3

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.