💼 Case: lets define a function Boolean function $f: \{ 0,1 \} \to \{ 0,1\}$ which takes and outputs bits

• We define a 2 bit system dependent on $f$ as follows: $U_f:\ket{x,y}\to \ket{x,y\otimes f(x)}$ explicitly

  $$ \hat U_f =\sum_{x=0}^1\sum_{y=0}^1 \ket{x} \bra{x}\otimes \ket{y \oplus f(x)}\bra{y} \\ $$

• If we now apply it to the state $\frac{1}{\sqrt{2}}\bigl(\lvert 0\rangle + \lvert 1\rangle\bigr)\otimes\lvert 0\rangle$ gives

  $$ \begin{aligned} \hat U_f \Bigl(\tfrac{1}{\sqrt{2}}\bigl(\lvert 0\rangle + \lvert 1\rangle\bigr)\otimes\lvert 0\rangle\Bigr) =\frac{1}{\sqrt{2}} \Bigl(\hat U_f\lvert 0,0\rangle + \hat U_f\lvert 1,0\rangle\Bigr) =\frac{1}{\sqrt{2}}\Bigl(\lvert 0,f(0)\rangle + \lvert 1,f(1)\rangle\Bigr) \end{aligned} $$

  💎 Conclusion: here we see that both $f(0)$ and $f(1)$ were computed simultaneously

We can generalise this to $n$ bits of input

• $U_f$ now has $n+1$ inputs with the first $n$ being input to $f$
• It has $n+1$ outputs with $n$ being identical to the original $n$ as can be seen in the representation

🗒️ Note: bared line with $n$ means $n$ lines

• Here for our first state we we use the $n$ tensor product of Hadamard operation applied to $\ket{0}$

  $$ (\underbrace{H\otimes H \otimes \ldots \otimes H}{n \;\text{times}})\ket{\underbrace{00\ldots 0}{n \;\text{times} }}=H^{\otimes n} \ket{0}^{\otimes n}=\frac{1}{\sqrt{2^n}} \sum_{x\in\{0,1\}^n} \ket{x} $$

• Applying our state to our general $U_f$ gives

  $$ U_f:\frac{1}{\sqrt{2^n}} \sum_{x\in \{ 0,1 \} ^n} \ket{x} \ket{0} \to \frac{1}{\sqrt{2^n}} \sum_{x\in \{ 0,1 \} ^n} \ket{x}\ket{f(x)} $$

💎 Conclusion: again all the $2^n$ values of $f$ are computed in one step

However extracting useful information in the collapse here is complicated

Deutsch’s algorithm

Here we consider our previous $U_f$

1️⃣ Setup:

• We begin with 2 qubits $\ket{0}\otimes \ket{1}=\ket{01}=\ket{\psi_0}$

• We can then apply the Hadamard gates to each qubit

  $$ H\ket{0} = \frac{1}{\sqrt{2}} (\ket{0}+\ket{1}) \qquad H\ket{1} = \frac{1}{\sqrt{2}} (\ket{0}-\ket{1}) $$

  Where the combined state after applying $H\otimes H$ to $\ket{01}$ is

  $$ {\ket{\psi_1}=(H\otimes H)\ket{\psi_0} = [\tfrac{1}{\sqrt{2}} (\ket{0}+\ket1)]\otimes [\tfrac{1}{\sqrt{2}} (\ket{0}-\ket1)]=\frac{1}{2} (\ket{0}+\ket1)(\ket{0}-\ket1)} $$

2️⃣ Algorithm:

• Now we apply our oracle operator $\hat U_f\ket{x,y}=\ket{x,y\oplus f(x)}$ where $x,y,f\in\{0,1\}$

  $$ \ket{\psi_2}=\hat U_f\ket{\psi_1} = \frac 12 \sum^1_{x=0} \sum^1_{y=0} \alpha_{x,y} \ket{x,y\oplus f(x)} $$

  where $\alpha_{x,y}$ come from the normalisation constants

• We can write this out more explicitly as

  $$ \ket {\psi_2}=\left \{ \begin{matrix} \pm \frac 12 ( \ket{0} + \ket{1})\otimes (\ket{0}-\ket{1}) & \text{if} & f(0)=f(1) \\[0.5em] \pm \frac 12 ( \ket{0} - \ket{1})\otimes (\ket{0}-\ket{1}) & \text{if} & f(0)\ne f(1) \end{matrix}\right . $$