什么是"量子计算"?

发布网友 发布时间：2022-04-20 08:04

我来回答

共2个回答

热心网友 时间：2023-04-28 04:56

一 ,梦想与惊喜
始自第一个电子计算机开始运转,构想能够超越传统所谓Turing Machines 的计算模型,便是许多科学家努力的梦想.美国阿冈国家实验室的Paul Benioff是第一位提出概念,认为利用量子物理的二态系统模拟数位0与1,可以设计出更有效能的计算工具.此概念稍后又经Feynman的引申,使得有更多的物理学家注意到量子力学与计算科学之间可能的关联.直到1985年,在英国牛津的物理学家David Deutsch发表的一篇论文里,所谓Quantum Church-Turing Machines才正式开始略具数学雏型,但此论文中所提示的量子计算范例则过於简易.
到了1994年,Bell Lab的应用数学家Peter Shor,於当年IEEE基础计算理论年会发表突破性工作—快速整数因数分解方法(现今已被称为Shor's Algorithm),量子计算的潜在应用实力便迅速引起广泛的注意.因为如果能对任意极大的整数快速作质数分解,就可以破解目前普遍采用的RSA密码系统.以传统已知最快的方法对整数N做质数分解,其计算的复杂度(Complexity,也就是所须计算的步数)是此整数位数()的指数函数;此难以突破的钜额计算复杂度提供了密码系统的安全性.Shor的方法却可将此复杂度降为多项式函数(虽然仅是机率性的),使得快速破解RSA密码系统成为可能.此工作所引起的震撼不难想像,自94年后有关量子计算,量子通讯或所谓量子资讯学的论文便疾速增加,也开始吸引大量研究经费的投入(特别是来自军方与工业界).目前在美国,欧洲,日本以及中国*,已经有许多专为此新领域而成立的研究团队或研究机构.而Shor本人则於98年柏林举行的国际数学大会,与Andrew Wiles(费马最后定理的证明者)一同获奖表扬(虽然不是费尔兹奖,但仍被视为与其对等).
二 ,平行与纠缠
量子计算机的实现,不是为了取代传统的计算机,实际上也无法取代.一个有效的量子计算方法,其成功在於巧妙的结合本身特徵优势,以及可在传统计算机快速执行的古典技巧,然后在特定极困难问题上超越已知的传统方法.这里所指的特徵优势主要有二—即所谓的量子平行(Quantum Parallelism)与量子纒结(Quantum Entanglement).量子平行简而言之,就是只需n个运算(酉变换,或译么正变换,Unitary Transforms),就可以准备出2n个可能状态,虽然这2n个状态是以线性组合的方式结为一个状态;所以自然也可以再一起通过另外一个变换,就相当於同时对此2n个状态做了该变换.而为准备此2n个状态,也只需要n个量子位元(Qubits,由二态量子系统来实现)即可.量子缠结由蒒丁格首先以德文Verschr nkung指出,原意为两手臂的交缠.而量子缠结的物理涵义是指两个或更多的量子系统间存在特定的所谓非局域性关联,因而使得某些物理量无法由单一或少数的系*立决定.此缠结特徵几乎在所有的量子运算中自然产生,也可能是计算所以加速的原因之一;但因为是自然产生,故往往不在计算过程中特别强调,待稍后其他范例再来说明量子缠结极其特殊的作用.
一个量子计算的过程可简单视为将所有可能的2n个输入(inputs),以线性组合的方式"储放"在n个量子位元上,再加上运算过程中辅助用的m个量子位元(,p是某一个多项式函数)的资料,一起通过适当数目(此数目也是n的某一个多项式函数)经特别设计的酉变换,之后2n个outputs即同时现,虽然仍旧以某种线性组合的方式储放在数个量子位元上.如何从这输出的线性组合态"萃取"—即测量其中一个或数个量子位元—正确的答案,则完全取决於运算过程中酉变换的选择与组合设计.至此可以看出量子计算能获致正确答案,往往是机率性(probabilistic or nondeterministic,如同量子力学一般)而非决定性的(deterministic).
三 ,分离与追寻
Shor整数因数分解方法的成功,在於精巧的结合了古典数论技巧与量子傅利叶变换(QFT,Quantum Fourier Transform).这里的古典数论技巧主要指的是计算模数函数的周期;N是待被分解的整数,a是任意选取比N小且与N互质的整数,而x是由0开始的整数.求得此函数的周期r后,就利用孰知的辗转相除法来计算,也就是与N的最大公约数,则至少其中之一将是N的因数.举例说明,假设,任意选取,则当,,(N,a足码已省略),所以此函数的周期.计算与15的最大公因数分别为5和3,恰好都是15的因数.此技巧早在70年代已被应用在数论与资讯科学研究上,本身即是机率性的方法.有两种情况致使此技巧无法求得因数,一为当计算最大公因数时得到1或N两个无效的解,二为当所求得模数函数的周期r是奇数.但发生此失败情况的机率可证明为不超过(m是N的质因数个数),所以此古典技巧是高度有效的机率性方法.
引用傅利叶变换是计算函数周期的惯常步骤.傅利叶变换原本是积分的运算,在电脑上执行就必须加以离散化,将积分的范围分割成Q个小区间(回忆初等微积分里求曲线下的面积).离散化后的傅利叶变换就可写成一个矩阵作用在一个有Q分量的向量运算,称为离散傅利叶变换(DFT,Discrete Fourier Transform).显而易见,DFT的计算复杂度是,而变换的精确度随Q递增.经观察矩阵元素具代学上特殊的周期与环型(cyclic)特性,早於20世纪初期已有数学家发现,只要将矩阵元素做特定规则的位置互换,就可以将计算复杂度骤降为.但当时计算机尚未出现,所以此突破性工作并没有引起注意.到了60年代由Cooley与Tukey两位数学家重新发现与证明,此加速后的变换即现今计算上熟知的快速傅利叶变换(FFT,Fast Fourier Transform).Shor方法所援用的量子傅利叶变换,是由IBM的Coppersmith於94年首先给出,数学上可视为快速傅利叶变换的量子计算版本.量子计算中基本的Hadamard Transform H(H:, )即是的快速傅利叶变换F2,意即
HF2.
所谓的快速傅利叶变换,是指将矩阵元素做适当的置换后,变换的矩阵就可分解为的矩阵.再经同样规则的元素置换后,此矩阵可再分解为的矩阵.经过n次的递回分解,最后就降至最小的矩阵F2(在此假设).换句话说,所谓的快速傅利叶变换,就是由F2加上适当的相位调整建构而成.经此置换与分解,原矩阵作用在Q分量向量的运算复杂度就由降为.虽然型式略有不同,量子傅利叶变换同样是由H加上适当的相位调整建构而成.然而更有过之,由於量子平行的自然特性,Q单位的变换可藉由个量子位元同时平行运算,使得量子傅利叶变换的计算复杂度又更进一步降为—显然的,这是计算上相当可观的进展.虽然经由量子测量结果,能正确估算出模数函数的周期r仍属机率性,但由於每次尝试的计算复杂度已大为降低,所以整体而言仍保证了因数分解的快速取得.
依此估算,假使量子电脑可在未来十年内实现,运用Shor方法因数分解一个一仟位元的整数,不超过五分钟即可获得答案.但预估此时传统电脑的计算能力,操作已知最快的古典方法分解同样位元的整数,却可能需要10万年!两者速度差异之钜,由此可见.在实验方面IBM Almaden研究中心的华裔科学家Isaac L. Chuang已於2001年底,成功的利用核磁共振(NMR)技术,以7个量子位元完成的因数分解.固然熟练的运用诸多数论与分析的技巧,Shor此里程碑贡献真正揭示给人们的是量子傅利叶变换的快速与实用.受此启发,已有许多文献延续报告QFT在不同问题的推广与应用.
继Shor的快速因数分解方法后,另外一个较重要的量子计算研究成果,是於96年由Bell Lab的Lov Grover所提出的量子资料库搜寻(Quantum Seaching),如今已称作Grover's Algorithm.此方法所针对的命题为:在一个有N()个物件的资料库中,若且惟若有一个物件合乎所指定的要求,请搜寻出此物件.以古典的方法做搜寻其复杂度(搜寻的步数)为,而量子搜寻的复杂度则减为.此方法的原理是首先将资料库中每一个物件视为一个单位正交基底向量,遂形成了一个2n维数的(希尔伯特)空间(所以需要n个量子位元);暂以为代表被搜寻物件的基底向量.然后将所有基底以相等振幅相加做为初始向量,将此向量暂记为.换句话说,量子态以等振幅线性组合了资料库内所有N个物件.所谓的量子搜寻其实就是尽量放大向量中代表被搜寻物件基底分量的振幅,而当在分量振幅达到最大时测量,就有最高的机率攫取到此被搜寻物件.代数上分量振幅的放大,就等同於几何上将向量尽量移至 的方向.虽然是处於一个2n维数的高维空间,将移至 最便捷的路径就是沿著此二向量所张成的平面做旋转;Grover的方法就是找出对应此旋转的酉变换.虽然数学结构上远不如Shor方法的精巧与繁复,但Grover搜寻有更广泛的实用价值,因此也引发了许多后续研究.
量子平行是量子计算加快的主因,而量子平行则完全归因於量子波动力学的特质—量子态之间可作线性组合,形成另外一个量子态.基於此优势,一适当准备的初始态,通过经特别设计的酉变换作用,数目呈指数成长的所有可能答案便可同时产生,但却是以某种线性组合的方式写在一个量子态中.如果此过程'设计得好的话 ',如Shor与Grover的方法,则有很高的机率可攫取(测量)所须的正确答案.依此概念,量子计算是否可能破解扰人的NP-Complete问题 所谓NP-Complete问题,简而言之是指有一族群极困难的问题,其问题的解答存在有方法可彼此转换,而此转换方法的计算复杂度是以一多项式函数来描述.但如果要直接解决此族群内某一个问题,目前已知的方法则仍维持指数型函数的复杂度;古典的邮差送信问题即是其中著名的一例.如果完全根据以上量子平行的思考,则期望似乎不是乐观的,甚至可以论证要百分之百(即deterministically)破解NP-Complete问题是不可能.这与所谓量子"不可克隆定理"(No-Cloning Theorem)的论证基本类似,原因也是受制於量子态可作线性组合的特质.所谓的量子不可克隆定理是指在一量子系统中,不存在酉变换可对'任意 '的量子态做复制—完全不同於古典世界的电脑,复制任意的资料是基本功能.正是成也量子波动,不成也是量子波动.但这都无法挫阻量子计算的研究,因为对解决特定困难问题(机率性)的钜额加速,足已肯定其发展价值.而事实上在另一方面,也正由於量子波动的特质,使得在传递量子态组成的讯息过程中,具有"凡窃听必留下线索"(No Disturbance,No Information Gained)的特性.因为如果能窃取任意某部份的资料,而不被通讯者察觉蛛丝马迹,就等同复制了该部份的资料,此违反了量子不可克隆定理.由於根据此特性可能发展出更高安全性的通讯技术,所以近年来也刺激了量子通讯的积极研究.
如前所述,量子缠结并非在计算过程中刻意放入,而是自然产生.谈到量子缠结,就不能不提量子*传输,此课题已在本期李建二教授文中有深入介绍,在此只略作说明.
四 ,春娇与志明
早於70年代,Stephen Wiesner已提出量子通讯的相关想法,但由於此类概念对当时而言过於前卫,所以其原始论文迟迟未获发表.直到92年与Charles Bennett合作关於超密加码(Superdense Coding)的论文,才使此概念正式见诸於世.也是该论文将量子缠结的特徵优势,首次应用到通讯技巧上.
到了第二年,Bennett与合作者又更进一步援用量子缠结态,提出了量子隐传(Quantum Teleportation,或译为量子远传)的构想.就数学原理,超密加码与量子隐传是两个互为对偶(Dual)的概念.首先假设春娇(Alice)与志明(Bob)是一对相隔甚远的恋人,春娇想把手边的一个单一量子位元"*传递"给志明当礼物.但春娇完全不知道此位元处於何型式的量子态,所以只能假设为一般的量子态;当然她不能去测量它,因为一旦测量,此量子态就改变了.还好没将修过的量子力学忘光,事前他们已准备了一副老字号的EPR缠结对,将此量子对的第一个位元由春娇带走,第二个位元由志明保留.所谓的EPR缠结对是指由两个量子位元所形成的缠结态,总共可以写成四个正交量子态,分别为
,,,.
描述两个量子位元的量子态需要四维的希尔伯特空间,这四个字正交单位量子态亦可视为此空间的一组正交基底向量,称为贝尔态(Bell states).虽然选用其中任一缠结态皆可,但通常惯用来做隐传的过程说明.春娇与志明分别带走此缠结对的一个位元,理论上就是将两人以这量子态"缠结"在一起,无论地理上相隔有多远.
当春娇想把手上的礼物量子位元隐传给志明时,她只须将此位元与原先带来的位元(得自於EPR缠结对)同时一起做所谓的"贝尔态测量"(Bell-State Measurement).也就是春娇做完这两个量子位元的测量后,一定是落在四个正交贝尔态的其中一态.然后春娇再根据测量结果,以电话指示志明对他手上的量子位元做对应的酉变换:春娇所测得的贝尔态若为,, 或,志明则分别(按次序)选用酉变换I,Z,X或Y来修正手上的量子态.这里I是单位变换(),X对应位元值互换(),Z对应相位的改变(),以及 ().
数学上极简易的证明,经过此对应酉变换的作用,志明手上位元的量子态就完全转换成,也就是原先春娇手上礼物位元的量子态—换句话说,未经实际距离上的传递,春娇已将手上的量子礼物送给了志明,一个科幻电影中常见的情节.
超密加码的过程也极为类似,只是更为简单.春娇选取上面四种之一的酉变换,作用在自己手上的位元(来自EPR缠结对),然后将此作用后的量子位元传给志明.志明接到此位元后就与自己原先手上的位元(EPR缠结对的第二个位元)一起做贝尔态测量,其结果也一定是落在四个正交量子态的其中之一,由此即可得知春娇原先所选择的酉变换—也就是说,仅靠一个量子位元,就可以传递两个古典位元的资讯.进一步的推广,利用K个EPR缠结对,可以隐传任意K个量子位元;而任意2K个古典位元资讯的传递,只需藉由K个量子位元的运载.就数学上而言,过程中所牵涉到的酉换变,实际上是在进行所谓量子错码修正,而EPR缠结对则扮演著量子修正密码(Quantum Error Correcting Code)的角色.
更进一步的探索可发觉,要隐传K个量子位元,并非一定都需要K个EPR缠结对的辅助.如果传递前已经有关於此待隐传量子态的部份讯息,例如此量子态具某类特定型式等等(即此量子态不再是'任意 '),则确实可以只用缠结程度较少的缠结量子态来做隐传的媒介.同样的,部份关於传递资讯的特定事先知识(á prior knowledge),也可以用来抵减超密加码传载时所需量子缠结态的缠结程度.此观察的重要物理意涵是—量子缠结蕴含资讯量!而稍后提出的量子修正密码亦可进一步体现此意涵,量子缠结不只蕴藏资讯,更可以用来保护资讯.
五 ,只是正开始
量子修正密码的研究,也是由Shor最早引入.其目的在於对抗量子计算与量子通讯过程中,由於环境影响所造成不可避免的消相干(Decoherence)效应.此效应会使计算与通讯过程中量子态产生不预期的错误,如位元值的变异—某量子位元的0与1态互换,以及相位的变异—量子态正号与负号相位的改变.修正密码的研究自二十世纪上半期,随通讯时代的萌芽即已开始,本身已是一门发展极为成熟的学科,不同的只是古典修正密码无须考虑相位的变异.在95至97之间,Shor,Steane等人首先引申古典修正密码中最基本的线性群密码(Linear Group Code)概念,建立了量子修正密码的理论架构.其原理简而言之,就是加密后的密码字(Codewords)本身构成一个线性加法群,这个群可以分隔出数类可以纠正的位元值错误(一类错误就对应此加法群所分割出的一组字串,形成所谓的coset),并预测各类错误所该呈现的病徵(Syndrome).当发生错误的量子态穿过一个特别设计的酉变换(通常称为Parity-Check Matrix)后,病徵即显现,而此病徵会以一个量子态写入一个辅助的量子暂存器.测量暂存器的量子态可得知该病徵,然后做出对应的修正,即以前述的X算符(对付位元值变异)作用在发生错误的量子位元上.根据数学上的恒等式HZH(H -1H),相位的变异在对偶空间内(即经前述的傅利叶或Hadamard算符H的转换后)就成了位元值的变异.所以将量子态经H的映射后,如法泡制,测量出对应的位元值错误,然后以X算符进行修正.再经由H映射转回原空间后,相位的错误即已修迄,原本的量子态则告恢复.
约在此同时,一位加州理工学院的研究生Daniel Gottesman独立发展出一套更简单的方法.对一个密码量子态找出其对应的一组所谓嵌定密码生成子(Stabilizer Code Generators),或者也可以反过来说由此组生成子来定义此密码量子态,因此称作嵌定密码(Stabilizer Code).两者的关系是密码量子态是生成子的本徵态,且本徵值为1;如果此量子态在某位元发生(位元值或相位)变异,则对至少其中一个生成子会产生的本徵值.
现以7个位元的CSS(Calderbank -Shor- Steane)密码为例来做说明.这个密码只有能力修正一个位元的变异,更多位元变异的修正其基本原理一致,只是密码建构的过程略加繁复.CSS密码将每一个态与态分别加密为7个位元的量子态:
,

.
注意量子态有8个分量,分量对应的字串构成一个7位二元字串的子群;而量子态分量的字串则对应此子群所分割出的一个coset.定义此嵌定密码需要6个生成子,分别为
,,, ,,.
第一个生子的作用是将量子态的前四位元做位元值的变异(即),而第四个生成子的作用是对前四位元做相位的变异(即前四位元若有个1,则乘上相位),其他生成子的作用可类推.不难看出与二量子态皆是这六个生成子的本徵态,且本徵态值全为.假设态在第二位元发生了相位的变异,成了
.
这变异后的量子态仍然是六个嵌定密码生成子的本徵态,只是对S1与S2两个生成子的本徵值改为.不难验证所有单一位元(位元值或相位)的变异(总共14种),皆可从对六个生成子的或本徵值分布完全判定.再看本例,对应第二位元相位变异的算符()与S1及S2两生成子为"反交换",意即及,而与其他四个生成子为可交换(注意嵌定密码生成子彼此一定是可交换)—本徵值正负号的由来即在於此.对於其他形式的变异,也可以由检查对应算符与生成子的交换性,轻易得出其应有的本徵值分布.
虽然较早被提出,7位元的CSS密码尚非最经济的选择.如果只为修正一个位元值的变异,不难验证,将与以三个量子位元加密即已足够;即与,所对应的嵌定密码生成子为.但若要更进一步纠正一个位元的相位差异,则至少需要五个量子位元的加密,其对应的嵌定密码生成子为 .小小的练习,读者可根据此组生成子,尝试找出所定义的5位元加密量子态—此密码为修正单一位元(位元值或相位)变异的最佳答案.而此5位元加密量子态的(16个)分量并不全为的相位,某些分量是以的相位加入此量子态.这说明了相位本身也具载藏资讯的功能,故可缩减密码的位元数.
嵌定密码在检定变异时完全不需要备有纪录病徵的暂存器,只须通过嵌定密码生成子的检验即可(因为是生成子的本徵态,所以作用后仍维持原量子状态).此外也不须像CSS密码要分两阶段,先修正位元值变异的错误,再修正相位的变异.故不只步骤简化,数学建构的过程也更合乎量子力学的精神.由於是透过观察与特定算符(嵌定密码生成子)的对易关系来检定变异,Gottesman因此称此类密码为海森堡图像(Heisenberg Picture)的量子修正密码.
在量子计算与量子通讯过程中,或自然产生,或刻意援用,不同型式的量子缠结态随处可见.除了先前提到最简易的贝尔态之外,量子修正密码所对应的加密量子态,皆是不同缠结程度的量子态.如果再加上与环境的交互作用,又可产生更为复杂的缠结态.如何去理解,区分与量化这些掬手可得的缠结态,甚至进而开发其在计算与通讯上的应用价值,是目前量子资讯学最重要的研究课题之一.此刚起步不久的新兴领域,一方面因实用的前瞻性引领前进,另一方面也因提供再认识量子力学的新视野,而引人入胜.

热心网友 时间：2023-04-28 04:57

量子信息与量子计算简明教程

一个量子计算的过程可简单视为将所有可能的2n个输入(inputs),以线性组合的方式"储放"在n个量子位元上,再加上运算过程中辅助用的m个量子位元(,p是某一个多项式函数)的资料,一起通过适当数目(此数目也是n的某一个多项式函数)经特别设计的酉变换,之后2n个outputs即同时现,虽然仍旧以某种线性组合的方式储放在数个量子位元上.如何从这输出的线性组合态"萃取"—即测量其中一个或数个量子位元—正确的答案,则完全取决於运算过程中酉变换的选择与组合设计. 有本书叫<量子信息与量子计算简明教程>不放自己看看
作者：陈汉武 编
出版社：东南大学出版社
ISBN：7564103493
印次：1

纸张：胶版纸 出版日期：2006-6-1
字数：240000
版次：1