Quantum Algorithms Database
Bernstein-Vazirani Algorithm
Finds a hidden binary string encoded in a function using just one query, versus many queries classically — a simple but illustrative example of quantum parallelism.
Year
1992
Inventor(s)
Ethan Bernstein & Umesh Vazirani
Speedup Type
Exponential Speedup
Difficulty
★★☆☆☆
The Problem
Given a 'black box' function that computes the dot product of the input with a hidden secret string, determine the secret string.
How It Works
Prepares all inputs in superposition, queries the function once, and uses interference so that measuring the resulting state directly reveals the hidden string in a single shot.
Real-World Impact
Mainly an educational stepping-stone algorithm, often taught right after Deutsch-Jozsa, used to build intuition for how quantum parallelism extracts global information about a function efficiently.