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
- Quantum Computing: Lecture Notes
Ronald de Wolf, 2019
- Quantum complexity theory
Ethan Bernstein, Umesh Vazirani, 1997
Lean context
- Lean declaration
QuantumAlg.BernsteinVazirani.main
Copy a short prompt with the import, theorem name, citations, and public source link.