← Quantum Store · Guides · Lessons · Glossary · About · Türkçe
What is the Bernstein–Vazirani algorithm?
The Bernstein–Vazirani algorithm finds the hidden bit string s inside a function f(x) = s·x in a single query, instead of the n queries needed classically.
In the problem defined by Ethan Bernstein and Umesh Vazirani in 1993, the function returns the sum (mod 2) of the bitwise products of a hidden string s and the input. Classically each bit has to be queried separately.
The quantum circuit has the same skeleton as Deutsch–Jozsa. The oracle is built with one CNOT from each input qubit where s has a 1 to the helper qubit; after the final H gates the inputs read s directly.
Try it yourself
The lesson Bernstein–Vazirani: find the hidden string in one go lets you try this concept in the browser, with no installation.
Related packages
Related concepts
- Deutsch–Jozsa algorithm · The Deutsch–Jozsa algorithm is one of the first quantum algorithms: it decides with certainty, in a single query, whether a function is constant or balanced.
- CNOT gate · The CNOT (controlled-NOT) gate is a two-qubit gate that flips the target qubit when the control qubit is 1; it is the basic tool for creating entanglement.
- Quantum circuit · A quantum circuit is a quantum program made of gates applied to qubits in order, followed by measurements.