本書系統(tǒng)且全面地梳理了模型檢測量子系統(tǒng)的原理以及基于這些原理的算法,涵蓋作者相關論文中的重要研究成果。本書講解如何應用模型檢測技術來驗證量子工程系統(tǒng)的正確性、安全性和可靠性,包含步驟詳盡的算法以及豐富的示例和練習。書中首先介紹模型檢測和量子理論的基礎知識,然后討論量子自動機、量子馬爾可夫鏈和量子馬爾可夫決策過程的可達性問題,介紹求解這些問題所需的數(shù)學工具和算法,之后介紹一系列用于檢測超算子值馬爾可夫鏈的計算樹邏輯或線性時序邏輯的算法,后指明該領域的發(fā)展方向。
模型檢測是一種主要用于驗證有限狀態(tài)系統(tǒng)的動態(tài)性質的算法技術。經(jīng)過35年以上的發(fā)展,已經(jīng)成為一種重要的硬件和軟件系統(tǒng)驗證技術,并在信息與通信技術(ICT)行業(yè)中得到了許多成功的應用。模型檢測的特殊吸引力主要得益于以下兩個特征:
完全自動的;
當性質不滿足時提供反例,因此在調試中作用顯著。
由于計算和通信系統(tǒng)中存在各種隨機現(xiàn)象,模型檢測已被系統(tǒng)地擴展用于驗證概率系統(tǒng),例如馬爾可夫鏈和馬爾可夫決策過程。
隨著量子計算和量子通信的出現(xiàn),特別是其在過去幾年的快速發(fā)展,人們自然期望進一步擴展模型檢測技術以驗證量子系統(tǒng)。事實上,從將概率模型檢測直接應用于量子系統(tǒng)(特別是量子通信協(xié)議)開始,對模型檢測量子系統(tǒng)的研究已經(jīng)進行了10多年。在處理越來越一般的量子系統(tǒng)時,人們逐漸認識到,模型檢測量子系統(tǒng)需要某些與經(jīng)典系統(tǒng)(包括概率系統(tǒng))從根本上不同的原理。在近期的研究中,模型檢測量子系統(tǒng)的一些基本原理得到了發(fā)展,但相關研究成果分散在各種會議和期刊論文中。
本書試圖系統(tǒng)地闡述到寫作時間為止提出的模型檢測量子系統(tǒng)的原理以及基于這些原理的算法。本書末尾簡要討論了一些潛在的應用和未來研究的主題。希望本書可以作為研究人員踏入這一新領域時的入門指南,并為該領域的進一步發(fā)展奠定基礎。
本書還計劃作為研究生的教學用書,因此其內容組織基于一定的教學目標。鑒于量子計算和信息的學習者可能具備計算機科學或物理學背景,在章節(jié)的安排上,第2章和第3章為預備章節(jié),其中第2章為物理學背景的學生簡要介紹模型檢測,第3章為計算機科學背景的學生簡要介紹量子理論。之后,從簡單的模型和檢測性質到更復雜的模型和檢測性質,逐步介紹量子系統(tǒng)的模型檢測技術。
致謝
本書的材料主要來自作者及合作者的一系列論文。在此感謝俞能昆博士、李楊佳博士、應圣鋼博士和官極博士,與他們的合作愉快且富有成效。沒有他們的貢獻,這本書是不可能完成的。
本書中的工作得到了中國國家重點研發(fā)計劃(批準號:2018YFA0306701)、澳大利亞研究委員會(批準號:DP160101652和DP180100691)、中國國家自然科學基金(批準號:61832015)和中國科學院前沿科學重點研究計劃的支持。謹此致謝。
應明生
清華大學計算機科學與技術系智能技術與系統(tǒng)國家重點實驗室教授,清華大學量子軟件研究中心主任。中國科學院軟件研究所研究員、學術副所長。悉尼科技大學量子軟件與信息中心杰出教授。曾獲中國青年科技獎、自然科學一等獎、中國計算機學會王選獎一等獎。
他的研究領域包括量子計算、程序設計語言的語義學以及人工智能中的邏輯。他為量子程序建立了包括部分正確性與完全正確性的Floyd-Hoare型邏輯,特別是證明了其(相對)完備性。他將高級量子控制結構引入量子語言中,以更加嚴格、完整和系統(tǒng)的形式推出了量子case結構、量子遞歸結構、二次量子化、量子程序疊加等一系列概念。
他著有Foundations of Quantum Programming(2016)和Topology in Process Calculus: Approximate Correctness and Infinite Evolution of Concurrent Programs(2001)。此外,他目前還擔任ACM Transactions on Quantum Computing的(聯(lián)合)主編。
馮元
悉尼科技大學量子軟件與信息中心教授。曾任清華大學計算機系副研究員。他的研究興趣包括量子系統(tǒng)的形式化驗證、量子程序理論、量子信息與計算以及概率系統(tǒng)。已在國際重要期刊和主流會議上發(fā)表論文70余篇。曾獲得澳大利亞研究理事會(ARC)未來研究基金(2010)。
譯者序
前言
第1章引言1
1.1第二次量子革命需要新的
驗證技術2
1.2經(jīng)典系統(tǒng)的模型檢測技術2
1.3模型檢測量子系統(tǒng)的困難3
1.4模型檢測量子系統(tǒng)的研究
現(xiàn)狀3
1.5本書結構5
第2章模型檢測基礎7
2.1系統(tǒng)建模8
2.2時序邏輯10
2.2.1線性時序邏輯10
2.2.2計算樹邏輯13
2.3模型檢測算法16
2.3.1線性時序邏輯模型檢測
16
2.3.2計算樹邏輯模型檢測23
2.4模型檢測概率系統(tǒng)25
2.4.1馬爾可夫鏈和馬爾可夫
決策過程25
2.4.2概率時序邏輯26
2.4.3概率模型檢測算法27
2.5文獻注記30
第3章量子理論基礎31
3.1量子系統(tǒng)的狀態(tài)空間32
3.1.1希爾伯特空間32
3.1.2子空間35
3.1.3量子力學的基本假設I
36
3.2量子系統(tǒng)的動態(tài)過程36
3.2.1線性算子37
3.2.2酉算子39
3.2.3量子力學的基本假設II
40
3.3量子測量41
3.3.1量子力學的基本假設III
41
3.3.2投影測量42
3.4量子系統(tǒng)的復合44
3.4.1張量積44
3.4.2量子力學的基本假設IV
45
3.5混合態(tài)46
3.5.1密度算子46
3.5.2混合態(tài)的演化和測量47
3.5.3約化密度算子47
3.6量子操作48
3.6.1量子力學基本假設II的
一個推廣48
3.6.2量子操作的表示50
3.7文獻注記51
第4章模型檢測量子自動機53
4.1量子自動機54
4.2Birkhoffvon Neumann量子
邏輯56
4.3量子系統(tǒng)的線性時間性質61
4.3.1基本定義61
4.3.2安全性質62
4.3.3不變性63
4.3.4存活性質66
4.3.5持續(xù)性質67
4.4量子自動機的可達性70
4.4.1量子系統(tǒng)的(元)命題
邏輯71
4.4.2量子自動機可達性的
滿足72
4.5量子自動機不變性的檢測
算法74
4.6量子自動機可達性的檢測
算法77
4.6.1檢測