Bernstein-Vazirani quantum speedup = n (linear in problem size)

Exact query-complexity result. Quantum: 1 oracle query recovers the n-bit hidden string s exactly. Classical lower bound: any classical algorithm (deterministic or randomised) requires ≥ n queries by an adversary / information-theoretic…