Bernstein-Vazirani algorithm

In plain terms

An oracle holds a secret string of bits and, for any input string you send, returns a single bit, the parity, meaning whether the number of positions where both your input and the secret have a one is odd or even. Classically each query buys you one bit of the secret, so a secret of a given length costs that many queries, and no cleverness helps.

Bernstein and Vazirani ask once. Prepare the uniform superposition, the register holding every possible input at once with equal weight, let the oracle act, so it writes each parity into the sign of the corresponding amplitude rather than into a separate output, and then undo the superposition. The interference is total, so the register reads the secret string itself, with certainty, every time.

There's no probability, no repetition and no post-processing, so it's one query and one answer.

In CSD

Bernstein-Vazirani is an algorithm witness in the same family as Deutsch-Jozsa and Simon, an oracle between two layers of Hadamard gates, and the corpus proves the strong version, that the full circuit's output is concentrated entirely on the secret string, with that outcome having probability one and every other outcome probability zero. Unlike the reduced analysis of Simon's algorithm, this is the complete circuit, superposition, oracle and undoing, with no measurement reduction along the way.

The standing disclaimer applies as ever, as the algorithms consume the programme's unitary-evolution pillar and don't support the foundations.

Mathematically

The circuit is H^n then the phase oracle |x> to (-1)^{<a,x>} |x> then H^n, on |0^n>. The output amplitude at y is (1/2^n) sum over x of (-1)^{<y+a, x>}, and the character sum reduces to 2^n [y = a], the Kronecker delta. The corpus proves outcome a with probability one (bv_certain) and every other outcome zero (bv_zero).

The content is one orthogonality of characters over F_2^n, and the algorithm is the observation that a single physical query evaluates all the parities in superposition.

The name

Ethan Bernstein and Umesh Vazirani published the algorithm inside their 1993 STOC paper on quantum complexity theory, the paper that defined BQP and made quantum computation a complexity class rather than a curiosity. Vazirani, at Berkeley, went on to shape much of the field's theory, and Bernstein was his doctoral student.

Related entries

• Deutsch-Jozsa algorithmThe Deutsch-Jozsa algorithm settles a question with a single query where any exact classical method needs exponentially many, and the problem it solves is useless by design and historic for exactly that reason.
• Simon's algorithmSimon's algorithm was the exponential separation that convinced Shor, as a hidden bitwise mask, unfindable classically without exponential work, falls to a handful of quantum queries and some linear algebra.
• Hadamard testThe Hadamard test turns a matrix element, a complex number buried inside an operator, into the bias of a single coin.
• Grover's algorithmGrover's algorithm finds one marked item in an unsorted list in a number of steps proportional to the square root of the list size, and a separate theorem shows that no quantum algorithm can do better.
• quantum Fourier transformThe quantum Fourier transform runs Fourier's transform as a single reversible motion of a quantum register, and it's the lens that turns hidden periods and phases into outcomes a measurement can land on.