量子程式設計基礎
Foundations of Quantum Programming
應明生（Mingsheng Ying） 著
張鑫向、宏傅鹂、向濤 譯
第1章 引言和預備知識
量子軟體工程的挑戰在于如何對傳統的軟體工程進行重新設計和擴充，使得程式員可以像操縱傳統程式一樣對量子程式進行操縱。
--Grand Challenges in Computing Research (2004)
量子程式設計主要研究如何在未來的量子計算機上程式設計，包括下面兩個問題：
- 現有的程式設計方法和技術如何擴充到量子計算機上？
- 什麼樣的程式設計方法和技術可以有效利用量子計算的特有能力？
因為量子系統中存在奇異的特征，如量子資訊的不可克隆性、量子程序之間的糾纏、觀測結果不可交換等均深植于程式變量之中，是以許多在傳統計算機程式設計領域取得極大成功的技術難以遷移到量子計算機上。更重要也更具挑戰性的問題是：如何尋找抽象的程式設計範式和編 程模型等才能最大化地利用量子計算的特有能力——并行性？這個問題并不能從傳統的程式設計經驗中獲得啟示。
1.1量子程式設計研究簡史
量子程式設計的概念最早是Knill在1996年提出的。他設計了量子随機通路機；(QRAM)模型，并提出一系列編寫量子僞代碼的規定。在接下來的20年中，量子程式設計的研究繼續如火如荼地進行，主要包括以下幾個方向。
1.1.1量子程式設計語言的設計
早期研究主要集中在量子程式設計語言的設計方面。20世紀90年代末和21世紀初，有幾種進階量子程式設計語言被設計出來。例如，Omer設計了第一個量子程式設計語言QCL,此外,他還實作了該語言的模拟器。Sanders和Zuliani基于Dijkstra衛式指令語言提出了量子程式設計語言qGCLo。Bettelli等人對C++進行了擴充，并實作了一個用于量子程式設計的C++庫。将經典程式控制流與量子資料相結合，Selinger定義了第一個函數式量子程式設計語言QPL。随後，Altenkirch和Grattage回 引入量子控制流設計了量子函數式程式設計語言 QML。Tafliovich和Hehner對一種謂詞程式設計語言進行了量子化的擴充，該擴充語言可以為這樣的程式開發技術提供支援，即用它開發出來的程式所執行的每一步都可以被證明是正确的。
最近，Green等人和Abhari等人分别設計了兩個通用的、可擴充的量子程式設計語言Quipper和Scaffold,并開發了它們的編譯器。Lapets等人設計了領域專用的量子程式設計語言QuaFL。除此之外，Wecker和Svore開發了量子軟體體系結構LIQUi|），并提供了内置于F#的量子程式設計語言。
1.1.2量子程式設計語言的語義
程式設計語言的形式語義是對該語言的嚴格數學描述，以便能夠對該語言文法之下的本質有精确而深刻的了解。一些量子程式設計語言的操作語義或指稱語義在定義的時候就已經提供了，比如 qGCL、QPL和QML。
人們提出了兩種量子程式謂詞轉換語義的思路。第一種是Sanders和Zuliani在設計qGCL的時候提出的：通過觀測（測量）步驟，将量子計算歸約為機率計算，這樣為機率程式開發的謂詞轉換語義就可以移植到量子程式中來。第二種是DHondt和Panangaden設計的，它将量子謂詞定義為由特征值所屬機關區間内的厄米算子所表示的實體可觀測量。針對一類稱為投影算子的特殊量子謂詞，文獻［225］對量子謂詞轉換語義做了進一步研究。人們将注意力集中于投影謂詞，是因為它允許使用Bitkhoff-von Neumann量子邏輯中豐富的數學工具去建立各種量子程式的健壯性條件。
人們還對一些量子計算的技術進行了研究，這些技術往往是抽象的，與具體的程式設計語言無關。Abramsky和Coeck提出了一種基于量子力學基本假設的範疇論公式，我們可以用它來對量子程式和通信協定（比如隐形傳态）進行優美的描述。
該領域近來的進展如下。基于Girard發明的，并由AbramskyHaghverdi和Scott 進一步範式化的互動幾何，Hasuo和Hoshino提出了一種包含遞歸的函數式量子程式設計語義模型。Pagani. Selinger和Valiron為這種函數式程式設計語言設計了一種指稱語義，這類量子程式設計語言帶有遞歸特性，以及根據線性邏輯量化語義構造出來的無限資料類型。Jacobs對量子程式設計中的塊狀結構進行了範疇式的公理化描述。Staton提出了一種可以對量子程式進行公式化推理的代數語義架構。
1.1.3量子程式的驗證和分析
與量子世界相比，人類的直覺感受與經典世界更加契合。而這恰恰意味着，相比在經典 計算機上進行程式設計，人們在量子計算機上進行程式設計可能會出現更多的錯誤。是以，對量子程式的驗證技術進行研究至關重要。Baltag和Smets的對量子系統中的資訊流進行了動态邏輯的形式化描述。Brunet和Jorrand介紹了一種使用Bitkhoff-von Neumann量子邏輯對量子程式進行推理的方法。Chadha、Mateus和Sernadas提出一種Floyd-Hoare體系的證明系統來對那些隻允許邊界疊代的指令式量子系統進行推理。Feng等人提出了一些有用的證明法則用于對純粹的量子程式進行推理。文獻［221］開發了滿足完備性的量子程式中局部和整體正确性的Floyd-Hoare邏輯。
在實作和優化程式的過程中，程式分析技術非常有用。文獻［227］率先對量子程式終止性分析進行了研究，它研究了以幺正變換作為循環體的基于測量的量子循環。文獻［234］使用量子馬爾可夫鍊的語義模型對一般性量子循環的可終止性進行了研究。文獻［234］也證明了，可以通過量子态和可觀測量之間的Schr6dinger-Heisenberg對偶性将證明機率性程式屬性的Sharir-Pnueli-Hart方法進行擴充，使其在量子程式中也同樣适用。這一研究思路在文獻［152-153,235-236,238］中得以延續，它們均基于量子馬爾可夫決策過程的可達性分析對不确定性和并發性量子程式的可終止性進行了研究。Jorrand和Perdrix提出了另一類量子程式分析技術，他們揭示了如何将抽象解釋技術應用到量子程式中。
1.2量子程式設計的方法
很自然地，對量子程式設計的研究是從将經典程式設計模型、方法和技術擴充到量子領域開始的。正如1.1節所述，相關研究人員已經設計了指令式和函數式量子程式設計語言，并對許多經典程式的語義模型、驗證和分析技術進行了擴充，使其可以适用于量子程式設計。
量子程式設計的最終目的是最大限度地發揮量子計算機的計算能力。相較于現有的計算機, 量子計算機的主要優勢來源于它的并行性——量子疊加态，以及由此衍生出來的諸如量子糾纏的概念。是以，量子程式設計中的一個關鍵問題就是如何将量子并行性的優勢與現有的傳統程式設計模型進行結合。在我看來，可以通過如下兩種疊加範式來解決這個問題。
1.2.1資料疊加——帶經典控制的量子程式
資料疊加範式的主要思路是引入一類可以操控量子資料的程式結構，比如幺正變換、量子測量等。但是，使用這類範式的量子程式的控制流與經典程式設計中的控制流非常相似。舉例來說,在經典程式設計中，一般用于定義控制流的基本程式結構是條件語句(if…then . . • else - .fi), 或者更具一般性的case語句：
對于任意的2,子程式Pi由布爾表達式Gi所控制，且隻有當e是true的時候才會執行 Pi.對公式(1.1)的一個很自然的量子化擴充是基于測量的case語句：
其中q是量子變量，M是對q進行的測量操作，mi,••• ,mn是測量M所有可能的結果。 對于任意的i, Pi都是一個量子子程式。該語句會根據測量M的結果選擇一條指令去執行: 如果輸出是血分，那麼會執行相應的程式因為是根據經典資訊 —— 量子測量的結果來 選擇需要執行的程式的，是以我們将上述過程稱為使用經典控制的量子程式設計。是以，可以基于這類case語句對量子程式設計中其他的程式結構(比如循環和遞歸)的控制流進行定義。
因為輸入的資料和程式計算的都是量子資料，即資料疊加，但程式本身不允許疊加，是以我們将上述程式設計範式稱為資料疊加範式。因為程式中的資料流是量子的，但是控制流仍然 是經典的，是以Selinger将這類範式精準地描述為“量子資料，經典控制”。
目前關于量子程式設計的主要研究方向是資料疊加範式，該範式使用經典控制流對量子程式設計進行處理。
1.2.2程式疊加——帶量子控制的量子程式
受量子遊走的結構啟發，人們發現還可以用一類在本質上與資料疊加範式完全不同的方法定義量子程式設計中的case語句 —— 由量子“硬币"控制的量子case語句：
其中
是外部“硬币”系統c的狀态希爾伯特空間的一組标準正交基，根據“硬币”空間
的基态來選擇子程式Pi去執行。因為态是可以疊加的，是以這是量子資訊而非經典資訊。 此外，我們可以定義量子選擇：
直覺上而言，量子選擇(1.4)通過“擲硬币”程式C構造子程式3, • • •,耳的執行路徑的疊 加态，然後再執行量子case語句。在量子case語句的執行過程中，每一個子程式Pi都在自 己的執行路徑上獨立運作，且它們各自的執行路徑都包含于Pi,・・・R 所組成的疊加态中。 我們可以基于這類量子case語句和量子選擇對一些新的量子程式結構進行定義，比如量子遞歸。
我們将這類量子程式設計方法稱為程式疊加範式。從量子case語句和量子選擇中可以發現，程式疊加範式中的控制流具有天然的量子特性。是以，可以将這類範式描述為“量子資料，量子控制”。
必須承認，這種範式還處于發展的初級階段，還有一系列基礎性的問題沒有解決。但另一方面，我堅信這種範式引入了一種新的考慮量子程式設計的方法，這種方法可以幫助程式員進 一步開拓量子計算強大的計算能力。
1.3全書結構
這本書以從資料疊加到量子疊加為線索，對量子程式設計理論基礎進行了系統的論述。本書主要介紹指令式函數程式設計，但是大多數的觀點和技術也同樣可以推廣到函數式量子程式設計中。
本書分為以下四個部分：
- 第一部分包括本章和第2章(預備知識)。閱讀本書首先需要對量子力學、量子計算 和程式設計語言有大緻的了解。第2章對量子力學和量子計算所需的基礎知識進行了介 紹。至于程式設計語言理論，建議讀者查閱标準教科書，[21,158,162,200]。
- 第二部分研究資料疊加範式中帶經典控制的量子程式，共分為三章。第3章詳細地介紹了帶經典控制（條件語句、循環和遞歸）的量子程式的文法、操作語義和指稱語義。第4章介紹了對帶經典控制的量子程式的正确性進行推理論證的邏輯基礎。第5章設計了一系列用于分析帶經典控制的量子程式的數學工具和算法技術。
- 第三部分研究程式疊加範式中帶量子控制的量子程式，分為兩章。第6章定義了量 子case語句和量子選擇及其語義，并建立了一套可以對包含量子case語句和量子選 擇在内的量子程式進行推理的代數法則。第7章舉例說明了如何使用量子case語句 和量子選擇來定義帶量子控制的遞歸。此外，還通過二次量子化（即一類處理可能包含不同數量粒子的量子系統的數學架構）對這類遞歸的語義進行了定義。
- 第四部分由獨立的一章組成，列舉了幾個在量子程式設計方面很重要卻沒有在上述部分提及的問題，并指出下一步計劃研究的幾個方向。
- 關于閱讀本書：從圖1.1中，我們發現可以通過以下三種路徑完成對本書的閱讀：
- 路徑1：第2章-第3章一第4章。這條路徑針對對量子程式的邏輯感興趣的讀者。
- 路徑2：第2章-第3章一第5章。這條路徑針對對量子程式的分析感興趣的 讀者。
- 路徑3：第2章一第3章一第6章一第7章。這條路徑針對想要學習資料疊加 範式和程式疊加範式的量子程式結構的讀者。
當然，從頭到尾讀完本書，讀者才能得到一幅關于量子程式設計的全景畫面。
- 教學建議：關于量子程式設計的短期課程可以基于第2章和第3章來進行教學。此外，本 書的第一部分和第二部分可以作為大學生或者研究所學生一個學期或者兩個學期的課程 内容。如果是一個學期的課程，那麼教學安排可以根據前面介紹的前兩條路徑之一進 行設計。因為帶量子控制的量子程式設計理論（程式疊加範式）仍處于發展的初級階段， 是以最好将第6章和第7章的内容作為研讨班的材料而非教學課程内容。
- 練習：本書中有一些引理和命題的證明留作練習。它們通常都不太難，通過完成這些 練習，讀者可以更好地了解相關内容。
- 研究問題：本書第二部分和第三部分每章的最後都會給出一些未來有待研究的問題。
- 文獻注解：第2章到第7章的最後一節都是文獻注解，給出了引用和參考文獻，并為 接下來的閱讀提供建議。本書最後提供了完整的參考文獻，包括按照首字母排序的引 用文獻和推薦閱讀書目的清單。
- 勘誤：我很樂意收到關于本書的任何意見和建議。如果你找到本書中的任何問題，請将這些錯誤資訊通過E-mail的形式發送給[email protected]或者yingmsh©tsinghua.edu.cn。