9.9 The Bernstein-Vazirani algorithm
Suppose I were to say to you: algorithm$Bernstein-Vazirani Bernstein-Vazirani algorithm
I’m thinking of a number from 0 to 15 inclusive.
Ask me questions to guess which one it is.
How would you go about guessing the number? How many questions would you need?
This is a search problem, but it has some structure. The numbers in the collection we are searching are consecutive and ordered. There is no reason to consider an O(n) sequence of questions such as
“Is it 0?” No.
“Is it 1?” No.
“Is it 2?” No.
⋮
“Is it 13?” Yes.
Grover could help with an O(√n) approach, but we can do better with O(log2(n)) classically:
“Is it greater than 7?” Yes.
“Is it greater than 11?” Yes.
“Is it greater than 13?” No.
“Is it greater than 12?” Yes.
“...
