BV, DJ
Deutsch-Jozsa
Problem Statement
Given an oracle
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
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