MilestoneTheory & algorithmsConfirmed
Bernstein and Vazirani reveal a hidden bit string with one quantum query
1993
Ethan Bernstein and Umesh Vazirani give a quantum method for learning a hidden n-bit string from a black-box linear function in one query, compared with n classical queries for exact recovery. This is a theoretical advantage in access to the black box, not a general-purpose speedup.
Why it matters
The algorithm gives a simple example of how interference extracts a global property with fewer queries, helping establish the foundations of quantum complexity theory.
Ethan Bernstein · Umesh Vazirani
Related
Added Oct 28, 2026. Spotted an error? Tell us and we will review it.