> ## 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 Algorithm: Solving a Problem with One Function Call

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.

```python theme={null}
def f(x: int) -> int:
    if x == 0:
        return 1
    else:
        return 0
```

To determine whether the function is constant or balanced, we need to call it for both possible inputs.

```python theme={null}
y0 = f(0)
y1 = f(1)

if y0 == y1:
    print("Classical: Constant")
else:
    print("Classical: Balanced")
```

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

```python theme={null}
from rhyme import qint
from cmath import pi

b = qint(0, 1)
```

Both `0` and `1` now have equal amplitudes as shown in the debugger:

![Rhyme debugger showing amplitudes after qint](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_qint.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=af9968a370edf438b92edc1d67c0a2f8)

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

```python theme={null}
b = qint(0)
b.add_phase(
    lambda i: pi if f(i) == 1 else 0.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)](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/deutsch_0.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=7c4720ee9ea353eb1fc9a8622be85f6b)

Now, let's do the same with a `qint` containing only `1`:

```python theme={null}
b = qint(1)
b.add_phase(
    lambda i: pi if f(i) == 1 else 0.0
)
```

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

Now that we have seen what the operation does to each input, let's apply it to both inputs at once.

```python theme={null}
b = qint(0, 1)
b.add_phase(
    lambda i: pi if f(i) == 1 else 0.0
)
```

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

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.

```python theme={null}
def pair(i: int) -> int:
    if i == 0:
        return 1
    if i == 1:
        return 0
    return i
```

Here, `0` is paired with `1`, and `1` is paired with `0`.

Next, we define `lr()` to select the left side of the pair.

```python theme={null}
def lr(i: int) -> bool:
    if i == 0:
        return True
    else:
        return False
```

We now apply `interfere()` to our quantum value.

```python theme={null}
b.interfere(pair, lr)
```

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 \rightarrow \frac{A+B}{\sqrt{2}}
$$

$$
1 \rightarrow \frac{A-B}{\sqrt{2}}
$$

Substituting the original amplitudes, where $A=-\frac{1}{\sqrt{2}}$ and $B=\frac{1}{\sqrt{2}}$:

$$
0 \rightarrow \frac{-\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}}}{\sqrt{2}} = 0
$$

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

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.

```python theme={null}
res = b.observe()

if res == 0:
    print("Quantum: Constant")
else:
    print("Quantum: Balanced")
```

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

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?

| Classical | Quantum |
| - | - |
| 2 function calls | 1 function call |
| Checks both inputs separately | Uses superposition to process both inputs together |
| Compares the two outputs | Observes the result after interference |

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!**


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