BV, DJ

Deutsch-Jozsa

Problem Statement

Given an oracle $ƒ$: ${\{0,1\}}^n\to \{0,1\}$, determine whether this oracle is

• Constant: All inputs map to the same output

• Balanced: Exactly half of the inputs map to the same output

Classical Computation

Given we have a bit-string of length $n$ consisting of either $\{0,1\}$

• Best Case: You only input $2$ queries and see their results are different, immediately telling you they are balanced

• Worst Case: $𝙾\left(2^n\right)$

Bernstein-Vazirani

Given an oracle $ƒ$: ${\{0,1\}}^n\to \{0,1\}$, where we know $ƒ\left(x\right)$ will output the dot product between $x$and a secret string $s$ $\mathrm{mod}(s\in {\{0,1\}}^n,2)$, find $s$