量子諭示器（oracle）

想像一個封閉的盒子，它只做一件事：你遞給它一個輸入，它就告訴你「是，這是一個解」或者「不是」。量子諭示器就是這樣一個盒子，只是它被造得能讓量子演算法向它提問。不過，它並不會把答案明明白白地交到你手上，而是悄悄地給正確的輸入做上記號——通常是翻轉某個解的振幅的符號（也就是相位），或者翻轉一個額外的「答案位元」——而其它一切都保持原樣。你可以把它想成一枚隱形墨水的印章：解都被蓋上了章，但在你做更多工作之前，仍然沒法直接讀出蓋章的是哪些。

由於量子電腦可以讓許多輸入同時處於疊加態，一次諭示器查詢就能把所有匹配的輸入一起蓋上章。炒作往往就是從這裡悄悄溜進來的，所以要當心：這一次查詢並不會揭示答案。那些記號藏在你無法直接看到的振幅裡，此刻去測量，只會得到一個隨機的輸入。接下來，像 Grover 演算法這樣的方法會用一輪又一輪的干涉（振幅放大），把那些相位記號慢慢變成一個又大又可讀的機率——這也正是為什麼在 N 個項目中搜尋時，Grover 仍然需要大約 N 的平方根次查詢：這是一個實實在在、但僅僅是二次方的加速，而不是什麼一次到位的魔法查表。

諭示器之所以重要，是因為它讓我們能用查詢複雜度來衡量一個演算法有多巧妙：它要成功，最少得向盒子請教多少次。這是在同一個問題上公平比較量子方法與經典方法的一種乾淨辦法。但要留意——這裡的誠實很重要——諭示器是一種抽象。在真實機器上它並不是免費的：總得有人用普通的、可逆的（么正）閘把它實實在在地搭出來，讓它真正去做那個「是/否」檢查，而這套搭建本身是有代價的。數查詢次數告訴你的，是一個演算法使用這個盒子的效率，而不是執行它的全部開銷。