BV, DJ

Deutsch-Jozsa

Problem Statement

Given an oracle ƒ: {0,1}n→{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: 𝙾(2n)

Bernstein-Vazirani

Given an oracle ƒ: {0,1}n→{0,1}, where we know ƒ(x) will output the dot product between xand a secret string s mod(s∈{0,1}n,2), find s