動機
一般的多量子比特態,需要指數多個概率幅才能寫下來。但某些態有較短的描述:指定一組可交換且數值已知的可觀測量,讓這些方程決定狀態。例如 Bell 態是同時對 和 具有特徵值一的唯一態。此描述保留關聯,卻不用列出四個概率幅,而且能推廣至很多量子比特。
要把短描述用於模擬,還必須能有效更新它。我們需要說明,門如何改變方程,測量如何改變方程,以及如何取得測量概率。符號一直重要: 和 具有相同的非恆等張量因子模式,測量意義卻相反。
本篇建立只儲存生成元、並明確保留四值相位的 tableau 表。它與常見的單一符號比特慣例略有不同,所以每條更新都從指定的算子次序推導。所得算法對計算基輸入、指定 Clifford 門及 Pauli 測量,證明精確模擬結論;它不模擬任意量子電路,也不列出指數長的概率表。
定義
令
定義 4.1.1
(Pauli 行編碼)
對二元向量 和 ,把 Pauli 編碼為
次序是全部 因子先於全部 因子。特別地,單量子比特行 表示 ,而 表示 。二元座標按模二相加,記為 ;相位指數則按模四相加。相位公式中的內積,先作整數加總,再按所示模數化簡。
定義 4.1.2
(穩定子態)
純穩定子態由 個彼此交換、獨立的厄米(Hermitian) Pauli 生成元 指定,其生成群不含 。獨立表示二元行向量 的秩為 ;上標標記生成元,下標則標記量子比特座標。狀態是共同 特徵向量,歸一化後只差整體相位。可展開投影 檢查唯一性:獨立性使每個非空乘積都是非恆等 Pauli,故跡為零。投影的跡為一,因此秩為一。
定義 4.1.3
(Tableau 與 Clifford 共軛)
本篇的 tableau 就是這 行,每行有 個二元座標及兩個相位比特。Clifford 酉算子把 Pauli 群共軛映至自身。我們使用
以及按 定義的受控非門。若狀態經 演變,穩定子就按 演變。測量厄米 Pauli ,是使用兩個投影 ,結果標記為 。
定理/命題
定理 4.1.4
(保留相位的 Pauli 算術)
乘法規則為
兩行可交換,當且僅當 模二成立。一行為厄米,當且僅當 模二成立。
定理 4.1.5
(本篇慣例下的共軛更新)
對每個生成元行使用下列規則。右邊全部是舊值,未指定的項保持不變:
這些門是 Clifford 門,共軛後的行指定演變後的態。CNOT 不更新相位,是本篇先 後 的次序慣例之結果,並不是每一種 tableau 慣例的規則。
定理 4.1.6
(純穩定子態的 Pauli 測量)
若有生成元與 反交換,兩個結果的概率均為 。選一個這樣的主元 。對其餘每個與 反交換的生成元,使用原來主元及保留相位的乘法,把它改為 。其他行不變,最後按抽樣結果 ,把主元改成 。新行描述歸一化的測量後狀態。
若全部生成元都與 交換,就在 上解出與 有相同二元座標的生成元乘積。其真正帶符號乘積不是 就是 ,相應結果確定為 或 ,狀態不變。
定理 4.1.7
(本篇實際證明的模擬結論)
從計算基乘積態出發,由 、受控非門和已編碼厄米 Pauli 測量組成的電路,可使用 比特儲存量及多項式經典時間作精確抽樣。只儲存生成元的做法,每個所列門需 ,用二元高斯(Gauss)消去處理每次測量至多需 。若門的選擇依賴過去測量結果,而其經典控制能在多項式時間內計算,仍在結論範圍內。
這是對指定理想電路模型的構造性 Gottesman–Knill 結論。下面證明更新不變量及抽樣概率;但不證明任意抽象 Clifford 酉算子都能由此門集合成,不證明較快的 destabilizer 表算法,也不處理任意混合或含雜訊輸入,以及不受限制的非 Clifford 門。有效抽樣一條記錄,也不同於印出全部可能記錄。
證明思路
證明
(重排 Pauli 因子所產生的符號)
乘法的唯一額外符號,來自把 移過 。每個重疊對貢獻一個負號,得到 。把乘法次序反過來就得到交換測試。取伴隨時, 次序反轉,相位也共軛,所以厄米性要求 ,恰是所述奇偶條件。兩個可交換穩定子行的乘積仍為厄米;任意兩個反交換行的乘積則未必如此。
證明
(驗證單量子比特與 CNOT 的更新)
對門,直接矩陣乘法給出 、、 和 。Hadamard 因而把局部 和 的次序反轉,向相位加入 。相位門貢獻 ,並把舊的 比特加到 比特。這同時證明兩條單量子比特規則,包括局部因子為 時的符號。
在基態上檢查受控非門可得
全部變換後的 因子仍可置於全部 因子之前,不需要把某個 移過某個 ,因為它們本來就以該次序到來。因此二元更新不用改變 。酉共軛保留乘法、交換關係及共同特徵空間,所以保留 tableau 的狀態意義。
證明
(隨機測量結果與新生成元)
對隨機測量,反交換主元給出
所以兩個投影概率相同。歸一化分支為 。每個未改變的交換生成元都穩定此分支;兩個反交換生成元之積也與 交換並穩定它;最後, 在所選分支上特徵值為一。改變後的非主元行仍獨立,生成舊二元行空間的一個 維子空間。測量向量不在該空間,因為它與舊主元反交換,舊行空間中的每個向量卻都與舊主元交換。加入測量行後,秩回到 。分支非零,所以新群不能含 。因此這些行精確指定歸一化分支,而不只是列出它滿足的一些限制。
證明透視
先用舊主元消去,才替換它
兩個都與測量反交換的舊行,其乘積會與測量交換,這正是更新所需的抵消。先替換主元會破壞此論證:把反交換行乘上新的測量行,可能得到反厄米算子。應保存原來主元,以精確 Pauli 乘法完成全部消去,最後才放入帶有所測符號的可觀測量。
證明
(由極大性得到確定測量)
確定結果的情況用到極大性,而不只是交換的口號。令 是舊二元行空間,配上雙線性形式
此形式非退化,因為與座標 、 向量配對,能檢測每個座標。因此正交補的維數是 。交換性給出 ,維數相等便有兩者相等。所以與每行交換的測量必在 內。二元消去找出係數,再乘上帶符號的行,決定結果是 還是 ;厄米性排除 的相位差。這證明確定概率,也解釋為何消去後不能把相位丟掉。
概念視角結構
穩定子態是極大迷向子空間
先暫時不理符號。二元行 位於 ,配上上文的雙線性型 ; 個獨立而互相對易的生成元生成滿足 的子空間,即極大迷向子空間。穩定子態就是這樣的子空間再加上一組符號選擇。 時有三個子空間(、、),各有兩種符號,共六個態; 時有十五個子空間、六十個態。
證明
(儲存量、運行時間與精確抽樣)
對基輸入 ,以 初始化各行。表示式使用 比特。每個所列門只觸及每行固定數目的項;測量與全部行的交換測試,以及隨機情況的消去,需 比特操作。確定情況的成員判定,可用普通二元消去在 操作完成,再作保留相位的乘法。每個隨機分支用一枚公平硬幣。由於條件概率和新狀態都與量子測量相同,歸納法加概率鏈式法則便證明整條記錄的精確抽樣,不必列舉分支。
Aaronson 與 Gottesman 的較快算法保留額外行,避免此消去步驟。本篇不證明該改良及較強的效能界;明確的生成元算法已足以對指定模型建立多項式模擬。
例題詳解
例題 4.1.8
(三個門之後仍要保留單量子比特的符號)
從由 穩定的 出發,其行為 。依次作用 、、,各行變成
它們表示 ,故最後測量 必得 。若只保留最後的二元對,就會遺失符號。穩定子方程的符號指定特徵值,不是態向量無關緊要的整體相位。
例題 4.1.9
(典範相位不變,為何仍可表示負 YY)
以量子比特一控制量子比特二的受控非門,共軛 。原行有 、、;更新後兩個二元向量都為 ,相位仍為零。所得算子是
這不與相位規則矛盾。把典範有序乘積轉成局部 因子時,會出現兩個 。若另一慣例是在局部 標記前儲存正負號,就要在另一位置處理這個轉換。
例題 4.1.10
(Bell 關聯與真正隨機的第一次測量)
從 出發,作用 和受控非門,初始生成元 變成 。其乘積是 ,所以測量 必得 。
若改為測量 ,它與第一生成元反交換,每個結果 的概率為 ,新生成元是 。其乘積為 ,故隨後的 測量必有相同結果。兩分支是 和 。經典抽樣可以精確保留這個關聯;穩定子可有效模擬,不表示沒有糾纏。
反例模式
非 Clifford 相位破壞 Pauli 更新
對 ,
它不是 Pauli 算子。態 的 、 期望值為 , 期望值為零,所以沒有非恆等的單量子比特 Pauli 以它作特徵態。本篇的一行純態表示對此門不封閉。但表示法失效,不等於證明每個含 的電路都難以經典模擬;例如 。
第二個反例涉及確定情況,而不是門集合。
反例模式
不完整的碼空間描述中,交換仍不足夠
兩量子比特上的單一生成元 指定碼空間,而非純態; 和 Bell 態都在其中。 與此生成元交換,但在第一個態上必得正結果,在第二個態上卻均勻隨機。確定情況的證明需要 個獨立生成元和極大的二元行空間,不能只用較少生成元,忽略尚未決定的邏輯態後仍套用它。
常見錯誤
常見錯誤
(共軛方向錯誤,或使用已被覆寫的座標)
狀態按 演變時,要使用 ;反方向共軛回答另一個問題。二元更新右邊全部用舊座標,再儲存新行;若混入已覆寫座標,即使公式正確也可能得到錯結果。
常見錯誤
(生成元的符號不是整體相位)
不要把 Pauli 的和當成單一 Pauli,也不要把生成元符號與態的整體相位混淆。二元消去決定乘積的支撐模式,真正的相位則決定特徵值。未先翻譯所表示算子,就在不同 tableau 慣例之間抄用相位公式,尤其容易出錯。
常見錯誤
(模型外的門不能證明困難性)
模擬器假設理想操作和完整指定狀態的穩定子輸入,沒有證明一般容錯或雜訊閾值,也沒有只憑模型外某個門的出現就建立困難性結論。緊湊表示可能不再適用,但不會自動令每個這類電路實例都很難。
總結
Pauli 行結合二元支撐與相位,後者必須在乘法和共軛中保留。所列 Clifford 門保持此表示。Pauli 測量不是均勻隨機並替換主元,就是以極大性及帶符號成員判定得到確定結果。這些性質對指定理想模型給出精確多項式時間抽樣,但合成、最優化表、較廣輸入及雜訊模型仍不在已證結論內。
練習
快速檢查
(以典範乘法規則計算 和 。為何不修正相位,就不宜把這些乘積當作厄米穩定子生成元?)
把 編碼成 。
解答 · 答案
反交換乘積帶虛相位。對 ,相位為 ,二元對為 ,所以 。反向次序沒有交叉貢獻,故 。兩者都反厄米,與兩個反交換厄米算子相乘一致。穩定子行替換使用彼此交換的生成元,其乘積仍為厄米。
快速檢查
(從 出發,作用 再 ,然後測量 。求概率及每分支的新生成元;立即重測 又如何?)
測量前的生成元是 。
解答 · 答案
結果隨機一次,然後確定。門給出生成元 ,它與 反交換,所以每個結果的概率為 。結果 把唯一生成元替換成 ;新態因此是特徵值 的 特徵態,立即重測必得相同結果。
快速檢查
(對 Bell 生成元 和 ,測量 並以第一生成元作主元。兩舊行都與測量反交換,求新生成元及概率。)
先用原主元消去第二行,再替換主元。
解答 · 答案
消去兩個反交換行:第二行成為 ,新主元是 ,每個 的概率為 。兩個新生成元彼此交換且獨立。乘積行的典範相位為零,兩個二元向量都是 ;把它讀成正的 就是符號錯誤。
快速檢查
(三量子比特態的生成元為 、、。先測 再測 ,以生成元乘積推導其關聯,不要列態向量。)
第一結果決定新的帶符號 生成元。
解答 · 答案
三個比特共享同一個結果。 與 反交換,故每個結果 的概率為 。兩個舊 對生成元與它交換,保持不變。新生成元 乘 得 ,再乘 得 。所以後來測量 必得 。代數用三行而不是八個概率幅追蹤此關聯。