Month: December 2025

The Cost of Garbage in Quantum Computing

The Hidden Witness

Why You Must Clean Up “Junk Bits” with Uncomputation

1. The “Observer” Effect

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.

Case A: Ideal (No Junk)

H
H
|0>
|0>

100% Interference

Case B: Broken (With Junk)

H
+
H
|0>
|0>
?
|junk>

Random 50/50 Noise

2. Mathematical Working

Ideal Case: (1/2) ( |0> + |1> + |0> – |1> ) = |0>
(Identical paths cancel perfectly.)

Junk Case: (1/2) ( |00> + |10> + |01> – |11> )
(Terms cannot cancel because the ancilla bit is different. Interference is destroyed.)

3. The Solution: Uncomputation

To restore interference, we follow the Compute-Copy-Uncompute pattern. This resets our ancilla to |0> and removes the “witness.”

Input |x>
Ancilla |0>
Target |0>
COMPUTE
+
UNCOMPUTE
|x> (Clean)
|0> (Clean)
|f(x)> (Result)

4. Qiskit Implementation

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(3)
qc.h(0) 
qc.cx(0, 1) # COMPUTE: Create Junk on q1
qc.cx(1, 2) # COPY Result to q2
qc.cx(0, 1) # UNCOMPUTE: Clean Junk back to |0>
qc.h(0)     # Interference Restored!

qc.measure_all()
counts = AerSimulator().run(transpile(qc, AerSimulator())).result().get_counts()
print(f"Resulting state: {counts}")

Built with Qiskit 1.x • Quantum Series 2025

About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

America’s $200 AI Coding Tool Just Met a $3 Chinese Rival, GLM-4.7

https://www.techloy.com/americas-200-ai-coding-tool-just-met-a-3-chinese-rival-glm-4-7/

Reversible Computation in Quantum Computing

Reversible Computation in Quantum Computing

Mastering Reversibility, Ancilla Bits, and Unitary Logic

1. The Necessity of Reversibility

In classical logic, gates like AND are inherently irreversible. Because they compress two input bits into a single output bit, information is physically destroyed. For example, if an AND gate outputs ‘0’, you cannot distinguish if the original inputs were (0,0), (0,1), or (1,0). This “many-to-one” mapping results in information loss that manifests as heat dissipation.

In quantum computing, thermodynamics and the laws of physics require all operations to be Unitary (U†U = I). This means every quantum gate must be a 1-to-1 (bijective) mapping; no information is ever lost, and the entire computation can be run in reverse to recover the initial state.

AND
Out: 0

The Logic Gap: If the output is 0, the input could be (0,0), (0,1), or (1,0). The path back is lost.

2. Ancilla Bits & Uncomputation

Because we cannot erase information, we use Ancilla bits as temporary “scratch space.” However, if these qubits are left in an arbitrary state, they remain entangled with the computation. Uncomputation (running gates in reverse) resets them to |0>, “cleaning” the quantum workspace.

The Toffoli Gate (CCX)

The Toffoli gate is reversible because its mapping is bijective. No two inputs result in the same output.

+
In: A
In: B
In: C
Input (A, B, C) Output (A, B, C ⊕ AB) Status
0, 0, 00, 0, 0Unique
1, 1, 01, 1, 1Flipped (AND)
1, 1, 11, 1, 0Flipped Back

The Fredkin Gate (CSWAP)

The Fredkin gate is a controlled-swap operation. It swaps the states of the two target qubits (T1 and T2) if and only if the control qubit (C) is in the state |1>. It is conservative, meaning it preserves the Hamming weight (number of 1s) from input to output.

Because it is a universal gate, we can simulate all standard classical logic by fixing certain inputs:

  • NOT: Set T1=0, T2=1. Output T2 becomes NOT C.
  • AND: Set T2=0. Output T2 becomes C AND T1.
  • OR: Set T1=B, T2=1. Output T1 becomes C OR B.
✕
✕
In: C
In: T1
In: T2

3. Mathematics: Unitary vs. Hermitian

Proof: Is Pauli-Y Unitary?

Y =
0–i
i0
Y† =
0–i
i0

Pauli-Y is Unitary (Y†Y = I). Because Y = Y†, it is also Hermitian.

Unitary but NOT Hermitian: The S Gate

S =
10
0i
≠
S† =
10
0–i

