0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – dkaeae
    Jul 3, 2019 at 8:17
  • $\begingroup$ By copy he meant CNOT from the result qubit to another intially-zero qubit. $\endgroup$
    – Taylor Huang
    Jul 3, 2019 at 15:05

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Taylor Huang
    Jul 4, 2019 at 6:21
  • 1
    $\begingroup$ $\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. $\endgroup$
    – dkaeae
    Jul 4, 2019 at 7:18
  • $\begingroup$ 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. $\endgroup$
    – Taylor Huang
    Jul 4, 2019 at 8:24
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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