量子计算机 林晓菲 2004-05-14.

Slides:



Advertisements
Similar presentations
专题复习 --- 走进名著 亲近经典 读完《鲁滨孙漂流记》这本精彩的小说 后,一个高大的形象时时浮现在我的眼 前,他就是勇敢的探险家、航海家鲁滨 孙。他凭着顽强的毅力,永不放弃的精 神,实现了自己航海的梦想。 我仿佛看到轮船甲板上站着这样的一 个人:他放弃了富裕而又舒适的生活, 厌恶那庸庸碌碌的人生,从而开始了一.
Advertisements

國中教育會考說明 年 5 月 14 日(六) 105 年 5 月 15 日(日)  08:20- 08:30 考試說明  08:20- 08:30 考試說明  08:30-  09:40 社 會  08:30-  09:40 自 然 09:40- 10:20 休息 09:40-
歡迎 南投縣數學領域輔導團蒞臨指導. 數學領域輔導團跨縣市交流 講員 : 林鴻哲 嘉義市數學領域輔導團.
创意鄱阳湖— 一种基于无形资源理念开发鄱阳湖的思考 以传奇背景音乐作为开场,体现创意创造传奇 南昌大学 黄细嘉
3.1 信息加密技术概述 3.2 密码技术 3.3 密钥管理 3.4 网络加密技术 习题与思考题 参考文献 实训指南
防盜裝置  學生科技探究.
饮食中的平衡 酸 性 食 物 与 碱 性 食 物.
知识聚焦 光合作用 呼吸作用 条件 场所 原料 产物 物质变化 能量变化 有光无光都可以 需要光 主要是线粒体 叶绿体 二氧化碳、水
控制方长投下的子公司,需要编制合并报表的演示思路
600年前,鄭和率領世界上最強大的艦隊,浩浩蕩蕩的駛入印度洋,展開一場「文化帝國」的海上大秀。
質數的應用 – RSA加密演算法 國立中央大學 資工系 江振瑞.
勝過這世界 我能勝過這世界 因有耶穌在我心 黑暗權勢已破碎 因耶穌基督寶血. 勝過這世界 我能勝過這世界 因有耶穌在我心 黑暗權勢已破碎 因耶穌基督寶血.
8 企业信息管理的定量分析 第八讲 企业信息管理的定量分析 8.1 企业信息化水平的测评 8.2 企业信息管理绩效的测评.
古文選讀.
教科書:資訊與網路安全概論,黃明祥、林詠章著,Mc Graw Hill出版,普林斯頓總經銷
农信社信贷产品实务技能提升培训.
台中縣立大里高中 理化科實習教師 曹佑民 老師
第十章 肌肉活动的神经控制 第一节 神经系统概述 第二节 运动的神经控制 [复习思考题] 神经组织 神经传导的一般特征 神经元间的信息传递
校務會議 業 務 報 告 教官室 主任教官: 廖世文 中校 99/06/25.
高齡者道路交通事故特性與道安防制措施 研究計畫報告
95課綱 歷史科第二冊(中國史) 第三單元(章) 近世發展(宋、元明、清) 第三主題(節) 士紳社會與庶民文化
4量子通信与加密.
第一单元 走进化学世界 课题 1 化学使世界变得更加绚丽多彩.
301——隆重登场.
理 想 理想是大海的航标, 指引你前进的方向; 理想是闪闪的明灯, 照亮你前进的航程; 理想是生命的动力,帮助你战胜困难;
課程:諮商概論 指導老師:李秀玉老師 閱讀書籍:傷癒—低估自我的醫治(一) (P.60~69)
植物辨識及分類 呂春森 基隆市立暖暖高級中學 植物辨識及分類 呂春森 基隆市立暖暖高級中學.
高中生职业生涯规划 河南省淮滨高级中学 朱凯
——奧科特公開及內部培訓 系列課程(三)之十一
第三课 闲话“家”常 1.
06資訊安全-加解密.
“华东师大数学系部分老同事活动”(辛卯聚会)记事
第五节 读图表述.
財團法人中華民國證券櫃檯買賣中心 交 易 部 中華民國101年8月
102學年度預算編製說明會 主辦單位:會計室 102/02/22.
材料作文审题立意训练.
定风波.
专题1 化学家眼中的物质世界 第三单元 人类对原子结构的认识 原子结构模型的演变 高一化学备课组 杨伏勇.
計算機概論 蘇俊銘 (Jun Ming Su) 資料加密技術簡介 計算機概論 蘇俊銘 (Jun Ming Su)
喜愛大自然的老師----段秋華.
班級:電資一 組長:程英傑 組員:黃智駿、廖夢溪、李金霖 黃粵丞、蘇長益 指導老師:陳美美 老師
中国未成年人法制安全课程 酒精饮料我不喝 小学段 第三讲 NO.
经 络 学.
公開鑰匙加密演算法 密碼學大革命 public key所想要解決的問題 public key密碼系統特性
本章涉及的主要问题: 汇票中的出票、背书、 票据种类 承兑、保证行为 票据行为 汇票中的付款和追索 票据权利及其内容 有关本票的制度
RSA-256bit Digital Circuit Lab TA: Po-Chen Wu.
密碼學簡介與簡單生活應用 Introduction to Cryptography & Simple Applications in Life 2010 Spring ADSP 05/07.
第9课 北美大陆上的新体制 导入新课 新课教学 课堂小结 知识结构 巩固练习
二、現代的加解密法:RSA 非對稱式密碼系統的一種。
計算方法設計與分析 Design and Analysis of Algorithms 唐傳義
清华大学 计算机科学与技术系 李恺威 简单数理逻辑及其应用 清华大学 计算机科学与技术系 李恺威
如何寫工程計畫書 臺北市童軍會考驗委員會 高級考驗營 版.
基礎密碼學 非對稱式金鑰加密法 樹德科技大學 資訊工程系 林峻立 助理教授.
第三章 數據保密系統.
李开祥 郭雪丽 马高峰 杨洋 孙凤英 陈静 Copyright © 2007 西安交通大学电子商务系
公開金鑰密碼系統 (Public-Key Cryptosystems)
第一章 打开物理世界的大门.
B2B -- 99/09/01 ~ 99/11/10異動項目 1.公告區 1-1 登入首頁連結到公告區,將原登入資訊加到公告區
公钥密码学与RSA.
DES算法.
應用加密技術 A 譚惠心 指導教授:梁明章教授.
組合科學 (Combined Science)
國民年金 np97006.
第5讲 问题识别、议程与政策备选方案 做人在有疑之处不疑,做学问在无疑之处有疑。————胡适 利益集团.
_14RSA加密的基本原理 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
所得稅法第14條、第126條修正條文 薪資所得計算方式二擇一 定額減除 特定費用減除 維持現行薪資所得特別扣除額20萬元減除方式
关于复杂性理论的一点探讨 孙广中
台灣房價指數 台灣房屋 中央大學 2011年7月29日.
海葵與小丑魚 照片來源:
Presentation transcript:

