5
$\begingroup$

I'd like to ask rather some basic questions regarding "uncomputation".

I understand the operation itself and returning the garbage bits back to the original product states .. etc. But I wonder if there is a simple example that shows any issue if we don't do "uncomputation"? Does it lead to wrong results if the circuit continues carrying these "garbage bits" to the end? I see the algorithm like HHL has the uncomputation in the end also. I looked around the textbooks and youtube etc. I couldn't find any good resource to show why the uncomputation is important.

Thank you for your kind help.

$\endgroup$

1 Answer 1

6
$\begingroup$

In general, the state of auxiliary qubits which are used during computation is entangled with the state of output qubits. This entanglement prevents interference from happening, which in turn leads to unwanted results.

As a demonstration, assume that we will start with an equal superposition then calculate the state $|x\rangle|(x ∧ ¬x)\rangle$ and finally apply Hadamard gate to the first qubit. Since $|(x ∧ ¬x)\rangle$ is always $|0\rangle$, applying Hadamard gate should cause a destructive interference and the output state should be $|00\rangle$.

Now, to calculate $(x ∧ ¬x)$ we will use an auxiliary qubit to store $¬x$ then ANDing $x$ and $¬x$ in the output qubit:

circ = QuantumCircuit(3)
circ.h(0)

# Use auxiliary qubit to calculate ¬x
circ.cx(0, 2)
circ.x(2)

# Calculate x ∧ ¬x
circ.ccx(0, 2, 1)

circ.h(0)

The resulting circuit should look like

enter image description here

The output of this circuit is:

enter image description here

As you can easily see, the destructive interference didn't happen. However, if we modify the previous circuit to uncompute the value of the auxiliary qubit:

circ = QuantumCircuit(3)
circ.h(0)

# Use ancilla qubit to calculate ¬x
circ.cx(0, 2)
circ.x(2)

# Now, calculate x ∧ ¬x
circ.ccx(0, 2, 1)

# Uncompute:
circ.x(2)
circ.cx(0, 2)

circ.h(0)

The circuit plot:

enter image description here

Now the destructive interference takes place and the output state (without the auxiliary qubit) is $|00\rangle$.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you for the very insightful explanation. Just a bit more about the Hadamard gates and "destructive" interference. We knew "destructive" interference is happening beforehand because the logic inside always yields to 0 regardless of q0 state right? @Egretta.Thula $\endgroup$ Jan 31, 2022 at 15:56
  • $\begingroup$ It'd be great if you could also show the resulting probabilities so that the answer is more complete, thanks! $\endgroup$
    – prairie99
    Feb 9, 2023 at 0:32

Your Answer

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

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