Deutsch–Jozsa Algorithm: One Query Beats Classical

What is the Deutsch–Jozsa Algorithm?

The Deutsch–Jozsa algorithm is a quantum computing algorithm designed to determine whether a given function f: {0,1}^n → {0,1} is constant or balanced. A function is considered constant if it outputs the same value for all inputs, and balanced if it outputs 0 for half of its inputs and 1 for the other half.

The algorithm was introduced by David Deutsch and Richard Jozsa in 1992 as a way to showcase the potential speedup achievable with quantum computers over classical ones.

How Does It Work?

The algorithm begins by preparing n qubits in a superposition state, which means each qubit is both 0 and 1 simultaneously. This initial state allows the algorithm to explore all possible inputs of the function f(x) at once through quantum parallelism.

After applying the Walsh–Hadamard transform to these qubits, an oracle (a black box that computes f(x)) is applied. The oracle changes the phase of the superposition states based on the value of f(x). Finally, another Hadamard transformation is applied to all n qubits, and a measurement is taken. If the function is constant, the result will be 0 with certainty; if it's balanced, there’s an equal probability of measuring either 0 or 1.

Why Is It Significant?

The Deutsch–Jozsa algorithm demonstrates a fundamental difference between classical and quantum computing. While a classical computer would need to evaluate the function f(x) on all possible inputs (2^n evaluations for n qubits), the quantum version can determine if the function is constant or balanced with just one query.

This problem, while seemingly simple, sets the stage for more complex problems that could benefit from similar speedups in future quantum algorithms.

Real-World Applications

While the Deutsch–Jozsa algorithm itself is not directly applicable to practical problems like cryptography or database search, it serves as a foundational demonstration of how quantum computers can process information fundamentally differently from classical ones.

Understanding and developing algorithms like this one helps researchers design more complex quantum algorithms that could have significant real-world implications in fields such as chemistry, optimization, and machine learning.

Frequently asked questions

Try it live

Everything above runs in your browser — open Deutsch–Jozsa Algorithm — One Query Beats Classical and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.