量子計算中有三個反覆出現的思想:干涉可以揭示函數的整體承諾結構;糾纏可以產生超出經典共享隨機性模型的關聯;冗餘編碼可以保護量子資訊,而無需讀出未知概率幅。每個結論都依賴精確的模型。下面分別研究一個例子,並說明其局限。
Simon 的隱藏異或掩碼
定義 2.5.1
(Simon 承諾與預言機)
函數 滿足 Simon 承諾,是指存在非零 ,使得
目標是通過查詢可逆預言機 找出 。下文中 表示逐位點積模 , 是 上的正交子空間。
因此每個函數值恰有兩個原像,且兩者都相差同一個未知掩碼。儘管 是二對一的,該預言機仍置換基態,因而是酉變換。
命題 2.5.2
(Simon 樣本落在正交子空間內)
從 開始,對第一個寄存器作用 ,查詢 ,再對第一個寄存器作用 並測量它。測量結果 在 的 維子空間 上均勻分佈。
證明
(原像配對與奇偶性抵消)
第一層 Hadamard 門和查詢之後,狀態為 。測量第二個寄存器得到某個值 ;在這個條件下,第一個寄存器為
由於 ,且模 時 ,第二層 Hadamard 門之後, 的概率幅為
當 時它為零;當 時,其模平方為 。第二寄存器取任何值都得到同一分佈,因此每次運行都從 維子空間 均勻抽樣。測量第二寄存器有助於推導,但也可以省略:直接捨棄它,第一寄存器的分佈相同。
證明透視
隱藏掩碼如何進入證明
承諾只用了一次:它說明某個值的兩個原像是 與 ,且 相同。點積的雙線性使平移 變成相對符號 ,而未知的代表元 只出現在整體符號 中,它不影響概率。這就是為甚麼分佈不依賴所見到的函數值 。
Hadamard 變換恰好消去相對符號為負的結果;剩下的樣本是方程,並非掩碼本身。沒有承諾就沒有共同的 ,也就沒有抵消的規律,下面的反例會說明這一點。必須重複抽樣,直到樣本生成 ,從而確定它的一維正交補。
重複運行得到線性方程 ,再通過 上的高斯(Gauss)消去法求解。樣本 不提供資訊,重複樣本也可能線性相關。
命題 2.5.3
(由樣本恢復掩碼)
若樣本 生成 ,則 是對所有 滿足 的唯一非零解 。對 個獨立樣本,它們未能生成 的概率至多為 。
證明
(正交補與並集界)
若樣本生成 ,任何解 都與整個 正交。在 上點積是非退化的,所以 的維數為 且包含 ;因此它就是 ,唯一的非零解便是掩碼。
若樣本未能生成 ,它們落在一個真子空間內,因此落在 上某個非零線性泛函的核中。這樣的泛函有 個。對固定的一個,其核的元素個數是 的一半,所以每個均勻樣本落入其中的概率為 , 個獨立樣本全部落入的概率為 。對這些泛函使用並集界即得結論。
因此 次查詢可達到常數成功概率,繼續取樣可提高成功率。經典查詢下界指的是相同的承諾黑箱模型;查詢次數本身不包括實現具體預言機的代價。
例題 2.5.4
(三比特掩碼的樣本)
當 、,可能的輸出為 000、001、110、111,概率均為 。由 和 得到兩個獨立方程 、;唯一非零解是 110。一次運行通常不足以確定掩碼。
常見錯誤
(單個樣本不是掩碼)
樣本 只滿足 ;它是關於 的一個方程,並非 本身。在三比特例子中,樣本 完全有效,卻不同於 ,而樣本 完全不帶資訊。樣本只是偶然地等於掩碼,如下面的雙比特例子。必須等方程組只剩下一個非零解,才輸出掩碼。
一個完整的雙比特預言機計算
例題 2.5.5
(雙比特預言機的完整電路)
取 ,令 。函數表把 映至 ,把 映至 。因此每對原像相差 ,符合承諾。在隱藏掩碼問題中,學習者並不直接得到此表;這裏列出它是為了檢驗電路。
兩個寄存器均從 出發,經過第一層 Hadamard 門和預言機後,狀態為
每項乘積的第一個態屬於輸入寄存器。對它作用 , 保持不變,而 變成 。因此聯合態為
第一寄存器中沒有 或 。 和 各以概率 出現:對每個結果,兩個對應的輸出寄存器態正交,故概率幅的模平方相加。樣本 給出 ;再用承諾 ,便確定 。樣本 不給任何限制。這個例子的樣本恰好等於掩碼,但一般並非如此。
每次重新製備並獨立運行, 次後至少見到一次 的概率是 。所以本例三次查詢後,從樣本方程確定掩碼的概率為 。這個概率來自測量結果,並非對 的隨機選擇;它也依賴學習者使用非零掩碼的承諾。若所有樣本均為零時採用猜測策略,其成功概率會不同,並取決於未知掩碼的模型和猜測方式。
快速檢查
(改用 。找出掩碼和兩個可能樣本。如果首兩次獨立樣本都是 ,單憑樣本數據能確定掩碼嗎?)
解答 · 答案
原像對是 和 ,故 。由 得 或 ,各以概率 出現。兩個零樣本只給出方程 ,三個非零雙比特掩碼都與這些樣本方程相容。這裏展示的函數表能確定掩碼,但算法只獲准查詢預言機,並不直接獲知函數表。
承諾不能被悄悄略去。下面的例子對一個不是二對一的函數運行同一電路,說明樣本此時不能確定任何掩碼。
反例模式
沒有承諾就沒有掩碼可找
命題:無論 是甚麼函數,電路都只會從某個超平面 ()中抽樣。取 ,即 、,它不是二對一的。第二寄存器以概率 顯示 ,此時第一寄存器為 。經 後, 的概率幅是 除以 ,概率為 。第二寄存器以概率 顯示 ,第一寄存器為 ,四個結果的概率均為 。合起來,結果 的概率分別為 。四個字串都會出現,所以樣本生成 ,使所有樣本滿足 的唯一解是 。沒有任何非零掩碼與數據相容。上面的命題需要二對一承諾。
CHSH 與非定域關聯的含義
定義 2.5.6
(局域策略與 CHSH 表達式)
在 CHSH 實驗中,Alice 和 Bob 分別接收輸入比特 ,並輸出符號 。確定性的局域策略預先指定 。局域隱變量策略是確定性策略的概率混合,其中輸入選擇與共享隱變量獨立,且每一方的輸出只依賴本方輸入和隱變量。CHSH 表達式為
定理 2.5.7
(經典 CHSH 界)
對每個局域隱變量策略,。
證明
(確定性賦值與取平均)
由於 都是 , 和 中恰有一個非零,且等於 ;另一個括號為 ,所以每個確定性賦值都有 。局域隱變量策略是這些賦值的混合,絕對值為 的量的期望,其絕對值至多為 。
現在雙方共享 ,並取可觀測量
它們均為厄米(Hermitian)算子,且特徵值為 。
定理 2.5.8
(超過經典界的量子策略)
在 上取這些可觀測量,CHSH 期望為 。
證明
(四個關聯量)
代入可觀測量,
在 上, 和 的期望均為 ,所以 。
若輸入均勻隨機,遊戲要求雙方輸出相同符號,唯獨 時要求相反符號。獲勝概率為 ;量子策略得到 ,經典局域策略至多為 。
常見錯誤
(非定域關聯不是信號傳遞)
違反不等式排除了上述局域隱變量解釋,並不違反無信號原則。這裏每一方的邊緣輸出均勻隨機;單獨觀察它,無法讀出遠方選擇的輸入。比較關聯仍需經典通信,所以這種違反不能用來傳送消息。
保護一個量子比特免受比特翻轉
定義 2.5.9
(三比特翻轉碼)
此碼把 編碼成三個量子比特:
編碼電路從 開始,以第一個比特為控制、依次對另外兩個比特作用受控非門。其錯誤校驗子(syndrome)是可交換奇偶算子 和 的特徵值對。
常見錯誤
(編碼不是複製)
編碼態並不是三個 的副本:結果一般是糾纏態,而三個副本會包含八個基態項,係數如 。未知態不能被複製,這正是此冗餘要靠關聯來建立的原因。
假設錯誤被承諾為無錯誤或某個單比特翻轉 。四種情況的特徵值對為:
| 錯誤 | ||
|---|---|---|
| 無 | ||
定理 2.5.10
(單比特翻轉的糾正)
對這四種情況中的每一種,編碼態都是 和 的共同特徵向量,特徵值如上表,且這四個值對互不相同。作用校驗子所指明的 即可恢復 。
證明
(碼字及其補的奇偶性)
基態 是 的特徵向量,特徵值為 ;也是 的特徵向量,特徵值為 。 的兩項互為按位取補,而把所有位取補不改變每對位的奇偶性。因此兩項有相同的校驗子,該狀態是特徵向量。取其中一項來讀: 給出 ; 給出 ; 給出 ; 給出 。四個校驗子互不相同,所以校驗子確定發生了哪個 ;又因 ,再作用一次就恢復 。對所有 校驗子都相同,所以測量它不會透露 的任何資訊。
例題 2.5.11
(第一個比特翻轉的校驗子)
對 ,項 有 、。項 有 、。兩項都給出校驗子 ,正是 那一行,再作用 就恢復 。在無錯誤這個邊界情形,兩項都給出 ,不作任何糾正。
對 ,兩個基態項對兩個奇偶算子的特徵值均為 。因此錯誤校驗子能識別錯誤,卻不區分 項和 項;再作用 即恢復編碼態。校驗子測量揭示的是承諾範圍內發生了哪個錯誤,而非編碼的計算基值。
此碼能糾正一個比特翻轉,卻不能糾正任意單比特錯誤。
反例模式
比特翻轉碼不能糾正相位錯誤
命題:三比特碼能在任何單比特錯誤之後恢復編碼態。取 。此時 ,它與無錯誤狀態具有相同的兩個 校驗子,所以解碼器不作任何糾正,相對相位的改變就保留下來。輸入 ()時,編碼的加態變成與之正交的編碼減態。該命題只在錯誤被承諾為比特翻轉時成立。糾正一般錯誤需要同時檢測相位錯誤的編碼和校驗子方案;容錯操作還需控制編碼、量子門和校驗子提取本身引入的錯誤。
練習與解答
快速檢查
(在 、 的 Simon 承諾下,列出可能的樣本 。)
解答 · 答案
在 上,條件 給出 000、010、101、111,概率均為 。
快速檢查
(對確定性符號 、,化簡 CHSH 表達式。任何 的選擇能使其絕對值超過 嗎?)
解答 · 答案
,所以無論 如何選擇,其絕對值恰為 2。
快速檢查
(三比特碼中發生 會產生甚麼校驗子?如何修正?)
解答 · 答案
奇偶值對是 ;再作用 ,利用 即可恢復。