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). 
Interactive Proofs via Postselection?
cc.complexity theory;complexity classes;quantum computing;interactive proofs
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}$.  