# Deutsch-Jozsa algorithm

We explain the Deutsch-Jozsa algorithm, a generalization of the Deutsch algorithm.  
For function $f$, which can take $2^n$ kinds of inputs (00...000 to 11...111), we assume that one of the following conditions holds.

1.  $f(x)$ is same for all inputs,
namely, $f(x)=0$ for all $x$ or $f(x)=1$ for all $x$.

2. $f(x)$ is different in half of the inputs,
namely, $f(x)=0$ for $2^{n-1}$ of inputs $x$, and $f(x)=1$ for others.

This algorithm determines whether Oracle is 1\. or 2\. above.

The circuit is here.



It has $n$ qubits $\lvert 0\rangle$ and 1qubit $\lvert 1\rangle$ as  initial states.

Now let's check the states.

$$
\begin{align}
\lvert \psi_1\rangle &= \biggl(\otimes^n H\lvert 0\rangle \biggr)\otimes H \lvert 1\rangle \\
&= \frac{1}{ \sqrt{2^{n+1}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} \bigl( \lvert x\rangle \otimes (\lvert 0\rangle - \lvert 1\rangle) \bigr) \\
&= \frac{1}{ \sqrt{2^{n+1}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} \lvert x\rangle \otimes \lvert 0\rangle - \frac{1}{ \sqrt{2^{n+1}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} \lvert x\rangle \otimes \lvert 1\rangle \\
\end{align}
$$


For the $n$ th qubit, you can see that swapping $\lvert 0\rangle$ and $\lvert 1\rangle$ changes the overall sign.

Next, consider $\psi_2$.  
Because $f(x)$ operates to $n$ th qubit,

$$
f(x) = 0 \to n\text{ th qubit is NOT be flipped.}
$$
$$
f(x) = 1 \to n\text{ th qubit is flipped.}
$$

Dividing the summation by $f(x) = 0 \text{ or } 1$ for each term,

$$
\frac{1}{ \sqrt{2^{n+1}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} \lvert x\rangle \otimes \lvert 0\rangle \xrightarrow{U_f} \frac{1}{ \sqrt{2^{n+1}} } \sum_{f(x)=0} \lvert x\rangle \otimes \lvert 0\rangle + \frac{1}{ \sqrt{2^{n+1}} } \sum_{f(x)=1} \lvert x\rangle \otimes \lvert 1\rangle
$$

$$
\frac{1}{ \sqrt{2^{n+1}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} \lvert x\rangle \otimes \lvert 1\rangle \xrightarrow{U_f} \frac{1}{ \sqrt{2^{n+1}} } \sum_{f(x)=0} \lvert x\rangle \otimes \lvert 1\rangle + \frac{1}{ \sqrt{2^{n+1}} } \sum_{f(x)=1} \lvert x\rangle \otimes \lvert 0\rangle
$$

We can see that $n$ th qubit is flipped when $f(x)=1$.

Therefore,

$$
\lvert \psi_2\rangle = \frac{1}{\sqrt{2^n}} \biggl( \sum_{f(x)=0}\lvert x\rangle - \sum_{f(x)=1}\lvert x\rangle \biggr) \otimes \frac{1}{\sqrt{2}} (\lvert 0\rangle - \lvert 1\rangle)
$$

In the case "1.$f(x)$ is same for all inputs", each of terms for $f(x)=0$ or $f(x)=1$ vanish.  
So,

$$
\begin{align}
\lvert \psi_2 \rangle &= \pm \frac{1}{ \sqrt{2^{n}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} \lvert x\rangle \otimes \frac{1}{\sqrt{2}} (\lvert 0\rangle - \lvert 1\rangle) \\
&= \pm \biggl( \otimes^{n} H \lvert 0\rangle \biggr) \otimes H \lvert 1\rangle
\end{align}
$$

As a consequence, $\lvert \psi_3 \rangle$ is

$$
\lvert \psi_3 \rangle = \pm \lvert 00...00 \rangle \otimes H\lvert 1 \rangle
$$

In this case, the measurmet results from the $0$ th to $n$ th qubits will all be "0".

In the case "2.$f(x)$ is different in half of the inputs", because the signs are different for $f(x)$,

$$
\lvert \psi_2 \rangle = \frac{1}{ \sqrt{2^{n}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} (-1)^{f(x)} \lvert x\rangle \otimes \frac{1}{\sqrt{2}} (\lvert 0\rangle - \lvert 1\rangle)
$$

$$
\begin{align}
\lvert \psi_3 \rangle &= \frac{1}{ \sqrt{2^{n}} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} (-1)^{f(x)} (\otimes^nH) \lvert x\rangle \otimes \frac{1}{\sqrt{2}} (\lvert 0\rangle - \lvert 1\rangle) \\
&= \frac{1}{ 2^{n} } \sum^{2^n}_{x\in \{ 0, 1 \}^n} (-1)^{f(x)} \bigl( \sum^{2^n-1}_{y=0}(-1)^{x\cdot y}\lvert y \rangle \bigr) \otimes \frac{1}{\sqrt{2}} (\lvert 0\rangle - \lvert 1\rangle)
\end{align}
$$

Now, consider the probability $\rm{Pr}(0)$ that all the measurements results from the $0$ th to the $n$ th qubits are "0".  
It is squared absolute value of the amplitude of state $\lvert y \rangle\ (y=0)$.  

Because $x\cdot y=0$ when $y=0$,

$$
\mathrm{Pr}(0) = \biggl| \frac{1}{2^n} \sum^{2^n}_{x\in \{ 0, 1 \}^n} (-1)^{f(x)} \biggr|^2
$$

If $f(x)$ is different in half of the inputs, all the terms cancel each other out, so $\mathrm{Pr}(0) =0$.  
Therefore, the result of measuring up to $n$ th qubits from the $0$ th will never be all "0".  

From the above, we can determine the oracle by whether the results of measuring the qubits up to the ($n-1$) th bit are all $0$ or not.

Let's implement this in blueqat.


```python
from blueqat import Circuit
import numpy as np
```

Let's implement oracle for case 1\. and 2\., respectively.

In the case 1\., we invert the $n$ th qubit regardless of the qubits up to the ($n-1$) th.

In the case 2\., we prepare $n$ $CX$ gates such that each qubit up to the ($n-1$) th qubit is a control bit and all target bits are the $n$ th qubit.    
In this case, the $n$ th qubit is inverted for half of the possible values of the qubits up to the ($n-1$) th qubit, while remains unchanged for the other half.


```python
def oracle_1(c):
    n = c.n_qubits
    c.x[n-1]
    
def oracle_2(c):
    n = c.n_qubits
    for i in range(n-1):
        c.cx[i, n-1]
```

The following is the main body of the algorithm.    
まず、オラクルが 1\. と2\. のどちらであるかを乱数で決めます。これが求めたい正解となります。  
First, set the oracles 1\. or 2\. by random number. This will be the correct answer we want to find.  

Next, use the Deutsch-Jozsa algorithm to determine the oracle.  

Finally, check if the result of the discrimination and the oracle selected by a random number in advance match.


```python
n = 4

c = Circuit(n + 1)
c.x[n].h[:]

if np.random.rand() > 0.5:
    oracle_1(c)
    oracle = "f(x) = 1 for all x."
else:
    oracle_2(c)
    oracle = "f(x) = 0 for half x and f(x) = 1 for others."

c.h[:]
res = c.m[:].run(shots = 1000)

print("Oracle:", oracle)
print("Results of quantum circuit:", res)

if [arr[:n] for arr in res.keys()] == ['0'*n] and oracle == "f(x) = 1 for all x.":
    print("OK")
elif [arr[:n] for arr in res.keys()] != ['0'*n] and oracle == "f(x) = 0 for half x and f(x) = 1 for others.":
    print("OK")
else:
    print("incorrect")
```

    Oracle: f(x) = 1 for all x.
    Results of quantum circuit: Counter({'00001': 1000})
    OK


Now we determined the oracle using the Deutsch-Jozsa algorithm.


```python

```

e33914a12b5b0d139474d60fc5e8f6a910fd3490
ipynb
Jupyter Notebook
tutorial/101_deutsch-jozsa.ipynb
ssmi1975/Blueqat-tutorials
f2962a7eda733568d228cb1ebbcd2c2f409f84cb
Apache-2.0
2021-11-22T19:18:09.000Z
2022-01-30T22:38:03.000Z
tutorial/101_deutsch-jozsa.ipynb
ssmi1975/Blueqat-tutorials
f2962a7eda733568d228cb1ebbcd2c2f409f84cb
Apache-2.0
2021-11-23T22:41:58.000Z
2022-01-30T17:46:46.000Z
tutorial/101_deutsch-jozsa.ipynb
ssmi1975/Blueqat-tutorials
f2962a7eda733568d228cb1ebbcd2c2f409f84cb
Apache-2.0
2022-01-04T22:29:13.000Z
2022-01-30T08:38:20.000Z
Qwen/Qwen-72B
1. YES
2. YES