Deutsch's Algorithm

Deutsch's Algorithm

Deutsch's algorithm is the simplest example of a quantum algorithm that outperforms its classical counterpart, and it is often the first quantum algorithm a student encounters. The problem is this: given black-box access to a one-bit Boolean function f(x), decide whether f is constant (f(0) equals f(1)) or balanced (f(0) differs from f(1)). Classically this requires evaluating the function twice, once for each input, because a single evaluation cannot distinguish the two cases. Deutsch's algorithm answers the question with just one query to the oracle by exploiting quantum parallelism and interference: it places the input qubit in a superposition so the oracle acts on both inputs at once, then uses a Hadamard transform to interfere the results so that the global property (the parity of f) is written into a single measurable bit. This Cirq example implements the streamlined version of the algorithm from Nielsen and Chuang's textbook, constructing the oracle for a chosen function, building the circuit, simulating it, and reading out whether the function is constant or balanced from a single measurement. It is a concise, foundational demonstration of how interference turns quantum superposition into a computational speedup.

Run it

pip install -r requirements.txt
python deutsch.py

Source and license

Imported from examples/deutsch.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.