Since S ≠ S†, you must apply the S-Dagger gate to reverse an S rotation.

4. Qiskit Verification

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(3)
qc.x([0, 1]) # Controls to |1>

# Toffoli is Hermitian (U = U†), so applying it twice cleans the ancilla
qc.ccx(0, 1, 2) # Calculation step
qc.ccx(0, 1, 2) # Uncomputation step

qc.measure_all()
counts = AerSimulator().run(transpile(qc, AerSimulator())).result().get_counts()
print(f"Resulting state: {counts}") # Expect {'011': 1024}

Built with Qiskit 1.x • Quantum Series 2025

About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Deutsch Algorithm Revisited: Quantum vs Classical Implementation in Qiskit

QUANTUM SERIES 2026
Quantum vs classical implementation of Deutsch’s Algorithm in Qiskit: same answer, half the queries.

The previous post covered the theory: four Boolean functions, the reversible oracle Uf, the phase-kickback derivation, and the single-query measurement result. This post puts it into running code. We implement the classical two-query approach and the quantum one-query approach side by side in Qiskit so the advantage is visible, not just promised.

1  ·  The Challenge

Given a black-box function f: {0,1} → {0,1}, determine whether it is constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)).

Approach Oracle queries required Strategy
Classical 2 Evaluate f(0), then f(1), compare
Quantum (Deutsch) 1 Query in superposition, read phase via interference
The quantum advantage: instead of probing the function at individual inputs, the algorithm queries it at a superposition of both inputs simultaneously, then uses interference to extract a global property (constant vs balanced) with a single measurement.
2  ·  Oracle Functions

First we build the four oracle circuits. Each implements one of the four single-bit Boolean functions as a reversible quantum gate. The constant oracles ignore x; the balanced oracles use x as a control.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def create_constant_oracle(constant_value):
    “””Creates a constant oracle (returns 0 or 1 for all inputs)”””
    oracle = QuantumCircuit(2, name=f”Constant_{constant_value}”)
    if constant_value == 1:
        oracle.x(1)  # Flip the output qubit
    return oracle

def create_balanced_oracle(balance_type):
    “””Creates a balanced oracle”””
    oracle = QuantumCircuit(2, name=f”Balanced_{balance_type}”)
    if balance_type == ‘identity’:
        # f(x) = x
        oracle.cx(0, 1)
    elif balance_type == ‘negation’:
        # f(x) = NOT x
        oracle.x(0)
        oracle.cx(0, 1)
        oracle.x(0)
    return oracle
3  ·  Classical Approach: Two Queries Required

The classical algorithm calls the oracle twice: once with input 0 to learn f(0), and once with input 1 to learn f(1). Each query is a separate circuit run.

def classical_deutsch_query1(oracle):
    “””First query: Evaluate f(0)”””
    qr = QuantumRegister(2, ‘q’)
    cr = ClassicalRegister(1, ‘c’)
    qc = QuantumCircuit(qr, cr)
    # Input: x = 0 (already initialised to |0>)
    qc.barrier()
    qc.compose(oracle, inplace=True)
    qc.barrier()
    qc.measure(1, 0)  # Measure output to get f(0)
    return qc

def classical_deutsch_query2(oracle):
    “””Second query: Evaluate f(1)”””
    qr = QuantumRegister(2, ‘q’)
    cr = ClassicalRegister(1, ‘c’)
    qc = QuantumCircuit(qr, cr)
    qc.x(0)  # Input: x = 1
    qc.barrier()
    qc.compose(oracle, inplace=True)
    qc.barrier()
    qc.measure(1, 0)  # Measure output to get f(1)
    return qc
Classical bottleneck: two separate measurements, two separate circuit executions. The classical algorithm measures the output qubit q[1] in both cases to read the function values directly.
4  ·  Quantum Approach: One Query Suffices

The quantum circuit initialises q[1] = |1⟩, applies Hadamard gates to both wires, queries the oracle exactly once, then applies a final Hadamard to q[0] before measuring it. The oracle is never called again.

