[Quantum Information] Deutsch-Jozsa Algorithm

 Deutsch-Jozsa Algorithm

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

Deutsch-Jozsa Algorithm

• Multi-qubit Deutsch Algorithm
• Problem:
  • For $N=2^n$, we are given an $N$-bit string
  • input: $x\in\{0,1\}^N$ such that either:
    1. all $x_i$ have the same value: constant
    2. $N/2$ of the $x_i$ are 0 and $N/2$ of the $x_i$ are 1: balanced
  • goal: find out whether $x$ is constant or balanced

The query setting:

• Can think of $N$-bit memory, which can access at any point of our choice (A random access memory)
• A memory access can be done via a so-called black box, which outputs $x_i$ on input $i$
• can be realized by a $(n+1)$-quibit unitary:
  $$O_x|i,b\rangle\longmapsto |i,b\oplus x_i\rangle$$
• if we set the target qubit to $|-\rangle$
  $$O_x|i\rangle|-\rangle\longmapsto (-1)^{x_i}|i\rangle|-\rangle$$
  1. Basis $|i\rangle$ picks up the phase of $(-1)$ if $x_i=1$, otherwise, nothing happens.
  2. target qubit remains in $|-\rangle$ (omitting)
  3. called phase oracle

  if change $|-\rangle$ to $|+\rangle$
  $O_x|i\rangle|+\rangle\longmapsto|i\rangle|+\rangle$
  no change depends on $x_i$

Deutsch-Jozsa Algorithm

1. start with $|\psi_0\rangle=|0\rangle^{\otimes n}$ registers
2. apply Hadamard gate to each qubit
   • $$\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}|i\rangle$$
   • more generally
     $$|\psi_1\rangle=\frac{1}{\sqrt{2^n}}\sum_{j\in\{0,1\}^n}(-1)^{i\cdot j}|j\rangle$$
3. apply a phase oracle $O_{x,\pm}$
   • $$|\psi_2\rangle=\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}(-1)^{x_i}|i\rangle$$
4. apply another Hadamard gate to each qubit
   • $$|\psi_3\rangle=\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}(-1)^{x_i}\sum_{j\in\{0,1\}^n}(-1)^{i\cdot j}|j\rangle$$
   • the amplitude of $|j\rangle=|0...0\rangle$
   • since $i\cdot O^n=0$ for any $i\in\{0,1\}^n$
     $$\frac{1}{2^n}\sum_{i\in\{0,1\}^n}(-1)^x_i=\begin{cases} 1 & \text{if }x_i=0, \forall\ i & \text{constant}\\ -1 & \text{if }x_i=1, \forall\ i & \text{constant} \\ 0 & &\text{balanced}\end{cases}$$
5. measure the final state

The probability to project onto $|0...0\rangle$ in the final state is $1$ if $x$ is constatnt
If $x$ is balanced, some other outcome will be obtained.

Only one quantum query and $O(n)$ other operations (H-gates)
but not exponential

• classical: needs at least $N/2+1$ queries. ($N=2^n$)

but more efficiently if we allow a small error probability

• example:

  • query $x$ at two random positions
  • output $x$ is constant if two bits are the same
  • output $x$ is balanced if two bits are different

  output the correct answer with probability $1$ if $x$ is constant
  output the correct answer with probability $1/2$ if $x$ is balanced
  $\Rightarrow$ Total probability to output the correct answer: $3/4$

Bernstein-Vazirani Problem

• Problem:
  For $N=2^n$, we are given a bit string $x\in\{0,1\}^n$ with the property that there is some unknown bit string $a\in\{0,1\}^n$ such that 

  $$x_i=i\cdot a\text{ mod }2$$

• goal: to find $a$

• exactly the Deutsch-Jozsa Algorithm, the final measurement suprisingly yields the output $a$ with certainty.

• quantum:

  • deterministic
  • one query

• classical:

• allowed to output with a small error probability
• $n$ queries

Readings

Deutsch, D., & Jozsa, R. (1992). Rapid Solution of Problems by Quantum Computation.

Nielsen and Chuang

1.4.4 The Deutsch–Jozsa algorithm