量子信息的基本概念.ppt

BEA Confidential * * BEA Confidential * 算法: 用于求解某一类问题的指令序列集合。 算法复杂度( computational complexity)：用于衡量算法的难易程度。 一个问题的大小可以用一个整数n表示，n是指定这个问题需要输入的信息量的度量。如果一个问题的大小是n，解这个问题的算法需要的时间（或计算步数）为T（n），当n增大时T（n）的增加不比n的一个多项式函数增加更快，称这一算法为多项式时间算法，不是多项式时间的算法称为指数算法。 能用多项式时间算法求解的问题称为P类问题。人们将迄今未找到多项式时间解法（但并未证明它没有多项式时间算法）的问题称为NP类问题。 量子并行性 ( quantum parallelism): 量子并行性：由于量子叠加性，量子计算机不仅可以作用于某个计算基态，而且可以同时作用于各个计算基态。 考虑作用于N量子比特上的函数 f 。f 的变量有2N个，经典计算需2N次，而量子计算只需计算一次。 量子计算机运行一次，其效果相当于 一台经典计算机运行2N次，或者 2N台经典计算机并行运行一次。 但由于量子信息的的隐匿性等原因，量子算法的设计极为困难。 量子算法 x x 量子算法 Thank You BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential * BEA Confidential. | * Chapter One Ocean University of China Content: 量子信息简介 1.1 量子隐形传态 1.5 量子克隆 1.4 量子计算 1.3 量子比特 1.2 量子算法 1.6 Ocean University of China 1.1 量子信息(quantum information)简介 QI是研究用量子力学系统完成信息处理的学科。 QI最初起源于人们对量子力学的探究，以及人们对单个量子系统进行完备控制的兴趣。 超光速？→ 量子不可克隆定理（No-cloning theorem) 腔量子电动力学（Cavity Electro-dynamics, C-QED) 扫描隧道显微镜（Scanning tunneling microscope, STM) QI是计算机科学发展的结果。 1936年图灵提出计算模型——图灵机 冯?诺依曼提出存储程序工作原理，五大部件 1947年晶体管诞生 1965年提出Moore定律，21世纪前20年尺度将达极限，量子效应将 使电路无法正常工作 Ocean University of China 算法的有效性：计算复杂度（computational complexity) 有效算法：计算时间随问题规模按多项式增长 非有效算法：计算时间随问题规模指数增长 例：大数因子分解，130位数～1个月; 400位数～1010年(宇宙年龄) 1985年，Deutsch：量子计算机(quantum computer)可能更有效！ Deutsch算法 1994年，Shor算法 1995年，Grover算法 QI是信息论和通信科学发展的结