The Problem
In the Deutsch Algorithm, we work with a function that takes a 1-bit unsigned integer as input and returns either0 or 1.
The Deutsch-Jozsa Algorithm generalizes this idea to a function that takes an -bit unsigned integer as input and returns either 0 or 1.
The function is guaranteed to be either constant or balanced:
- A constant function always returns the same output, either
0or1, for every possible input. - A balanced function returns
0for exactly half of the possible inputs and1for the other half.
0 to , giving us possible inputs.
For example, if , the possible inputs are 0, 1, 2, and 3. A constant function could return 0 for all four inputs, while a balanced function could return 0 for 0 and 3, and 1 for 1 and 2.
Our task is to determine whether the function is constant or balanced.
The Classical Approach
Let’s first look at how we solve this problem using classical computing. Forn bits, there are possible inputs. A classical computer can call the function with different inputs and check its outputs.
If we keep getting the same output, the function might be constant. But it could also be balanced, and we may have only checked inputs that give the same output.
In the worst case, we need to check inputs to be certain.
Why one extra input? A balanced function can return the same output for as many as half of all possible inputs. Once we check one more input, a different output proves that the function is balanced. If all the outputs are still the same, the function must be constant.
Classical Worst-Case Function Calls
The worst-case number of function calls is .
As the number of bits increases, the number of function calls also grows rapidly.
The Quantum Approach
Now let’s solve the same problem using quantum computing. The key idea is to create a quantum value that contains all possible inputs, apply a function-dependent phase change, and then use interference to determine whether the function is constant or balanced. Let’s see how we can implement this in Rhyme.quint.all(size=n) function creates a quantum integer containing every value that can be represented with n bits.
For n = 3, the possible values are 0 to 7.
All eight possible inputs are now available in the same quantum value with equal amplitudes, as shown in the debugger:

Changing the Phase
Before we use interference, we apply the function to the quantum value through a phase change.add_phase() operation changes the phase of every input value taccording to the output of f(t).
- If
f(t)returns0, the phase remains unchanged. - If
f(t)returns1, the phase changes byπ, reversing the sign of the amplitude.
1 when the sine is positive and 0 otherwise.
For n = 3, we choose m = 5:
The function returns
1 for four inputs and 0 for the other four. Since each output occurs for exactly half of the inputs, this is a balanced function.
The amplitudes after add_phase() are shown in the debugger:

add_phase() call applies the function-dependent phase change to every input value in the quantum superposition. We do not need to call f(t) separately for each input in our quantum algorithm.
Interference
Now comes the most interesting part of the algorithm: interference. We use theinterfere() operation to combine amplitudes in a way that allows us to distinguish between a constant and a balanced function.
In the Deutsch Algorithm, we used interference to combine two values. Here, we extend the same idea to multiple bits.
for loop goes through each bit of our quantum integer. For every bit, bit_pair(k) identifies the values to pair, while bit_lr(k) selects one side of each pair.
The interfere() operation then combines the amplitudes of these pairs. Depending on their phases, the amplitudes can reinforce or cancel each other.
For n = 3, the loop runs three times: once for each bit, with k = 0, 1, and 2.
Let’s see how the amplitudes change after each iteration of the loop.
After the first iteration (k = 0):

k = 1):

k = 2):

n = 1 and the loop runs just once using range(1). Instead of writing a separate operation for each number of bits, we use the same loop for any register size.
After all the interference steps, the amplitudes have been combined so that the result can reveal whether the function is constant or balanced.
How the Amplitudes Come Together
As the interference steps run through each bit, the amplitude of the input0 collects contributions from all possible input values.
For a constant function, the contributions to the amplitude at 0 add up constructively. Its amplitude becomes 1 if the function always returns 0, or -1 if it always returns 1. This means that the amplitude at every other input must be zero, because the absolute squares of all the amplitudes must add up to 1. Therefore, observing can only give the value 0.
For a balanced function, the contributions to the amplitude at 0 cancel each other out. Half of them are positive and half are negative, so the final amplitude is zero. Other inputs can still have non-zero amplitudes, so in general, observing may give any value but 0.
Let’s look at how the amplitudes combine in general. Let represent the amplitudes after the phase change. After each interference iteration, the amplitude of 0 becomes:
- After the first iteration (
k=0), it becomes
- After the second iteration (
k=1), it becomes
- After the third iteration (
k=2), it becomes
k=2 becomes 0. This is true for any balanced function.
For a constant function, the phase change either leaves all amplitudes unchanged or reverses all their signs. If, for example, we start with an equal amplitude of for each of the eight inputs, substituting these values into the k=2 expression gives:
So, for a constant function, the final amplitude is either 1, or -1 if all signs are reversed, while for a balanced function, it is 0. This difference allows the Deutsch-Jozsa Algorithm to distinguish between the two cases.
Observing the Result
After interference, we observe the quantum value to determine whether the function is constant or balanced.0 is either 1 or -1. Therefore, observing the quantum value gives 0.
If the function is balanced, the amplitude at 0 is zero, so observing gives us a non-zero value.
We can use this to classify the function:
- If
observe(x)returns0, the function is Constant. - Otherwise, the function is Balanced.
Putting It All Together
Now let’s combine everything into ourdeutsch_jozsa() function.
f: the function we want to classify.n: the number of bits in the input.x: the quantum value containing all possible inputs.
for loop applies interference across every bit. Finally, we observe the result and return whether the function is constant or balanced.
Running the Experiment
Let’s test our algorithm using two functions. The first function is constant and always returns0.
m = 5.
We can now run both experiments with n = 3.
Classical vs Quantum
Both approaches work with the same possible inputs. The difference is how many times they need to call the function to determine whether it is constant or balanced.
What Have We Learned?
The Deutsch-Jozsa Algorithm extends the Deutsch Algorithm from a single-bit input to an -bit input. We start with all possible inputs in superposition, useadd_phase() to encode the function’s outputs in their phases, and apply interference across every bit using a for loop. Finally, we observe the result to identify whether the function is constant or balanced.
The key idea is that we do not need to check the function’s outputs one by one. With one quantum function call, interference allows us to distinguish between the two types of functions.
And that’s how we implemented the Deutsch-Jozsa Algorithm in Rhyme!