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. Jul 3, 2019 at 8:17
• By copy he meant CNOT from the result qubit to another intially-zero qubit. Jul 3, 2019 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.
• $\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. Jul 4, 2019 at 7:18