The Bernstein-Vazirani algorithm is a textbook example of quantum speedup. Given a function f(x) = s·x (inner product mod 2 with a hidden string s), a classical computer needs n queries to find s. The quantum algorithm finds it in one. This seems like genuine quantum advantage — the interference pattern from a single superposition query reveals the entire secret string.
Chmura shows it's not quantum at all. The Hadamard gate, the core of the algorithm, is a global basis rotation — it maps the computational basis to the Fourier basis. The “quantum computation” that follows is linear algebra over GF(2) — the same binary arithmetic a classical computer would do. The entire algorithm is classical computation performed in a conjugate basis. The speedup comes from choosing a coordinate system in which the answer is visible, not from any genuinely quantum resource.
The distinction matters: globally rotated circuits versus topologically twisted ones. A global rotation changes what you call “up” and “down” — it's a change of coordinates, not a change of physics. A topological twist creates entanglement, where measurement outcomes in one part depend on another part in a way no classical system can replicate. The Bernstein-Vazirani algorithm is all rotation, no twist.
This doesn't diminish the algorithm's pedagogical value — it just reclassifies it. The lesson isn't “quantum computers can do things classical computers can't.” The lesson is “choosing the right basis can make a hard problem trivial.” That's a classical insight dressed in quantum notation. The Hadamard gate is powerful not because it creates superposition but because it diagonalizes the problem.
The deeper structural claim: some apparent quantum speedups are notational artifacts. The physics didn't change; the description did. Recognizing which algorithms genuinely require quantum resources — entanglement, non-Clifford gates, topological complexity — requires distinguishing coordinate changes from physics changes. The hardest part of quantum computing may be figuring out which parts are actually quantum.