Month: December 2025

The Cost of Garbage: Why We Must Clean “Junk Bits”

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

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 irreversible. In quantum computing, all operations must be Unitary ($U^{\dagger}U = I$), meaning they are perfectly reversible. Information is never lost; it is simply transformed.

AND
Out: ?

Information Loss: You cannot reconstruct inputs from the output.

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.

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)

✕
✕
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

Deutsch Algorithm Revisited: Quantum vs Classical Implementation in Qiskit

Deutsch Algorithm Revisited: Quantum vs Classical Implementation in Qiskit

A practical comparison showing the quantum advantage with working code

Introduction

In the previous post on the Deutsch algorithm, we explored the theoretical foundations of this groundbreaking quantum algorithm. Today, we’re taking it further by implementing both the quantum and classical approaches in Qiskit, allowing us to see the quantum advantage in action.

This hands-on implementation demonstrates why the Deutsch algorithm is considered the first example of quantum computational superiority—solving a problem with fewer oracle queries than any classical algorithm can achieve.

The Challenge

Given a black-box function f: {0,1} → {0,1}, determine whether it is:

  • Constant: f(0) = f(1) (always returns 0 or always returns 1)
  • Balanced: f(0) ≠ f(1) (returns 0 for one input, 1 for the other)
🔑 Key Question: How many times must we query the function?
  • Classical: 2 queries required
  • Quantum: 1 query required

Complete Qiskit Implementation

Oracle Functions

First, we create the oracle functions representing all possible single-bit Boolean functions:

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

Classical Approach: Two Queries Required

The classical algorithm must query the oracle twice—once for f(0) and once for f(1):

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 initialized 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

Quantum Approach: One Query Suffices

The quantum Deutsch algorithm uses superposition and interference to determine the answer with a single oracle query:

def deutsch_algorithm(oracle):
    """Implements the Deutsch algorithm - requires only ONE query"""
    qr = QuantumRegister(2, 'q')
    cr = ClassicalRegister(1, 'c')
    qc = QuantumCircuit(qr, cr)
    
    # Step 1: Initialize q[1] to |1⟩
    qc.x(1)
    qc.barrier()
    
    # Step 2: Apply Hadamard gates (create superposition)
    qc.h(0)
    qc.h(1)
    qc.barrier()
    
    # Step 3: Apply the oracle (SINGLE QUERY!)
    qc.compose(oracle, inplace=True)
    qc.barrier()
    
    # Step 4: Apply Hadamard to input qubit
    qc.h(0)
    qc.barrier()
    
    # Step 5: Measure
    qc.measure(0, 0)
    
    return qc

Running the Comparison

Now let’s test all four possible oracles with both approaches:

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
    qc1 = classical_deutsch_query1(oracle)
    result1 = simulator.run(qc1, shots=1).result()
    f_0 = int(list(result1.get_counts().keys())[0])
    
    qc2 = classical_deutsch_query2(oracle)
    result2 = simulator.run(qc2, shots=1).result()
    f_1 = int(list(result2.get_counts().keys())[0])
    
    classical_result = "CONSTANT" if f_0 == f_1 else "BALANCED"
    
    # Quantum: 1 query
    qc_quantum = deutsch_algorithm(oracle)
    result_quantum = simulator.run(qc_quantum, shots=1000).result()
    counts = result_quantum.get_counts()
    
    quantum_result = "CONSTANT" if '0' in counts else "BALANCED"
    
    print(f"{name}: Classical={classical_result}, Quantum={quantum_result}")

Circuit Diagrams

Below are visual representations of the three circuit implementations. The classical approach requires two separate queries, while the quantum approach accomplishes the same task with a single query.

Classical Query 1: Evaluating f(0)

q[0]:
q[1]:
|0⟩
|0⟩
Oracle (Constant_0)
f(0)

