●1 緒論
1.1 量子計算
1.1.1 量子計算的影子——可逆計算
1.1.2 量子圖靈機與量子線路
1.1.3 量子算法
1.2 量子自動機
1.2.1 概況
1.2.2 量子有限自動機(QFA)
1.2.3 QFA的主要研究工作
1.2.4 QFA和其他研究分支的聯繫
1.3 等價性和最小化問題
1.3.1 經典自動機情形
1.3.2 量子自動機情形
2 預備知識
2.1 線性代數的相關概念與符號
2.1.1 線性空間
2.1.2 狄拉克符號
2.1.3 矩陣的基本操作
2.1.4 特殊矩陣
2.1.5 矩陣的分解與範數
2.2 量子力學基礎
2.2.1 量子比特
2.2.2 量子力學基本假設
2.2.3 密度算子
2.2.4 量子運算的算子和表示
2.3 經典自動機理論的相關概念與符號
3 量子自動機模型
3.1 測量一次的單向量子有限自動機
3.2 測量多次的單向量子有限自動機
3.3 帶控制語言的單向量子有限自動機
3.4 帶經典態的單向量子有限自動機
3.5 雙向量子有限自動機
3.6 帶量子和經典態的雙向有限自動機
3.7 多字符量子有限自動機
3.8 其他量子有限自動機
3.9 量子時序機
3.10 本章小結
4 量子自動機的等價性判定
4.1 準備知識
4.1.1 雙線性機及其等價性
4.1.2 量子自動機的等價性定義
4.2 量子時序機的等價性
4.2.1 方法一
4.2.2 多項式時間的等價性判定算法
4.2.3 方法二
4.3 測量一次的單向量子有限自動機的等價性
4.4 帶控制語言的單向量子有限自動機的等價性
4.5 測量多次的單向量子有限自動機的等價性
4.5.1 方法一
4.5.2 方法二
4.6 多字符量子有限自動機的等價性
4.6.1 輸入字母表隻含一個字符
4.6.2 輸入字母表為一般情況
4.7 本章小結
5 一般單向量子有限自動機
5.1 測量一次的一般單向量子有限自動機
5.1.1 閉包屬性
5.1.2 語言識別能力
5.1.3 等價性問題
5.2 測量多次的一般單向量子有限自動機
5.2.1 預處理
5.2.2 語言識別能力
5.2.3 等價性問題
5.3 本章小結
6 量子自動機的最小化
6.1 最小化的主要思想
6.2 概率有限自動機的最小化
6.3 測量一次的單向量子有限自動機的最小化
6.4 測量多次的單向量子有限自動機的最小化
6.5 一般單向量子有限自動機的最小化
6.5.1 預備知識
6.5.2 最小化問題
6.6 本章小結
參考文獻
索引
內容簡介
量子計算是計算機科學與量子力學交叉產生的新興學科,經過30多年的發展,在理論和實驗方面都已經取得了長足的進展。本書從計算機科學領域自動機理論的角度來考察量子計算,力圖通過有限自動機這個簡單而重要的模型來探索量子計算與經典計算的一些本質差異,認識量子計算的計算能力和局限性。