2
$\begingroup$

I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [KW00] 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].

I have read [AKN98] 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?

$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – Alan May 25 '17 at 12:40
  • $\begingroup$ 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... $\endgroup$ – permanganate May 25 '17 at 15:11
  • 4
    $\begingroup$ I think you're looking for the 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$. $\endgroup$ – Robin Kothari May 26 '17 at 3:19
  • $\begingroup$ 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). $\endgroup$ – permanganate May 26 '17 at 3:45
  • $\begingroup$ It seems that section 2.2.3 of 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 :/ $\endgroup$ – permanganate May 26 '17 at 3:53
4
$\begingroup$

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

  2. Using fresh qubits instead of resets

Reset equivalent to swap ancilla

  1. Deferring measurements until later.

Deferred measurement

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

$\endgroup$
  • $\begingroup$ 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 (crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC09/…). $\endgroup$ – permanganate May 30 '17 at 3:14
  • $\begingroup$ @permanganate They just use their own ancillae. Bring enough to run the protocol. Or bring along some way to make them. $\endgroup$ – Craig Gidney May 30 '17 at 4:07
  • $\begingroup$ 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. $\endgroup$ – permanganate May 30 '17 at 4:15
  • $\begingroup$ @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. $\endgroup$ – Craig Gidney May 30 '17 at 15:53
  • $\begingroup$ @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. $\endgroup$ – Craig Gidney May 30 '17 at 15:55

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.