量子计算理论基础

邱道文，生于1967年，理学博士，2002年8月清华大学计算机系博士后出站，同年“百人计划”人才引进中山大学计算机系任教。自2004年以来为中山大学计算机系教授，博士生导师。中山大学计算机系教授。二十余年来从事量子计算与量子信息的研究，在量子计算模型、量子查询算法、半量子密钥分配、量子信息中的不完备性和极限问题、模糊与概率自动机和离散事件系统方面取得了重要成果，解决了国际知名学者C. Moore和J. P. Crutchfield、J. Gruska、S. Gudder提出的问题。其研究将经典与量子计算处理相互融合，以期达到物理可实现性和本质上优于经典计算。在中科院一、二区和CCF A、B类等学术期刊和会议发表了160余篇学术论文，出版一部关于量子自动机的学术专著。

第1章 量子计算的发展历史与潜在应用

1.1 量子计算的发展历史

1.2 量子计算的潜在应用

1.3 量子计算的硬件发展

1.4 小结

参考文献

第2章 量子计算基本概念

2.1 量子比特

2.2 经典的逻辑运算门和电路

2.3 基本量子门与电路

2.4 小结

参考文献

第3章 线性代数基础

3.1 线性无关与基

3.2 线性算子与矩阵

3.3 Pauli矩阵

3.4 Cauchy-Schwarz不等式

3.5 特征值与特征向量

3.6 伴随算子和Hermitian算子

3.7 算子函数

3.8 算子分解定理

3.9 量子力学假设

3.10 密度算子

3.11 偏迹

3.12 超算子

3.13 小结

参考文献

第4章 基本的量子通信协议

4.1 BB84协议

4.2 B92协议

4.3 E91协议

4.4 超密编码

4.5 量子隐形传态

4.6 小结

参考文献

第5章 量子计算模型

5.1 单向量子有限自动机（1QFA）

5.1.1 单次测量的1QFA

5.1.2 多次测量的1QFA

5.1.3 带经典状态的1QFA

5.1.4 其他几类重要的1QFA

5.2 双向量子有限自动机（2QFA）

5.3 带量子与经典状态的双向有限自动机

5.4 量子下推自动机

5.5 量子文法

5.5.1 上下文无关文法与正则文法

5.5.2 量子正则文法

5.5.3 *量子上下文无关文法

5.6 量子图灵机（QTM）

5.7 量子电路

5.7.1 量子门

5.7.2 多项式时间模拟QTM

5.8 小结

参考文献

第6章 量子算法

6.1 概率算法与量子算法的基本关系

6.2 量子查询模型

6.3 查询复杂度与多项式度的关系

6.4 Deutsch算法

6.5 Deutsch-Jozsa算法

6.6 Simon算法

6.7 量子傅里叶变换

6.8 量子相位估计

6.9 *量子相位估计的详细概率分析

6.10 Shor因数分解算法

6.11 Shor离散对数算法

6.12 隐子群算法

6.13 Grover算法

6.14 量子振幅扩大

6.15 *量子振幅估计

6.16 *HHL算法

6.17 *变分量子特征值求解算法

6.18 *量子近似优化算法

6.19 小结

参考文献

第7章 量子计算复杂性

7.1 重访量子查询模型

7.2 量子状态区分

7.3 搜索问题下界

7.4 多项式法

7.5 敌对法

7.6 小结

参考文献

第8章 量子纠错

8.1 经典比特翻转纠错

8.2 量子比特翻转纠错

8.3 量子相位翻转纠错

8.4 Shor码

8.5 线性码

8.6 CSS码

8.7 *稳定子码

8.8 *二元量子MDS码

8.9 小结

参考文献

量子计算是基于量子力学原理调控量子比特进行信息处理的计算模式，是国内外重点关注的交叉研究领域。本书介绍量子计算理论中最为重要的基础知识和研究内容，并适当介绍密切相关的最新研究进展。全书共8章，第1章简要介绍量子计算的发展历史、背景及现状，并指出量子计算的优势及潜在应用；第2章描述与量子计算密切相关的基本概念，并指出经典计算是量子计算的特殊情形；第3章概述与量子计算密切相关的线性代数基础知识，特别是系统地归纳了算子(矩阵)分解的相关定理和超算子等内容；第4章陈述基本的量子密码和通信协议；第5章阐述基本的量子计算模型，包括量子有限自动机、量子图灵机与量子电路等；第6章介绍量子计算的核心内容——重要的量子算法，主要包括Deutsch算法、Deutsch-Jozsa算法、Simon算法、Shor算法与Grover算法，以及HHL算法、VQE算法和QA0A算法，同时还介绍隐子群算法，总结设计量子算法的基本工具，即量子相位估计方法与量子振幅。扩大方法；第7章介绍量子计算复杂性的基本知识与方法；第8章介绍量子纠错码的基本概念和方法，并阐述它们的纠错原理。