量子计算机 林晓菲 2004-05-14

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

量子计算机的发展及现状 三大热点 量子计算机 量子密码术 量子通信

量子计算机 20世纪后半页计算机技术大行其道,人类进入信息时代。随着计算机芯片的集成度越来越高元件越做越小,集成电路技术现在正逼近其极限 。 原件小型化过程

量子计算机 从大规模集成电路的发展史看,单粒子晶体管似乎是必然趋势。当一个晶体管里包含的杂质电子数目只有一个或少数几个时,量子行为便为主要性质,这时计算方式必然要用量子力学才能正确处理。 早在60年代, Landauer就已研究计算过程的可逆性与统计力学的关系。量子计算机的概念源于对可逆计算机的研究 。

量子计算机 早期量 子计算机,实际上是用量子力学语言描述的经典计算机,并没有用到量子力学的本质特性,如量子态的叠加性和相干性。 Feynman,Fredkin,Toffoli 等人考虑由量子力学原理确定计算规则发生的现象后,发现计算理论与物理学规律密不可分。

量子计算机 Deutch 指出,这种以量子力学原理決定的计算过程 (即量子计算) 很多方面体现出与经典计算非常不同的行为。 八十年代初期,一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行 之后很长一段时间,因为科学家们不能找到实际的系统可供进行量子计算机的实验,而且还尚不清楚量子计算机解决数学问题是否会比常规计算机快,这一研究领域渐趋冷清。

