What if you wanted to scale up the problem from Deutsch’s algorithm? What if instead of a single-bit input, the oracle took an input of $n$ bits, with $2^n$ possible inputs? The function would still be either constant (always producing the same output) or balanced (producing an equal number of 0s and 1s).
A classical computer would have to query the oracle more than half of the time to get a definitive answer. But the Deutsch-Jozsa algorithm solves this problem with just a single query, providing a stunning increase in efficiency as $n$ gets larger.
📦 The Power of a Promise Oracle
Like its predecessor, the Deutsch-Jozsa algorithm uses a promise oracle. This means we are given a quantum circuit that we can query, but we are promised that the function it contains will be either constant or balanced.
By leveraging this promise, the algorithm is able to focus on distinguishing between these two cases without needing to worry about other possibilities. This makes the problem much simpler and more suitable for a quantum solution. For $n$ bits, there are $2^n$ possible inputs, and the total number of possible functions is massive, but the promise guarantees that we only need to consider a very small subset of them.
🌀 From One Qubit to an Entire Register
The core idea of the Deutsch-Jozsa algorithm is to put the first register of $n$ qubits into an equal superposition of all possible $2^n$ inputs. This is done with a series of Hadamard gates. Then, we prepare a single auxiliary qubit in a special state and feed both registers into the oracle.
This one query uses quantum parallelism to evaluate the function for every single one of the $2^n$ inputs simultaneously. The oracle’s output is a new superposition that contains all of the results, encoded in the phase of the qubits.
💯 A Perfect Result in a Single Step
After the oracle query, the algorithm applies another set of Hadamard gates to the input register. This step uses interference to sort the information we need. If the original function was constant, the amplitudes of the output states interfere destructively, causing all states except $|0\rangle^{\otimes n}$ to disappear.
When we measure the register, we are guaranteed to get an output of all zeros. However, if the function was balanced, the amplitudes interfere differently, and the resulting superposition will have an amplitude of zero for the state $|0\rangle^{\otimes n}$.
This means that when we measure the register, we are guaranteed to get an output that is not all zeros. With just a single query to the oracle, the Deutsch-Jozsa algorithm gives us a definitive answer, proving its immense power over classical 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
- Cracking the Code: How Quantum Parallelism Solves Deutsch’s Problem in One Step
- 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
- Your First Quantum Program: The ‘Hello, World!’ of a Qubit
- Scaling Up: How Quantum Computers Handle Multiple Qubits
- The ‘Spooky Action’: What Happens When Qubits Entangle?