Classical Query 1: Input qubit q[0] remains in state |0⟩ → Oracle processes the input → Output qubit q[1] is measured to obtain f(0)

Classical Query 2: Evaluating f(1)

q[0]:
q[1]:
|0⟩
|0⟩
X
|1⟩
Oracle (Constant_0)
f(1)

Classical Query 2: X gate flips q[0] from |0⟩ to |1⟩ → Oracle processes the input → Output qubit q[1] is measured to obtain f(1)

Quantum Deutsch Algorithm (Single Query)

q[0]:
q[1]:
|0⟩
|0⟩
X
H
H
Oracle (Constant_0)
H
0 or 1

Quantum Deutsch: Initialize |01⟩ → Hadamard gates create superposition → Oracle query (single query!) → Final Hadamard on q[0] → Measure q[0] to determine function type

💡 Understanding the Circuit Elements

🔵 Oracle Box: Represents the black-box function we’re querying

🟠 H Gates: Hadamard gates create quantum superposition

🔴 X Gates: Flip qubit states (NOT gate)

📊 Measurement: Extracts classical information from qubits

📏 Qubit Lines: Horizontal lines represent quantum bits

📍 Input/Output: |0⟩, |1⟩ show quantum states

🔍 Key Observation

Notice that the classical circuits measure the output qubit (q[1]) to get the function values f(0) and f(1), while the quantum circuit measures the input qubit (q[0]) after interference. This fundamental difference allows the quantum algorithm to extract global properties of the function with a single query!

Sample Output

======================================================================
Testing: Constant 0 Oracle
======================================================================

[CLASSICAL APPROACH - Requires 2 queries]
  Query 1: f(0) = 0
  Query 2: f(1) = 0
  Result: Function is CONSTANT
  Total queries needed: 2

[QUANTUM APPROACH - Requires only 1 query]
  Measurement results: {'0': 1000}
  Result: Function is CONSTANT
  Total queries needed: 1

  ✓ Both methods agree: True

======================================================================
Testing: Balanced (Identity) Oracle
======================================================================

[CLASSICAL APPROACH - Requires 2 queries]
  Query 1: f(0) = 0
  Query 2: f(1) = 1
  Result: Function is BALANCED
  Total queries needed: 2

[QUANTUM APPROACH - Requires only 1 query]
  Measurement results: {'1': 1000}
  Result: Function is BALANCED
  Total queries needed: 1

  ✓ Both methods agree: True

Understanding the Quantum Advantage

Classical Approach

  • Evaluate f(0) explicitly
  • Evaluate f(1) explicitly
  • Compare the two results
  • 2 queries required

Must check both inputs individually

Quantum Approach

  • Query with superposition of both inputs
  • Use interference to extract global property
  • Measure to get answer
  • 1 query required

Exploits quantum parallelism

🎯 The Key Insight

The quantum algorithm queries the oracle with a superposition of both inputs simultaneously (|0⟩ + |1⟩), then uses quantum interference to extract global properties of the function without ever evaluating it on individual inputs. The measurement result directly tells us whether the function is constant or balanced.

Measurement Interpretation

Measurement Result Function Type Explanation
|0⟩ Constant Constructive interference – f(0) ⊕ f(1) = 0
|1⟩ Balanced Destructive interference – f(0) ⊕ f(1) = 1

Running the Code

To run this code yourself, you’ll need to install Qiskit:

pip install qiskit qiskit-aer

The complete code is available as a Python script that you can run directly. It will output the comparison for all four oracle types and display the results.

Conclusion

This implementation demonstrates the Deutsch algorithm’s quantum advantage in concrete terms:

  • Quantum speedup: 2x reduction in oracle queries (from 2 to 1)
  • First proof of concept: First algorithm to show quantum advantage over classical
  • Foundational technique: Introduces key quantum concepts (superposition, interference, phase kickback)