量子计算机 进入20世纪90年代,实验技术和理论模型的进步为量子计算机的实现提供了可能。 要使量子 计算成为现实,一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干 最有效的方法。主要的几种量子编码方案是:量子纠错码、量子避错码和量子防错码。

量子计算机 目前已经提出的在实验上实现对微观量子态的操纵方案主要利用了原子和光腔 相互作用、冷阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。 尤其值得一提的是1994年美国贝尔实验室的Peter W. Shor证明运用量子计算机能有效地进行大数的因式分解。

量子计算机 几年后Grover提出“量子搜寻算法”,可以破译DES密码体系。 于是各国政府纷纷投入大量的资金和科研力量进行量子计算机的研究美,英,德,法,加拿大,日本,中国大陆,台湾,新加坡,印度等已先后成立专门研究量子计算机的研究群。

量子密码术 量子密码术是密码术与量子力学结合的产物,它利用了系统所具有的量子性质。 首先想到将量子物理用于密码术的是美国科学家威斯纳。 1970年 ,威斯纳提出,可利用单量子态制造不可伪造的“电子钞票”。但这个设想的实现需要长时间保存单量子态,不太现实。

量子密码术 贝内特和布拉萨德在研究中发现,单量子态虽然不好保存但可用于传输信息。 1984年,贝内特和布拉萨德提出了第一个量子密码术方案,称为BB84方案,由此迎来了量子密码术的新时期。 1992年,贝内特又提出 一种更简单,但效率减半的方案,即B92方案。

量子密码术 量子密码术并不用于传输密文,而是用于建立、传输密码本。根据量子力学的不确定性原理以及量子不可克隆定理,任何窃 听者的存在都会被发现,从而保证密码本的绝对安全,也就保证了加密信息的绝对安全。

量子密码术 最初的量子密码通信利用的都是光子的偏振特性,在长距离的光纤传输中,光的偏振性会退化,造成误码率的增加。 目前主流的实验方案则用光子的相位特性进行编码。与偏振编码相比,相位编码的好处是对光的偏振态要求不那么苛刻。 目前,在量子密码术实验研究上进展最快的国家为英国、瑞士和美国。

量子通信 量子通信系统的基本部件包括量子态发生器、量子通道和量子测量装置。 按其所传输的信息分为两类:经典量子通信和量子通信。 经典量子通信主要用于量子密钥的传输 。

量子通信 量子通信可用于量子隐形传送和量子纠缠的分发。 隐形传送指的是脱离实物的一种“完全”的信息传送。从物理学角度,可以这样来想象隐形传送的过程:先提取原物的所有信息,然后将这些信息传送到接收地点,接收者依据这些信息,选取与构成原物完全相同的基本单元,制造出原物完美的复制品。

量子通信 量子力学的不确定性原理不允许精确地提取 原物的全部信息,这个复制品不可能是完美的。因此长期以来,隐形传送不过是一种 幻想而已。 1997年,在奥地利留学的中国青年学者潘建伟与荷兰学者波密斯特等人合作,首次实现了未知量子态的远程传输。这是国际上首次在实验上成功地将一个量子态从甲地的光子传送到乙地的光子上。

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

