時間旅行的量子門

王粲 陸朝陽 陳明城?

1)(中國科學(xué)技術(shù)大學(xué)近代物理系,合肥微尺度物質(zhì)科學(xué)國家研究中心,合肥 230026)

2)(中國科學(xué)技術(shù)大學(xué),中國科學(xué)院量子信息與量子科技前沿卓越創(chuàng)新中心,上海 201315)

1 引言

計算是一個物理過程,計算過程和能力受到物理定律的限制[1].例如,擦除一個比特信息的操作受到熱力學(xué)限制,存在最小能耗[2].計算科學(xué)中,一個被廣泛接受的假設(shè)——擴展丘奇圖靈論題提出,所有物理上合理的計算過程都可以用通用圖靈機來有效替代[3],同時這也定義了經(jīng)典計算可以有效求解的問題類別,即P 問題[4].當(dāng)我們在計算過程中引入量子力學(xué)原理,通過量子疊加和量子干涉,量子計算可以有效求解P 問題之外的問題.例如,量子Shor 算法可以求解的大數(shù)分解被認為是非P 問題[5]; 量子采樣算法也被認為位于P 問題之外,并且在近期實驗工作中被實現(xiàn),展示了量子計算的優(yōu)越性[6–9].

量子計算是目前在物理原理內(nèi)已知的最強的計算范式[10].考慮到計算的能力受到物理原理的制約,同時很多重要問題類別,比如NP-complete問題[11],處在量子計算能有效求解的范圍之外,因此研究量子計算的進一步擴展是一個很有趣的基礎(chǔ)問題.

為了擴展量子計算,相對論物理相關(guān)的新奇操作是一類重要候選.其中閉合類時曲線概念引起了廣泛的興趣[12],它可以實現(xiàn)量子態(tài)沿著封閉的類時曲線傳輸.閉合類時曲線引入了時間旅行的能力,量子態(tài)的閉合類時曲線在數(shù)學(xué)上通過自洽性方程來定義[13],并在最近的實驗中得到模擬演示[14,15].和量子計算模型結(jié)合后,可以擴大量子計算的可求解問題類別[16].

相比于量子態(tài)的時間旅行,這里我們引入另一種基于量子門的時間旅行.首先通過量子門線路圖形語言來形象展示時間旅行的量子門,并介紹其如何物理地通過張量網(wǎng)絡(luò)模擬實現(xiàn),最后設(shè)計新的量子算法來求解NP-complete 問題,展示超越正統(tǒng)量子計算的能力.

2 擴展的量子計算機

2.1 時間旅行的量子操作門

量子計算的標(biāo)準(zhǔn)通用量子門線路模型是通過單量子比特門和雙量子比特CNOT 門來搭建,量子比特的狀態(tài)信息是從左往右逐步流動[10].其中雙量子比特門需要在對齊的同一個時間窗口上進行操作,如圖1(a)所示.而在圖1(b)中,展示了打破這種時間對齊的CNOT 門,并且同時展示了作用在一個量子比特的過去或未來的CNOT 門操作.我們把這種新奇的CNOT 門稱作進行了時間旅行的CNOT 門.

包含時間旅行量子門的門線路打破了量子信息的流動順序,因此無法在物理上直接實現(xiàn).通過將量子門線路解釋成張量網(wǎng)絡(luò),可以在無時間旅行能力的系統(tǒng)中等效地模擬實現(xiàn)這類門線路的輸出[17].如圖2 所示,我們在時間旅行門的拐角上引入兩個分支,作為一個新的輔助量子比特的輸入和輸出.如果將這個輔助量子比特初始化和投影測量到態(tài)上,同時在這之間,輔助比特和時間旅行CNOT 門的起點和終點位置的量子比特分別實現(xiàn)CZ 和CNOT 門,那么輔助量子比特之外的輸出就等效于包含時間旅行量子門線路的輸出.

圖2 等效的張量網(wǎng)絡(luò)表示,借助輔助量子比特(藍色線)可以非確定性地模擬實現(xiàn)時間旅行CNOT 門 (a)示例1,在時間旅行門的兩個拐角,引入兩個分支,認作一個輔助量子比特(藍色線),將其初態(tài)制備到 |+〉態(tài)并同時后選擇投影到〈+| 態(tài),右圖是相應(yīng)的標(biāo)準(zhǔn)量子門線圖表示; (b)示例2,相比示例1 時間旅行門作用在同一個物理量子比特上,示例2 展示了其作用在不同物理量子比特上的情形Fig.2.Equivalent tensor network representation.Using auxiliary qubits (blue line),the implementation of a time-travelling CNOT gate can be nondeterministically simulated: (a) Example 1,where we introduce two branches at the two corners of the time-travelling gate and consider an auxiliary qubit (blue line) prepared in the |+〉 state and subsequently projected to the 〈+| state,the right diagram is the corresponding standard quantum circuit representation; (b) example 2,in contrast to example 1,demonstrates its operation on different physical qubits.

需要特別注意的是,我們所引入的時間旅行量子門是確定性的操作.而模擬實現(xiàn)的代價是借助輔助比特投影到,測量后選擇是概率性的.這是時間旅行打破物理原理的代價,在真實物理體系里只能是非確定性的實現(xiàn).

2.2 更強大的擴展量子算法

