Skip to main content
In classical computing, we need to call a function twice to determine whether it is constant or balanced. But in quantum computing, we can solve the same problem with just one function call. This is the basic idea behind the Deutsch Algorithm. Let’s see how it works in Rhyme.

The Problem

We have a function f(x) that takes a single bit as input and returns a single bit as output. The function can be either constant or balanced:
  • A constant function returns the same output for both inputs.
  • A balanced function returns different outputs for the two inputs.
For example, a constant function could return 0 for both 0 and 1. A balanced function could return 0 for 0 and 1 for 1. Our task is to determine which type of function we have.

The Classical Approach

Let’s first solve this problem using classical computing. We define a function f(x) that returns 1 when x is 0, and 0 otherwise.
To determine whether the function is constant or balanced, we need to call it for both possible inputs.
Here, we make two function calls: f(0) and f(1), one for each input. If both outputs are equal, the function is constant. Otherwise, it is balanced. Since our function returns different outputs, the result is Balanced. The classical approach requires two function calls to determine whether an unknown function is constant or balanced.

The Quantum Approach

Now let’s solve the same problem using quantum computing. Instead of checking both inputs separately, we create a quantum value containing both 0 and 1 using qint().
Both 0 and 1 now have equal amplitudes as shown in the debugger:
Rhyme debugger showing amplitudes after qint
This means that our quantum value contains both possible inputs in superposition.

Changing the Phase

In the Deutsch Algorithm, we use the function to change the phase of each input instead of directly changing its value. Before applying the operation to the superposition, let’s see what the same phase operation does to 0 and 1 individually. Let’s first apply add_phase() to a qint containing only 0:
Since f(0) = 1, the phase changes by pi, reversing the sign of the amplitude of 0 as shown in the debugger:
Rhyme debugger showing amplitudes after qint(0)
Now, let’s do the same with a qint containing only 1:
Since f(1) = 0, the phase remains unchanged, so the amplitude of 1 stays the same as shown in the debugger:
Rhyme debugger showing amplitudes after qint(1)
Now that we have seen what the operation does to each input, let’s apply it to both inputs at once.
This time, both 0 and 1 are present in the superposition. The same add_phase() call applies the function-dependent phase to both values. The resulting amplitudes are shown in the debugger:
Rhyme debugger showing amplitudes after add phase
The same add_phase() call applies the function-dependent phase to every value in the superposition. This allows the same operation to act on both 0 and 1 together instead of applying it separately to each input. For our example, the amplitude of 0 changes its sign, while the amplitude of 1 remains unchanged. Notice that the call to add_phase() is the same in all three examples. What changes is the input register: first 0, then 1, and finally both values in superposition.

Interference

Now we use interference to determine whether the function is constant or balanced. First, we define a function pair() that pairs the two inputs.
Here, 0 is paired with 1, and 1 is paired with 0. Next, we define lr() to select the left side of the pair.
We now apply interfere() to our quantum value.
The interfere() operation combines the amplitudes of the paired values. Depending on their phases, the amplitudes can either reinforce or cancel each other. In our example, the two amplitudes have opposite signs. They cancel for 0 and reinforce for 1 because of the way interfere() combines the pair. The interfere() operation combines these amplitudes: 0→A+B20 \rightarrow \frac{A+B}{\sqrt{2}} 1→A−B21 \rightarrow \frac{A-B}{\sqrt{2}} Substituting the original amplitudes, where A=−12A=-\frac{1}{\sqrt{2}} and B=12B=\frac{1}{\sqrt{2}}: 0→−12+122=00 \rightarrow \frac{-\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}}}{\sqrt{2}} = 0 1→−12−122=−11 \rightarrow \frac{-\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{2}}}{\sqrt{2}} = -1 As a result, the amplitude of 0 becomes 0, and the amplitude of 1 becomes -1. This is shown in the debugger:
Rhyme debugger showing amplitudes after interference
Only 1 has a non-zero amplitude, so observing the quantum value gives us 1.

Observing the Result

Finally, we observe the quantum value to get the result.
As we saw above, the only non-zero amplitude is -1. After observing the quantum value, the amplitude becomes 1, as shown in the debugger:
Rhyme debugger showing resulting amplitudes of 0 and 1
If the result is 0, the function is constant. If the result is 1, the function is balanced. In our example, the result is 1, so the function is balanced.

What Have We Learned?

The key idea is that the quantum algorithm uses superposition to work with both inputs in one call, phase changes to encode the function’s outputs, and interference to distinguish between constant and balanced functions. For this problem, the classical approach requires two function calls, while the quantum approach uses only one function call. And that’s how you implement the Deutsch Algorithm in Rhyme!