量子力学原理 量子计算机以量子力学建立逻辑体系,与量子计算机有关的量子力学的原理,即量子状态的主要性质包括: ●状态叠加 ●干涉性 ● 纠缠 ●状态叠加 ●干涉性 ● 纠缠 ●不可复制性与不确定性 ●状态变化

量子力学原理 状态叠加 設 {|n>}為可能的量子状态,則{∑iaik|k}也是一个可能的量子状态。对应于量子计算,这表示量子计算机可以代表经典计算机的很多状态。 它使得大规模的量子并行存储成为可行, 如 n 能阶系統至少可存 2n个数据, 由于理论上n无上限。 因此, 可以利用此特性作大规模的存储。又由于各状态之间有相位相干,存储过程是平行的。

量子力学原理 干涉性 状态叠加时,依各状态间的相位关系可能出现相长或相消的状态,这是经典计算机的布尔状态所不具备的特征。 状态变化 量子依照幺正变换法则,有系统的汉密尔顿算子决定其变化。

量子力学原理 干涉性,状态变化这两个性质是量子并行计算的基础,因为系统的各个状态按照幺正变换同时变化,故一次量子计算可以同时作用在多个数据上。 量子计算机的优越性主要体现在量子并行计算上

量子力学原理 纠缠 整体的状态波函数不变并不一定表示各成份状态的波函数不变,这说明各成分波函数间有非定域的关联性。 不可复制性与不确定性 不能精确的复制一个状态,也不能在不打扰该状态的情况下观察此状态

量子力学原理 纠缠,不可复制性与不确定性是量子加密,密码术,量子通信的基础。 借助于纠缠性质,原则上可以实现超距的重生-灭体过程。 量子状态的不可复制性与不确定性是的量子通信免于被窃听或者即使被窃听也无法解读。

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

量子计算基础 量子比特 量子寄存器 量子门 量子网路

量子比特 在经典计算机中,运算的基本单元是比特(bit),它的基本状态是二值布尔逻辑状态(0或1) 在量子计算机中,运算的基本单元是量子比特(q-bit),它的基本状态是两种状态的叠加。

量子比特 规定原子在基态时记为 |0〉,在激发态时原子的状态记为 |1〉。原子除了保持上述两种状态之外,还可以处于两种态的线性叠加,记为 |φ〉=a |1〉+ b |0〉 a和b分别代表原子处于两种态的几率幅

量子比特

量子比特 一种典型的量子比特—量子点 它基本上是一个被困在原子牢笼中的单一电子。当量子点暴露在刚好合适波长的激光脉冲下并持续一段时间,电子就会达到一种激发态:而第二次的激光脉冲又会使电子衰落回它的基态。电子的基态和激发态可以被视为量比的0和1状态,而激光在将量比从0状态撞击到1状态或从1撞击到0的应用,能够被看成是一种对取非功能的控制。

量子比特 一种典型的量子比特—量子点 如果激光持续时间只有取非功能要求的一半,那么电子将同时处于基态和激发态的重叠中,这也等价于量比的连贯性状态。而更多复杂的逻辑功能可以通过使用成对的安排好的量子点被模拟出来。因此,看起来量子点是一个合适的建造量子计算机的候选人。

量子寄存器 存储一系列量子比特的体系称为量子寄存器 假如有一个由三个比特构成的寄存器 在经典计算机中,可以表示0~7共8个数,并且在某一时刻,只能表示其中的一个数 000 001 010 011 100 101 110 111

量子寄存器 若此寄存器器是由量子比特构成 ,每个量子比特可以处于|0〉或 |1〉或 |0〉与 |1〉的叠加态,既在某时刻一个量子存储器可以表示8个数 。 0〉|0〉|0〉+ |0〉|0〉|1〉+ |0〉|1〉|0〉+ |0〉|1〉|1〉+ |1〉|0〉|0〉+ |1〉|0〉|1〉+ |1〉|1〉|0〉+ |1〉|1〉|1〉

量子寄存器 3个量子比特的系统