def deutsch_algorithm(oracle):
    “””Implements Deutsch’s algorithm — requires only ONE query”””
    qr = QuantumRegister(2, ‘q’)
    cr = ClassicalRegister(1, ‘c’)
    qc = QuantumCircuit(qr, cr)

    # Step 1: Initialise q[1] to |1>
    qc.x(1)
    qc.barrier()

    # Step 2: Hadamard on both wires (superposition)
    qc.h(0)
    qc.h(1)
    qc.barrier()

    # Step 3: Single oracle query
    qc.compose(oracle, inplace=True)
    qc.barrier()

    # Step 4: Final Hadamard on q[0]
    qc.h(0)
    qc.barrier()

    # Step 5: Measure q[0] — the INPUT qubit, not the output
    qc.measure(0, 0)
    return qc

The quantum circuit measures q[0], the input qubit. The classical circuits measure q[1], the output qubit. That structural difference is the entire quantum advantage: the quantum algorithm reads a global property of the function via interference, not an individual function value.

5  ·  Running the Comparison

Test all four oracles with both approaches and compare query counts.

oracles = [
    (“Constant 0”,           create_constant_oracle(0)),
    (“Constant 1”,           create_constant_oracle(1)),
    (“Balanced (Identity)”, create_balanced_oracle(‘identity’)),
    (“Balanced (Negation)”, create_balanced_oracle(‘negation’))
]
simulator = AerSimulator()

for name, oracle in oracles:
    # Classical: 2 queries
    f_0 = int(list(simulator.run(classical_deutsch_query1(oracle), shots=1).result().get_counts().keys())[0])
    f_1 = int(list(simulator.run(classical_deutsch_query2(oracle), shots=1).result().get_counts().keys())[0])
    classical_result = “CONSTANT” if f_0 == f_1 else “BALANCED”

    # Quantum: 1 query
    counts = simulator.run(deutsch_algorithm(oracle), shots=1000).result().get_counts()
    quantum_result = “CONSTANT” if ‘0’ in counts else “BALANCED”

    print(f”{name}: Classical={classical_result}, Quantum={quantum_result}”)

Sample output:

Constant 0:          Classical=CONSTANT, Quantum=CONSTANT
Constant 1:          Classical=CONSTANT, Quantum=CONSTANT
Balanced (Identity): Classical=BALANCED, Quantum=BALANCED
Balanced (Negation): Classical=BALANCED, Quantum=BALANCED
Both methods always agree. The quantum result is deterministic: the simulator returns 100% |0⟩ for constant oracles and 100% |1⟩ for balanced ones, with zero noise on shots=1000.
6  ·  Circuit Overview

Classical Query 1 — Evaluate f(0)
q[0] stays in |0⟩, both wires pass through Uf, and q[1] is measured to read f(0).

q[0]: |0⟩ (not measured)
Uf
q[1]: |0⟩ M f(0)

Classical Query 2 — Evaluate f(1)
An X gate flips q[0] to |1⟩, both wires pass through Uf, and q[1] is measured to read f(1).

q[0]: |0⟩ X (not measured)
Uf
q[1]: |0⟩ M f(1)

Quantum Deutsch — Single Query
H gates create superposition on both wires, one oracle query encodes f(0) ⊕ f(1) as a phase, the final H on q[0] converts phase to amplitude, and measuring q[0] gives the answer directly.

q[0]: |0⟩ H H M 0=const, 1=bal
Uf
q[1]: |1⟩ H
The structural difference: the classical circuits measure the output qubit q[1] to read individual function values. The quantum circuit measures the input qubit q[0] after interference to read a global property of the function. That is what lets a single query reveal whether the function is constant or balanced.
7  ·  Measurement Interpretation and Conclusion

The measurement result on q[0] maps directly to the function type:

Measure q[0] Function type Interference mechanism
0 Constant f(0) ⊕ f(1) = 0 → constructive on |0⟩
1 Balanced f(0) ⊕ f(1) = 1 → destructive on |0⟩, constructive on |1⟩

The quantum speedup is 2x here (one query instead of two). Modest for a two-input function, but the same technique scales: Deutsch-Jozsa extends this to n-bit functions, cutting 2n−1+1 classical queries down to one. Simon’s algorithm extends it further. Shor’s algorithm for factoring, the most consequential quantum algorithm known, relies on the same architectural idea: query in superposition, encode information as phase, extract via interference and measurement.

To run the code: pip install qiskit qiskit-aer. The full comparison script outputs all four oracle types side by side. Try modifying the oracle functions to explore how each gate sequence implements f.

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Deutsch’s Algorithm in Quantum Computing: The 4 Cases

QUANTUM SERIES 2026
The four Boolean functions, the reversible oracle, and the single-query Deutsch circuit with full derivation.

