Does anyone know of a proof for the 'principle of deferred measurement'?

  • 2
    $\begingroup$ Related: this answer of mine works through two important cases. $\endgroup$ Jul 1 at 19:06
  • 2
    $\begingroup$ Can you take the hints from problem 5 of O'Donnell's homework set? I always intuited it as a consequence of the no-communication theorem; a violation of the principle of deferred measurement may allow Alice to take some of qubits, and make a measurement of her qubits whose results were contingent on whether or not Bob waited until the end to measure his qubits, or instead measured his qubits in-situ during the running of the circuit. $\endgroup$
    – Mark S
    Jul 1 at 23:57

I'll assume the "principle of deferred measurement" refers to the equality shown in the figure in the relevant Wikipedia page: the possibility of writing a "classically conditioned" operation as a standard conditional operation followed by a measurement (where measurement basis and basis used for the conditional operation are presumably the same).

I'll also try to keep things general, and thus use generic channels and measurements in lieu of just unitary gates. You can just replace in the following POVMs with standard projective measurements (i.e. $\mu(b)=|b\rangle\!\langle b|$), channels with unitary gates (i.e. $\Phi_b(X)= U_b X U_b^\dagger$), and generic operators/density matrices with pure states (i.e. $X=|\psi\rangle\!\langle\psi|$) to specialise to the case that might be of more direct interest for circuit model computations.

(Measure and then conditional operation) Assume a bipartite space $\newcommand{\Tr}{\operatorname{Tr}}{\cal X\otimes Y}$. Measuring on ${\cal X}$ with a POVM $\{\mu(b):b\in\Sigma\}\subset\operatorname{Pos}({\cal X})$ and applying a channel $\Phi_b\in\mathrm C(\mathcal Y)$ on ${\cal Y}$ conditioned to the measurement outcome $b$ corresponds to a channel of the form $$\Psi\in\mathrm C({\cal X\otimes Y,\cal Y}), \\ \qquad \Psi(X) \equiv %\sum_b \langle \mu(b)\otimes \Phi_b,X\rangle \sum_{b\in\Sigma} \Phi_b(\Tr_1[(\mu(b)\otimes I_{\cal Y})X]) = \sum_{b\in\Sigma} (\mu(b)^*\otimes\Phi_b)(X),\tag1$$ that is, $\Psi=\sum_{b\in\Sigma}\mu(b)^*\otimes \Phi_b$, where $\mu(b)^*:X\mapsto \langle \mu(b),X\rangle\in\mathbb C$ denotes the functional sending any operator in ${\cal X}$ to the corresponding expectation value. Note that

  1. The expression might look convoluted, but I'm literally just saying: we measure the state $X$ in some way codified by $\mu$, and if we get the outcome $b$ we apply some channel $\Phi_b$ on the residual state on ${\cal Y}$.
  2. This expression can equivalently be written in a way that makes the sequential nature of the process more obvious: $\mu(b)^*\otimes \Phi_b$ corresponds to first measure and then apply operation conditionally to the measure. Writing it as $$\mu(b)^*\otimes \Phi_b = \Phi_b\circ(\mu(b)^*\otimes I)$$ might make it clearer.

(Conditional operation and then measure) I suppose a fair way to model a conditional gate/channel is as a channel $\tilde\Psi\in\mathrm C({\cal X\otimes Y})$ of the form $$\tilde\Psi = \sum_{b\in\Sigma} E_{bb}\otimes \Phi_b, \qquad E_{bb}\equiv |b\rangle\!\langle b|.$$ If we then measure the $\mathcal X$ register, the resulting state is $$ \sum_{b\in \Sigma} \langle b|\Tr_2(X)|b\rangle \Phi_b(\Tr_1(X)) = \left[\sum_{b\in\Sigma} (E_{bb})^*\otimes \Phi_b \right] (X), $$ which you might observe to be identical to (1), choosing $\mu(b)=E_{bb}\equiv |b\rangle\!\langle b|$.

  • $\begingroup$ +1 It's cool to know the principle applies to channels and POVMs, too. However, I think it's more general than the ability to commute measurements through controls. It says that for any circuit $C$ with intermediate measurements there is another circuit $C'$ where all measurements are terminal and that agrees with $C$ on all inputs, e.g. measurement sandwiched between two unitaries can be made terminal too (by adding ancilla, see 2nd example here). $\endgroup$ Jul 4 at 6:39
  • $\begingroup$ @AdamZalcman I see. I suppose "circuit with intermediate measurements" could be modeled in general as a channel with Kraus operators corresponding to the different possible measurement outcomes (or more precisely, the different possible combinations of measurement outcomes). Then a possible corresponding matching unitary evolution with measurements only at the end should be the isometry obtained putting all the Kraus operators one above the other, with the measurement outcomes "selecting" a corresponding block in this isometry. $\endgroup$
    – glS
    Jul 4 at 20:49
  • $\begingroup$ I'm not sure whether one can also control the gate decomposition with this type of argument though. That is to say, the isometry/unitary thus obtained might not admit a gate decomposition resembling the original one. Though I guess that might make sense, after all, removing intermediate measurements from a circuit potentially makes for a completely different type of dynamics $\endgroup$
    – glS
    Jul 4 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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