# Deutsch-Jozsa Algorithm
- Multi-qubit Deutsch Algorithm
- **Problem:**
- For $N=2^n$, we are given an $N$-bit string
- input: $x\in\{0,1\}^N$ such that either:
1. all $x_i$ have the same value: **constant**
2. $N/2$ of the $x_i$ are 0 and $N/2$ of the $x_i$ are 1: **balanced**
- **goal:** find out whether $x$ is constant or balanced

### The query setting:
- Can think of $N$-bit memory, which can access at any point of our choice (A random access memory)
- A memory access can be done via a so-called *black box*, which outputs $x_i$ on input $i$
- can be realized by a $(n+1)$-quibit unitary:
$$O_x|i,b\rangle\longmapsto |i,b\oplus x_i\rangle$$
- if we set the target qubit to $|-\rangle$
$$O_x|i\rangle|-\rangle\longmapsto (-1)^{x_i}|i\rangle|-\rangle$$
1. Basis $|i\rangle$ picks up the *phase* of $(-1)$ if $x_i=1$, otherwise, nothing happens.
2. target qubit remains in $|-\rangle$ (omitting)
3. called **phase oracle**
> if change $|-\rangle$ to $|+\rangle$
> $O_x|i\rangle|+\rangle\longmapsto|i\rangle|+\rangle$
> no change depends on $x_i$

### Deutsch-Jozsa Algorithm
1. start with $|0\rangle^{\otimes n}$ registers
2. apply Hadamard gate to each qubit
- $$\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}|i\rangle$$
- more generally
$$\frac{1}{\sqrt{2^n}}\sum_{j\in\{0,1\}^n}(-1)^{i\cdot j}|j\rangle$$
3. apply a phase oracle $O_{x,\pm}$
- $$\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}(-1)^{x_i}|i\rangle$$
4. apply another Hadamard gate to each qubit
- $$\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}(-1)^{x_i}\sum_{j\in\{0,1\}^n}(-1)^{i\cdot j}|j\rangle$$
- the amplitude of $|j\rangle=|0...0\rangle$
- since $i\cdot O^n=0$ for any $i\in\{0,1\}^n$
$$
\frac{1}{2^n}\sum_{i\in\{0,1\}^n}(-1)^x_i=\begin{cases}
1 & \text{if }x_i=0, \forall\ i & \text{constant}\\
-1 & \text{if }x_i=1, \forall\ i & \text{constant} \\
0 & &\text{balanced}\end{cases}$$
5. measure the final state
> The probability to project onto $|0...0\rangle$ in the final state is $1$ if $x$ is constatnt
> If $x$ is balanced, some other outcome will be obtained.

> Only **one** quantum query and $O(n)$ other operations (H-gates)
> *but not exponential*

- **classical**: needs at least $N/2+1$ queries. ($N=2^n$)
> but more efficiently if we allow a small error probability

- example:
- query $x$ at two random positions
- output $x$ is constant if two bits are the same
- output $x$ is balanced if two bits are different

output the correct answer with probability $1$ if $x$ is constant
output the correct answer with probability $1/2$ if $x$ is balanced
$\Rightarrow$ Total probability to output the correct answer: $3/4$

### Bernstein-Vazirani Problem
- **Problem:**
For $N=2^n$, we are given a bit string $x\in\{0,1\}^n$ with the property that there is some unknown bit string $a\in\{0,1\}^n$ such that $$x_i=i\cdot a\text{ mod }2$$
- **goal:** to find $a$
- exactly the *Deutsch-Jozsa Algorithm*, the final measurement suprisingly yields the output $a$ with certainty.

- quantum:
- deterministic
- one query
- classical:
- allowed to output with a small error probability
- $n$ queries