# Deutsch Algorithm

- A glance of both side of the coin at the same time by integrating the coin
(classical: at least two glance of both side)

- relies on **quantum superposition** and **entanglement**
- asks a **partial** question about a system

- *Input $x$:*
- $x\in\{0,1\}$
- *Outcome $f(x)$:*
- $f(x)\in\{0,1\}$
- *Problem:*
- $\begin{cases}
f(0) = f(1) & \text{constant} \\
f(0) \neq f(1) & \text{balanced}
\end{cases}$
> not interested in $f(0)$ and $f(1)$

### classical computation

1. compute $f(0)$ and $f(1)$
2. compare $f(0)$ and $f(1)$
> **Two** evaluation of $f$
> With less than two (zero, one), one can only **guess** $f$ is constant or balanced

### quantum computation
- claim:
- just one $f$
- won't (must not) obtain the information about individual value of $f$
1. Use two qubits
$$
|x\rangle = \alpha_x |0\rangle + \beta_x|1\rangle \\
|y\rangle = \alpha_y |0\rangle + \beta_y|1\rangle
$$
in a product state $|x,y\rangle = |x\rangle|y\rangle$

2. Use 2-qubit unitary transformation $U_f$
$$
U_f|x\rangle|y\rangle \rightarrow |x, y\oplus f(x)\rangle
$$
> Remark: after $U_f$, it may not be a product state
> $|x, y\oplus f(x)\rangle \neq|x\rangle| y\oplus f(x)\rangle$

> Apply $U_f$ twice, $U_f^2 = \mathbb{1}$ (identical)
> $U_f$ is an unitary, $U_f^\dagger = U_f$
- Every application of $U_f$ requires only **one** evaluation of $f$

- *Can we thus answer the question by a quantum algorithm that requires only a single application of $U_f$?*

- <ins>First try</ins>:
- $|x\rangle = |+\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$
$|y\rangle = |0\rangle$
- $U_f|x\rangle|y\rangle = \frac{1}{\sqrt{2}} (|0\rangle|f(0)\rangle+|1\rangle|f(1)\rangle)$
$\Rightarrow$ state contains both function values in **superposition** in the second qubit and (in general) **entangled** with the first qubit
- **Problem:** if we measure first qubit, superposition collapses with probability $1/2$ to either $|0\rangle|f(0)\rangle$ or $|1\rangle|f(1)\rangle$
$\Rightarrow$ <font color=red>not better than two evaluations</font>

$\Rightarrow$ <font color=orange>Quantum parallelism</font> is an ingredient for speed up
but we also need <font color=orange>Algorithm interference</font>: a way of constructively interfering the paths such that the desired information is amplified, and the information we do not care about becomes inaccessible

- <ins>Second try</ins>:
- $|x\rangle$
$|y\rangle = |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$
- $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$
- Again $|x\rangle = |+\rangle$
- $U_f|+\rangle|-\rangle = \frac{1}{\sqrt{2}}((-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle)|-\rangle$

$\Rightarrow$$\begin{cases}
\text{if }f(0)=f(1) & U_f|+\rangle|-\rangle=(\pm 1)|+\rangle|-\rangle \\
\text{if }f(0)\neq f(1) & U_f|+\rangle|-\rangle=(\pm 1)|-\rangle|-\rangle
\end{cases}$

> Information $f$ is constant or balanced is now encoded in the **first qubit**
> Information $f(0)$ and $f(1)$ is now as **global phase factor** $\pm 1$
>, which are inaccessible

- Final step: measure the first qubit in $X$-basis
$\begin{cases}
f \text{ is constant } & |+\rangle\text{ with probability 1}\\
f \text{ is balanced } & |-\rangle\text{ with probability 1}
\end{cases}$