In quantum information, the Bernstein-Vazirani algorithm proves the supremacy of quantum computers over classical deterministic or probabilistic computers. It is extremely similar to the Deutsch-Jozsa algorithm, and even uses the same circuit.
It solves a very artificial problem: we are given a “black box” function that takes an -bit and returns a single bit, which we are promised is the lowest bit of the bitwise dot product of with an unknown -bit string :
The goal is to find . To solve this problem, a classical computer would need to call exactly times with for . However, the Bernstein-Vazirani algorithm allows a quantum computer to do it with only a single query. It uses the following circuit:
Where is a phase oracle, whose action is defined as follows, where :
That is, it introduces a phase flip based on the value of . For an example implementation of such an oracle, see the Deutsch-Jozsa algorithm: its circuit is identical to this one, but describes in a different (but equivalent) way.
Starting from the state , applying the Hadamard gate to all qubits yields:
This is an equal superposition of all candidates , which we feed to the oracle:
Then, using the definition of the Hadamard transform and the fact that it is its own inverse, one final set of -gates leads us to:
Which, upon measurement, gives us the desired binary representation of . For comparison, the Deutsch-Jozsa algorithm only cares whether or , whereas this algorithm is interested in the exact value of .
- J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.
- S. Aaronson, Introduction to quantum information science: lecture notes, 2018, unpublished.