量子谕示器（oracle）

想象一个封闭的盒子，它只干一件事：你递给它一个输入，它就告诉你「是，这是一个解」或者「不是」。量子谕示器就是这样一个盒子，只是它被造得能让量子算法向它提问。不过，它并不会把答案明明白白地交到你手上，而是悄悄地给正确的输入做上记号——通常是翻转某个解的振幅的符号（也就是相位），或者翻转一个额外的「答案位」——而其它一切都保持原样。你可以把它想成一枚隐形墨水的印章：解都被盖上了章，但在你做更多工作之前，仍然没法直接读出盖章的是哪些。

由于量子计算机可以让许多输入同时处于叠加态，一次谕示器查询就能把所有匹配的输入一起盖上章。炒作往往就是从这里悄悄溜进来的，所以要当心：这一次查询并不会揭示答案。那些记号藏在你无法直接看到的振幅里，此刻去测量，只会得到一个随机的输入。接下来，像 Grover 算法这样的方法会用一轮又一轮的干涉（振幅放大），把那些相位记号慢慢变成一个又大又可读的概率——这也正是为什么在 N 个条目中搜索时，Grover 仍然需要大约 N 的平方根次查询：这是一个实实在在、但仅仅是二次方的加速，而不是什么一次到位的魔法查表。

谕示器之所以重要，是因为它让我们能用查询复杂度来衡量一个算法有多巧妙：它要成功，最少得向盒子请教多少次。这是在同一个问题上公平比较量子方法与经典方法的一种干净办法。但要留意——这里的诚实很重要——谕示器是一种抽象。在真实机器上它并不是免费的：总得有人用普通的、可逆的（酉）门把它实实在在地搭出来，让它真正去做那个「是/否」检查，而这套搭建本身是有代价的。数查询次数告诉你的，是一个算法使用这个盒子的效率，而不是运行它的全部开销。