6月24日,由智谱AI支持,北京市科委、中关村管委会科普专项经费资助的系列栏目“科普大佬说”第四期于AI TIME 开讲,本次讲座邀请了中国科学院计算技术研究所研究员孙晓明老师,带大家走进量子计算的世界。
量子计算定义
试图借助量子力学特性来获得计算上的加速
(1)量子叠加(Quantum superposition)——薛定谔的猫
(2)量子纠缠(Quantum entanglement)——心有灵犀
尽管上述两个假设听起来很是荒诞,但是却被科学家从实验上证实是可能成立的。
在量子力学初期还没有建立足够理论的时候,冯•诺依曼就已经在其专著《量子力学的数学基础》中通过数学公理化体系来定义量子力学。
这样一来,只要我们拥有线性代数的基础知识就可以学习量子力学。
量子力学假设
对于量子力学来说,有几个基本的假设。
图灵机(Turing Machine)
图灵机的组成:有穷控制器,读写头,无穷纸带,转移规则
事实上,量子计算也是完全符合图灵模型的,两者的唯一差别是经典计算机可能在计算效率上稍微差一些。
量子算法
在量子图灵机上运行量子算法:
(1)从可计算性的角度:量子图灵机 ≡ 经典图灵机
i.e, 量子计算也不能够解决不可计算的问题,例如:停机问题
(2)量子计算可以在一些重要问题上比经典算法有效率提升
我们不禁思考,能否刻画清楚在哪些问题上的量子算法能够比最好的经典算法有加速?
量子电路
量子计算就是如上图这样,左边准备好一个量子态,经过一些酉变换(量子门),在得到量子态之后做测量,最终会以概率的形式塌缩到一个经典态。我们希望其获得正确解的概率尽可能的高。
量子计算的历史
最近几年量子计算的飞速发展主要是因为一些科技巨头的推动,国内外如Google、IBM、微软、阿里、腾讯、百度、华为、字节跳动、京东等巨头的布局也促使着量子计算的研究不断进步。
Deutsch-Jozsa算法
(1)经典算法:2n-1+1次查询
(2)量子算法:1 次查询
量子查询模型
量子计算只能进行酉操作(可逆变换),如何对输入数据进行访问?通过oracle Ox(黑盒,神谕)
对于可逆操作,早在量子计算发展起来之前就已备受关注。Toffoli门可以实现任何可逆布尔函数(即Toffoli是通用门)。
用量子的方式将其实现出来的好处在于计算时若输入叠加的态可以在经过量子门时同时得到全部的计算结果。
我们可以将上面的整个操作理解为上述数学表达式。通过这样的一个例子,我们为大家展示了量子计算是如何工作的。
分解质因数——Shor算法
大整数分解质因数问题:输入一个n位长的整数,将其分解质因数
1994年,Shor教授提出了如下算法:假如输入数字长度是n位,算法复杂度大致是n2量级,而目前最好的经典算法关于n是指数量级。
这个算法的核心部分主要都是经典的计算,而用量子解决的只是下面这样一个问题:找周期。
具体来说,假如要分解N=35。我们在随机取a的情况下,a的不同次方在模为35的时候会呈现一个周期数列。
在找到周期r之后,我们用辗转相除算法计算gcd(a^(r/2)-1,35)和gcd(a^(r/2)+1,35)得到分别含有模35的两个因子7和5。
量子部分首先制备一个大的叠加态,然后用一个模幂乘法电路实现(x,a^x),这也是一个可逆的操作。
又由于a^x是有周期的,所以我们只需进行一个傅里叶的逆变换就可以以高概率找出周期。
和经典的计算方法对应,我们采用的傅里叶变换可以递归的拆解为下图中的电路来实现。
隐子群问题
隐子群问题涵盖了许多重要的问题,如质因数分解、离散对数、图同构、最短格基向量问题等。这些都是密码学中比较重要的问题。
无结构搜索——Grover算法
数组搜索问题:
在一个没有排序的数组中找到一个特定的元素
大数据处理:10^8 → 10^4 密码分析:2^90 → 2^45
类似于之前做法,通过制备一个叠加态,并经过一步神谕作用,我们可以得到全部f(i)的叠加(|f(1)⟩+|f(2)⟩+⋯+|f(N)⟩如上图中的电路所示)。
但是由于测量到每一个具体的f(i)的概率只有1/N,所以简单的通过叠加和测量的算法无法起到加速的作用,而Grover教授设计的算法通过循环的调用神谕和Grover翻转操作使得测量得到正确结果的概率接近于1。
Grover算法推广
在Grover算法的基础上,人们将其进一步拓展到振幅放大算法。
振幅放大算法
问题:如何找到一个局部极大值
有先验知识的量子搜索
在一些搜索问题之中是存在先验知识的,比如我们在剪枝的时候知道哪些分枝存在好的路径。每一条路径的概率不一样,所以我们讨论了一种带有先验知识的搜索。
问题:带先验知识的量子搜索
权重判定问题的精确量子算法
权重判定问题:
我们得到的结果如下图所示:
最终,对所有的k和l,我们都可以得出其对应的量子算法复杂度。
求解线性方程组
输入:矩阵A和向量b,求解x使得Ax=b
(1)经典算法:高斯消元
(2)Harrow-Hassidim-Lloyd算法*
a)Input, Output
b)Cannot be used to find specified xi
c)Matrix A必须具有稀疏性
d)K-mean, classification, SVD, SVM, recommendation systems…
(3)Ambainis’2012对算法进一步做了改进,将复杂度降低到如下量级:
斜距阵线性系统求解
当我们想要拟合出一条直线,我们发现方程数量是远比未知数数量多的。
针对这个问题,我们提出了一个量子算法,发现也可以达到指数级别的加速。
我们同时也研究了如何对算法的电路进行优化,使其能够在近期NISQ设备跑一些量子算法,如何进行线路优化也是当前量子计算的重要课题。
量子随机游走
量子游走,我们不止可以向左或向右走,还可以产生向左和向右的叠加态。在走很多步之后,我们就得到了一个很大的叠加态。
(1)布尔公式求值:
AND-OR博弈树求解
(2)元素相异问题:
判定一个数组中的元素是否全部相异,而且能达到如下的复杂度加速
(3)三角形判定问题:
相对于经典算法,量子算法的数量还很少。
量子算法的设计比经典算法更加困难(量子力学特性限制,比经典有真正意义的加速),但发展空间和潜力巨大(经典算法数以千计,重要量子算法只有十到几十个),有机会取得根本性突破。
接下来,我们对量子计算的未来进行一下展望。
Hartree-Fock on a superconducting qubit quantum computer
最近几年,一些量子计算的实验装置被制造了出来。如谷歌的悬铃木芯片,通过经典量子混合的模式构造了一个量子电路,电路中的门上都带有大量参数。随后人们进行测量,同时还有一个目标优化函数,根据测量的结果反馈并反复迭代优化参数。
当下多数方法都采用了经典和量子混合的模式,通过量子产生一个纠缠态且有很多参数,通过测量等获得反馈并回来优化参数。
经典-量子混合框架
经典-量子混合计算框架:
(1)VQE, QAOA, QGAN, …
(2)图的最大割集(Max-Cut)
量子体积(Quantum Volume)
IBM在前些年仿照摩尔定律提出了量子体积这一概念。
一台量子设备的量子体积定义为2v:当且仅当它能够以“高概率正确”运行比特数和深度都为v的随机量子电路。
下面是IBM超导量子计算的一个路线图。
潜在应用场景——交通优化
德国大众公司和D-Wave合作进行了如下研究,整个流程更像是一种模拟计算。
丰田公司进行了交通灯优化。
潜在应用场景——机器学习
用机器学习来加速量子的研究,或者用量子计算做机器学习的问题都是正在发展的新兴方向。
量子多臂老虎机
最近,我们也从强化学习等方向做了一点工作。
多臂老虎机是强化学习中很重要的模型,老虎机其实代表的是目前拥有很多策略,但是每种策略的收益是一个随机变量。
我们需要探索不同策略并尽可能找出最好的策略。
我们将其推广到了量子多臂老虎机,同时证明了量子模型能取得比经典层面更好的悔值上界,如下所示。
潜在应用场景——金融
未来挑战
我们仍需要理解与刻画量子计算的能力和极限——量子可以在哪些问题上加速?最多可以加速到多少?
(1)量子计算能否在多项式时间内解决NP完全问题?
① 后量子密码,量子计算经典验证,…
(2)新型量子算法
① 困难问题的量子算法(例如图同构),量子机器学习的算法和理论,量子模拟与量子采样,变分量子算法,量子启发式算法…
(3)含噪中尺度量子系统(Noisy Intermediate-Scale Quantum Computing,NISQ)
① 量子纠错,分布式量子计算,电路压缩与化简,浅层量子电路算法…