Deutsch’s Algorithm determines whether a single-bit function f(x) is constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)) using only one oracle query. To understand how the algorithm works, we first need to see how each possible function is physically realised as a reversible quantum gate, and then how the complete Deutsch circuit encodes that function into a measurable phase difference.

1  ·  The 4 Possible Functions

With a single input bit x ∈ {0,1} and output bit f(x) ∈ {0,1}, there are exactly four possible Boolean functions. Two are constant (output ignores the input) and two are balanced (output depends on the input).

# Name f(0) f(1) Gate implementation Type
1 Constant Zero 0 0 Identity — no gates needed Constant
2 Constant One 1 1 X gate on output wire only Constant
3 Balanced ID 0 1 CNOT (x = control, y = target) Balanced
4 Balanced NOT 1 0 X on x, CNOT, X on x (flip, copy, restore) Balanced

The two balanced oracles as quantum circuits. Both have x on the control wire and y on the target wire, with the bottom wire carrying y ⊕ f(x) as output.

Balanced ID — f(x) = x

x: control — x unchanged
y: + y ⊕ x = y ⊕ f(x)

Balanced NOT — f(x) = ¬x

x: X X flip, control, restore
y: + y ⊕ ¬x = y ⊕ f(x)
Key point: both constant oracles leave the x wire untouched and act only on y. Both balanced oracles use x as a control and output y ⊕ f(x) on the target wire. All four are reversible, which is required for quantum computation.

2  ·  The General Oracle Uf

All four functions are wrapped in a single reversible gate Uf that leaves the input register unchanged and XORs the function value into the output register:

Uf |x⟩|y⟩  =  |x⟩ |y ⊕ f(x)⟩

As a two-wire circuit, Uf passes x unchanged on the top wire while the bottom wire carries y ⊕ f(x). The box spans both wires to show they are processed jointly by a single gate:

x: x (unchanged)
Uf
y: y ⊕ f(x)

The reversibility of Uf is guaranteed because XOR is its own inverse: applying Uf twice returns the original state. This property allows quantum algorithms to query f without destroying the superposition.

Setting y = |−⟩ = (1/√2)(|0⟩ − |1⟩) turns Uf into a phase-kickback machine: Uf|x⟩|−⟩ = (−1)f(x)|x⟩|−⟩. The function value is encoded in the phase of the control qubit rather than the target, and the target remains in |−⟩ unchanged.

3  ·  The Complete Deutsch Circuit

The algorithm wraps Uf in Hadamard gates on both wires. Initialise q[0] = |0⟩ and q[1] = |1⟩, apply H to both, query Uf once, apply a final H to q[0], then measure q[0]:

q[0]: |0⟩ H H M
Uf
q[1]: |1⟩ H
|ψ₀⟩ |ψ₁⟩ |ψ₂⟩

The three states at each checkpoint:

State Expression Note
|ψ₀⟩ |0⟩|1⟩ Initialisation
|ψ₁⟩ |+⟩|−⟩ = ½(|0⟩+|1⟩)(|0⟩−|1⟩) After both H gates
|ψ₂⟩ (1/√2)[(−1)^f(0)|0⟩+(−1)^f(1)|1⟩] ⊗ |−⟩ After Uf, before final H
The target qubit q[1] stays in |−⟩ throughout. Only the phase of q[0] changes, carrying the function information via kickback.

4  ·  Mathematical Proof

The full derivation follows four steps. Each is exact; no approximation is involved.

Step 1 — Initialisation:
  |ψ₀⟩ = |0⟩|1⟩

Step 2 — Apply H to both wires:
  |ψ₁⟩ = |+⟩|−⟩
       = (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ − |1⟩)

Step 3 — Apply U_f (phase kickback on |−⟩ target):
  U_f |x⟩|−⟩ = (−1)^f(x) |x⟩|−⟩

  |ψ₂⟩ = (1/√2)[ (−1)^f(0)|0⟩ + (−1)^f(1)|1⟩ ] ⊗ |−⟩

Step 4 — Apply H to q[0] and inspect cases:

  Constant  f(0) = f(1) = c:
    |ψ₂⟩ = (−1)^c (1/√2)(|0⟩ + |1⟩) ⊗ |−⟩
    After H: (−1)^c |0⟩ ⊗ |−⟩  →  Measure 0

  Balanced  f(0) ≠ f(1):
    |ψ₂⟩ = ±(1/√2)(|0⟩ − |1⟩) ⊗ |−⟩
    After H: ±|1⟩ ⊗ |−⟩  →  Measure 1
