# CNOT in reversible computing and entanglement

We have a classical reversible circuit $$U$$ implementing a classical boolean function $$f: \left\{0, 1\right\}^n \to \left\{0, 1\right\}$$, which also takes some $$a$$ ancilla bits, and has side effect of outputting garbage $$g(x)$$. Then we have the following circuit diagram for uncomputing the garbage.

The trick is to CNOT the answer qubit (which I'll call the 2nd qubit) $$f(x)$$ with a fresh ancilla (the 1st qubit) initialized to $$|0\rangle$$, which changes the state of the first qubit to $$f(x)$$. Then we use the inverse of the circuit and get back $$|x\rangle$$ and other ancilla qubits back to $$|0\rangle$$.

If we are using this circuit with classical inputs, then it is clear that $$f(x) \in \left\{0, 1\right\}$$. Then, $$f(x)$$ CNOT $$0$$ is the same as taking the XOR of the two bits.

If we feed the input a uniform superposition of all the inputs, then we want the circuit to behave as follows: $$\frac{1}{\sqrt{2^n}}\sum_{x \in \left\{0,1\right\}^n} |x\rangle \otimes |0\rangle^{\otimes a+1} \mapsto \frac{1}{\sqrt{2^n}}\sum_{x \in \left\{0,1^n \right\}} |x\rangle \otimes |f(x)\rangle \otimes |0\rangle^{\otimes a}.$$

Now this is the part I don't understand. In the quantum case, $$|f(x)\rangle$$ can be a general quantum state $$a|0\rangle + b|1\rangle$$, and CNOT has the effect of entangling the first qubit with the second one, such that the joint state of the two qubits is now $$a |00\rangle + b|11\rangle$$. Now, $$U^{-1}$$ undoes everything done inside $$U$$, but it does not undo the CNOT between the first two bits. Therefore, after everything, the first two qubits should still be entangled, right? In that case, why can we write each term in the output as $$|x\rangle \otimes |f(x)\rangle$$, which indicates that they are not entangled. When we talk about reversible computing, $$f(x)$$ is the scalar value of the function of the input vector $$x$$, and $$|f(x)\rangle$$ is a single basis vector, not a superposition of basis vectors. So it all works out and leaves the first qubit entangled with just the inputs, not the garbage qubits.

• I understand when $x$ is a fixed classical input, but I am concerned about the case when it is a superposition, in particular the uniform superposition of all $n$-bit strings. – taninamdar Jun 9 at 21:11
• We express the superposition as the sum of certain basis vectors; thus each term of the sum has x being a single basis vector and will not be in superposition. If you do the computation term-by-term, you'll see that the garbage qubits end up unentangled from the rest. – Mariia Mykhailova Jun 9 at 23:09

An illuminating example is reported in the last page of the following lecture notes:

http://people.cs.uchicago.edu/~ftchong/33001/lecture09.pdf

This statement is not quite right: CNOT has the effect of entangling the first qubit with the second one, such that the joint state of the two qubits is now a|00⟩+b|11⟩. In your circuit CNOT only applies operation but does not entangle state, because there are no Hadamard gates.

I.e. This state is not entangled: and this one is: • Can you explain what exactly is wrong in that statement? $a|00\rangle + b|11\rangle$ is an entangled state, isn't it? – taninamdar Jun 10 at 16:44
• It is, but you do not get it just by applying CNOT. You get entangled state by CNOT with Hadamard before. I have added a couple images to my response to illustrate this. – Rimgaudas Laucius Jun 10 at 20:59