Loading AI tools
Quantum algorithm From Wikipedia, the free encyclopedia
The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997.[1] It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function.[2] The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.[1]
Given an oracle that implements a function in which is promised to be the dot product between and a secret string modulo 2, , find .
Classically, the most efficient method to find the secret string is by evaluating the function times with the input values for all :[2]
In contrast to the classical solution which needs at least queries of the function to find , only one query is needed using quantum computing. The quantum algorithm is as follows: [2]
Apply a Hadamard transform to the qubit state to get
Next, apply the oracle which transforms . This can be simulated through the standard oracle that transforms by applying this oracle to . ( denotes addition mod two.) This transforms the superposition into
Another Hadamard transform is applied to each qubit which makes it so that for qubits where , its state is converted from to and for qubits where , its state is converted from to . To obtain , a measurement in the standard basis () is performed on the qubits.
Graphically, the algorithm may be represented by the following diagram, where denotes the Hadamard transform on qubits:
The reason that the last state is is because, for a particular ,
Since is only true when , this means that the only non-zero amplitude is on . So, measuring the output of the circuit in the computational basis yields the secret string .
A generalization of Bernstein–Vazirani problem has been proposed that involves finding one or more secret keys using a probabilistic oracle.
[3]
This is an interesting problem for which a quantum algorithm can provide efficient solutions with certainty or with a high degree of confidence, while classical algorithms completely fail to solve the problem in the general case.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.