Quantum complexity theory

The journal version of the Bernstein–Vazirani hidden-string algorithm, cited from the complexity table. The algorithm was introduced at STOC 1993. One quantum query learns the hidden string s from the oracle that returns the mod-2 inner product of s with the query. A classical algorithm uses n queries. The separation is polynomial, not exponential. This library does not restate the paper's recursive Fourier-sampling bound, and it does not yet have an algorithm page for the result.