The Cost of Garbage in Quantum Computing: Why You Must Clean Up Junk Bits

#quantumcomputing #qiskit #tutorial #computerscience

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