Why is it important to eliminate the garbage qubits?

Question

Most reversible quantum algorithms use standard gates like Toffoli gate (CCNOT) or Fredkin gate (CSWAP). Since some operations require a constant $\left|0\right>$ as input and the number of inputs and outputs is equal, garbage qubits (or junk qubits) appear in the course of the computation.

So, a principal circuit like $\left|x\right>\mapsto\left|f(x)\right>$ actually becomes $\left|x\right>\left|0\right>\mapsto\left|f(x)\right>\left|g\right>$,
where $\left|g\right>$ stands for the garbage qubit(s).

Circuits that preserve the original value ends up with $\left|x\right>\left|0\right>\left|0\right>\mapsto\left|x\right>\left|f(x)\right>\left|g\right>$

I understand that garbage qubits are inevitable if we want the circuit to stay reversible, but many sources${}^1$ claim that it is important to eliminate them. Why is it so?

---

${}^1$ Due to requests for sources, see for example this arXiv paper, pg 8, which says

However, each of these simple operations contains a number of additional, auxiliary qubits, which serve to store the intermediate results, but are not relevant at the end. In order not to waste any unneccesary [sic] space, it is therefore important to reset these qubits to 0 so that we are able to re–use them

or this arXiv paper which says

The removal of garbage qubits and ancilla qubits are essential in designing an efficient quantum circuit.

or the many other sources - a google search produces many hits.

Answer 1

Quantum interference is the heart and soul of quantum computation. Whenever you have junk qubits they're going to prevent interference. This is actually a very simple but very important point. Let's say we have a function $f:\{0,1\}\to\{0,1\}$ which maps a single bit to a single bit. Say $f$ is a very simple function, like $f(x)=x$. Let's say we had a circuit $C_f$ which inputs $x$ and outputs $f(x)$. Now, of course, this was a reversible circuit, and could be implemented using a unitary transformation $|x\rangle\to|x\rangle$. Now, we could feed in $\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ and the output would also be $\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$. Let us now apply Hadamard transform gate and measure what we get. If you apply the Hadamard transform to this state $\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$, you get the $|0\rangle$ state, and you see $0$ with probability $1$. In this case there was no junk created in the intermediate steps, while converting the classical circuit to a quantum circuit.

But, let's say we created some junk in an intermediate step when using a circuit like this one:

.

For this circuit, if we start off in the state $|x\rangle|0\rangle = \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle \right)|0\rangle$, after the first step we get $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$. If we apply the Hadamard transform to the first qubit, we end up with:

$$\frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle + \frac{1}{2}|10\rangle - \frac{1}{2}|11\rangle$$

If we make a measurement on the first qubit we get $0$ with probability $\frac{1}{2}$, unlike in the previous case where we could see $0$ with probability $1$! The only difference between the two cases was the creation of a junk bit in an intermediate step, which was not gotten rid of, thus leading to a difference in the final result of the computation (since the junk qubit got entangled with the other qubit). We will see a different interference pattern than in the previous case when the Hadamard transform is applied. This is exactly why we don't like to keep junk around when we are doing quantum computation: it prevents interference.

Source: Professor Umesh Vazirani's lecture on EdX.

Answer 2

If you want to use a quantum circuit as a subroutine (such as an oracle) to a quantum algorithm that makes use of interference, you must allow interference by a process known as uncomputing your ancillary (or, in your words, garbage) qubits. Uncomputing is always possible: Since your gates are reversible, you can just apply their inverse. That is, after the step you mentioned, $\left|x\right>\left|0\right>\left|0\right>\mapsto\left|x\right>\left|f(x)\right>\left|g\right>$, you perform another computation (or uncomputation) that leads to $\left|x\right>\left|f(x)\right>\left|0\right>$.