While the speedup may seem modest for this toy problem, the techniques demonstrated here—querying a function with superposition and extracting global properties through interference—scale to more complex algorithms like Deutsch-Jozsa, Simon’s algorithm, and ultimately Shor’s algorithm for factoring.

🚀 Next Steps:
  • Experiment with the code and modify the oracles
  • Try visualizing the quantum states at each step
  • Explore the Deutsch-Jozsa algorithm (generalization to n-bit functions)
  • Study the mathematical foundations of quantum interference

Have questions or want to discuss quantum algorithms? Drop a comment below!

Happy quantum coding! 🎯⚛️

Deutsch’s Algorithm in Quantum Computing: The 4 Cases

Deutsch’s Algorithm: Complete Guide

From Initialization to Measurement.

Deutsch’s Algorithm determines if a function f(x) is Constant or Balanced using only a single query. First, we examine how these functions are physically built.

The 4 Possible Functions

In these examples, we set the bottom input to 0 so the output is exactly f(x).

1. Constant Zero Function: f(x) = 0
x
0
Identity (No Gates)
2. Constant One Function: f(x) = 1
X
3. Balanced ID Function: f(x) = x
+
4. Balanced NOT Function: f(x) = ¬x
+
X

The General Oracle (Uf)

x
y
Uf
x
y ⊕ f(x)

The Complete Circuit

To detect the function type, we initialize the bottom wire to |1⟩ and use Hadamard gates to create superposition.

|0⟩
|1⟩
H
H
Uf
KICKBACK ↑
H
|ψ₀⟩
|ψ₁⟩
|ψ₂⟩

Mathematical Proof

1. Initialization: |ψ₀⟩ = |0⟩|1⟩

2. Superposition: |ψ₁⟩ = |+⟩|-⟩ = ½(|0⟩+|1⟩)(|0⟩-|1⟩)

3. The Kickback Effect: Applying Uf to |x⟩|-⟩ results in:
Uf |x⟩|-⟩ = (-1)f(x) |x⟩|-⟩

This means the output of the function is shifted into the phase of the first qubit.

4. Global State |ψ₂⟩:
|ψ₂⟩ = 1/√2 [ (-1)f(0)|0⟩ + (-1)f(1)|1⟩ ] ⊗ |-⟩

Final Measurement

If f(0) = f(1) (Constant) → State is ±|+⟩ → Measure 0
If f(0) ≠ f(1) (Balanced) → State is ±|-⟩ → Measure 1

Understanding Phase Kickback in Quantum Computing

How the target controls the controller.

In standard classical logic, a Control Bit dictates what happens to a target. However, in quantum mechanics, the relationship is symmetric. When the target qubit is in an eigenstate of the operator, the phase is “kicked back” to the control qubit.

|+⟩
|−⟩
|−⟩
|−⟩
CNOT CIRCUIT

Notice above: The Target qubit remains unchanged (|−⟩), but the Control qubit flips from |+⟩ to |−⟩.

STEP 1: DEFINE INITIAL STATE

|ψ0⟩ = |+⟩ ⊗ |−⟩

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

STEP 2: EXPAND TERMS

Multiplying coefficients gives 1/2:
|ψ0⟩ = ½ [ |00⟩ − |01⟩ + |10⟩ − |11⟩ ]

STEP 3: APPLY CNOT GATE

Target flips (0↔1) only if Control is 1:
|ψ1⟩ = ½ [ |00⟩ − |01⟩ + |11⟩ − |10⟩ ]

STEP 4: FACTOR & REARRANGE

Group terms by the control qubit:
|ψ1⟩ = ½ [ |0⟩(|0⟩ − |1⟩) − |1⟩(|0⟩ − |1⟩) ]
∴ |ψ1⟩ = |−⟩ ⊗ |−⟩

Why is this important?

The math shows that while we applied the gate to the target, the relative phase of the control qubit changed from positive to negative. This mechanism is the foundation of quantum algorithms like Shor’s and Grover’s.