The Deutsch Algorithm

Quantum Speedup

The Deutsch algorithm was the first quantum algorithm to demonstrate a speedup over classical computation. It solves a specific problem in 1 query that classically requires 2.

The problem: Given a function $f: {0, 1} o {0, 1}$, determine if $f$ is:

• Constant: $f(0) = f(1)$ (always outputs 0, or always outputs 1)
• Balanced: $f(0) eq f(1)$ (outputs 0 for one input and 1 for the other)

Classically, you must evaluate $f(0)$ and $f(1)$ separately — 2 queries.

The Deutsch algorithm evaluates $f$ in quantum superposition, getting the answer in 1 query.

The algorithm's outcome is determined by $f(0) oplus f(1)$:

• 0 → constant
• 1 → balanced

def deutsch(f):
    if f(0) == f(1):
        return "constant"
    else:
        return "balanced"

There are exactly 4 possible functions:

Your Task

Implement deutsch(f) that classifies the function. Then define the four possible functions and test each one.