0
$\begingroup$

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.

enter image description here

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – taninamdar Jun 9 at 21:11
  • $\begingroup$ 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. $\endgroup$ – Mariia Mykhailova Jun 9 at 23:09
1
$\begingroup$

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

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

| improve this answer | |
$\endgroup$
1
$\begingroup$

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: enter image description here

and this one is:

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain what exactly is wrong in that statement? $a|00\rangle + b|11\rangle$ is an entangled state, isn't it? $\endgroup$ – taninamdar Jun 10 at 16:44
  • $\begingroup$ 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. $\endgroup$ – Rimgaudas Laucius Jun 10 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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