The global phase (−1)^c in the constant case is unobservable. All that matters is whether the amplitudes on |0⟩ and |1⟩ are in phase (constant) or out of phase (balanced), which the final H converts to a deterministic measurement.

5  ·  Final Measurement

The measurement of q[0] after the final Hadamard gives a deterministic result in both cases:

Measure q[0] Function type Why
0 Constant f(0) ⊕ f(1) = 0; amplitudes add constructively on |0⟩
1 Balanced f(0) ⊕ f(1) = 1; amplitudes cancel on |0⟩, survive on |1⟩

A classical algorithm must evaluate f(0) and f(1) separately, requiring two queries. Deutsch’s algorithm queries Uf exactly once, using superposition to probe both inputs simultaneously and interference to extract a global property of the function. This is the first demonstrated quantum computational advantage over any classical approach.

The technique introduced here — query in superposition, encode information as phase, extract via interference — is the blueprint for Deutsch-Jozsa, Simon’s algorithm, and ultimately Shor’s factoring algorithm.
About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Understanding Phase Kickback in Quantum Computing

QUANTUM SERIES 2026
How the target controls the controller and why this underpins Grover’s, Shor’s, and Deutsch’s algorithms.

In standard classical logic, a control bit dictates what happens to a target. In quantum mechanics the relationship is symmetric. When the target qubit is in an eigenstate of the gate operator, the eigenvalue phase is kicked back onto the control qubit, leaving the target unchanged while flipping the relative phase of the control. This post derives that result from first principles using the CNOT gate on |+⟩ ⊗ |−⟩.

1  ·  The CNOT Circuit and the Kickback Setup

The circuit places the control qubit in superposition |+⟩ and the target qubit in |−⟩. Since |−⟩ is an eigenstate of X with eigenvalue −1, the kickback occurs.

control: |+⟩ |−⟩
target: |−⟩ + |−⟩
Key observation: The target qubit is unchanged after the CNOT. The control qubit flips from |+⟩ to |−⟩. The phase was kicked back to the control, not forward to the target.

2  ·  Full Derivation: |+⟩ ⊗ |−⟩ through CNOT

Step 1 — Define the initial state

|ψ₀⟩ = |+⟩ ⊗ |−⟩
  = (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ − |1⟩)

Step 2 — Expand the tensor product

|ψ₀⟩ = (1/2)[ |00⟩ − |01⟩ + |10⟩ − |11⟩ ]

Step 3 — Apply the CNOT gate

|ψ₁⟩ = (1/2)[ |00⟩ − |01⟩ + |11⟩ − |10⟩ ]

Step 4 — Factor and identify the result

|ψ₁⟩ = (1/2)[ |0⟩(|0⟩ − |1⟩) − |1⟩(|0⟩ − |1⟩) ]
  = (1/√2)(|0⟩ − |1⟩) ⊗ (1/√2)(|0⟩ − |1⟩)
  = |−⟩ ⊗ |−⟩
The target qubit is still |−⟩ — unchanged by the CNOT. The control qubit changed from |+⟩ to |−⟩. The −1 eigenvalue of the target has been kicked back as a relative phase onto the control.

3  ·  Why Phase Kickback Matters

The math shows that while we applied a gate to the target, the relative phase of the control qubit changed from positive to negative. This is a structural property of controlled unitaries acting on their eigenstates, and it appears at the core of every major quantum algorithm.

AlgorithmHow phase kickback is used
Deutsch’s AlgorithmThe oracle kicks a −1 phase onto the control qubit to encode whether f is constant or balanced, extractable with a single H gate measurement.
Grover’s AlgorithmThe oracle flips the sign of the target state’s amplitude by kicking a −1 phase back to the control register, enabling amplitude amplification.
Shor’s AlgorithmQuantum Phase Estimation relies entirely on phase kickback to transfer eigenvalue information from the target register to the control register.
The general rule: for any unitary U with eigenstate |u⟩ (so U|u⟩ = eⁱᵖ|u⟩), a controlled-U gate with the control in superposition kicks the phase eⁱᵖ back to the control qubit. The target is unchanged.
About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