> ## Documentation Index
> Fetch the complete documentation index at: https://docs.rhymeq.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Deutsch-Jozsa Algorithm: Finding Patterns with One Function Call

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)$ 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)$ that takes an $n$-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 $n$-bit unsigned integer can represent values from `0` to $2^n - 1$, giving us $2^n$ possible inputs.

For example, if $n=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 $2^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 $2^{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 $2^{n-1} + 1$.

| Number of bits (n) | Possible inputs | Worst-case calls |
| - | -: | -: |
| 1 | 2 | 2 |
| 2 | 4 | 3 |
| 3 | 8 | 5 |
| 4 | 16 | 9 |
| 5 | 32 | 17 |

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.

```python theme={null}
import math
from rhyme import quint, observe

n = 3

x = quint.all(size=n)
```

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](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_jozsa_quint.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=2d438e69931d92a338f2f38eda73ecb7)

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.

```python theme={null}
x.add_phase(lambda t: math.pi if f(t) else 0)
```

The `add_phase()` operation changes the phase of every input value `t`according 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`:

```python theme={null}
m = 5

def balanced(t):
    return math.sin(2 * math.pi * m * (t + 0.5) / 2**n) > 0
```

For our eight inputs, the function gives the following outputs:

| Input | `f(t)` | Phase change |
| - | - | - |
| `000` (0) | 1 | π |
| `001` (1) | 0 | 0 |
| `010` (2) | 0 | 0 |
| `011` (3) | 1 | π |
| `100` (4) | 0 | 0 |
| `101` (5) | 1 | π |
| `110` (6) | 1 | π |
| `111` (7) | 0 | 0 |

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()](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_jozsa_addphase.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=a5e6e4aae7cbae94de92250d88187c5e)

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.

```python theme={null}
for k in range(n):
    x.interfere(x.bit_pair(k), x.bit_lr(k))
```

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.](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_jozsa_interfere1.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=598b0fddba07e3d31d251572b33b1a89)

After the second iteration (`k = 1`):

![quantum amplitudes after the second iteration of the interference loop, with k = 1.](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_jozsa_interfere2.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=e890f34dee0482e07f3d3df403b378c2)

After the third iteration (`k = 2`):

![quantum amplitudes after the third iteration of the interference loop, with k = 2.](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_jozsa_interfere3.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=c4443f58d18b1780e5f246fad986ef44)

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 $(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

$$
\frac{a_0+a_1}{\sqrt{2}}
$$

* After the second iteration (`k=1`), it becomes

$$
\frac{a_0+a_1+a_2+a_3}{2}
$$

* After the third iteration (`k=2`), it becomes

$$
\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/\sqrt{8}$ for each of the eight inputs, substituting these values into the `k=2` expression gives:

$$
\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.

```python theme={null}
return "Constant" if observe(x) == 0 else "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.

```python theme={null}
import math
from rhyme import quint, observe

def deutsch_jozsa(f, n, x):
    x.add_phase(lambda t: math.pi if f(t) else 0)

    for k in range(n):
        x.interfere(x.bit_pair(k), x.bit_lr(k))

    return "Constant" if observe(x) == 0 else "Balanced"
```

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`.

```python theme={null}
def constant(t):
    return 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`.

```python theme={null}
n = 3
m = 5

x = quint.all(size=n)
print("Constant function:", deutsch_jozsa(constant, n, x))

x = quint.all(size=n)
print("Balanced function:", deutsch_jozsa(balanced, n, x))
```

We create a fresh quantum value for each experiment so that the second experiment starts independently of the first.

Output:

```
Constant function: Constant
Balanced function: Balanced
```

Both functions are correctly classified by the same algorithm.

## Classical vs Quantum

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

| Aspect | Classical | Quantum |
| - | - | - |
| Number of possible inputs | $2^n$ | $2^n$ |
| Worst-case function calls | $2^{n-1} + 1$ | 1 |
| Main idea | Check inputs individually | Superposition and interference |
| Final result | Compare function outputs | Observe after interference |

![Comparison of classical vs quantum](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_jozsa_comparison.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=5319e52fe8602ddd55cfaad4fa39561b)

## What Have We Learned?

The Deutsch-Jozsa Algorithm extends the Deutsch Algorithm from a single-bit input to an $n$-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!**


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.