Hacker Dōjo Workshop：
研究种类：量子算法
资助金额：80 USDT
Bounty链接：https://dorahacks.io/daobounty/227
分享者：YST
赏金发布链接：https://bscscan.com/tx/0x7c89e1a63c32f2adfb4ac3636d1c340fc7829a8bcbc3d0ef19ab59aeab00af42
本项目由Hacker Dōjo资助，文章转载请联系
Telegram: @DoraDojo0
WeChat: @HackerDojo0
E-mail: hackerdojo0@gmail.com
量子计算基础
（分享人：华中科技大学 路松峰）
1.一个物理实验
假设光从光源处穿过分光仪，光线会发生折射或反射现象，两个检测设备均能检测到50%光源。我们则推理光线会均匀反射或折射到相应检测设备。
 
通过实验验证其推理（如下图），光从光源0发出，实验表明0、1处均检测到50%光源，推理成立。
假定只有一个光子从光源发出，那么光子会出现在哪？继续进行实验，放置两块分光仪，并将原先两处检测设备替换成两面镜子，光线经过折射与反射，照射在检测设备上。通过上述实验推断，检测设备均能检测到光源。但实验结果显示，光源只能在一个检测设备上检测到，上方检测设备无法检测到光源。此实验结果与之前实验推理不一致。科学家通过大量实验得出结论—光子透过分光仪并不是随机反射或折射，而是反射和折射必然都会发生，但由于量子力学的不可观测性，使得上方检测设备无法观测到光子。
我们对此实验模型稍加改动，在光线线路上放置镜子M（如下图），B检测设备检测到25%光源，去掉镜子M，B检测设备检测到100%光源。实验得出结论，量子力学中一个光子同时处在两个分支，但经典概率学无法解释光子会选择哪种途径传播。
2.量子计算相关的基本概率
2.1量子比特
量子计算的基础是量子力学，量子力学中最重要的概念是量子比特。经典比特是二进制变量，其数值一般记作二进制中的0或1。在经典计算中，实际电路1视为高电压，0一般指0v电压，也就是地。量子比特的表现形式则不同，它不是通过数字而是由向量|0〉和|1〉表示。量子比特的物理形式不统一，由多种形式（光子、电子…）表示，但是数学形式已经统一。量子比特的状态由计算机态（0态或1态，对应狄克拉符号记法为｜0〉、｜1〉）的线性组合描述，通常称为叠加态。大多数情况下，量子比特｜0〉和｜1〉的叠加态|φ〉=α|0〉+β|1〉（要求|α|2+|β|2=1）其中α和β为复数。我们可以赋予这个二维系统一个几何表示：Bloch球，其中0为z轴，1为z轴的反方向，简单可以理解为平面上的0和1。
（Bloch球）
对于上述分光仪实验（如下图），光子在上面出现记成｜0〉，在下面出现记成｜1〉，合在一起叠加态就是|φ〉=α|0〉+β|1〉 = 1*|0〉+0*|1〉 = |0〉。
如果光子只出现在上面，α为1，β为0；如果两边均有光子，则α、 β≠0。｜0〉和｜1〉是向量 的缩写。
下图为简化版的Bloch球，任何情况下量子比特都为α|0〉+β|1〉，量子在二维空间里，α和β的数值可以有无限个，只需满足|α|2+|β|2=1。所以一个量子
比特的形式可以有多种，矩阵形式为
2.2量子力学的基本特点：
2.2.1非决定论
经典是决定的，如果给定当前系统足够的知识，那么未来是可以预测的，如牛顿力学、社会学、股票…（不能预测是因为知识不够），马克思、爱因斯坦都是决定论者。但是量子世界本质是不能预测的，相同的多个系统，在相同条件、相同时间下测量，其结论是不一致的。
2.2.2测不准或不确定性
经典是可观察的，如之前的光子实验，光子在两侧都能观测到，测量不会引起系统变化，相同的系统测量多次，条件相同结果就会相同。量子世界本质是不能测量的，如果测量则会引起坍塌到经典世界。在相同条件下进行多次测量，结果也会不同，测量速度会影响位置，反之亦然。量子力学中不确定性与量子叠加态有关。
2.3量子叠加
量子叠加，就是指一个量子系统可以处在不同量子态的叠加态上。例如，此时此刻“你”存在两个状态，一个是正在观看量子力学的直播课，另一个是在宿舍打游戏，用量子力学解释两个状态是同时存在的，但是两个状态却不能同时被观察到，一旦观察到其中一个状态，另一个状态就不会存在。此现象如同薛定谔的猫，猫就理应处于死猫和活猫的不确定状态，是一种所谓死和活的叠加状态中。微观世界中量子通常属于叠加态，但是在宏观世界中量子以何种形式存在没有确定的定论。两个量子也存在叠加态。 为一个量子， 为另一个量子， 2个量子结合的数学展开式为
用矩阵表示为
2.4量子纠缠
叠加 |φ〉=α|0〉+β|1〉可以是单个量子也可以是多个量子。在经典世界里量子纠缠是不存在的，纠缠是多个量子状态才可能出现，其不能写成积态（例如：｜00〉+｜11〉）例如，同时掷两枚硬币，一般情况会出现4种可能性（正反、正正、反正、反反），但是处于纠缠态的两枚硬币只会存在两种可能性（正反、反正）。将两枚硬币视为量子比特，如果其处于纠缠态，不论距离有多远，只要A硬币正面朝上，那么B硬币一定反面朝上，反之亦然。如果把纠缠态的量子分别放置于地球和月球，两个量子就像有心灵感应般，零延迟、发生同步反应。我们利用其原理可以实现量子通信。量子力学运用到计算中，通常有以下假设
量子力学假设1
任何一个孤立的物理系统（量子计算也是针对系统）都可以由一个复向量内积空间 （线性空间）来描述，系统由基向量描述。例如,单量子比特的系统就由|0〉和|1〉决定，系统任意时刻的状态都可以由叠加态|φ〉=α|0〉+β|1〉表示。系统是由基向量组成的状态向量描述。
量子力学假设2
在封闭的物理系统中，每一时刻都有一个状态与之对应演化|φ’〉=U |φ〉，我们称其为离散型量子力学变化，其中｜φ’〉视作初始状态，U为变化状态，同时薛定谔提出了连续性方程： 此公式适用于一切物理现象，其中H
为哈密特量，只要知道了哈密特量，任何系统都能完全解释。
量子力学假设3
量子测量由一组测量算子 {Mm}来描述。指标m与测量结果相关。测量前系统状态为|ψ>，则结果m发生的可能性由p(m) = <ψ|Mm+Mm|ψ>给出。因为量子测量会引起坍塌，所以量子测量总是在计算的最后进行。
量子力学假设4
复合系统的状态由子系统的状态的张量积组成。
2.4经典与量子对比
经典比特
可以完全地被测量
测量不会改变系统状态
可以拷贝
可以删除
量子比特
可以部分被测量
测量会改变系统状态
不能拷贝
不能删除
3.量子计算的历史
1900- Max Plank 提出 黑体辐射理论;标志着量子理论的诞生
1905-Albert Einstein 提出了光电效应理论。
1911- Ernest Rutherford 提出原子的行星模型
1913- Niels Bohr 提出氢原子的量子模型.
1923- Louis de Broglie 提出 实物粒子的波动性
1925- Werner Heisenberg 形成量子矩阵力学.
1926-Erwin Schrodinger 提出波西数的动态方程，薛定谔方程
1926-Erwin Schrodinger and Paul Dirac 证明了 海森堡的矩阵公式与迪拉克的代数表达与薛定谔的波方程是一致的.
- Paul Dirac 独立地， Max Born, Werner Heisenberg, and Pasqual Jordan3人联合起来获得了量子力学的完整公式
1926- John von Neumann 把希尔伯特空间的概念引入了量子力学
1927- Werner Heisenberg 提出不确定性原理
1936- Alan Turing 提出通用图灵机模型，UTM.
1936 - Alonzo Church 发表论文断言：任何可以计算的函数都可以用通用图灵机计算出来.
1945-ENIAC, 世界上第一台通用计算机，J. Presper Eckert and John Macauly.
1946-John von Neumann提出冯诺依曼体系结构.
1948 - Claude Shannon 发表通讯的数学原理.
1953- 第一台商用计算机 UNIVAC 1问世.
1961 -Rolf Landauer 断言：计算就是物理，研究计算中热量生成问题.
1973- Charles Bennet 研究计算的可逆逻辑.
1981- Richard Feynman 提出任何物理系统包括量子系统可以精确地被量子计算机模拟.
1982- Peter Beniof 突出图灵机的量子力学模型
1984 - Charles Bennet and Gilles Brassard 提出量子密码协议：BB84
1985- David Deutsch 重新定义了邱其-图灵假设.
1993 - Bennet, Brassard, Crepeau, Josza, Peres, Wooters *现了量子隐形传态
1994 - Peter Shor 大整数质因子分解量子算法.
1996- LK Grover 量子搜索算法
4.量子线路
4.1重写实验
将左下图实验抽象化形为右下图，光从光源0处发出，光子在上面出现记成｜0〉，在下面出现记成｜1〉，测量仪器1检测到100%光源。
将实验复杂化，在下面的分支增加一个延时器，在上面观察到光的概率是
，在下面观察到光的概率是
4.2线路分析
从数学上证明量子力学的正确性，将线路分成四部分①为初态，②‚为经过分光仪，③为经过延时器，④为再次经过分光仪。
我们从数学上来进行推算，初始状态时，上侧有光子，下侧没有光子（图1），所以初始状态是： 。通过量子力学推断，光子在
｜0〉、｜1〉都存在，结果如图2。线路第三部分光子经过延时器，延时器处于｜1〉线路上，所以｜1〉结果变化为 ，最终结果如图3。线路第四部分
光子进过另一个分光仪，经过推算结果为 。
实验最后得出的结果就是我们猜想的结果，所以量子力学完美地解释了其现象—光子在上下都会存在。我们用数学证实了其结果。
（图1） （图2） （图3）
分光仪实验的计算结果，实际上就是一个变换，我们可以用矩阵来表示这个变换，以一个光子为例，分光仪的变换用 来表示，延时器用 来表示，该式子是从左往右读，但计算方式是从右往左计算，从 开始，依次相乘，最终得到 。
该矩阵形式还可以继续简化，比如分光仪可以表示为 ，延时器可表示为 ，把两个分支合在一起，把分光仪、延时器用门电路形式为 。当然，门不同，运算也会不同，门有很多种，例如单量子门的话，常见的有非(NOT)门，即X中的0变成1,1变成0，此外，还有Z门，Y门…
当有两个量子比特时，我们可以用 线路来表示，矩阵式为
通常我们需要控制两个量子位门线路，如图 ，若上方点的线路为1的话，它可以把下面翻转，如果上面是0的话，下面并不做任何翻转，表示为
这叫控制U门，即将0变成1,1变成0的状态。若U变为X，我们叫做控制非(NOT)门，当第一个数字是0时，后面无论是0或1，状态都不变。当第一个数字是1
时，则后面的0变成1，1变成0，表示为 。
5.量子运算的应用
量子计算可以适用于加法、减法、函数运算。量子运算通常会有几个模块，一个S模块，一个C模块，S模块就是常规的加法（如图1）。C是进位的加法，可以用以下线路来表示，上面为S线路，下面为进位线路，也叫控制非门法（如图2）。如果是N位的话，实际上就是很多C和S 结合在一起，这也可以做加法。此外，我们也可以用量子来做函数运算，利用X²真值表来解量子函数f(x)=X²
（图1） （图2）
5.1大整数因子分解Shor算法
信息安全有两个重要的分支，一个是公钥密码，一个是私钥密码，私钥密码即加密和解密用的同一个秘钥，就像我们平常用Word加密，加密和解密用的是同一个密钥，用私钥密码计算时，最困难的在于密码保存，比如加密一个文档发给对方，为了安全起见，通常不可能把加密的文档和密钥同时给对方，这就给如何保存密码带来了麻烦。
公钥密码，加密和解密用的不同密钥，例如有两个密钥K1和K2，K1可保留同时用来解密，K2可公开但不能解密。
公钥算法为什么可以有两个不同的密钥呢？实际上这是一个数学难题，其实就是一个大整数因子分解的问题。比如15，可以由35得到，又比如21，可以由37算出，但若是一个数很大，要想算出它是由哪两个数相乘得来，就需要耗费大量的时间和精力。
5.2量子搜索
1994年，Shor等人提出的以大整数因子分解的量子多项式算法，在业内引起轰动，这就是Shor算法，实际上就是用的量子叠加态的思路。不过该算法是个特例，只能用来解决某一类问题。1996年，由Grover提出的Grover’s算法，有时也称为量子搜索算法，指一种在量子计算机上 运行的非结构化搜索算法，是一种通用算法，我们知道，人工智能，机器学习的很多算法，最终都归结于搜索，Grover就解决了搜索这一难题。
5.3量子通信
量子通信是指利用量子纠缠效应进行信息传递的一种新型的通讯方式，量子通信解决了私钥密码传输的问题，在经典计算机里，密码传输很困难，但利用量子力学原理，对量子态进行操控，在两个地点之间进行信息交互，可以有效解决信息安全问题。
利用固定的两个量子态纠缠的粒子A和B，他们分别表达一定的信息，以A为密钥，把B传送到另一地点，若想破译信息，根据量子纠缠原理，则必须用A粒子再次和B形成纠缠态方可破译，这大大提高了信息传递的安全性，且破译具有唯一性。
5.4量子纠错
量子纠错是现代量子信息处理领域的理论基础，它是为了解决量子计算机的错误回复问题而提出的一种理论定理。
5.5量子搜索算法
我们以一个例子，来比较经典算法和量子搜索算法的不同，从而更加直观地看到Grover算法在实际生活中对我们产生的重要影响。
（1）经典算法：
假设我们有N个未经排序的数据。如果使用经典算法寻找其中的某个数据X，条件是它（并且只有它）满足P（X）=TRUE,比方说X代表一个人的工号，P（X）是看他是不是现任CEO，那么你只能从第一个数据开始，一个一个地看它是不是CEO的工号，直到你瞎猫碰上死耗子。在这种算法中，计算复杂度是O（N）。最糟糕的情况，仍要找N-1次（如下图所示）。所以，我们尝试用Grover算法来解决这个问题。
（经典算法分析图）
（2）Grover算法（又称无序数据库搜索算法）：
在Grover算法中，我们可以将N个数据同时储存在log₂N个量子比特中，然后同时计算N个函数P（X）的取值，也就是同时看它是不是CEO的工号。在log₂N个量子比特所表示的量子态可以看做N个状态的叠加。在这个状态上做一次函数P（）在计算，就相当于同时在N个状态上做了N次P（）的计算。（如下图所示）
（Grover算法分析图）
但量子计算是不可观测的，这么多数据，你只能观察到一个，是或者不是，在这种情况下，能遇到正确答案的概率就会非常低，即1/N，这样做毫无意义也浪费时间，我们可以寻找一个更好的方法。
Grover算法为我们提供了这样一个思路，同时计算N个P（X）的取值后，先不要读取，而是通过量子操作略微增加结果为CEO工号的那个数据发生的概率。在每做一次Grover算法之后，结果是CEO的概率增加一次，经过多次的Grover算法以后，比如重复√N次之后，是CEO的正确结果变成了100%，其他结果都为0。（如下图所示）
（经过多次Grover算法后的意图）
7.量子通信与量子密码学
7.1量子隐形传态
比如Alice拥有一个量子比特｜X＞，她要把｜X＞传递给Bob,但是他们之间只有经典通道，这时候通常传不了，由于x不可观察，所以要想将信息传给Bob十分困难。我们可以通过以下方式来解决。
假定Alice和Bob分别还拥有一个纠缠的量子比特｜Z＞和｜Y＞，｜Z＞和｜Y＞处于纠缠态，只需Alice测量｜Z＞，然后把测量结果告诉Bob，Bob就可以得到｜X＞。也就是说，在此处，量子隐形传态涉及3个量子比特：Alice想传送的量子比特（有效载荷），以及她与Bob共享的一对处于纠缠态的量子比特（传输通道）。
7.2量子密码的安全性基础
基于原理：1.海森堡测不准原理 2.量子不可复制定理
基本特征：
1.无条件安全性
是指在攻击者具有无限计算资源的条件下仍不可能破译此密码系统。
2.对窃听的可检测性
是指两个用户之间通信受到干扰时，通信者根据测不准原理可以同步检测出干扰存在与否。
7.3 BB84协议
在量子传输过程中，需要使用到BB84协议。1984年，两位科学家Bennett和Brassard，联合提出了世界上第一个量子密钥分发协议——BB84协议，此后拉开了量子加密实用化的进程。
具体做法如下：
假设Alice以线偏振和圆偏振光子的四个状态方向为基础产生一个随机的量子比特串S={ , ,… },其中B={ , , ｜↗＞,｜↖＞ }，Alice通过量子传输信道将量子比特串S发送给Bob，Bob随机选择测量基序列来测量他收到的光子，其中Mi是线偏振光B1、圆偏振光B2之一，Bob通过经典信道通知Alice他所选定的测量基序列，Alice也通过经典信道通知Bob采用的测量基中正确的序号（在没有窃听的情况下，若Alice和Bob的测量基相同，则结果确定），Alice和Bob保存测量基相同的测量结果，放弃测量基不一致的测量结果，根据所选用的测量基序列的出错率判定是否有攻击存在。举例如图：
7.4量子密码的研究方向
1.量子密钥管理
量子密钥管理包括量子密钥产生、分配、存储和校验等几个部分，其中在理论上和技术方面最成熟的是量子密钥分配。
2.量子密码算法
与经典密码一样，量子密码的目的也是为了有效保护信息，并且这种保护也是通过变换现实的
3.量子认证
量子认证是量子密码中的一个重要组成部分，内容涉及量子认证码、量子签名以及量子信道认证等。
4.量子秘密共享
量子秘密共享已经成为量子密码的一个重要研究方向，在理论和实验上都取得了初步进展。
5.量子密码安全协议
量子密码安全协议主要包括量子掷币、量子比特承诺、量子不经意传输、量子安全多方计算等。
8量子计算的其他技术及未来展望
8.1量子计算的意义
1，摩尔定律已经失效，寻找新的计算模式 2，科学技术发挥赞趋势、国家重大战略需求
8.2量子计算机的基本要求
1）能长期保持相干性——与外界很好隔离的封闭量子系统
2）外界能够精确地控制其演化并读出结果——与外界有良好的耦合
8.3现有实现量子计算机物理体系现状
8.4量子计算平台和工具
1.本源量子云计算平台（中科大，郭光灿）
2.微软： Azure Quantum（开放，生态，Q#）
3.IBM： Quantum Experience
4.谷歌： OpenFermion （开源）量子编程框架Cirq
5.量子计算模拟 Qiskit https://www.qiskit.org/
6.量子机器学习 Pennylane
https://pennylane.ai/qml/ 支持GPU，支持Tensorflow和PyTorch
7.其他 Tensorcircuit、 Qpanda
8.5 未来研究方向
量子计算+机器学习/人工智能（姚期智：未来等于“量子计算+人工之智能”）人工智能擅长模式匹配，而这也是量子计算的优势。在未来几百年时间两者的融合之后，我们将需要思考谁将成为世界的主宰。
量子编程
(1) 量子编程语言
D-Wave的Qbsolv,命令式编程的QCL,函数式编程的Quipper, 微软Q#
(2) 量子编译
超导量子计算机（谷歌：悬铃木， IBM）
绝热量子计算机（D-Wave)
拓扑量子计算机（微软）
量子点量子计算机
钻石量子计算机
囚禁粒子量子计算机
光量子计算机（九章）
通用量子计算机
发展高速、精确的量子操控技术
新型量子信息存储载体的研究
绝热量子计算和量子仿真研究
抗噪声量子方法的探索：退相干机理及抑制方法研究
量子状态辨识
量子密码学
量子通信中的量子中继技术
