Academy K

Bernstein-Vazirani Algorithm

InterviewDerivationquantum algorithmsoracleslinear algebra

Related module: Early algorithms

Problem statement

The Bernstein-Vazirani algorithm finds a hidden string ss where f(x)=s⋅x(mod2)f(x) = s \cdot x \pmod 2.

  1. How many queries does a classical algorithm need?
  2. Describe the quantum algorithm that uses only 1 query.
  3. Why does the algorithm output ss exactly?

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.