BV, DJ

Deutsch-Jozsa

Problem Statement

Given an oracle : , 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 consisting of either

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

• Worst Case:

Bernstein-Vazirani

Given an oracle : , where we know will output the dot product between and a secret string , find