Originally published on malcolmlow.net
In quantum computing, anything that "knows" what a qubit is doing acts as a Witness. Leftover data (Junk Bits) on an ancilla qubit act as witnesses, destroying the interference your algorithm needs to work.
1 . The Observer Effect
Consider a simple circuit where a qubit passes through two Hadamard gates. Classically, two inversions cancel. Quantum mechanically, the same is true — only if no information leaks out between them.
Case A: Ideal — No Junk
q0: |0> --H-----------H-- => |0> (100% probability)
The two Hadamard gates cancel perfectly. Measurement always yields |0>.
Case B: Broken — With Junk
q0: |0> --H----*-------H-- => |0> or |1> (50/50 noise)
|
q1: |0> -------X---------- => |junk> (records q0's path)
The ancilla qubit q1 becomes entangled with q0. It now "knows" which path q0 took — and that knowledge destroys the interference.
2 . Mathematical Working
Ideal Case — interference works:
Start: |0>
After H: (1/sqrt2)(|0> + |1>)
After H: (1/2)(|0> + |1> + |0> - |1>) = |0> (cancel!)
The |1> terms cancel — constructive interference on |0>.
Junk Case — interference destroyed:
Start: |0>|0>
After H on q0: (1/sqrt2)(|0> + |1>)|0>
After CX: (1/sqrt2)(|00> + |11>) <- entangled!
After H on q0: (1/2)(|00> + |10> + |01> - |11>)
The terms cannot cancel because q1 differs in each: |00> vs |10> are orthogonal states. Interference is destroyed.
3 . The Solution: Uncomputation
To restore interference, follow the Compute-Copy-Uncompute pattern:
q_in : |x> --[COMPUTE]--+--[UNCOMPUTE]-- |x> (unchanged)
|
q_anc: |0> -------------+--[UNCOMPUTE]-- |0> (cleaned)
|
q_out: |0> -------------+--------------- |f(x)> (result)
Step by step:
- Compute — apply your function gates, writing the result onto q_anc
- Copy — CNOT the result from q_anc into q_out
- Uncompute — run the compute gates in reverse, resetting q_anc to |0>
With q_anc back to |0>, the witness is gone and interference is fully restored.
4 . Qiskit Implementation
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
qc = QuantumCircuit(3)
# q0 = input, q1 = ancilla, q2 = output
qc.h(0)
qc.cx(0, 1) # COMPUTE: entangle q0 -> q1 (creates junk)
qc.cx(1, 2) # COPY: copy result q1 -> q2
qc.cx(0, 1) # UNCOMPUTE: reverse compute, reset q1 -> |0>
qc.h(0) # Interference fully restored
qc.measure_all()
counts = AerSimulator().run(transpile(qc, AerSimulator())).result().get_counts()
print(f"Resulting state: {counts}")
The same circuit as a wire diagram (@ = control, X = target):
q0: |0> --H--@---------@--H-- M
| |
q1: |0> -----X----@----X----- M (ancilla: |0> -> junk -> |0>)
|
q2: |0> ----------X---------- M (output: holds f(x))
The second cx(0,1) exactly reverses the first, leaving q1 in |0>. With the witness removed, the final h(0) performs clean interference and q0 deterministically outputs |0>.
5 . Why This Matters in Practice
Uncomputation is not just a theoretical nicety. In real quantum algorithms:
| Context | Why it matters |
|---|---|
| Grover's oracle | Must leave ancilla qubits clean after marking the target, or subsequent diffusion steps decohere |
| Arithmetic circuits | Reversible adders/multipliers accumulate garbage at every intermediate step — all must be uncomputed before measurement |
| Fault-tolerant circuits | Strict qubit budgets; junk bits consume physical qubits that could otherwise be used for error correction |
The Compute-Copy-Uncompute pattern is the standard solution across all three contexts.
Quantum Series 2025 · Built with Qiskit 1.x