[Quantum Information] Deutsch Algorithm

 Deutsch Algorithm

Notes from RWTH Aachen University course 
“Quantum Information” Summer semester 2020
professor: Müller, Markus

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$?

• First try:

  • $|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$ 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\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}$
• Quantum circuit implementing Deutsch’s algorithm.

Readings

Nielsen and Chuang

1.4.3 Deutsch’s algorithm