<p>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.</p>

<p>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$ <strong>MPostBQP</strong>[k], since <strong>MPostBQP</strong>$[k]$ can be viewed as a BQP machine which can make $k$ queries to a PP oracle, and hence $P^{\# P}\subseteq$ <strong>MPostBQP</strong>.</p>

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

<p>We can write any computation in <strong>MPostBQP</strong> 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 <strong>MPostBQP</strong>[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 <strong>MPostBQP</strong>[k] in the following, as it leads to a more aesthetically pleasing result.</p>

<p><strong>The below is updated from the original version to fix a hole in the proof.</strong></p>

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

<p>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 <strong>MPostBQP</strong>[1] is in $BPP^{\# P[4]}$. </p>

<p>Next we calculate the measurement result of the second qubit. To do this, we run the same <strong>#P</strong> 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 <strong>#P</strong> oracle.</p>

<p>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&lt;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. </p>

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

CC BY-SA 3.0
2011-04-11T00:09:57.793Z
2011-04-11T14:55:14.413Z
2011-04-11T14:55:14.413Z
Joe Fitzsimons
<p><strong>[Revised.]</strong> 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.</p>

<p>Most people will understand "postselection" in the sense of a conditional probablity. Indeed, the current version of the <a href="http://en.wikipedia.org/wiki/PostBQP#Basic_properties" rel="nofollow">Wikipedia article on <strong>PostBQP</strong></a> describes it that way; and viewed as an operation on density operators (in which one applies a completely-positive trace-non-increasing map &Phi;, such that &Phi;<sup>2</sup>&nbsp;=&nbsp;&Phi;, and then renormalizes the trace) one recovers this definition.</p>

<p>Given this definition of postselection, your defintion of an <strong>MPostBQP</strong>[<em>k</em>] algorithm can be simulated by a <strong>PostBQP</strong> 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 <a href="http://www.arXiv.org/abs/quant-ph/0412187" rel="nofollow"><em>Quantum Computing, Postselection, and Probabilistic Polynomial-Time</em></a> which introduces the class <strong>PostBQP</strong>.</p>

<p>This can be shown explicitly by noting that, for a sequence of bits <em>P</em><sub>1</sub>&nbsp;, &nbsp;<em>P</em><sub>2</sub>&nbsp;, &nbsp;... to be postselected (<em>e.g.</em> in the <code>1</code> state, which is usual), there is no difference between conditioning on them being <code>1</code> in the middle of the computation and conditioning on them being <code>1</code> 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 <code>1</code>, we can compute their logical AND before post-selection and then postselect on that conjunction being <code>1</code>. 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.</p>

<p>Thus, using the common definition of postselection in terms of conditional probabilities, we would have <strong>MPostBQP</strong>[<em>k</em>]&nbsp;=&nbsp;<strong>PostBQP</strong> for all <em>k</em>&nbsp;&gt;&nbsp;0.
<br><br>
As I have noted in the comments above, I do not think that the operation which you describe on state vectors &mdash; specifically, involving renormalization of state-vectors <em>independently in each branch of the probability distribution over measurement outcomes</em> &mdash; 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'.
<br><br>
<strong>[Edit.]</strong> 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.</p>

CC BY-SA 2.5
2011-03-27T15:04:32.803Z
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
CC BY-SA 2.5
2011-03-27T15:41:11.373Z
@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
CC BY-SA 2.5
2011-03-27T16:02:09.387Z
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
CC BY-SA 2.5
2011-03-27T18:28:21.713Z
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
CC BY-SA 2.5
2011-03-27T20:00:24.127Z
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
CC BY-SA 2.5
2011-03-27T20:56:22.720Z
I've analysed your example in my newest revision. Perhaps you can tell me how you obtain the probability distributions which you describe?
Niel de Beaudrap
CC BY-SA 2.5
2011-03-27T21:23:16.343Z
@Niel: it is possible to write your answer using LaTeX. This will avoid some of the formatting troubles you are having.
Dave Clarke
CC BY-SA 2.5
2011-03-27T21:25:51.223Z
@Dave Clarke: thanks, I know about LaTeX editing here, and have used it before. However, I try as much as possible to avoid using it, because (much as I like LaTeX) it loads slowly here.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-27T21:55:55.177Z
@Niel: I just posted my analysis which conflicts with yours. I'm trying to work through yours -- having a little trouble with the typesetting! I'll let you know if I figure out the source of the conflict.
Shaun Harker
CC BY-SA 2.5
2011-03-28T00:53:20.297Z
Okay, here it is: your density matrix version of postselection doesn't correspond to my pure-state formalism version of postselection. Your analysis ought to coincide with mine if you use the definition of density matrix postselection operator I give in my edit.
Shaun Harker
CC BY-SA 2.5
2011-03-28T08:13:52.270Z
@Shaun: See my comments above (esp. the comment beginning with "Having reflected on [...]", which is likely to remain the last or second-to-last comment I make there).
Niel de Beaudrap
CC BY-SA 2.5
2011-03-27T09:46:23.620Z
2011-03-28T09:12:49.950Z
2011-03-28T09:12:49.950Z
Niel de Beaudrap
<p>It would seem from you definition of <strong>MPostBQP</strong>, that this is simply <strong>PostBQP</strong> in fancy dress. Rather than trying to convince you that the measurements can be reordered, perhaps you would find it more convincing to prove <strong>MPostBQP = PP</strong>, since it is known that <strong>PostBQP = PP</strong> (see <a href="http://arxiv.org/abs/quant-ph/0412187" rel="nofollow">quant-ph/0412187</a>). To prove this, we separate it into two tasks: </p>

<ol>
<li>proving that <strong>PP $\subseteq$ MPostBQP</strong> and </li>
<li>proving that <strong>MPostBQP $\subseteq$ PP</strong></li>
</ol>

<p>The first task is trivial, since <strong>PP=PostBQP=MPostBQP[1] $\subseteq$ MPostBQP</strong>. The second task is is really the main question here, but is answerable by making a simple adaptation to the proof that <strong>PostBQP = PP</strong>, given in <a href="http://arxiv.org/abs/quant-ph/0412187" rel="nofollow">quant-ph/0412187</a> (see the <a href="http://en.wikipedia.org/wiki/PostBQP" rel="nofollow">Wikipedia page on PostBQP</a> for an outline of the proof). </p>

<p>The following is adapted from the Wikipedia proof sketch for <strong>PostBQP = PP</strong>. </p>

<p>We can write out the circuit corresponding to any <strong>MPostBQP</strong> 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.</p>

<p>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 <strong>MPostBQP</strong> then ensures that either $\pi(1) \geq 2\pi(0)$ or $\pi_0 \geq 2\pi_1$. The idea is then to construct a <strong>PP</strong> 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}$.</p>

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

<p>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&#39;} F(A,w,\alpha,X)F(A,w,\alpha&#39;,X) - \sum_{w \in S_0} \sum{\alpha,\alpha&#39;} F(A,w,\alpha,X)F(A,w,\alpha&#39;,X)$.</p>

<p>Such a <strong>PP</strong> machine can then be defined as follows:</p>

<ol>
<li>Pick a computational basis state $w$ uniformly at random.</li>
<li>If $w \notin S_0 \cup S_1$, then stop and accept with probability $1/2$, and reject otherwise.</li>
<li>Pick two sequences $\alpha$ and $\alpha&#39;$ of $G$ computational basis states uniformly at random.</li>
<li>Compute $X = F(A,w,\alpha,x)F(A,w,\alpha&#39;,x)$.</li>
<li>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.</li>
</ol>

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

CC BY-SA 3.0
2011-04-10T17:52:37.757Z
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
CC BY-SA 3.0
2011-04-10T17:58:59.510Z
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
CC BY-SA 3.0
2011-04-10T17:59:57.433Z
@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
CC BY-SA 3.0
2011-04-10T18:39:46.407Z
@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
CC BY-SA 3.0
2011-04-10T18:40:44.783Z
What I am suggesting is that this reasoning doesn't apply to the decision tree formalism for "measure" and "select" operations as I defined them. Have you worked the 3-qubit example in the decision tree to see what I am getting at?
Shaun Harker
CC BY-SA 3.0
2011-04-10T18:42:32.537Z
@Shaun: Yes, I have worked through it, but I still don't see any change in the probability of the unmeasured qubit being in a given state depending on the ordering.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-10T19:20:41.257Z
Pertaining to philosophy: when one adds something like "quantum suicide" to the mix, then things that were empirically moot and only philosophical in nature suddenly become empirical (e.g. Max Tegmark's quantum suicide experiment to prove many-worlds). The decision tree model to incorporate selections and measurements is one in which measurements are fundamentally irreversible. So in this framework I don't see that we can proclaim them equivalent to unitary evolutions, which are fundamentally reversible.
Shaun Harker
CC BY-SA 3.0
2011-04-10T19:21:47.310Z
I mean, have you literally drawn the decision tree, labelled the nodes with appropriate pure states, labelled the edge weights according to the rules I gave, and looked at the probability distribution you get on the leaves?
Shaun Harker
CC BY-SA 3.0
2011-04-10T19:38:53.373Z
@Shaun: Ah, ok, I see your point about the decission tree, though I'm not sure this really coincides with the usual understanding of postselection.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-10T19:55:24.897Z
@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
CC BY-SA 3.0
2011-04-10T19:59:17.420Z
Yes, yes, that's precisely right. It doesn't correspond to it, you are right. I think I should call it "selection" instead of post-selection, since I think people take the "post" to mean they can understand it with by rejection trials "post"-experiment (giving you conditional probability). I really mean adding the fantasy power of instantaneously altering physics to guarantee an outcome of a measurement, (like with quantum suicide, say) and also that we have some real irreversibility in measurements and these selections which is implicit in the decision tree scheme.
Shaun Harker
CC BY-SA 3.0
2011-04-10T19:59:27.043Z
(continued) You seem to have something very different in mind, which I now understand to be a collapse onto a particular branch of the wave function in such a way that the probability of getting a particular branch is not affected by the postselection.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-10T20:00:35.327Z
Do note that I've already said in an edit to my question that I agree it shouldn't be called post-selection.
Shaun Harker
CC BY-SA 3.0
2011-04-10T20:01:02.940Z
In this case, surely **MPostBQP = $P^{PP}$**.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-10T20:01:32.017Z
Yes, that comment about the branches hits the nail on the head. That's precisely the property that I'm trying to exploit to get more computational power. That is what the question is really about.
Shaun Harker
CC BY-SA 3.0
2011-04-10T20:04:32.077Z
If you could give a fully fleshed out explanation for why that is so, I would surely accept your answer!
Shaun Harker
CC BY-SA 3.0
2011-04-10T20:10:17.000Z
Ok, I'll give it a go.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-10T16:56:55.360Z
2011-04-10T16:56:55.360Z
Joe Fitzsimons
<p>Define the computational model MPostBQP to be identical to <a href="http://arxiv.org/pdf/quant-ph/0412187v1" rel="nofollow">PostBQP</a> except we allow polynomially many qubit measurements before the post-selection and final measurement. </p>

<blockquote>
  <p>Can we give any evidence indicating that MPostBQP is more powerful than PostBQP? </p>
</blockquote>

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

<p>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:</p>

<blockquote>
  <p>Do we have AM[k] $\subset$ MPostBQP[k]?</p>
</blockquote>

<p>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 <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#am" rel="nofollow">there is an oracle relative to which AM is not contained in PP</a>, this could give an affirmative answer for my first question.</p>

<p>Finally, for the polynomially many rounds case,</p>

<blockquote>
  <p>Do we have PSPACE $\subset$ MPostBQP[poly]? If so, is it equality?</p>
</blockquote>

<p>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 <em>is</em>) all of PSPACE.</p>

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

<p>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:</p>

<blockquote>
  <p>Procedure: <em>Step 1.</em> Apply the unitary operator corresponding to $C_n$ to the input state $\left\vert 0\cdots  0\right&gt; \otimes \left\vert x \right&gt;$. Note the length of the first $\left\vert0\cdots 0\right&gt;$ register is at most polynomial in the length of $x$. <em>Step 2.</em> 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&gt;$ (and have a guarantee that the probability is non-zero so the postselection is valid, of course). <em>Step 3.</em> Finally, measure a last qubit in the first register, and return true if we measure $\left \vert 1 \right&gt;$ and false otherwise.</p>
</blockquote>

<p>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. </p>

<p>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: <em>Postselecting on the kth bit</em> 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!</p>

<p>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&gt; \left&lt; a_i \right\vert$. Let $\left\vert A_i \right&gt;$ 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&gt; \left&lt; A_i \right\vert$.</p>

<p>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) <em>we already watched happen.</em> 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.</p>

<p>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 <em>postselection</em>. Given the amount of confusion, I have to agree with him. So let's call what I defined to be <em>selection</em>, 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). </p>

CC BY-SA 2.5
2011-03-26T22:55:52.460Z
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
CC BY-SA 2.5
2011-03-26T23:13:45.593Z
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
CC BY-SA 2.5
2011-03-27T15:38:07.440Z
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
CC BY-SA 2.5
2011-03-27T15:50:45.923Z
@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
CC BY-SA 2.5
2011-03-27T16:23:03.487Z
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
CC BY-SA 2.5
2011-03-27T20:59:09.663Z
I don't see how you get these probabilities; see me analysis in my revised post below.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-27T21:20:29.247Z
@Shaun Harker: with respect to your edit at about 5PM EDT, the operational definition of "project and renormalize" is identical to the abstract definition in terms of conditional probabilities. Indeed, if your look at what it would mean operationally to evaluate the conditional probability, it is precisely to project and renormalize. You aren't actually generalizing beyond the usual formalism.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-27T21:46:18.820Z
First scheme: Measuring the first qubit yields 1 or 0 in equal probabilities. After we postselect (for zero) on the third qubit, then the measurement of the second qubit is guaranteed to match the measurement of the first qubit. So we get $1/2$ odds for the outcome 1. Second scheme: We postselect on the third qubit first. This changes the state to $(\alpha \left\vert 000 \right> + \beta \left\vert 110 \right>)/\sqrt{\alpha^2 + \beta^2}$. Again the first and second qubits must measure the same, but this time we have $\beta^2 / (\alpha^2 + \beta^2)$ odds for the outcome 1.
Shaun Harker
CC BY-SA 2.5
2011-03-27T22:00:25.640Z
The problem is that, in the meausurement/postselection order 1-3-2, upon post-selecting the third bit to be 0 there is no longer a uniform distribution on the value of the first bit. We must reject those trials in which the third bit is 1: these occur in an uneven distribution across the possible values of the first bit.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-27T22:06:58.723Z
But doesn't this talk of "trials" and "rejection" mean you are adopting the conditional probability definition of postselection, and not the nonlinear operator definition?
Shaun Harker
CC BY-SA 2.5
2011-03-27T22:14:49.407Z
@Shaun: I fail to see the difference. Acting on density operators, postselection is a non-linear operator which is easily defined *in terms of* linear CPTP maps; the non-linearity which one adds (of renormalization) has the effect of precisely capturing the notion of conditional probability. (To put it another way: when you renormalize, just what can the renormalization factor be used to represent?)
Niel de Beaudrap
CC BY-SA 2.5
2011-03-28T07:42:39.680Z
@Shaun: with respect to your edit of 9pm EDT, I think there is a problem with the idea of preserving "the statistics of events (measurements) we already watched happen". When we perform a measurement, we only obtain a sample, not a distribution; if you are wary of commuting postselection with measurement, then you should distrust the idea that postselection should preserve the probability distribution of any measurement which precedes it, and therefore abandon any restriction that the statistics of such measurements be preserved by the postselection.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-28T07:49:20.783Z
@Shaun: I would strongly suggest to you use density operators (not "my" analysis using density operators, but simply *an* analysis using density operators) for such questions. While I was also taught initially to work using only pure state vectors, in my experience these should actually be treated as 'derived' concepts in quantum informatics, a useful shorthand for those cases when one is dealing with a rank-1 density operator. Here, we are definitely *not* dealing with pure states (*i.e.* rank-1 operators), because mixtures are involved.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-28T08:11:33.940Z
@Shaun: Having reflected on your interest in a definition "which does not trivialize [your] question", I will stop trying to convince you that you are using the wrong definition of 'postselection'. Your notion can certainly be used as a means of constructing something like a decision tree, with nodes labelled by state-vectors, in a well-defined manner; as such, it's a reasonable mathematical process to study. Just be aware that this process is not "postselection", as many in the field (particularly experimentalists) understand the term. So, just be cautious about calling it that.
Niel de Beaudrap
CC BY-SA 2.5
2011-03-30T10:07:48.563Z
@Shaun: You assert that post selection and measurements don't commute. I honestly don't see how you get this. The projector onto the $|0\rangle$ is $(I+Z)/2$ which clearly commutes with a measurement of the $Z$ observable.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-31T03:04:23.643Z
I think the best way to see what I am saying is the decision tree notion, like Niel said. I'll try to rewrite the question to clarify it when I get some time... this has turned out to be far more troublesome that I expected.
Shaun Harker
CC BY-SA 2.5
2011-04-04T22:57:01.097Z
@Shaun: I've read through everything again, and it still seems to me that Niel is correct and this is trivially PostBQP. Your analysis above claiming to prove that the measurements don't commute is entirely incorrect, since after the measurement and postselection, only one outcome is possible. You seem to be confusing the issue by comparing the path dependent intermediate probabilities.
Joe Fitzsimons
CC BY-SA 2.5
2011-04-06T19:41:46.033Z
@Joe: If you read what Niel is saying closely, you'll see he actually says "it's a reasonable mathematical process to study". He just doesn't like using the term "postselection" for the process I describe. I'm very, very, very aware that if you define post-selection as conditional probability then it trivializes my question. Are you saying that "selection", as I defined it, still gives us equality to PostBQP? Because that I am not aware of, nor has Niel argued is true, and if you can prove it, I'd love for it to be an answer!
Shaun Harker
CC BY-SA 2.5
2011-04-07T11:57:48.683Z
@Shaun: If my understanding is correct that you are simply arguing about the order measurements and postselection are performed in, then yes, this is still PostBQP. My understanding of what you mean by postselection is projecting onto a specified branch of the wave function. Please let me know if this is a correct understanding of what you are asking, in which case I will post a proof as an answer.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-09T07:31:17.730Z
@Joe: Construct a binary tree with a single root, labeled with a pure state $U\left\vert x \right>$ arising from a polytime quantum computation. Label children of a node at depth $d$ with the renormalized projections corresponding to the outcomes of measuring the $d_i$th qubit. Label edge weights either by Born's rule for measure (M) nodes, or with 0 and 1 for select (S) nodes. Label leaf nodes either "yes" or "no". As transition probabilities the weights give a distribution on "yes" & "no" leaves. A bounded error complexity class arises. Extra rules on ordering M & S give the classes above.
Shaun Harker
CC BY-SA 3.0
2011-04-09T07:42:55.987Z
I (implicitly) used this decision-tree definition to work out the three-qubit example.  What I found was that when I permuted the order of measure and select moves and reconstructed the corresponding decision tree, I obtained a different distribution on the outcomes.
Shaun Harker
<cc.complexity-theory><complexity-classes><quantum-computing><interactive-proofs>
Interactive Proofs via Postselection?
Shaun Harker
# Interactive Proofs via Postselection?

(Asked by: username_0 on 2011-03-26)

Define the computational model MPostBQP to be identical to [PostBQP](http://arxiv.org/pdf/quant-ph/0412187v1) 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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#am), 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).

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, interactive-proofs
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_2**: @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?  
> **username_0**: 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$.  
> **username_2**: I don't see how you get these probabilities; see me analysis in my revised post below.  
> **username_2**: @Shaun Harker: with respect to your edit at about 5PM EDT, the operational definition of "project and renormalize" is identical to the abstract definition in terms of conditional probabilities. Indeed, if your look at what it would mean operationally to evaluate the conditional probability, it is precisely to project and renormalize. You aren't actually generalizing beyond the usual formalism.  
> **username_0**: First scheme: Measuring the first qubit yields 1 or 0 in equal probabilities. After we postselect (for zero) on the third qubit, then the measurement of the second qubit is guaranteed to match the measurement of the first qubit. So we get $1/2$ odds for the outcome 1. Second scheme: We postselect on the third qubit first. This changes the state to $(\alpha \left\vert 000 \right> + \beta \left\vert 110 \right>)/\sqrt{\alpha^2 + \beta^2}$. Again the first and second qubits must measure the same, but this time we have $\beta^2 / (\alpha^2 + \beta^2)$ odds for the outcome 1.  
> **username_2**: The problem is that, in the meausurement/postselection order 1-3-2, upon post-selecting the third bit to be 0 there is no longer a uniform distribution on the value of the first bit. We must reject those trials in which the third bit is 1: these occur in an uneven distribution across the possible values of the first bit.  
> **username_0**: But doesn't this talk of "trials" and "rejection" mean you are adopting the conditional probability definition of postselection, and not the nonlinear operator definition?  
> **username_2**: @Shaun: I fail to see the difference. Acting on density operators, postselection is a non-linear operator which is easily defined *in terms of* linear CPTP maps; the non-linearity which one adds (of renormalization) has the effect of precisely capturing the notion of conditional probability. (To put it another way: when you renormalize, just what can the renormalization factor be used to represent?)  
> **username_2**: @Shaun: with respect to your edit of 9pm EDT, I think there is a problem with the idea of preserving "the statistics of events (measurements) we already watched happen". When we perform a measurement, we only obtain a sample, not a distribution; if you are wary of commuting postselection with measurement, then you should distrust the idea that postselection should preserve the probability distribution of any measurement which precedes it, and therefore abandon any restriction that the statistics of such measurements be preserved by the postselection.  
> **username_2**: @Shaun: I would strongly suggest to you use density operators (not "my" analysis using density operators, but simply *an* analysis using density operators) for such questions. While I was also taught initially to work using only pure state vectors, in my experience these should actually be treated as 'derived' concepts in quantum informatics, a useful shorthand for those cases when one is dealing with a rank-1 density operator. Here, we are definitely *not* dealing with pure states (*i.e.* rank-1 operators), because mixtures are involved.  
> **username_2**: @Shaun: Having reflected on your interest in a definition "which does not trivialize [your] question", I will stop trying to convince you that you are using the wrong definition of 'postselection'. Your notion can certainly be used as a means of constructing something like a decision tree, with nodes labelled by state-vectors, in a well-defined manner; as such, it's a reasonable mathematical process to study. Just be aware that this process is not "postselection", as many in the field (particularly experimentalists) understand the term. So, just be cautious about calling it that.  
> **username_3**: @Shaun: You assert that post selection and measurements don't commute. I honestly don't see how you get this. The projector onto the $|0\rangle$ is $(I+Z)/2$ which clearly commutes with a measurement of the $Z$ observable.  
> **username_0**: I think the best way to see what I am saying is the decision tree notion, like Niel said. I'll try to rewrite the question to clarify it when I get some time... this has turned out to be far more troublesome that I expected.  
> **username_3**: @Shaun: I've read through everything again, and it still seems to me that Niel is correct and this is trivially PostBQP. Your analysis above claiming to prove that the measurements don't commute is entirely incorrect, since after the measurement and postselection, only one outcome is possible. You seem to be confusing the issue by comparing the path dependent intermediate probabilities.  
> **username_0**: @Joe: If you read what Niel is saying closely, you'll see he actually says "it's a reasonable mathematical process to study". He just doesn't like using the term "postselection" for the process I describe. I'm very, very, very aware that if you define post-selection as conditional probability then it trivializes my question. Are you saying that "selection", as I defined it, still gives us equality to PostBQP? Because that I am not aware of, nor has Niel argued is true, and if you can prove it, I'd love for it to be an answer!  
> **username_3**: @Shaun: If my understanding is correct that you are simply arguing about the order measurements and postselection are performed in, then yes, this is still PostBQP. My understanding of what you mean by postselection is projecting onto a specified branch of the wave function. Please let me know if this is a correct understanding of what you are asking, in which case I will post a proof as an answer.  
> **username_0**: @Joe: Construct a binary tree with a single root, labeled with a pure state $U\left\vert x \right>$ arising from a polytime quantum computation. Label children of a node at depth $d$ with the renormalized projections corresponding to the outcomes of measuring the $d_i$th qubit. Label edge weights either by Born's rule for measure (M) nodes, or with 0 and 1 for select (S) nodes. Label leaf nodes either "yes" or "no". As transition probabilities the weights give a distribution on "yes" & "no" leaves. A bounded error complexity class arises. Extra rules on ordering M & S give the classes above.  
> **username_0**: I (implicitly) used this decision-tree definition to work out the three-qubit example.  What I found was that when I permuted the order of measure and select moves and reconstructed the corresponding decision tree, I obtained a different distribution on the outcomes.  

---

## 3 answers

### Answer by username_3 on 2011-04-11. Score: 5 | Accepted answer

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

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 by username_2 on 2011-03-27. Score: 5

**[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**](http://en.wikipedia.org/wiki/PostBQP#Basic_properties) 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*](http://www.arXiv.org/abs/quant-ph/0412187) which introduces the class **PostBQP**.

This can be shown explicitly by noting that, for a sequence of bits *P*1 ,  *P*2 ,  ... 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_2**: I've analysed your example in my newest revision. Perhaps you can tell me how you obtain the probability distributions which you describe?  
> **username_4**: @Niel: it is possible to write your answer using LaTeX. This will avoid some of the formatting troubles you are having.  
> **username_2**: @Dave Clarke: thanks, I know about LaTeX editing here, and have used it before. However, I try as much as possible to avoid using it, because (much as I like LaTeX) it loads slowly here.  
> **username_0**: @Niel: I just posted my analysis which conflicts with yours. I'm trying to work through yours -- having a little trouble with the typesetting! I'll let you know if I figure out the source of the conflict.  
> **username_0**: Okay, here it is: your density matrix version of postselection doesn't correspond to my pure-state formalism version of postselection. Your analysis ought to coincide with mine if you use the definition of density matrix postselection operator I give in my edit.  
> **username_2**: @Shaun: See my comments above (esp. the comment beginning with "Having reflected on [...]", which is likely to remain the last or second-to-last comment I make there).  

---

### Answer by username_3 on 2011-04-10. Score: 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](http://arxiv.org/abs/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](http://arxiv.org/abs/quant-ph/0412187) (see the [Wikipedia page on PostBQP](http://en.wikipedia.org/wiki/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**.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: @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.  
> **username_3**: @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.  
> **username_0**: What I am suggesting is that this reasoning doesn't apply to the decision tree formalism for "measure" and "select" operations as I defined them. Have you worked the 3-qubit example in the decision tree to see what I am getting at?  
> **username_3**: @Shaun: Yes, I have worked through it, but I still don't see any change in the probability of the unmeasured qubit being in a given state depending on the ordering.  
> **username_0**: Pertaining to philosophy: when one adds something like "quantum suicide" to the mix, then things that were empirically moot and only philosophical in nature suddenly become empirical (e.g. Max Tegmark's quantum suicide experiment to prove many-worlds). The decision tree model to incorporate selections and measurements is one in which measurements are fundamentally irreversible. So in this framework I don't see that we can proclaim them equivalent to unitary evolutions, which are fundamentally reversible.  
> **username_0**: I mean, have you literally drawn the decision tree, labelled the nodes with appropriate pure states, labelled the edge weights according to the rules I gave, and looked at the probability distribution you get on the leaves?  
> **username_3**: @Shaun: Ah, ok, I see your point about the decission tree, though I'm not sure this really coincides with the usual understanding of postselection.  
> **username_3**: @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)  
> **username_0**: Yes, yes, that's precisely right. It doesn't correspond to it, you are right. I think I should call it "selection" instead of post-selection, since I think people take the "post" to mean they can understand it with by rejection trials "post"-experiment (giving you conditional probability). I really mean adding the fantasy power of instantaneously altering physics to guarantee an outcome of a measurement, (like with quantum suicide, say) and also that we have some real irreversibility in measurements and these selections which is implicit in the decision tree scheme.  
> **username_3**: (continued) You seem to have something very different in mind, which I now understand to be a collapse onto a particular branch of the wave function in such a way that the probability of getting a particular branch is not affected by the postselection.  
> **username_0**: Do note that I've already said in an edit to my question that I agree it shouldn't be called post-selection.  
> **username_3**: In this case, surely **MPostBQP = $P^{PP}$**.  
> **username_0**: Yes, that comment about the branches hits the nail on the head. That's precisely the property that I'm trying to exploit to get more computational power. That is what the question is really about.  
> **username_0**: If you could give a fully fleshed out explanation for why that is so, I would surely accept your answer!  
> **username_3**: Ok, I'll give it a go.  

---

