1. 问题背景

Bernstein–Vazirani 算法解决的是这样一个 oracle 问题：

假设有一个黑盒函数

        

它定义为

        

其中 s 是一个固定的  位二进制串 ，
而  表示按位点乘然后求和模 2（即两个二进制串的按位与之后数 1 的个数再模 2）。

点乘（dot product）定义

        

等价于

         

这里  是异或（模 2 加法，每次完成加法后直接 mod 2后，再参与下一个 mod-2-加，或者全部加法的结果 mod 2）， 是按位与。

例子：
若 , 

        

2. 经典解法

黑盒  对任何输入  返回 。

目标：找出隐藏的 。

经典做法：

        输入 （只有第 0 位是 1），得到 ​。

        输入 （只有第 1 位是 1），得到 ​。

        依此类推，输入  个不同的“只有一个 1”的串，得到  的所有位。

所以 经典需要  次查询。

3. 量子解法（Bernstein–Vazirani 算法）

量子情况下，我们假设黑盒是一个 量子 oracle ​，它作用在  上：

        

其中  是单个量子位。

关键步骤

1. 初始态：

         

1. 对前  位（查询寄存器）施加 ，对最后一位（目标位）施加 （ 得到  ​）。

   此时整体态为：

         

1. 应用 ​：

         

注意：

        

因为若 ，则  变成  。

所以：

        

其中  ，所以：

        

1. 丢弃最后一个量子位（它已分离），对前  位再作用 。

回忆：

        

反过来：

        

交换求和：

        

1. 括号内的求和：

        

其中 。
这个求和是 0，除非 （即 ），此时为 1。

所以结果是 。

最终：测量前  位，确定性地得到 。

4. 结论

        经典：需要  次查询。

        量子：只需要 1 次查询 就得到 。

         是二进制点乘模 2，它出现在 oracle 的相位  中，量子并行 + 干涉把它提取出来。

        这个算法是量子计算比经典有查询复杂度优势的早期例子之一（1992年），比 Grover 还早，并且是 Deustch–Jozsa 的推广。