- Published on

# Deutsch's Algorithm: One Query is Better Than Two Queries

- Authors
- Name
- Galih Laras Prakoso
- @galihlprakoso

This is another win for Quantum Computing over Classical Computing, to solve Deutsch's Problem, Quantum Computing needs less query compared to Classical Computing. What's Deutsch's Problem?

## Deutsch's Problem

It's pretty simple, imagine a function $f(x) \rightarrow y$, where $(x,y) \in \{0,1\}$. Your job is to simply determine whether the function is **Constant** or **Balanced**. What does it means? please look at this table:

$x_a$ | $f_a(x_a)$ | $x_b$ | $f_b(x_b)$ |
---|---|---|---|

0 | 0 | 0 | 0 |

1 | 0 | 1 | 1 |

$x_c$ | $f_c(x_c)$ | $x_d$ | $f_d(x_d)$ |
---|---|---|---|

0 | 1 | 0 | 1 |

1 | 0 | 1 | 1 |

We can divide these functions into two groups, constant: $f_a(x_a)$, $f_d(x_d)$, and balanced: $f_b(x_b)$, $f_c(x_c)$. In other way, we could see this problem as the same as doing $XOR$ to all possible outputs of given inputs $x \in {0,1}$:

$f(x_1)$ | $f(x_2)$ | $f(x_1) \otimes f(x_2)$ |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

As you can see that we could group the function by looking at their results of $XOR$-ing all possible inputs $(0,1)$.

## Classical Computing

We can solve this problem using Classical Computing by querying all possible inputs to the function. Why two queries? Because, knowing $f(x_1) = 0$ doesn't give you enough information whether to determine whether it's a **Constant** or **Balanced** function. $f(x_2)$ could still be 0 which will make this function **Constant**, or it could also be 1 which will make this function **Balanced**.

So, the best of what Classical Computing can do to solve this problem is by doing two queries.

## Quantum Computing

Better than Classical Computing, by using Quantum Computing, we're able to solve the Deutsch's Problem using just single query. All we need to have is a unitary matrix $U_f$ which is a permutation matrix that will somehow have the capability to $XOR$ the value of the first qubit $x$ with the second qubit $y$.

As you can see that the circuit above is capable to solve the Deutsch's Problem by using just single query. By looking at the result of the measurement of the first qubit, we will be able to determine whether the function $f$ is **Constant** or **Balance**. It will output $0$ when the function is **Constant** and $1$ when the function is **Balanced**.

### Mathematical Explanation

I will breakdown the explanation into three states, we will observe the evolution of the qubit states: $\ket{a}$,$\ket{b}$,$\ket{c}$:

Initially we have this $\ket{a}$ state:

$\ket{a} = \ket{+}\ket{-} = \frac{1}{2}\ket{0}(\ket{0} - \ket{1}) + \frac{1}{2}\ket{1}(\ket{0} - \ket{1})$

We will keep the $\ket{-}$, because it will be easier to be used to explain the transformation to the next state after applying the $U_f$ gate:

$\ket{b} = \ket{+}\ket{-} = \frac{1}{2}\ket{0}(\ket{0 \otimes f(0)} - \ket{1 \otimes f(0)}) + \frac{1}{2}\ket{1}(\ket{0 \otimes f(1)} - \ket{1 \otimes f(1)})$

Okay, it seems a little bit complicated 🙄, let's simplify the equation with one notes (we need to keep the $\ket{-}$ state isolated), because it will intuitively tells us that the second qubit is unchanged. By observing the equation above, we could generalize the equation to be like this:

$\ket{0 \otimes a} - \ket{1 \otimes a} = (-1)^a(\ket{0} - \ket{1})$

A gentle reminder: $x^0 = 1$. By using this generalization, we could transform our $\ket{b}$ state to be like this:

$\ket{b} = \frac{1}{2}\ket{0}(-1)^{f(0)}(\ket{0} - \ket{1}) + \frac{1}{2}\ket{1}(-1)^{f(1)}(\ket{0} - \ket{1})$

or

$\ket{b} = \ket{-}\bigl(\frac{\ket{0}(-1)^{f(0)} + \ket{1}(-1)^{f(1)}}{\sqrt{2}}\bigl)$

Actually, we can also take out $(-1)^{f(0)}$:

