听出隐藏的比特串：Bernstein-Vazirani

先备导航：你需要 031（DJ 模板与相位回踢）、017（H 是翻译官）、021（H 门）、024（电路图）。

下一篇预告：033《百万抽屉千次摇：Grover I》。

听出隐藏的比特串：Bernstein-Vazirani

收音机的老体验：拧动旋钮，满世界散落的电波里，忽然有一个频率"咔"地对齐——噪声退成背景，一个台清晰地浮出来。

上篇的 DJ 算法读出了 1 比特的性质（f 是否恒等）；本篇把赌注抬高：黑箱里藏着一整串比特，比如 1011——量子电路能不能"拧一次旋钮"，让整串秘密像电台一样清晰地浮出来？答案是能。这就是 Bernstein-Vazirani 算法（下称 BV）：电路与 DJ 几乎一模一样，多出来的只有一步——而正是这一步，把"读 1 比特性质"升级成"读 n 比特串"，并顺手创造了一项纪录：经典 n 次，量子一次的指数级分家。

黑箱里藏了什么

设定：一串秘密比特 s（n 个比特，比如 4 比特的 1011）。黑箱函数 f 定义为：

f(x) = s 与 x 的"逐位相乘再求和"（模 2）

别被记号吓住，它是个朴素的动作：把 x 和 s 并排摆好，逐位对照，数"两边都是 1"的位置有几个，只报奇偶。例如 s=1011、x=0110：两边同时为 1 的位置有第 2、3 位共两个——偶数个，f(0110)=0。换个 x=1001：同时为 1 的只有第 1 位一个——奇数，f=1。

这个函数像一台奇偶计数器：每喂一个 x，它告诉你"x 和 s 的重合度是单还是双"——每次调用泄露一比特信息。现在玩老游戏：

• 经典：想知道 s 的每一个比特，只能发"单点探针"——问 1000…、0100…、0010…，每次探一个位；n 个比特，n 次调用，一个都不能少。
• 量子：一次调用，整串 s 出炉。

电路：DJ 的骨架，多一步解码

q0..qn(输入): ──H──■──H──M   （n 条输入线都过 H）
                 │
辅助 q:      ──H──X─────    （|−⟩ 伏笔，同 DJ）

和 031 篇逐字同款：H 铺开、黑箱回踢、H 收网。变化只有两处——输入线从 1 条变 n 条（铺开的是全部 2^n 个输入），以及黑箱从"任意函数"换成这台奇偶计数器。走一遍，看 s 怎么浮出来：

第一步，铺开。n 条线全过 H，账本上是 2^n 支等长的箭头，每支对应一个输入串 x。

第二步，回踢。黑箱调用一次，每支箭头按 f(x) 拿到自己的符号——回忆 031 篇：辅助线备着 |−⟩，f(x)=1 的那支被乘 −1。于是 2^n 支箭头带上了符号图案：f(x)=0 处 +，f(x)=1 处 −。而这个图案由 s 决定（f 是 s 的奇偶计数器）——s 被编码成了"符号的分布模式"，相位墨水，老配方。

第三步，解码——本篇真正的新东西。对 n 条线全部再过一次 H。奇妙的事发生了：那幅由 s 画出的符号图案，恰好是一个基态在 H 视角下的长相。拿 2 比特、s=11 做全例：四支箭头的符号是 +、−、−、+，合起来的态是 (|00⟩−|01⟩−|10⟩+|11⟩)/2——眼熟吗？拆开看，它就是 |−⟩|−⟩（两根线各自都是反相点）。而 H 是翻译官（017 篇），它把 |−⟩ 原路送回 |1⟩——两根线齐齐落回 |1⟩，测量得到 11，概率 100%。

s 有多长，浮出来的电台就有多长：一次测量，读出的直接就是 s 本身。没有猜、没有统计、没有概率优势——和 DJ 一样，干涉把答案逼成确定。

凭什么"一次"

宪法条款（031 篇）在此兑现：经典探针每次调用泄露 1 比特（单点 x 只碰一个位），n 个比特必须 n 次；量子的一次调用里，全部 2^n 个输入同场，每个输入的奇偶答案各就各位写进自己的箭头符号——s 的全部信息一次编完，第二层 H 一步解码。不是"同时问了 2^n 次"（黑箱只响了一声），而是"一次提问作用在所有问题的叠加上，且答案是全局的"。

BV 的历史位置要摆正：它是 DJ 的直接推广（DJ 就是 n=1 的 BV），真正的大事在下一步——1993 年 BV 证明"n 次对 1 次"后，1994 年 Simon 算法把分离推到指数级，几个月后 Shor 顺着 Simon 的肩膀摘走了分解问题（035~038 篇的剧情线）。BV 本身同样是个"承诺问题"（黑箱恰好是内积计数器，人造痕迹重，实用价值有限），但它是 Simon→Shor 谱系的中间站——教科书里它就是为三篇之后的大戏垫场的。

把类比拆掉

收音机类比借了哪里：

• 不像之一：收音机接收的是传播过来的电磁波，台在天上、你在收；量子电路没有传播——s 从头到尾没离开过账本，"浮出来"的是账本内部的一次基变换（017 篇：翻译官翻回计算基）。
• 不像之二：旋钮可以对准任意频率，且频率连续可调；BV 的"一次对齐"只对内积函数这种承诺黑箱成立——黑箱换成别的函数，同样的电路测出来就是一锅随机（承诺之外无魔法，这是所有黑箱算法的共同边界）。

带走的行李

1. BV=DJ 多比特版：H 铺开全部输入 → 内积黑箱把 s 编成箭头符号图案 → H 一步解码，一次测量直接读出整串 s，概率 100%。 2. 符号图案=基态的 H 视角：由 s 画出的相位分布恰好是某个基态在 H 基下的长相，翻译官翻回去就落回那个基态——基变换视角是读量子电路的第二双眼睛。 3. 谱系位置：经典 n 次对量子 1 次的纪录（DJ 的 n=1 特例推广），Simon→Shor 的垫脚石；"一次读串"仅对承诺黑箱成立。

下一站的钩子：DJ 和 BV 都"一次定乾坤"，听着玄，但它们的问题都是人造的。下一个问题终于落地：上百万个抽屉里找一个目标——数据库搜索，人间刚需。量子给多少加速？不是一次，是千次。033《百万抽屉千次摇：Grover I》。

#量子计算 #从硬币到纠错 #BernsteinVazirani #黑箱问题