Uncomputing measurement gate?

So one of Aaronson's lecture note (https://www.scottaaronson.com/democritus/lec10.html) pointed out that, if we'd like to simulate a BQP-oracle, technically speaking, the oracle of address-target form. $$\forall x\in\{0,1\}^n, b\in\{0,1\}: |x,b\rangle\mapsto|x,f(x)\oplus b\rangle$$

Because such oracle should linearly extend to superposition inputs, we must detangle the output bit with internal (intermediate) qubits. Then one way is to "un-compute" the entire program, namely for BQP circuit $$\tilde{f}$$ computing $$f$$. First compute $$\tilde{f}$$, then apply a CNOT on the answer bit, finally uncompute everything except the CNOT-source bit.

So my problem is, in the previous paragraph, he just simulate the measurement gate by a unitary gate. When we perform the un-computing step, we also uncompute that "fake measurement gate". However, it seems not even make sense to un-measure a state. How should I argue that these techniques would work and eventually take us to $$BQP^{BQP}=BQP$$ result?

• Could you point out exactly where in the note does Aaronson says a CNOT gate is used? AFAICT he only says to take the query's result and copy it. – dkaeae Jul 3 '19 at 8:17
• By copy he meant CNOT from the result qubit to another intially-zero qubit. – Taylor Huang Jul 3 '19 at 15:05

You seem to be under the impression that we need to measure a qubit in order to copy it. That is not the case because the copy operation is performed by the mapping $$|a,b\rangle \mapsto |a,a \oplus b\rangle$$ which, when $$b = 0$$, can be realized by a CNOT gate. There is no measurement involved at all. You only need to know how many ancilla bits (i.e., initialized to zero) you need beforehand so as to have an adequate quantum circuit size.

• Actually that's not what I meant. I meant the following: In general a circuit (even decisional circuit) might contain multiple measurements. So if we follow what Aaronson have done, i.e. use unitary gate to simulate all except the last measurements, then whenever we want to detangle the inner state from answer bit (because we want to implement its oracle), we will have to un-compute the simulated measurement. How does that even make sense? – Taylor Huang Jul 4 '19 at 6:21
• $\textsf{BQP}$ is defined in terms of (uniform) quantum circuits, which are made only of unitary operations and contains no measurement gates. The measurement is performed only at the end to collapse the circuit's output to a single value. A quantum computation may contain arbitrary measurement gates, but that is a different notion. – dkaeae Jul 4 '19 at 7:18
• They could be the same. Note that any deterministic computation could be simulated by quantum gates. So whatever you do after measurement could be implemented as a quantum circuit. For decisional problem, one could only took the measurement at the end, and substitute each other measurement into a circuit snippet. As said by Aaronson, apply a CNOT gate into that measured bit instead of actually measuring it would be mathematically equivalent. – Taylor Huang Jul 4 '19 at 8:24

The fact that you can simulate intermediate measurements is only used to argue that BQP_WITH_MEASUREMENTS equals BQP.

Once having this established, you just forget about it. Yes, you can’t undo a measurement. But the good thing is that you never have to.