$\ket{b} = (-1)^{f(0)}\ket{-}\bigl(\frac{\ket{0} + \ket{1}(-1)^{f(0) \otimes f(1)}}{\sqrt{2}}\bigl)$

When $f(0) \otimes f(1) = 0$, we will get:

$(-1)^{f(0)}\ket{+}\ket{-}$

otherwise, when $f(0) \otimes f(1) = 1$ we will get:

$(-1)^{f(0)}\ket{-}\ket{-}$

Now, we arrived to the observation of last state $\ket{c}$. In this state, we just simply apply $H$ (Hadamard) operation to the first qubit and it will simply give us this states:

When $f(0) \otimes f(1) = 0$, we will get:

$(-1)^{f(0)}\ket{0}\ket{-}$

When $f(0) \otimes f(1) = 1$ we will get:

$(-1)^{f(0)}\ket{1}\ket{-}$

As you can see that the second qubit is unchanged ($\ket{-}$) while the first qubit's state is depending on the result of $f(0) \otimes f(1)$. After the measurement on the first qubit, we will get the classical value $0$ when the function is **Constant** and $1$ when the function is **Balanced**.

## Qiskit Implementations

First, we need to define the four functions $f_a(x)$,$f_b(x)$,$f_c(x)$,$f_d(x)$. All these four functions is just a quantum circuit with some qubit operations that represent the behaviour of each function:

Import qiskit library:

```
from qiskit import QuantumCircuit
```

$f_a(x)$: $\bigl(f(0) = 0$, $f(1) = 0\bigl)$:

```
def f_a() -> QuantumCircuit:
circuit = QuantumCircuit(2)
return circuit
print(f_a())
```

Output:

```
q_0:
q_1:
```

$f_b(x)$: $(f(0) = 0$, $f(1) = 1)$.

```
def f_b() -> QuantumCircuit:
circuit = QuantumCircuit(2)
circuit.cx(0, 1)
return circuit
print(f_b())
```

Output:

```
q_0: ──■──
┌─┴─┐
q_1: ┤ X ├
└───┘
```

$f_c(x)$: $(f(0) = 1$, $f(1) = 0)$.

```
def f_c() -> QuantumCircuit:
circuit = QuantumCircuit(2)
circuit.cx(0, 1)
circuit.x(1)
return circuit
print(f_c())
```

Output:

```
q_0: ──■───────
┌─┴─┐┌───┐
q_1: ┤ X ├┤ X ├
└───┘└───┘
```

$f_d(x)$: $(f(0) = 1$, $f(1) = 1)$.

```
def f_d() -> QuantumCircuit:
circuit = QuantumCircuit(2)
circuit.x(1)
return circuit
print(f_d())
```

Output:

```
q_0: ─────
┌───┐
q_1: ┤ X ├
└───┘
```

Next, we need to create a circuit for our Deutsch Algorithm:

```
def deutsch_algo_circuit(function: QuantumCircuit):
n = function.num_qubits - 1
circuit = QuantumCircuit(n + 1, n)
circuit.x(n)
circuit.h(range(n + 1))
circuit.barrier()
circuit.compose(function, inplace=True)
circuit.barrier()
circuit.h(range(n))
circuit.measure(range(n), range(n))
return circuit
print(
deutsch_algo_circuit(
f_c()
)
)
```

Output:

```
┌───┐ ░ ░ ┌───┐┌─┐
q_0: ┤ H ├──────░───■────────░─┤ H ├┤M├
├───┤┌───┐ ░ ┌─┴─┐┌───┐ ░ └───┘└╥┘
q_1: ┤ X ├┤ H ├─░─┤ X ├┤ X ├─░───────╫─
└───┘└───┘ ░ └───┘└───┘ ░ ║
c: 1/════════════════════════════════╩═
0
```

All we need to do now is just running our algorithm on Quantum Computing simulator:

```
from qiskit_aer import AerSimulator
circuit = deutsch_algo_circuit(f_c())
result = AerSimulator().run(circuit, shots=1, memory=True).result()
measurements = result.get_memory()
if measurements[0] == "0":
print("constant")
else:
print("balanced")
```

Output:

```
balanced
```

Yeay! We've successfully solve the Deutsch's Problem using Deutsch's Algorithm and run it on Quantum Computing simulator and get expected result. You could try to test another function and see whether it's returning the expected or not.

If you have anything to discuss, please drop your comments below! 🍻🍻