[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