我們引入時間旅行量子門的目的是,通過盡可能小的自然的改動,來實現(xiàn)擴展的量子計算.下面將描述一個擴展算法,可以在多項式時間求解布爾可滿足性SAT 問題(Boolean satisfiability problem)[11].SAT 問題是計算機科學(xué)中的經(jīng)典問題,屬于NP-complete 類別.SAT 問題由n個布爾變量m個子句組成.求解該問題需要找出n個布爾變量的一組值使得m個布爾邏輯子句同時成立.

本文量子算法由三部分構(gòu)成.其中第一部分是n個量子比特的寄存器,用于存儲SAT 問題的布爾變量,初始化為 |0〉?n.第二部分是m個量子比特,用于標(biāo)記各個邏輯子句是否滿足,初始化為 |1〉?m.第三部分包含1 個標(biāo)記量子比特,初始化為 |1〉,用于標(biāo)記上面的m個子句是否全被滿足,如果全部滿足,就反轉(zhuǎn)該標(biāo)記比特.該部分的線路包含了時間旅行的CNOT 門,具體如圖3(a)所示.

圖3 求解SAT 問題 (a)設(shè)計的量子算法,門線路的深度線性正比于SAT 問題規(guī)模,即子句的數(shù)量 m,最上面n個量子比特作為SAT 問題解的寄存器,中間 m 個量子比特用于標(biāo)記 m 個邏輯子句是否被獨立滿足,最后一個量子比特標(biāo)記位用于判斷是否所有的邏輯子句被同時滿足; (b)最后標(biāo)記位上的時間旅行CNOT 門的運行細節(jié),這里 p 對應(yīng)張量網(wǎng)絡(luò)解釋中的后選擇概率,當(dāng)算法中的標(biāo)記位為 |1〉時,相應(yīng)的輔助量子比特的后選擇投影概率為0; 而標(biāo)記位為 |0〉時,后選擇投影概率為1,算法最終只輸出標(biāo)記位為 |0〉的情況,這對應(yīng)上面寄存器里只存儲了正確的解Fig.3.Solving the SAT problem.(a) The designed quantum algorithm,with the depth of the circuit linearly proportional to the SAT problem size,i.e.,the number of clauses m .The top n qubits serve as registers for solving the SAT problem,the middle m qubits are used to mark whether m logical clauses are independently satisfied,and the last qubits is used to determine whether all logical clauses are simultaneously satisfied.(b) Operational details of the time-travelling CNOT gate on the final marking qubit,here, p corresponds to the posterior-select probability in tensor network interpretation: When the marking qubit in the algorithm is |1〉,the corresponding auxiliary qubits have a posterior-select projection probability of 0;while the marking qubit is |0〉,the posterior-select projection probability is 1.The algorithm ultimately only outputs the case where the marking qubit is |0〉,corresponding to storing only the correct solutions in the registers above.

線路圖中,黃色的m個豎直框代表著多比特的受控NOT 門,由具體SAT 問題的各個子句具體內(nèi)容決定.如果一個子句沒有滿足,那就通過多比特的受控NOT 反轉(zhuǎn)對應(yīng)子句的量子比特.

算法運行時,布爾變量的寄存器通過哈德瑪門制備到所有可能的均勻疊加態(tài)上[10].第一種情況:如果寄存器里的布爾變量沒有滿足全部子句,標(biāo)記位將保持 |1〉,時間旅行CNOT 門執(zhí)行,通過上面介紹的張量網(wǎng)絡(luò)計算方法(如圖3(b)所示),時間旅行的成功概率p=0,實現(xiàn)了完美鎮(zhèn)壓寄存器里的錯誤解的概率幅.第二種情況: 如果寄存器里的布爾變量滿足全部子句,標(biāo)記位則被反轉(zhuǎn)成 |0〉,時間旅行CNOT 門沒有執(zhí)行,寄存器里的正確解不受影響.在張量網(wǎng)絡(luò)解釋中算法總的后選擇成功率為K/2n,K為SAT 問題滿足性解的個數(shù); 在時間旅行門的概念中,成功率為1.因此算法最后,布爾變量寄存器只確定性地保留了第二種情況的布爾變量組合,并隨后通過測量隨機塌縮輸出任意一個滿足所有子句的布爾變量組合.

該算法的復(fù)雜度正比于SAT 問題的規(guī)模,是線性復(fù)雜度的.門線路的深度正比于SAT 問題子句的數(shù)量.正統(tǒng)的量子計算可以有效求解的問題類別介于P 問題和NP 問題之間,這里設(shè)計的擴展量子算法有效求解了NP-complete 的SAT 問題.這也表明了在時間旅行量子門的參與下,計算復(fù)雜度類別P=NP,成功展示了時間旅行量子門具有超越正統(tǒng)量子計算的計算能力.

3 總結(jié)

計算機的能力受到物理定律的制約,量子計算機擴展了經(jīng)典計算機可有效計算問題的范圍.通過引入相對論時間旅行操作,相對論量子計算機可以在理論上進一步擴展量子計算的能力.在以往的工作中,時間旅行是通過閉合類時曲線實現(xiàn)的,多伊奇通過優(yōu)雅的自洽性方程將其結(jié)合到量子演化過程中.本工作通過量子門線路的圖形語言引入了自然的量子門的時間旅行擴展,并通過簡潔的算法示例展示了其對量子計算能力的顯著擴充.

本文介紹的張量網(wǎng)絡(luò)等效表示方法,為實驗?zāi)M提供了具體的實現(xiàn)方案.同時,也預(yù)期時間旅行的量子門在其他量子任務(wù)中也起到促進作用,包括實現(xiàn)確定性的非正交量子態(tài)甄別[18,19]、量子態(tài)克隆[20,21]等.