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{array}{ll}f(0)=f(1)& \text{constant}\\ f(0)\ne f(1)& \text{balanced}\end{array}$

  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
   

   $$\begin{gathered} |x⟩={\alpha }_x|0⟩+{\beta }_x|1⟩ \\ |y⟩={\alpha }_y|0⟩+{\beta }_y|1⟩ \end{gathered}$$
   in a product state
   $|x,y⟩=|x⟩|y⟩$

2. Use 2-qubit unitary transformation

   $U_f$
   
   $$U_f|x⟩|y⟩\to |x,y\oplus f(x)⟩$$

   Remark: after

   $U_f$, it may not be a product state
   

   $|x,y\oplus f(x)⟩\ne |x⟩|y\oplus f(x)⟩$

   Apply

   $U_f$ twice,

   $U_f^2=\mathbb{1}$ (identical)
   

   $U_f$ is an unitary,

   $U_f^{†}=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$?

• First try:

  • $|x⟩=|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$
    
    $|y⟩=|0⟩$
  • $U_f|x⟩|y⟩=\frac{1}{\sqrt{2}}(|0⟩|f(0)⟩+|1⟩|f(1)⟩)$
    
    $\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⟩|f(0)⟩$ or
    $|1⟩|f(1)⟩$
    
    $\Rightarrow$ not better than two evaluations
  $\Rightarrow$ Quantum parallelism is an ingredient for speed up
  but we also need Algorithm interference: a way of constructively interfering the paths such that the desired information is amplified, and the information we do not care about becomes inaccessible

• Second try:

  • $|x⟩$
    
    $|y⟩=|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$
  • $U_f|x⟩|-⟩=(-1{)}^{f(x)}|x⟩|-⟩$
  • Again
    $|x⟩=|+⟩$
  • $U_f|+⟩|-⟩=\frac{1}{\sqrt{2}}((-1{)}^{f(0)}|0⟩+(-1{)}^{f(1)}|1⟩)|-⟩$
  $\Rightarrow$
  $\{\begin{array}{ll}\text{if }f(0)=f(1)& U_f|+⟩|-⟩=(\pm 1)|+⟩|-⟩\\ \text{if }f(0)\ne f(1)& U_f|+⟩|-⟩=(\pm 1)|-⟩|-⟩\end{array}$

  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{array}{ll}f\text{ is constant }& |+⟩\text{ with probability 1}\\ f\text{ is balanced }& |-⟩\text{ with probability 1}\end{array}$