Imagine a simple problem: you are given a black box, or oracle, containing a function $f$ that takes a single bit as input and returns a single bit as output. The function is either ‘constant’ (always returns the same output for any input) or ‘balanced’ (returns a different output for each input).
The challenge is to figure out which of these two categories the function belongs to. On a classical computer, you would have to run the function twice—once for the input 0 and once for the input 1—to be sure. However, using Deutsch’s algorithm, a quantum computer can solve this problem with just a single query to the oracle.
🧠 The Power of Quantum Parallelism
The key to Deutsch’s algorithm is a phenomenon called quantum parallelism. This is the ability of a quantum computer to process all possible inputs to an algorithm simultaneously. Instead of feeding the oracle a single input bit, we create a superposition of both possible inputs, 0 and 1.
We prepare two qubits in a special state using Hadamard gates and send this superposition into the oracle. Due to quantum parallelism, the oracle processes both inputs at once, and its output is a new superposition containing the results for both inputs. In essence, the algorithm performs two computations in the time it takes to perform just one.
🪄 Phase Kickback: The Secret Ingredient
To get a usable answer, Deutsch’s algorithm uses a clever trick involving a property called phase kickback. After the oracle performs its simultaneous computation, it leaves a subtle, unobservable change in the phase of the qubit.
The algorithm uses a special arrangement of gates that ‘kicks back’ this change from one qubit to another, essentially encoding the nature of the function (constant or balanced) into the state of a single qubit. The oracle takes an input superposition and produces a new superposition with an encoded phase. This clever maneuver is what lets the algorithm do its work so efficiently.
💡 A Single Measurement, A Definitive Answer
After the phase kickback, the algorithm applies one final Hadamard gate to the first qubit and then measures it. Here’s the payoff: if the original function was constant, the measured result is guaranteed to be a 0.
But if the function was balanced, the measured result is guaranteed to be a 1. With just one query to the oracle, and a few simple quantum gates, we have a definitive answer. This beautifully simple algorithm was one of the first to demonstrate a task that a quantum computer can perform more efficiently than any classical computer, making it a cornerstone of modern quantum computing.
—
Glassner, Andrew. Quantum Computing: From Concepts to Code. No Starch Press, 2025.
More Topics
- The Quantum Threat: How Shor’s Algorithm Puts Modern Encryption at Risk
- The Deutsch-Jozsa Algorithm: An Exponential Leap in Quantum Problem Solving
- The Bernstein-Vazirani Algorithm: Unmasking a Secret With a Single Query
- Simon’s Algorithm: The First Quantum Speedup That Left Classical Computers in the Dust
- The ‘Spooky Action’: What Happens When Qubits Entangle?
- The Quantum Enigma: Why Measurement is the Most Unpredictable Step
- Can You Teleport a Qubit? The Amazing Alice & Bob Experiment
