量子计算机到底是啥？1 量子计算机是谁想起来的？1.1 Nature isn't classical, dammit (Feynman 1981)1.2 Many worlds interpretation (David Deutsch)2 量子计算机到底能干什么？能不能算停机问题？能不能实现指数加速？3量子计算机咋实现的？3.1 量子图灵机 Quantum Turing machines3.2

量子计算 17 量子算法2-量子Simon算法1 定理: Q(Simon)=O(n)Q(\text{Simon})=O(n)Q(Simon)=O(n), with O(n2)O(n^2)O(n2) quantum gates and O(n3)O(n^3)O(n3) post processing (Simon 1994)2 Simon量子电路上回书我们介绍了两个简单的量子加速算法：计算f(0)

量子纠缠1 量子纯态纠缠熵1.1 施密特(Schmidt)分解1.2 **香农熵(Shannon entropy)**1.3 **冯纽曼熵(von Neumann Entropy)**1.4 纠缠熵示例2 量子混合态纠缠判定如何量化量子纠缠是本次的主题，我们主要看纯态(pure state)和混合态(mixed state)两种情况。1 量子纯态纠缠熵假设张三李四的偶量子态(Bipartite Q

量子计算 14 量子通用门1 经典门与量子门2 量子通用门 Universal gates定理: {CNOT,all 1-qubit gates}\{\text{CNOT}, \text{all 1-qubit gates}\}{CNOT,all 1-qubit gates} is universalProof sketch3 近似通用门 (Approxim