When can be used the "uncompute garbage" trick in quantum computing?

Question

As far as I have understood, "uncomputation" in quantum computing is a way to restore the working memory to its initial state, while keeping the result of the computation in another register. This trick is usually explained as follows:

Assume you have a classical function $f : \{0,1\}^n \rightarrow \{0,1\}$. Then there exists a unitary $U_f$ that maps state $|x\rangle|0\rangle |0\rangle$ to $|x\rangle |g(x)\rangle |f(x)\rangle$, where $|g(x)\rangle$ is the state of the working space at the end of the computation. Moreover, $|x\rangle |g(x)\rangle |f(x)\rangle$ is a pure state (not a superposition). You can now add an extra register $|0\rangle$ in which the result $f(x)$ of the computation is CNOT at the end, i.e. we get $|x\rangle |g(x)\rangle |f(x)\rangle |f(x)\rangle$. Finally, apply $U_f^{-1}$ to the first three registers of this state so as to obtain $|x\rangle |0\rangle |0\rangle |f(x)\rangle$. The working memory has been cleaned.

I'm fine with this procedure. However, it seems to me that it works because $|x\rangle |g(x)\rangle |f(x)\rangle$ is a pure state. It would also be ok for a superposition of pure states that all have the same register $|f(x)\rangle$ at the end (before we CNOT). But it doestn't work in the other cases. Consider for instance this circuit:

After the first Hadamard has been applied, $x_1$ contains the result of the computation (it is the same as $|f(x)\rangle$ previously, but now it is a superposition). It is CNOT with the extra register $x_2$ and then another Hadamard is applied. The final state is $(|00\rangle+|01\rangle+|10\rangle-|11\rangle)/2$. Obviously, the first qubit has not been restored to its initial state.

My first question is: am I right when I say that the uncomputation trick only works when the register that is copied is not in superposition? My second question is about the following algorithm taken from this paper from Scott Aaronson:

$\mathcal{Q}_*$ is a quantum circuit that takes some witness $|z\rangle$ as input, and outputs $0$ or $1$. It can be thought as a circuit for QMA, for which the real input $x$ has been fixed and we want to know if there exists a witness that is accepted with high probability (the idea of this paper is to only try with pure states witnesses $|z\rangle$). In this context, I don't understand why the "uncompute garbage" step restores the memory. I think that the register containing the output $b$ is CNOT in an extra register (which will be measured later), but since it's usually a superposition of $|0\rangle$ and $|1\rangle$ I don't understand why the uncomputation would work.

Answer 1

I think I finally figured out what the answer was :) It seems that the "uncomputation trick" was first used for quantum computing in this paper: Strengths and Weaknesses of Quantum Computing (proof of Theorem 4.14). So basically I was right when I said that it only works for "exact" computation (i.e. the output register that contains $f(x)$ is not in superposition) but it can also be used when the error probability of the algorithm is low (in this case the uncomputation is not perfect, but the amplitude of the error term is low).

Let me explain how it works: we have a quantum algorithm $\mathcal{Q}$ that takes an input $|0\rangle |0\rangle$ and produces a state $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle$ where $y$ is the working space and $b_y \in \{0,1\}$ is the output register (the result of the computation). If the computation is "exact" then all the $b_y$ are equal to a same value $b$, i.e. the state is $\sum_y \alpha_y |y\rangle |b\rangle$. We now add an extra register in which we CNOT the result: $\sum_y \alpha_y |y\rangle |b\rangle |b\rangle$. Finally, we can apply $\mathcal{Q}^{-1}$ on the first two registers so as to obtain $|0\rangle |0\rangle |b\rangle$. The uncomputation is exact.

Assume now that there is some error probability $\varepsilon$, i.e. the probability of correctly measuring $b$ is $\sum_{y : b_y = b} |\alpha_y|^2 = 1 - \varepsilon$. Let's add the extra register to CNOT the result and denote $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b_y\rangle $ (in which some $b_y$ are different from $b$) and $|\phi'\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b\rangle$. If we apply $\mathcal{Q}^{-1}$ on the first two registers of $|\phi'\rangle$ we obtain $|0\rangle |0\rangle |b\rangle$ which is what we want. Unfortunately, we only know how to compute $|\phi\rangle$ (in which the last register is a superposition of $b$ and $1-b$). However, note that $\langle \phi | \phi' \rangle = \sum_{y : b_y = b} |\alpha_y|^2 = 1-\varepsilon$. Consequently, the inner product between $\mathcal{Q}^{-1} |\phi\rangle$ and $\mathcal{Q}^{-1} |\phi'\rangle = |0\rangle |0\rangle |b\rangle$ is also $1-\varepsilon$ (inner product is preserved by unitaries), which means that the amplitude of $|0\rangle |0\rangle |b\rangle$ in $\mathcal{Q}^{-1} |\phi\rangle$ is $1 - \varepsilon$. Thus, if $\varepsilon$ is small, then $\mathcal{Q}^{-1} |\phi\rangle$ is close to the correct uncomputed state $|0\rangle |0\rangle |b\rangle$. The uncomputation is almost exact.

I think this is the underlying reasoning in Aaronson's paper when he talks about "uncompute garbage". His circuit $\mathcal{Q}^{\star}$ has a very low error probability (due to an amplification step he performed before) and thus he does not care about the error part in the uncomputation.

There is also this paper: Quantum Entanglement and the Communication Complexity of the Inner Product Function (section 3) for another detailed use of uncomputation.