量子寄存器 3个量子比特的系统可以同时表示8个传统状态

量子门 在经典计算机中,逻辑判断是按真值表进行 任何逻辑运算均可以归类于3项基本的布尔操作: 非(NOT),与(AND),或(OR) 这些基本的逻辑运算称为门

量子门 与经典计算机的门相对应的,量子计算机中的量子门由幺正变换实施。 量子门的真值表较经典的真值表要广泛得多。 量子门是实现量子并行计算的基石。

量子门 可以作为实现量子计算的通用逻辑门的Fredkin 门和Toffoli门 Fredkin门的真值表

量子门 Toffoli门及其真值表

量子门 异或(XOR)门及其对应操作

利用XOR门与转动门构成的Toffolli门 量子网路 将量子门按某种方式连接,构成量子网路,以进行复杂的运算。 利用XOR门与转动门构成的Toffolli门

量子网路 K-位寄存器上作分离(快速)傅立叶变换的量子网路

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

shor算法 1994年,Peter Shor提出利用量子计算机将大数的素因子分解从NP问题简化为P问题。 Shor算法使双密钥系统土崩瓦解(如RSA算法),是量子计算机理论的里程碑。

RSA算法 以发明者的名字命名 Ron Rivest, Adi Shamir , Leonard Adleman

RSA算法 Private Key(p,q,r) 其中:p, q 是两个相异的质数 r 是与 (p-1)(q-1) 互质的数 Public key(m,n) 其中: m满足rm == 1 mod (p-1)(q-1) n = pq  

RSA算法 加密目标 对a加密,假设 a < n 加密结果 b == am mod n, (0 <= b < n) 解密过程 c == br mod pq (0 <= c < pq)

c == br mod pq (0 <= c < pq) r 是与 (p-1)(q-1) 互质的数 RSA算法 c == br mod pq (0 <= c < pq) r 是与 (p-1)(q-1) 互质的数 n = pq

RSA算法 求数N 的因子等效于求余因子函数的周期 余因子函数 f a, N ( x) = axmod N ,

RSA算法 设该函数的周期为r 当r 为偶数,且r mod N != + 1时 C = gcd ( ar/ 2 - 1 , N) , D = gcd ( ar/ 2 + 1 , N) C 和D 即为N 的两个因子

RSA算法 举例: 取 p=3,q=5,r=7 则 m=7 n=15 取 a=2 则 b=8

RSA算法 对n=15进行分解 余因子函数f a, N ( x) = axmod N a可取 2 ,4 ,7 ,8 ,11 ,13 ,14 1 ,7 ,4 ,13 ,1 ,7 ,4 ,13 ,1 ,7 , . . .

RSA算法 可见周期r=4 且满足r为偶数, ar/ 2 mod N ≠±1 于是,C = gcd ( ar/ 2 - 1 , N) = 3 D = gcd ( ar/ 2 + 1 , N) = 5 为N的两个质因子

shor算法 对N进行分解 设数N 在二进制中位数为L 取输入寄存器为2L位,输出寄存器为L位 它们的初始状态均设为0 ,两个寄存器总初始态为| 0〉| 0〉 利用“转动”门操作,将输入寄存器设置为

Shor算法 将余因子函数作用于输出寄存器,使其成为 对输出寄存器进行测量,若有s种可能的测量结果,则测量后与其他s-1种结果相关的态均不存在

Shor算法 设 z = fl,N(x)是某个最小值 l 所对应的测量结果,周期性要求所有的测量结果应可以表达为 fjr+l,N(x) j = 0, 1, 2, ⋯, A,A ≈ 22L/r。 测量后,输入寄存器的状态为

Shor算法 测量周期 r 对输入寄存器进行傅里叶变换

Shor算法 若 r 可整除 22L, 有 A = 22L/r – 1, 故 方括号内的函数,仅当c 为 22L/r 的倍数时有非零值 22L/r

