積和式, 玻色採樣和計數複雜性

04-24

這篇會講一講積和式 (Permanent) 和 $mathsf{#P}$ -completeness, 以及玻色採樣 (Boson Sampling) 之間的聯繫.

用以展示量子計算優越性 (quantum conputational supremacy)[6] 的候選問題有很多, 不過玻色採樣 (Boson sampling) 很可能是知名度最高的問題之一. 這一問題的美妙之處在於, 它聯繫了線性光學和積和式 (permanent), 因為光子 (photon) 在不同的模數 (mode) 上的概率分布, 可以對應到某個積和式上; 而積和式在計算複雜性理論中具有獨特的地位, 原因之一是它提供了第一個非平凡的 $mathsf{#P}$ -complete 問題. 有趣的是, 基於線性光學的技術給出了新的規約手段, 因而一併導出了一些特定類型的矩陣, 即 $GL(n)$ , $O(n)$ , $U(n)$ , $Sp(2n)$ 對應的積和式求值也是 $mathsf{#P}$ -complete 的[1].

本文的部分細節來自 Daniel Grier 上周的 seminar[1], 以及 2016 年 Scott Aaronson 在 Avi60 上的 talk[2]. Grier 和 Schaeffer 的工作已被 CCC 2018 接收. 本文亦發表於我的博客, 見積和式, 玻色採樣和計數複雜性 - Complexity Meets Quantum.

積和式與全同粒子

與行列式相比, 積和式相對要少見得多. 部分原因可能是行列式的性質相比之下要好得多, 比如說同態性質使得行列式能夠被有效地計算; 而積和式在計算上的困難有些出人意料, 這一問題甚至是 $mathsf{#P}$ -complete 的 (至少和 $mathsf{NP}$ -complete 一樣困難), 於是對積和式的刻畫也使得我們能夠對計數複雜性類 $mathsf{#P}$ 有更多地了解. 除此之外, 行列式和積和式也被用於描述量子力學中的全同粒子 (idential particles), 下面會從不同方面簡單的介紹積和式及其聯繫.

計數複雜性類: 計算積和式有多難

通常在第一學期的線性代數課程中會介紹行列式 (determinant), 我們可以用 Laplace expansion 導出其定義: 給定一個 $n imes n$ 矩陣 $Ain mathbb{R}^{n imes n}$ , 那麼行列式為 $Det(A) = sum_{sigmain S_n} (-1)^{sgn(sigma)} prod_{i=1}^n a_{i,sigma(i)},$ 這裡的 $S_n$ 是置換群, 裡面的每個置換 (permutation) 都是其中的元素. 長的置換可以由短的置換合成, 顯然最短的置換長度為 $2$ , 那麼 $sgn(sigma)$ 表示的是置換 $sigma$ 需要奇數 (或偶數) 個 $2$ -置換合成. 類似地, 我們也可以定義積和式

$Per(A)=sum_{sigmain S_n} prod_{i=1}^n a_{i,sigma(i)}.$

儘管它們都是對置換群中的所有置換求和, 但是使用了置換奇偶性的行列式的性質要好得多: 行列式有同態 (homomorphism) 性質 $Det(AB)=Det(A)Det(B)$ , 那麼一次 LU 分解足以完成行列式求值. 這意味著一個令人驚訝的事實: 儘管看起來我們需要對指數多項求值, 但是行列式求值有多項式時間演算法!

事實上我們知道 $mathsf{Determinant} in mathsf{NC}^2subseteq mathsf{P}$ , 即行列式求值可以由深度為 $O(log^2 n)$ 的布爾線路 (Boolean circuit) 在時間 $O(log^2 n)$ 內完成. 但是對於積和式, 由於沒有同構性質, 我們必須對指數多項求和 -- 即使是已知的最好的經典演算法, 積和式的精確計算的時間複雜度仍然需要 $O(n2^n)$ . 不過這事也不絕對, 如果把積和式求值限制在有限域 $mathbb{F}_2$ 上, 多項式時間演算法顯然是存在的 -- 因為這時候積和式和行列式等價. 事實上實數域上的 $0$ - $1$ 積和式求值, 在 1979 年被 Leslie Valiant 證明是 $mathsf{#P}$ -complete 的; 而 1991 年的 Toda 定理 $mathsf{PH} subseteq mathsf{P}^{mathsf{#P}}$ , 則告訴我們計數複雜性類 $mathsf{#P}$ 比我們想像中大得多, 因而積和式求值也是一個比看起來困難的多的問題.

計數複雜性類 $mathsf{#P}$ 說的是這麼一件事: 我們知道 $mathsf{NP}$ 說的是至少存在問題的"一個解" (witness), 能夠在多項式時間內被 (確定性 Turing 機) 驗證; 而 # 即數數 (number), 所以 $mathsf{#P}$ 說的則是這樣的"解"到底有多少個? 自然地, 我們從定義中知道 $mathsf{#SAT}$ 是 $mathsf{#P}$ 天然的完全 ( $mathsf{#P}$ -complete) 問題. 那麼如何證明這一結果呢? Valiant 從給定的 $mathsf{SAT}$ 實例 (instance) 出發, 利用變數 (variable) 和子句 (clause) 的關係構造了一個圖, 然後考慮這個圖的不相交圈覆蓋 (cycle cover) 的個數 -- 可以證明它正比於這個圖的鄰接矩陣的行列式, 從而得到 $0$ - $1$ 積和式求值是 $mathsf{#P}$ -complete 的. 需要說明的是, 這一工作是 Leslie Valiant 在 2010 年榮膺 Turing Award 的三篇文獻之一.

用積和式描述全同粒子

積和式並不是一個憑空出現的東西, 至少在量子力學裡不是. 直覺上來說, 玻色子和費米子最大的不同之處在於, 玻色子會"扎堆", 而費米子會遵從 Pauli 不相容原理. 回到量子力學中的全同粒子 (identical particle) 公設, 用於交換序號的算符 $hat{P}$ 的本徵態對於對稱態和非對稱態來說是不一樣的 (不考慮它們之間的相互作用), 這樣的做法被稱為一次量子化 (之所以這麼叫是因為二次量子化, 不過這裡有那麼點歷史包袱的意味). 具體來說, 非對稱態加了個因子來表示置換的奇偶性 (想想上一節的置換群 $S_n$ ). 這裡的對稱態對應的玻色子, 非對稱態對應的是費米子, 兩者的統計性質不同.

那麼我們可以從單粒子波函數來構造全同粒子波函數, 遍歷所有 $P$ 意味著遍歷所有排列.

對於玻色子, 我們有 $ilde{psi_S} = sum_{P} hat{P} psi_{k_1} (g_1) psi_{k_2} (g_2) cdots psi_{k_N} (g_N);$
而對於費米子, 則是 $ilde{psi_A} = sum_{P} (-1)^{sgn(P)} hat{P} psi_{k_1} (g_1) psi_{k_2} (g_2) cdots psi_{k_N} (g_N).$

回憶一下上一節的積和式和行列式定義, 不難發現玻色子情形對應積和式, 而費米子情形對應行列式 (稱為 Slater determinant). 注意到行列式有個性質, 如果兩行(或列)一樣的話, 那麼行列式值為零 -- 這意味著 Pauli 不相容原理.

關於積和式和行列式還有個段子, 來自 Scott Aaronson[2]:

搬到 Austin 的 Aaronson 發現在 Steven Weinberg 的量子力學教材上, 上面倆式子都叫 Determinant. 於是他就問 Weinberg, 你是不是不知道這東西叫 Permanent, Weinberg 表示我當然知道, 但是我得假設別人不知道, 畢竟對物理學家來說這就是個式子.

眾所周知, 玻色子的典型例子是光子, 而費米子的典型例子是電子. 既然光子如此司空見慣 (雖然積和式求值難如 $mathsf{#P}$ -complete), 這裡會不會有什麼新的想法來幫助我們計算積和式, 或者理解計數複雜性類 $mathsf{#P}$ 呢?

計算優越性: 玻色採樣與積和式求值

到此為止, 我們知道作為全同粒子的光子, 實際上可以看成不可區分的球, 那麼我們就回到了組合中常見的球和桶的模型. 於是 Scott Aaronson 師徒提出的玻色採樣 (Boson Sampling)[3] 說的是這麼件事, 假設你手上有 $n$ 個不可區分的球, 你需要把它們扔進 $m$ 個不同的桶里 (你技術很好不會扔到桶外面), 那麼球最終在桶里的排布會是什麼樣的?

這裡的 $n$ 個球就是光子, $m$ 個桶則是模 (mode); 並且球是不可區分的, 而桶是可區分的. 當然扔球的過程和線性光學的實驗設備有關, 具體什麼樣嘛可以看看這個網頁遊戲. 我們可以把這個問題數學化如下, 這裡的實驗設備由扔球矩陣 $A$ 刻畫.

什麼是玻色採樣

問題的輸入是不可區分球個數 $n$ , 和可區分桶個數 $m$ ; 以及扔球矩陣 $A_{mn}$ 和想要的球排布 $S = (s_1,cdots,s_m) in Phi_{m,n}$ , 其中 $sum_{i=1}^m s_i = n$ . 扔球矩陣 $A$ 形式如下, $A=egin{pmatrix} U_{11} & cdots & U_{1n}\ vdots & ddots & vdots\ U_{m1} & cdots & U_{mn}\ end{pmatrix}.$

如果我們把扔球矩陣 $A$ 的第 $i$ 行重複 $s_i$ 次, 那麼我們可以得到一個綜合了球排布和扔球矩陣的新扔球矩陣 $A_S$ , 形式如下 ( $n imes n$ 矩陣): $A_S=egin{pmatrix} U_{11} & cdots & U_{1n} & cdots & U_{1m}\ vdots & ddots & vdots & ddots & vdots\ U_{m1} & cdots & U_{mn} & cdots & U_{mm}\ end{pmatrix}$

問題的輸出是球排布 $S$ 出現的概率, 即佔據數表象 (occupation-number representation) 下的波函數 $mathrm{Pr}[S]=frac{1}{s_1!cdots s_m!} langle s_1,cdots,s_m|A_S|0,cdots,0 angle = frac{|Per(A_S)|^2}{s_1!cdots s_m!}.$ 為什麼上面會涉及積和式呢? 分母很好理解, 因為我們的球是不可區分的. 對於分子, 積和式 $Per(A_S)$ 中的每一項都對應著某種球置換 (ball permutation), 符合給定的球分布意味著所有"桶"里都必須有球 (因為允許空桶, 所以這裡又加了 $m$ 個球), 於是球排布 $S$ 出現的概率正比於新扔球矩陣 $A_S$ 的積和式的值.

線性光學: KLM 定理

Aaronson-Arkhipov[3] 說的是, 如果存在求解上述玻色採樣問題的有效經典(近似)演算法, 那麼會導致意想不到的計算複雜性後果 -- 我們相信這樣的後果不可能出現, 就跟我們相信 $mathsf{P} eq mathsf{NP}$ 一樣.

展開說的話, 我們知道線性光學中量子計算並不是通用 (universal) 的, 因為某些量子門無法實現. 而在 2000 年, Knill, Laflamme 和 Milburn 指出[5], 如果允許延遲選擇 (post-selection) 操作的話, 那麼線性光學量子計算是 universal 的, 這一結果稱為 KLM 定理. 即給定量子線路 $Q$ , 其中 CSIGN 門 (控制相位門) 個數為 $Gamma$ , 並且 $|I angle = |0,1,cdots,0,1 angle$ , 有下述結果 $langle I|phi(L)|I angle =frac{1}{4^{Gamma}} langle 0cdots0 | Q | 0cdots 0 angle,$ 其中 $phi(L)$ 是線性光學中對應的量子門, 具體做法如下:

用線性光學態表示量子態, 即用一個光子和兩個模來 (一個球和兩個桶) 表示一個量子比特 (稱為 Dual-rail encoding),比如 $|0 angle ightarrow |1,0 angle, |1 angle ightarrow |0,1 angle.$
單量子比特門可以直接實現.
CSIGN 門實現如下, 進行對 $2$ -模延遲選擇, 使得下述約束 (共有 $4 imes 4=16$ 個) 成立: $langle 0,1|phi(L)|0,1 angle = 1 Leftrightarrow langle 1,0,0,1 |phi(L)| 1,0,0,1 angle = frac{1}{4}.$

我們知道單量子比特門加上一個兩量子比特門可以實現通用 (universal) 量子計算. 需要說明的是, 實際中的延遲選擇和 $mathsf{PostBQP}$ 中的延遲選擇並不相同, 因為我們假設後者的延遲選擇發生概率大於 $1/2$ (遠遠大於實驗中的 $1/2^n$ ), 所以後者的計算能力要強於通用量子計算機 (即 $mathsf{BQP} subseteq mathsf{PostBQP} = mathsf{PP}$ ).

需要說明的是, 被用以顯示量子計算優越性的玻色採樣並不是 $mathsf{#P}$ -hard 的, 《科技導報》上的某實驗組的科普對此的陳述並不準確 -- 因為實際上 Aaronson-Arkhipov 給出的是近似採樣問題. 事實上, 如果把積和式近似計算的參數放寬的話, 我們甚至可以得到 quasi-polynomial time 的演算法, 見 Eldar 和 Mehraban 在去年的工作 [10].

如果讀者對 $mathsf{BQP}$ 稍有了解的話, 也很容易看出上述論題並不正確: 上世紀末我們就已經證明了 $mathsf{BQP}subseteq mathsf{PP}subseteq mathsf{#P}$ ; 那麼如果量子計算機能夠在多項式時間內精確計算玻色採樣, 即 $mathsf{#P}subseteq mathsf{BQP}$ 的話, 可以導出 $mathsf{BQP}=mathsf{#P}=mathsf{PP}=mathsf{PostBQP}$ , 那麼實驗中的延遲選擇發生概率應該是 $1/2$ 而不是 $1/2^n$ -- 這和現實矛盾.

玻色採樣的計算優越性

玻色採樣所討論的採樣問題, 準確地說是用非通用量子計算機 (線性光學量子計算) 來進行採樣, 對上述 KLM 定理稍加改進, 那麼對應的計算複雜性類是 $mathsf{PosBQP}$ . 類似地, 如果我們對經典計算機 (這裡討論的是隨機演算法) 也允許延遲選擇操作的話, 對應的計算複雜性類是 $mathsf{PostBPP}$ . 這裡的計算優越性是因為, 如果允許延遲選擇操作後, 量子情形相對經典情形沒有優勢 (即 $mathsf{PostBPP} = mathsf{PostBQP}$ ) 的話, 那麼 $mathsf{PH}$ 塌縮到第三層: $mathsf{PH} subseteq mathsf{P}^{mathsf{#P}} = mathsf{P}^{mathsf{PostBQP}} =mathsf{P}^{mathsf{PostBPP}}subseteq Delta_3$ 第一個包含關係是著名的 Toda 定理, 第二個則是 Aaronson 的工作, 第三個這裡關於計算優越性的假設, 最後一個則是 Sipser-Gacs 定理. 關於 $mathsf{PH}$ 的介紹和上述關係的更多介紹參見 Adam Bouland 在 It from Qubit Summer School 上的 talk[4].

關於量子計算優越性 (quantum computational supremacy) 的更多介紹, 參見 Aram Harrow 和 Ashley Montanaro 的科普[6]. 多說幾句, 上述計算複雜性理論中的假設 (比如 $mathsf{PH}$ 不會塌縮, 即 $mathsf{P} eq mathsf{NP}$ 的一般化版本) 只是可能的假設 (assumptions) 之一, 除此之外還有

Fine-grained complexity (細粒化複雜性?): 即把 $mathsf{SAT}$ 規約到某個問題上, 那麼如果這個問題存在足夠快 (比如說好於平方時間) 的多項式時間(經典)演算法, 則會違背 exponential time hypothesis (ETH); 如果我們找到了好於上述 bound 的量子演算法, 那麼這裡同樣有計算優越性.
Average-case assumptions (平均情形): 這裡關注平均情形下的 hardness. 比如說一個函數 $f$ 在某個分布 $D$ 上難以計算, 這意味著如果這裡沒有有效地經典演算法, 能夠對於從 $D$ 中採樣得到的大部分 $x$ 輸出 $f(x)$ . 最出名的例子應該是random circuit sampling.

需要說明的是, 體現計算優越性也可以不需要任何假設: 對於常數深度量子線路, Bravyi, Gosset 和 Koenig 給出了一個非常美妙的結果[7] (QIP 2018 plenary talk): 存在某個問題可以用常數深度 (constant-depth) 量子線路求解, 但是在經典情形下的則需要對數深度 (logarithmic depth) 概率線路 (probabilistic circuit), 這裡不再展開.

經典定理的量子證明: 線性光學與新的規約技術

其實積和式和玻色採樣還有一些時間上的巧合: 在關於玻色採樣的工作被 STOC 2011 接收的兩個月後, Leslie Valiant 就被宣布獲得 2010 年的 Turing Award -- 而 Aaronson 的積和式計算是 $mathsf{#P}$ -complete 的證明一文更是簡單直白, 為紀念 Valiant 的 Turing Award 而作.

Aaronson 的證明[8]給出了完全不同於 Valiant 的 $mathsf{#P}$ -completness 規約方式, 那麼這樣的藉助線性光學量子計算的新技術. 能否告訴我們關於積和式和計數複雜性的更多結果呢? Grier 和 Schaeffer 給出了肯定答案[1], 他們證明了 $GL(n)$ , $O(n)$ , $U(n)$ , $Sp(2n)$ 上的矩陣對應的積和式計算仍然是 $mathsf{#P}$ -complete 的:

對於特徵為 $p$ 的有限域 $mathbb{F}_p$ ( $p eq 2, 3$ ), 其上的矩陣的積和式的計算是 $mathsf{Mod_pP}$ -hard 的.

需要說明的是, 這裡的 $mathsf{Mod_pP}$ 也是計數複雜性類, 不過需要模 $p$ . 除此之外, 上述結果實際上是"二分 (dichotomy) 定理". 因為 $p=2$ 是行列式和積和式等價, $p=3$ 時有非平凡的經典演算法 (Kogan 1996)[9]. 下面簡單介紹如何用基於線性光學量子計算的規約技術, 證明酉矩陣的積和式計算是 $mathsf{#P}$ -complete 的.

證明路線和預處理

Aaronson 的證明[8]中討論的問題如下:

輸入: 給定的布爾函數 (Boolean function) $C:{0,1}^n ightarrow {0,1}$ .
輸出: $Delta C := sum_{xin{0,1}^n (-1)^{C(x)}}$ , 可以驗證 $Delta C/2^n=langle 0cdots 0|Q|0cdots 0 angle$ .

為了證明積和式的計算是 $mathsf{#P}$ 的, 我們需要把輸入實例 (instance) $C$ 設法規約到積和式上, 即導出 $Delta C propto Per(L_{I,I})$ . 中間過程需要藉助線性光學量子計算, 證明的大致路線如下:

把 $Delta C$ 編碼到量子線路 $Q$ 上, 得到 $langle 0cdots 0|Q|0cdots 0 angle$ .
把量子線路 $Q$ 對應到光學網路 (optic network) $L$ 上.
最終得到積和式和線性光學量子計算的對應關係, 即

$Delta C propto langle 0cdots 0|Q|0cdots 0 angle propto langle 1,0,cdots 1,0| phi(L)|1,0, cdots 1,0 angle propto Per(L_{I,I}).$

首先需要做的是把 $Delta C$ 用量子線路和量子比特編碼, 使用的量子線路 $Q$ 如下:

編碼過程, 圖片來自[1]

上述過程實際上就是量子 Fourier 變換, 展開來說的話: 我們知道 $H^{otimes n}$ 可以把真空態 $|0 angle^{otimes n}$ 變成 computational basis 的均勻疊加 $frac{1}{2^{n/2}}sum_{x in{0,1}^n} |x angle$ . 而 $Z$ 門的作用則是提取出 ${|+ angle,|- angle}$ 中的符號, 即對於 $|- angle = frac{1}{sqrt{2}}(|0 angle+|1 angle)$ , 我們有 $Z |- angle = -|- angle = (-1)^1 |- angle$ . 於是不難得到

$egin{aligned} langle 0cdots 0|Q|0cdots 0 angle &= frac{1}{2^n} left( sum_{xin {0,1}^n} langle x|langle -| ight) C left( sum_{xin {0,1}^n} |x angle |- angle ight)\ &= frac{1}{2^n} sum_{xin{0,1}^n} (-1)^{C(x)} = frac{Delta C}{2^n}, end{aligned}$

即我們成功地把布爾線路 $C$ 編碼到幾率幅 $langle 0cdots 0|Q|0cdots 0 angle$ 上.

從線性光學到量子線路

首先回顧一下線性光學中量子態如何表示: $n$ 個光子和 $m$ 個模, 可以看成 $n$ 個不可區分的球和 $m$ 個可區分的桶, 在佔據數表象下我們有 $|s_1,cdots,s_m angle$ , 即有 $s_k$ 個光子在第 $k$ 個模上. 不難驗證 Hilbert 空間的維度 $|mathcal{H}| = inom{n+m-1}{m-1} = inom{n+m-1}{n}$ , 因為球在桶中 (允許空桶) 的不同排布有 $|mathcal{H}|$ 中.

那麼線性光學中的量子門是什麼樣的呢? 比如 Hadamard 門可以看成兩個發射器一上一下自左向右平行發射了兩個小球, 然後中間某一裝置會把小球扔向右側上方或下方的接收器, 往哪扔球的概率取決於 $H$ (所以前文稱作"扔球矩陣"). 令 $phi(L)=H$ 的話, 不難得到 $egin{aligned} phi(L)|1,0 angle &= frac{1}{sqrt{2}}(|1,0 angle+|0,1 angle)\ phi(L)|1,1 angle &= frac{1}{sqrt{2}}(|2,0 angle-|0,2 angle)\ end{aligned}$

不難發現, 這裡的量子門的事情就是數數 (counting). 於是不難定義 $phi$ -變換如下:

給定量子態 $|S angle = |s_1,cdots,s_m angle$ 和 $|T angle = |t_1,cdots,t_m angle$ , 那麼對於光學網路 $L$ 有 $langle T|phi(L)|S angle = frac{Per(L_{S,T})}{sqrt{s_1!cdots s_m!t_1!cdots t_m!}},$ 其中 $L_{S,T}$ 去取決於光學網路 $L$ 和光子排布 $S,T$ , 即 $s_i$ 表示 $L$ 的第 $i$ 行重複 $s_i$ 次, $t_i$ 表示 $L$ 的第 $i$ 列重複 $t_i$ 次. 容易觀察, 令 $|S angle = |T angle = |I angle = |1,cdots,1 angle$ 的話, 可以得到 $langle T|phi(L)|S angle = Per(L)$ .

因而, 在允許延遲選擇 (post-selection) 操作後, 藉助上一節提及的 KLM 定理[5], 我們可以得到 Aaronson 證明中的下述定理[8]: $frac{Delta C}{2^n} = langle 0cdots 0|Q|0cdots 0 angle = 4^{Gamma} langle I|phi(L)|I angle = 4^{Gamma} Per(L_{I,I}).$ 這裡的 $Gamma$ 是量子線路 $Q$ 中兩比特門 CSIGN 門的個數. 看起來藉助線性光學量子計算, 我們幾乎得到了積和式是 $mathsf{#P}$ -complete 的新證明. 不過這裡有個問題, 矩陣 $L_{I,I}$ 並不是酉矩陣. 如果我們想把結論進一步加強到對於某一類矩陣 (比如酉矩陣, 正交矩陣, 可逆矩陣等等), 應該怎麼做呢?

如何處理酉矩陣

為了證明酉矩陣的積和式計算是 $mathsf{#P}$ -complete 的, 我們需要給 KLM 定理再增加一次編解碼過程, 然後使用 KLM 定理進行規約. 具體來說, 對於單量子比特 $|1,1,1,1 angle ightarrow |0,1,2,1 angle ightarrow |1,1,1,1 angle,$ 中間這項即是用編碼矩陣 $E$ 編碼後的新的模, 其中前兩個模仍使用 dual-rail encoding, 第三個模是剩餘的光子, 最後一個模則供延遲選擇 (post-selection) 操作使用.

Grier-Schaeffer 的工作給出了編碼矩陣 $E$ 對於特定類型矩陣的存在性, 可以通過求解一系列線性方程組得到; 而 CISGN 門也可以同類似方法得到, 均為域 $mathbb{Q}(alpha), alpha=sqrt{2+sqrt{2}}+sqrt{3+sqrt{6}}$ 上的矩陣. 於是我們最終得到了下述定理:

給定 $n$ -qubit 量子線路 $Q$ , 其中 CSIGN 門個數為 $Gamma$ . 可以構造相應的 $4n+2Gamma$ 個模上的線性光學線路, 其中 $L$ 是酉矩陣, 滿足下式 $frac{Delta C}{2^n} = langle 0cdots 0|Q|0cdots 0 angle = (-sqrt{6})^n(3sqrt{2/3})^{Gamma}langle 1,cdots,1|phi(L) |1,cdots, 1 angle propto Per(L_{I,I}).$

從而最終證明了酉矩陣的積和式計算是 $mathsf{#P}$ -complete 的, 基於線性光學量子計算的這一技術可以推廣到其他矩陣, 甚至積和式計算的近似情形. 完整證明見 Grier-Schaefer 的工作[1], 限於筆者能力, 這裡不再展開.

參考文獻

[1]:[1610.04670] New Hardness Results for the Permanent Using Linear Optics

[2]:IAS 的 video archive和Scott 的 script.

[3]:[1011.3245] The Computational Complexity of Linear Optics

[4]: It from Qubits Summer School 上 Adam Bouland 的 talk (Perimeter Institute Recorded Seminar Archive)

[5]:[quant-ph/0006088] Efficient Linear Optics Quantum Computation

[6]:Harrow, Aram W., and Ashley Montanaro. "Quantum computational supremacy." Nature 549.7671 (2017): 203.

[7]:[1704.00690] Quantum advantage with shallow circuits

[8]:[1109.1674] A Linear-Optical Proof that the Permanent is #P-hard

[9]: Kogan, Grigory. "Computing permanents over fields of characteristic 3: Where and why it becomes difficult." Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on. IEEE, 1996.

[10]: [1711.09457] Approximating the Permanent of a Random Matrix with Vanishing Mean