PHYSICS · Subjective · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms
Quantum Information and Technology, Ch Oracles, quantum parallelism and the first algorithms
Problem
Bernstein-Vazirani's oracle is f(x)=s⋅x for a fixed, unknown n-bit string s, and the main text already shows by a linear-algebra argument that n classical queries are necessary. Give a second, shorter argument for the same lower bound, by counting information rather than solving equations: state how many bits of information a single classical query can possibly return, how many bits are needed to pin down s exactly out of all 2n possibilities, and conclude that fewer than n classical queries can never suffice, whatever inputs are chosen and however the algorithm adapts them.