Shor算法 这一步的意义是:周期为 r 的状态函数的傅里叶变换得到周期为 22L/r 的状态函数 将f(c)以及c=j* 22L/r 代入得

Shor算法 对此时的输入寄存器进行测量,可得到满足c/22L = k/r , (k = 0, 1, 2, ⋯)的c值 将c/22L 消到一个不可约的分数后,就可以得到r得值。 已经证明,此算法重复O(㏒ r)可得到所需的结果

Shor算法

Shor算法 对于 r 不能整除 22L 的一般情况,情况比较复杂,可以通过一系列的数学和物理变化经过O(㏒ N)次重复计算后,得到r的值

Shor算法

Shor算法 Shor 算法为一种随机运算法,但因量子计算具有高度并行能力,每次运算可同时处理 22L 个数据,故允许重复计算从恶热得到高几率的结果(~1) 。卻又不至於影響計算的有效性。从上可知,以量子计算分解大数质因子所需的步数为 ㏒ N 的多项式,即将问题简化为P问题。

shor算法 经典因子分解与量子因子分解的比较 因为L ( L + 1) / 2 ≤L 2 当L > 5 ,则2L > L 2 设经典计算机的运算速度约1012 次/ 秒 作1030 次运算需1018 秒,而宇宙的寿命约为1017秒在量子计算机上采用量子算法, 需要作的运算次数约为L 2 ≈ 4 ×104 同样的运算速度,10 -8 秒可完成

shor算法 举例:取N=15,a=7 15需要四位二进制表示,于是设置输入寄存器为8位,输出寄存器为4位。设置寄存器的状态,并用余因子函数对其作用后,两个寄存器的总状态为(余数共有1,4,7,13四个)

shor算法 举例:取N=15,a=7 +| 3〉| 13〉+| 4〉| 1〉+| 5〉| 7〉 (1/ 16) ( | 0〉| 1〉+| 1〉| 7〉+| 2〉| 4〉 +| 3〉| 13〉+| 4〉| 1〉+| 5〉| 7〉 +| 6〉| 4〉+| 7〉| 13〉+| 8〉| 1〉 +| 9〉| 7〉+| 10〉| 4〉+| 11〉| 13〉 +| 12〉| 1〉+| 13〉| 7〉+| 14〉| 4〉 +|15〉| 13〉)

shor算法 举例:取N=15,a=7 对输出寄存器进行测量,将随机得到1,4,7,13中的一个,假设测得的是7 则输入输出寄存器的状态为

shor算法 举例:取N=15,a=7 (1/ 16) (| 1〉| 7〉+| 5〉| 7〉 +| 13〉| 7〉+| 9 >|7 >) =(1/16) (|1〉+|5〉+|9〉+|13〉)|7 〉

shor算法 举例:取N=15,a=7 对输入寄存器进行傅里叶变换,得到 c=64 将c/22L 约分得1/4,即 r= 4

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

参考文献 书籍

参考文献 人物

参考文献 杂志文章

参考文献 杂志文章

参考文献 杂志文章

参考文献 其它文章 Quantum Computation, Physics World, 1992, David Deutsch A quantum leap in secret communications. William Bown, New Scientist 30/1/93 Tight Bounds on Quantum Searching, M. Boyer, G. Brassard, P. Hoyer, A. Tapp Quantum Cryptoanalysis introduction, Artur Ekert Weirdest Computer of All, The Economist, 28 Sept. 1996

参考文献 其他文章 Is the universe a computer?. Julian Brown, New Scientist 14/6/1990 It takes two to tangle - in the quantum world. Ben Stein, New Scientist, 28/9/96 Quantum communication thwarts eavesdroppers. David Deutsch, New Scientist, 9/12/89 Quantum leap in code cracking computers. Mark Ward, New Scientist, 23/12/95 Quantum Code-breaking, The Economist, 30 Apr. 1994 Physical Revue Letters. (Vol. 78 p3414).

参考文献 网页

谢谢!