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 \(|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
     \[\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}\)
   • \[\frac{1}{\sqrt{2^n}}\sum_{i\in\{0,1\}^n}(-1)^{x_i}|i\rangle\]
4. apply another Hadamard gate to each qubit
   • \[\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