导语

  

内容提要

  

    本习题详解是应对当前出现的量子计算与量子信息的学习和研究的热潮，汇集整理我研究室多年来讨论班读书环节对《Quantum Computation and Quantum Information》的第三章节和第四章节的习题求解与解析的结果。
    第三章“计算机科学简介”内容主要涉及到计算机科学中的可计算性与计算复杂性相关知识点。“阅读内容”或选择教材论述中的重点进行摘录或根据习题求解补充相关知识点编辑内容，对原书中的32道习题进行了抛砖引玉的求解和解析。我们没有回答该章节最后留下的10个问题。这10个问题的格局都比较大，每一个问题都是可以或值得研究的内容。第四章“量子线路”围绕量子线路的基本模块和复杂量子计算通用语言等内容叙述量子计算的基本原理和方法。“阅读内容”或选择教材论述中的重点进行摘录或根据习题求补充相关知识点编辑内容，对原书中的51道习题进行了求解和解析。同样我们没有回答该章节最后留下的6个问题，但关于这6个问题的解答，我们在过去的讨论中查阅了当时的相关文献，并给出若干问题解答的相关研究成果，读者若有兴趣可以根据提示阅读相关论文。
    本题解可作为高等院校本科相关专业，或研究生阶段进入量子计算与量子信息学习者的教辅材料，也可作为对量子计算和量子信息感兴趣的研究人员和工程技术人员阅读相关书籍的辅助资料。

    陈汉武，博士，东南大学计算机科学与工程学院教授，博士生导师，《Mathematical  Review》与《IEEE Transactions on Information Theory》特约评审。自1 999年参加京都大学数理解析所量子信息讨论班后，对量子信息与量子计算萌发兴趣并开始关注量子计算与量子信息的科技进展。1999年4月开始主持为期一年的山口大学地区合作中心VBL项目《实现信息量子通信基础技术的理论研究》；归国后，2005年9月组建量子计算与量子信息研究室；2006年7月出版教材《量子计算与量子信息简明教程》。研究兴趣包括：量子可逆逻辑电路综合、量子安全通信协议、量子纠错编码、基于量子计算的图像处理等相关主题的量子计算理论研究与应用探索。在IEEE Transactions on Information Theory．IEEE Communications Letters．Quantum Information Processing，Quantum Information  and Computation，Chinese Physics Letter，Chinese Physics B，Science China Information Sciences，International Journal of Theoretical Physics等期刊上已累计发表论文124篇，其中SCI收录42篇，EI收录82篇，SCI表现不俗7篇。

第3章  计算机科学简介的阅读辅导与习题练习
  3.1  计算的模型
    3.1.1  Turing机
    3.1.2  线路
  3.2  计算问题的分析
    3.2.1  如何量化计算资源
    3.2.2  计算复杂性
    3.2.3  判定问题和复杂性P类和NP类
    3.2.4  更多的复杂性类
  3.3  对计算科学的思考
第4章  量子线路的阅读辅导与习题练习
  4.1  量子算法
  4.2  单量子比特运算
  4.3  受控运算
  4.4  测量
  4.5  通用量子门
    4.5.1  两级酉门(two—level unitary gate)是通用的
    4.5.2  单量子比特门和受控非门是通用的
    4.5.3  通用运算的一个离散集合
  4.6  计算的量子线路模型的总结
  4.7  量子系统的仿真