Query algorithms ยท Algorithms

Bernstein-Vazirani algorithm

Theorem statement

Let $f:\{0,1\}^n\to\{0,1\}:x\mapsto x\cdot s\bmod 2$ be the mod-2 inner-product function for an unknown $s\in\{0,1\}^n$. Given access to an oracle $O_f$ such that $O_f\ket{x,y}=\ket{x,y\oplus f(x)}$, there exists a quantum circuit that uses one query to $O_f$ and $2n+1$ Hadamard gates to exactly obtain $s$.

Sources

  1. Quantum Computing: Lecture Notes

    Ronald de Wolf, 2019

  2. Quantum complexity theory

    Ethan Bernstein, Umesh Vazirani, 1997

Lean context

Copy a short prompt with the import, theorem name, citations, and public source link.

Open Lean source