<p>The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae.</p>

<p>Any circuit with an intermediate measurement can be converted to a circuit that only has measurement as the last step. Doing so involves performing three simple transformations again and again:</p>

<ol>
<li><p>Moving measurements onto a fresh ancilla qubit.</p>

<p><a href="https://i.sstatic.net/uRVv0.png" rel="noreferrer"><img src="https://i.sstatic.net/uRVv0.png" alt="Ancilla measure"></a></p></li>
<li><p>Using fresh qubits instead of resets</p></li>
</ol>

<p><a href="https://i.sstatic.net/HCak8.png" rel="noreferrer"><img src="https://i.sstatic.net/HCak8.png" alt="Reset equivalent to swap ancilla"></a></p>

<ol start="3">
<li>Deferring measurements until later.</li>
</ol>

<p><a href="https://i.sstatic.net/hAyhV.png" rel="noreferrer"><img src="https://i.sstatic.net/hAyhV.png" alt="Deferred measurement"></a></p>

<p>Once you have a circuit where all the measurements happen at the end, replace the measurements with CNOTs onto fresh ancillae and throw away the ancillae without doing anything to them (or do stuff to them, it doesn't matter).</p>

<p>(Note that, if you do any classical post-processing of the measurement results, that post-processing should be moved into the quantum circuit. We're taking away the mechanism by which information was reaching the classical computer.)</p>

<p>The resulting circuit is unitary, and a black-box drop-in for the original circuit (except for all the extra clean ancillae that must be fed in).</p>

CC BY-SA 3.0
2017-05-30T03:14:49.223Z
My trouble is how can this be used in quantum interactive proofs? If you assume that the prover only uses unitaries, then it means that he must send the ancillae qubits that will allow the verifier to do his deferred measurements. This is not realistic (what if the prover performs so many measurements that he would have to send a lot of extra qubits for instance?). That's why I'm wondering if there is something else in the above paper (http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC09/KW00-parallel_qip.pdf).
permanganate
CC BY-SA 3.0
2017-05-30T04:07:54.570Z
@permanganate They just use their own ancillae. Bring enough to run the protocol. Or bring along some way to make them.
Craig Gidney
CC BY-SA 3.0
2017-05-30T04:15:47.010Z
So who is  measuring the ancillae of the prover? The prover himself? In this case we can't assume that the prover only uses unitaries.
permanganate
CC BY-SA 3.0
2017-05-30T15:53:45.313Z
@permanganate Measure them? Why would you do that? Just throw them away. Well, unless they store the result of the protocol. Keep those ones. Return them (unmeasured) as the answer. Even if the prover doesn't use unitaries, we can model them as if they did.
Craig Gidney
CC BY-SA 3.0
2017-05-30T15:55:20.657Z
@permanganate Even if the prover uses measurement, we can model them as if they didn't. Measurement doesn't give them any more power than clean ancillae do.
Craig Gidney
CC BY-SA 3.0
2017-05-31T05:43:20.380Z
Thank you, I think I got it: I hadn't realized that it doesn't change anything whether the prover measures the ancillae or not. I thought that deferred measurement requires the ancillae being measured at some point, but in fact it's not necessary if you don't use the outcome of the measurement.
permanganate
CC BY-SA 3.0
2017-05-26T18:14:40.710Z
2017-05-26T18:19:41.683Z
2017-05-26T18:19:41.683Z
Craig Gidney
<p>I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from <a href="http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC09/KW00-parallel_qip.pdf" rel="nofollow noreferrer">[KW00]</a> for instance:</p>

<blockquote>
  <p>Often we will describe quantum circuits in a high-level manner that suggests that measurements are performed at various times as the circuits are applied to some collection of qubits. In fact, as all of our circuits are assumed to be unitary, such measurements do not occur, but rather are assumed to be simulated by unitary gates as described in <a href="https://arxiv.org/pdf/quant-ph/9806029.pdf" rel="nofollow noreferrer">[AKN98]</a>.</p>
</blockquote>

<p>I have read <a href="https://arxiv.org/pdf/quant-ph/9806029.pdf" rel="nofollow noreferrer">[AKN98]</a> but it points to other papers (lemmas 1 and 4). It seems to be a standard result in quantum computing that just requires to add ancilla qubits. Could someone explain how it's done?</p>

CC BY-SA 3.0
2017-05-25T12:40:27.100Z
Quantum measurements cannot be represented by unitary matrices because (among other reasons) quantum measurements are not invertible. The way I read this quote is as saying "because we assume our circuits are representable by unitary matrices, we must therefore also assume that no measurements occur."
Alan
CC BY-SA 3.0
2017-05-25T15:11:15.713Z
I don't think it's the meaning of this quote. [KW00] is talking about quantum interactive proofs. By definition, the prover is all powerful in this framework and she can apply whatever unitary/measurements she wants. However, the action of the prover (at each round) is modeled by a unitary matrix in most of the papers about QIP. There must be an underlying argument...
permanganate
CC BY-SA 3.0
2017-05-26T03:19:41.713Z
I think you're looking for the [Deferred Measurement Principle](https://en.wikipedia.org/wiki/Deferred_Measurement_Principle). Essentially, you can avoid measuring a qubit by first "copying" its output to another fresh qubit set to $|0\rangle$ by doing a CNOT operation. This new qubit is not reused and is measured at the end. Now use the original qubit as if it were measured by the CNOT operation. That is, if you wanted to apply a unitary to some other qubits conditioned on this qubit being measured as a "1", use a controlled unitary conditioned on this qubit being $|1\rangle$.
Robin Kothari
CC BY-SA 3.0
2017-05-26T03:45:28.737Z
So for interactive proofs for instance the prover sends these fresh qubits to the verifier that has to measure them at the end? It seems strange because there could have been too many qubits to send (if the prover does a lot of measurements).
permanganate
CC BY-SA 3.0
2017-05-26T03:53:18.897Z
It seems that section 2.2.3 of https://arxiv.org/pdf/1610.01664.pdf answers my question: given a quantum channel $\Phi$ that transforms
an n-qubit register $X$ into an m-qubit register $Y$ one can add an $n+m$ qubits register $Z$ such that there exists a unitary $U$ acting on $n+2m$ qubits with $\Phi( |\psi\rangle) = Tr_Z(U|\psi\rangle \otimes |0^{2m}\rangle)$ for any $|\psi\rangle \in X$. This is presented as a consequence of Stinespring’s dilation theorem, but it doesn't seem easy to prove :/
permanganate
<quantum-computing><quantum-information><interactive-proofs>
Simulating quantum measurements by unitaries
permanganate
# Simulating quantum measurements by unitaries

(Asked by: username_0 on 2017-05-25)

I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [[KW00]](http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC09/KW00-parallel_qip.pdf) for instance:

> Often we will describe quantum circuits in a high-level manner that suggests that measurements are performed at various times as the circuits are applied to some collection of qubits. In fact, as all of our circuits are assumed to be unitary, such measurements do not occur, but rather are assumed to be simulated by unitary gates as described in [[AKN98]](https://arxiv.org/pdf/quant-ph/9806029.pdf).

I have read [[AKN98]](https://arxiv.org/pdf/quant-ph/9806029.pdf) but it points to other papers (lemmas 1 and 4). It seems to be a standard result in quantum computing that just requires to add ancilla qubits. Could someone explain how it's done?

**Tags:** quantum-computing, quantum-information, interactive-proofs
> **Comments:**
> **username_1**: Quantum measurements cannot be represented by unitary matrices because (among other reasons) quantum measurements are not invertible. The way I read this quote is as saying "because we assume our circuits are representable by unitary matrices, we must therefore also assume that no measurements occur."  
> **username_0**: I don't think it's the meaning of this quote. [KW00] is talking about quantum interactive proofs. By definition, the prover is all powerful in this framework and she can apply whatever unitary/measurements she wants. However, the action of the prover (at each round) is modeled by a unitary matrix in most of the papers about QIP. There must be an underlying argument...  
> **username_2**: I think you're looking for the [Deferred Measurement Principle](https://en.wikipedia.org/wiki/Deferred_Measurement_Principle). Essentially, you can avoid measuring a qubit by first "copying" its output to another fresh qubit set to $|0\rangle$ by doing a CNOT operation. This new qubit is not reused and is measured at the end. Now use the original qubit as if it were measured by the CNOT operation. That is, if you wanted to apply a unitary to some other qubits conditioned on this qubit being measured as a "1", use a controlled unitary conditioned on this qubit being $|1\rangle$.  
> **username_0**: So for interactive proofs for instance the prover sends these fresh qubits to the verifier that has to measure them at the end? It seems strange because there could have been too many qubits to send (if the prover does a lot of measurements).  
> **username_0**: It seems that section 2.2.3 of https://arxiv.org/pdf/1610.01664.pdf answers my question: given a quantum channel $\Phi$ that transforms an n-qubit register $X$ into an m-qubit register $Y$ one can add an $n+m$ qubits register $Z$ such that there exists a unitary $U$ acting on $n+2m$ qubits with $\Phi( |\psi\rangle) = Tr_Z(U|\psi\rangle \otimes |0^{2m}\rangle)$ for any $|\psi\rangle \in X$. This is presented as a consequence of Stinespring’s dilation theorem, but it doesn't seem easy to prove :/  

---

## 1 answers

### Answer by username_3 on 2017-05-26. Score: 6 | Accepted answer

The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae.

Any circuit with an intermediate measurement can be converted to a circuit that only has measurement as the last step. Doing so involves performing three simple transformations again and again:

1. Moving measurements onto a fresh ancilla qubit.

   [![Ancilla measure](https://i.sstatic.net/uRVv0.png)](https://i.sstatic.net/uRVv0.png)
2. Using fresh qubits instead of resets

[![Reset equivalent to swap ancilla](https://i.sstatic.net/HCak8.png)](https://i.sstatic.net/HCak8.png)

3. Deferring measurements until later.

[![Deferred measurement](https://i.sstatic.net/hAyhV.png)](https://i.sstatic.net/hAyhV.png)

Once you have a circuit where all the measurements happen at the end, replace the measurements with CNOTs onto fresh ancillae and throw away the ancillae without doing anything to them (or do stuff to them, it doesn't matter).

(Note that, if you do any classical post-processing of the measurement results, that post-processing should be moved into the quantum circuit. We're taking away the mechanism by which information was reaching the classical computer.)

The resulting circuit is unitary, and a black-box drop-in for the original circuit (except for all the extra clean ancillae that must be fed in).

> **Comments:**
> **username_0**: My trouble is how can this be used in quantum interactive proofs? If you assume that the prover only uses unitaries, then it means that he must send the ancillae qubits that will allow the verifier to do his deferred measurements. This is not realistic (what if the prover performs so many measurements that he would have to send a lot of extra qubits for instance?). That's why I'm wondering if there is something else in the above paper (http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC09/KW00-parallel_qip.pdf).  
> **username_3**: @permanganate They just use their own ancillae. Bring enough to run the protocol. Or bring along some way to make them.  
> **username_0**: So who is  measuring the ancillae of the prover? The prover himself? In this case we can't assume that the prover only uses unitaries.  
> **username_3**: @permanganate Measure them? Why would you do that? Just throw them away. Well, unless they store the result of the protocol. Keep those ones. Return them (unmeasured) as the answer. Even if the prover doesn't use unitaries, we can model them as if they did.  
> **username_3**: @permanganate Even if the prover uses measurement, we can model them as if they didn't. Measurement doesn't give them any more power than clean ancillae do.  
> **username_0**: Thank you, I think I got it: I hadn't realized that it doesn't change anything whether the prover measures the ancillae or not. I thought that deferred measurement requires the ancillae being measured at some point, but in fact it's not necessary if you don't use the outcome of the measurement.  

---

