Skip to main content
In the Deutsch Algorithm, we saw how quantum computing can determine whether a function is constant or balanced with just one function call. The Deutsch-Jozsa Algorithm extends this idea to functions with multiple-bit inputs. Let’s understand how it works, one step at a time, and implement it in Rhyme.

The Problem

In the Deutsch Algorithm, we work with a function f(x)f(x) that takes a 1-bit unsigned integer as input and returns either 0 or 1. The Deutsch-Jozsa Algorithm generalizes this idea to a function f(x)f(x) that takes an nn-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 0 or 1, for every possible input.
  • A balanced function returns 0 for exactly half of the possible inputs and 1 for the other half.
An nn-bit unsigned integer can represent values from 0 to 2n−12^n - 1, giving us 2n2^n possible inputs. For example, if n=2n=2, 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. For n bits, there are 2n2^n 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 2n−1+12^{n-1} + 1 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 2n−1+12^{n-1} + 1. 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.
The 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:
Rhyme debugger showing amplitudes of all bits inside quint
Instead of calling the function separately for each input, we can apply one operation to the entire quantum value.

Changing the Phase

Before we use interference, we apply the function to the quantum value through a phase change.
The add_phase() operation changes the phase of every input value taccording to the output of f(t).
  • If f(t) returns 0, the phase remains unchanged.
  • If f(t) returns 1, the phase changes by π, reversing the sign of the amplitude.
Let’s define a balanced function using a sine function. It returns 1 when the sine is positive and 0 otherwise. For n = 3, we choose m = 5:
For our eight inputs, the function gives the following outputs: 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:
Rhyme debugger showing amplitudes after add_phase()
The input values have not changed. Only the signs of their amplitudes have changed according to the function’s output. This single 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 the interfere() 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.
Let’s break this down. The 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):
quantum amplitudes after the first iteration of the interference loop, with k = 0.
After the second iteration (k = 1):
quantum amplitudes after the second iteration of the interference loop, with k = 1.
After the third iteration (k = 2):
quantum amplitudes after the third iteration of the interference loop, with k = 2.
Each iteration builds on the previous one. Together, these operations perform the multi-bit generalization of the interference step in the Deutsch Algorithm. This loop is one of the key ideas of the Deutsch-Jozsa Algorithm. It generalizes the single-bit case, where 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 input 0 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 (a0,a1,…,a7)(a_0,a_1,\ldots,a_7) represent the amplitudes after the phase change. After each interference iteration, the amplitude of 0 becomes:
  • After the first iteration (k=0), it becomes
a0+a12\frac{a_0+a_1}{\sqrt{2}}
  • After the second iteration (k=1), it becomes
a0+a1+a2+a32\frac{a_0+a_1+a_2+a_3}{2}
  • After the third iteration (k=2), it becomes
a0+a1+a2+a3+a4+a5+a6+a722\frac{a_0+a_1+a_2+a_3+a_4+a_5+a_6+a_7}{2\sqrt{2}} Now, let’s see what this means for our two types of functions. For a balanced function, half of the amplitudes have their signs reversed by the phase change. Their contributions cancel out, so the expression for 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 1/81/\sqrt{8} for each of the eight inputs, substituting these values into the k=2 expression gives: 8×1822=1\frac{8 \times \frac{1}{\sqrt{8}}}{2\sqrt{2}}=1 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.
If the function is constant, the amplitude at 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) returns 0, the function is Constant.
  • Otherwise, the function is Balanced.
The algorithm does not need to observe every possible input value. The interference has already arranged the amplitudes so that observing just once is enough to distinguish the two cases.

Putting It All Together

Now let’s combine everything into our deutsch_jozsa() function.
Our function takes three arguments:
  • f: the function we want to classify.
  • n: the number of bits in the input.
  • x: the quantum value containing all possible inputs.
First, we change the phases according to the function’s outputs. Then the 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 returns 0.
The second function is the balanced function we defined earlier, using the sine function with m = 5. We can now run both experiments with n = 3.
We create a fresh quantum value for each experiment so that the second experiment starts independently of the first. Output:
Both functions are correctly classified by the same algorithm.

Classical vs Quantum

Both approaches work with the same 2n2^n possible inputs. The difference is how many times they need to call the function to determine whether it is constant or balanced.
Comparison of classical vs quantum

What Have We Learned?

The Deutsch-Jozsa Algorithm extends the Deutsch Algorithm from a single-bit input to an nn-bit input. We start with all possible inputs in superposition, use add_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!