電路的門來自有限詞表,但單量子比特可以旋轉連續變化的角度。有限詞表怎樣做到足夠豐富?答案分為兩步:任意單比特酉算子都可用連續角度旋轉精確表示,而適當的有限門集能以任意指定精度近似這些旋轉。僅有近似存在性還不能說明電路需要多長。
記泡利(Pauli)矩陣為 ,也記作 。
定義 9.1.1
(泡利旋轉)
對實角度 和 ,繞 軸的旋轉為
第二個等式由 得到。誤差採用算子範數 。整個電路上的全局相位 不改變最終測量概率;但如果之後要對該操作加控制,就不能隨便丟棄相位,因為它會成為控制位兩個分支之間的相對相位。
精確的連續分解
定理 9.1.2
(單比特酉算子的歐拉形式)
每個 酉矩陣 均可用實數 表成
角度不一定唯一;當 或 時,某些相位可重新分配。
證明
(從矩陣元素讀出角度)
選擇 ,使 的行列式為一。列向量正交且行列式為一,推出
選 ,使 、。直接相乘可得右側第一列為
若兩項均非零,選擇 匹配其相位;若有一項為零,只需匹配另一項,冗餘參數可任取。兩個行列式為一的酉矩陣既有相同第一列,第二列也相同,故分解成立。
例題 9.1.3
(Hadamard 門)
設 。由 和 ,得到
從最右側的門開始執行。作為單獨的門時,因子 是全局相位。
例題 9.1.4
(相位門 S:退化的歐拉形式)
令 。因為 ,所以 ,即 、。此時歐拉(Euler)形式中只有和 被確定: 與 都可以,因為 。這就是定理中提到的非唯一性。
有限門集可以稠密
令 。我們證明 的有限門序列可在忽略全局相位的意義下近似任意單比特酉算子。因為 、,它們的逆也可表示成有限門序列。
定義 9.1.5
(近似普適門集)
若對每個單比特酉算子 和每個 ,都存在 中門的有限序列 和實數 使 ,就稱單比特門集 是近似普適的。
定理 9.1.6
(H 與 T 的單比特近似普適性)
對每個單比特酉算子 及每個 ,都存在由 組成的有限序列 和實數 ,使得 。
證明
(無理旋轉與兩條不平行軸)
令 、。忽略全局相位, 而 。因此它們的乘積忽略相位後為
寫成 ,其中單位向量 與 平行。這裏
是無理數。否則特徵值 都是單位根,其和必為代數整數;但 在有理數域上的首一不可約多項式是 ,常數項非整數,所以它不是代數整數。這裏使用的標準事實是:代數整數之和仍為代數整數,且代數整數的首一最小多項式有整數係數。
無理角的整數倍模 稠密,因此 的冪可以近似繞 的任意旋轉,至多差一個全局符號。用 共軛得到另一條軸 ,平行於 ,它與 不平行。設 為所有 門序列在算子範數下、忽略全局相位的閉包;於是 包含繞這兩軸的所有旋轉。
為何兩軸足夠? 包含繞這兩軸的任意小旋轉及其逆。矩陣乘積極限給出由 與 的任意實線性組合生成的旋轉。將兩個小旋轉構成交換子,並以 的尺度重複 次,其極限是由 生成的旋轉;這裏使用
具體而言,令 、。對實數 ,
其中 。泰勒(Taylor)展開給出每一步的誤差分別為 與 ;對酉矩陣乘積作望遠鏡分解,累積誤差趨於零。縮放交換子並反轉其順序,便可得到第三個方向的任意實係數。這三個向量生成 ,故乘積極限給出任意 。每個行列式為一的 酉矩陣都有這種形式,例如可由對角化得出。因此 包含忽略相位後的所有單比特酉算子。依閉包定義,對每個正誤差都有某個有限序列達到該誤差。
證明透視
稠密性證明給出甚麼、沒有給出甚麼
這個證明有兩個獨立的輸入。 為無理數來自一個算術事實,即 不是代數整數,它使 的冪在繞 的旋轉中稠密;若角度為有理數,就只得有限個旋轉。不平行的共軛軸 使交換子能產生第三個方向;沒有它,閉包只會留在繞 的單參數群之內。不顯然的一步是 Trotter 型極限:繞兩條軸的小旋轉之積收斂到它們的組合與交換子所生成的旋轉,所以閉集 也包含由交換子生成的單參數群。閉包和矩陣極限證明每個精度都存在有限序列,但並未給出有用的門數界或尋找序列的快速算法。
例題 9.1.7
(乘積 A 的角度與軸)
取 、,則 、、。於是 ,,而且 。因此 ,,。軸為 ,而 。二者的點積為 ,所以兩軸不平行。
精確性與效率是不同問題
有限字母表只有可數多個有限序列,即便識別全局相位之後,單比特旋轉仍有不可數多個。因此存在無法用有限 序列精確表示的門。這與稠密性並不矛盾:可數集合可以稠密。
Solovay–Kitaev 定理給出更強的效率結論:對固定的、逆封閉且在 中稠密的有限門集,在標準的門描述假設下,任意 目標都可用長度為 的多項式的序列近似到誤差 ,並可由高效經典算法編譯。單憑稠密性不能得到這一速率。本節只陳述該定理,並未證明它;應用於 時須處理全局相位約定。多比特普適門集除了單比特門,還需要 CNOT 之類的糾纏門;本證明只建立單比特部分。
常見錯誤
(稠密不等於可以精確表示)
的有限序列能任意接近每個酉算子,並不表示每個酉算子都等於某個序列。序列的集合可數,酉算子的集合不可數,所以多數酉算子是序列的極限,而不是序列本身。
常見錯誤
(在受控門中丟棄全局相位)
等式 對單獨的門無害。若兩者都加上控制,受控 等於受控 再在控制位上作用相位門 ,因為因子 只出現在控制位為一的分支,在那裏它是相對相位。因此這兩個受控門作為算子並不相同。
反例模式
只有一條軸不夠
所有 的乘積,即使容許任意實角度,都是對角矩陣。任意對角酉矩陣 都將 映到它的倍數,而 。二者作用在此輸入上的距離至少為 。因此即使容許全局相位, 旋轉也無法任意精確地近似 。單軸上的連續門集仍不普適。
練習與解答
快速檢查
(驗證 ,並解釋為何等式精確成立而非僅相差相位。)
把 用到指數的冪級數上。
解答 · 答案
因 ,對指數的冪級數逐項共軛便得 ,沒有丟棄相位。
快速檢查
(寫出 的歐拉形式,包括全局相位。)
從 出發,把 軸轉到 軸。
解答 · 答案
。共軛把 軸轉到 軸;直接相乘可核對全局相位。
快速檢查
(為甚麼可數性論證不能指出某個特定的門無法用 精確表示?)
想想可數性能判斷甚麼、不能判斷甚麼。
解答 · 答案
可數性說明至少有一個,實際上不可數多個門不在集合內,但不能判斷某個指定矩陣是否屬於該集合;後者需要研究門序列矩陣元素的額外代數性質。