第1章量子计算和量子行走
春秋末期战国初期，先人墨子在《墨经》中定义了何为力——力，形之所以奋也，揭示了力是使物体运动的原因。人类对力学坚持不懈地探索，直到19世纪才将宏观世界的力学研究视角转向了微观世界。20世纪初期，研究微观粒子运动规律的物理学分支——量子力学创立了。量子力学的诞生使人类对微观世界乃至宇宙产生了新的思索。1981年，美国阿拉贡国家实验室基于量子力学理论提出量子计算，为量子力学赋予了具有信息时代特色的新生命。摩尔定律（Moore’s law）指出：每18个月，集成电路上可以容纳的晶体管数目将会翻倍。实际上，物理元件不能无限缩小，摩尔定律必然有终结的一天。致力于量子计算和量子计算机的研发在顺应未来科技发展的趋势中存在必然性。目前，量子计算呈现出“双轨并行”的发展模式，一方面量子计算机处于百家争鸣的研发之中，超导量子、离子阱、金刚石色心、核磁共振、D-Wave退火机以及线性光学已成为量子计算机研发的主流材料和技术；另一方面，用以在量子计算机上运行的量子算法百花齐放，竞相登场。1994年，Shor[1]提出以自己名字命名的质因数分解量子算法——Shor算法，因该算法仅为多项式时间复杂度，对依赖大质数乘积难分解特点的现代密码学的安全性提出严峻挑战，同时也为量子计算和量子算法的设计提供了强大的研究动力。1996年，Grover[2]提出量子版本的数据库搜索算法，相比经典算法实现了平方根加速，并总结出振幅放大这一量子算法设计的重要技巧，促进了量子行走算法在标记点搜索问题上的研究。2009年，HHL（Harrow，Hassidim，Lloyd）量子算法在求解线性方程组问题中以节省指数级时间开销而闻名[3]，大力推动了量子机器学习的发展[4-6]。
近年来量子计算在诸多领域布局，人们对其未来应用展开了一系列开创性的探索。例如，富士通集团采用量子启发退火算法协助日本邮船株式会社优化复杂的运输船只配载规划问题，拟提高调度效率。该项目在2021年9月首次投入使用，日本邮船株式会社预计，采用量子启发退火算法后年度船只配载时间将节省约4000小时[7]。北京字节跳动科技有限公司于2022年公开了关于量子计算在化学小分子特性仿真方面的理论成果，该成果将在工业化学领域起到积极的促进作用[8]。合肥本源量子计算科技有限责任公司联合中国建设银行推出了量子期权定价应用与量子VaR值计算算法，其运行速度与准确率均优于国际同类算法[9]。以量子VaR值计算为代表的量子金融应用将吸引大量资本涌入量子计算，并优先在生物、医药以及教育等领域快速布局，这将为量子计算的研发和应用注入新活力。
不仅如此，国际知名企业谷歌和IBM等致力于研发量子计算机，并通过社交媒体渲染“量子霸权”（quantum supremacy）概念（实为量子优越性），加剧了量子计算研发的紧迫感；国内以百度、阿里巴巴、腾讯和华为为代表的企业争先布局量子计算以挖掘其巨大应用潜力。此外，以潘建伟院士等为代表的团队近年来在量子行走[10]和超长距离量子密钥分发[11]领域捷报频传。特别是“十四五”规划中，量子信息被列为具有战略性、前瞻性的前沿领域之一，使量子计算的概念被大众所熟知。未来，量子计算将在军事、化学、生物、信息安全、金融等众多领域发挥重要作用[5，12-13]。
本章涵盖了量子计算所涉及的基本概念及常用运算，是后续量子行走在复杂网络中应用的研究基础。
1.1量子计算基本概念
本节内容包括：狄拉克符号和量子比特、常见的运算和算符、量子线路基本概念以及量子力学的基本假设。
1.1.1狄拉克符号和量子比特
狄拉克符号（Dirac notation）是量子力学中对向量特有的表达，例如，向量u对应的狄拉克符号为
（1-1）
（1-2）
式中，T为转置符号；u为的共轭转置（conjugate transpose）；为元素的共轭值，仅在其包含虚数（imaginary number）时生效。在实际运算中，的计算可能更为简单，它与网络表示学习的浅层嵌入（shallow embedding）或图神经网络中的one-hot编码方式相似。当中仅有一个元素为1而其余元素均为0时，称之为标准正交基（orthogonal basis）或计算基（computational basis），本书统称为标准基。假设在具有n个节点的复杂网络中，任意节点均采用标准基的形式表达，则有。
在本书中，网络节点对应的标准基和量子行走中的硬币态均采用如公式（1-3）的形式表达。
量子比特（qubit）是量子计算中*小的信息单位，在表达形式上它是单位向量的线性组合，也称量子位。任意量子比特均采用狄拉克符号表示，设，一个由0和1量子比特构成的量子态（state）可以定义为10
（1-4）
式中，和表示概率振幅（probability amplitude），一般采用复数表示。对于经典比特，和可以代表具有对立关系的信息，如真和假。而在量子比特中，和本身便是“矛盾对立统一体”，因为二者均既包含又包含。量子比特这种“你中有我、我中有你”的编码方式所包含的信息更为丰富，也是量子比特具备潜在并行特性的主要原因。以量子（衍生）群体智能算法为例[14]，基于和形式对初始种群的双链编码方式可以避免种群在搜索过程中陷入局部*优。在本书介绍的量子行走中，和分别代表抛硬币后得到的正面向上或向下的硬币态；在其他量子算法中，和可以区分目标数据和非目标数据；而在量子线路中，和可以作为控制位影响算符的计算，输出期望的结果。公式（1-4）中，向量和的线性组合被称为叠加（superposition）态。当时，处于均等叠加态。在封闭量子系统（isolatedquantumsystem）中，如下条件是恒成立的：
（1-5）
式中，表示针对复数的模平方运算。公式（1-4）更为泛化的表达是将该量子态置于Bloch球内，引入角度.和相位参数，如，其中为虚数。因本书的核心内容较少涉及该部分知识，不再赘述，感兴趣的读者可参考文献[13]、[15]的详细介绍。
1.1.2常见的运算和算符
1.内积和外积
对于采用狄拉克符号表示的向量和量子态，量子计算中常见的运算便是内积（inner product）与外积（outer product），以公式（1-1）的和公式（1-2）的为例，向量内积的结果对应一个值，例如：
（1-6）
（1-7）
本书中，内积运算多在量子测量阶段发挥作用，利用量子行走算法的测量结果为网络的节点和链路打分；而外积运算主要用作构造演化算符，为离散时间量子行走提供行走的动力或为粒子指定行走路径。关于量子测量和演化，参考1.1.4节。
2.张量积和直和
当运算对象为矩阵或向量时，量子计算中更为广泛的运算为张量积（tensor product）和直和（direct sum）。张量积采用符号表示，假设存在行列数分别为和的矩阵和矩阵，二者的张量积可以表达为
（1-8）
依此类推，行列数分别为m×n和p×q的矩阵Am×n和矩阵Bp×q的张量积，其结果为矩阵Cmp×qn。值得注意的是，在量子计算中，张量积符号常被省略，如：
（1-9）
关于直和，全书采用符号表示。仍以矩阵A2×1和矩阵B2×3为例，二者的直和可表达为
（1-10）
显然，行列数分别为m×n和p×q的矩阵Am×n和矩阵Bp×q，其直和运算结果为(m+p)×(n+q)的矩阵C(m+p)×(n+q)。在本书中，张量积及直和运算主要用于构造封闭量子系统的希尔伯特空间。关于希尔伯特空间，参考1.1.4节。
3.三种常见的算符
算符（operator）沿用了物理学的翻译习惯，在量子图像处理等领域中常称之为算子[16]。下面介绍三种常见算符，即Hadamard算符、Fourier算符和Grover算符。Hadamard算符的表达相对简单，它可以视为对和量子比特外积结果的累加：
（1-11）
Fourier算符可以看作由相位参数.控制的矩阵，设相位参数.N为算符的行列数，为虚数。则Fourier算符F中第p行、第q列元素的计算方法为
（1-12）
式中，和从开始计数。因包含虚数，公式（1-12）在计算过程中会引入欧拉公式（Euler formula）将原式转化为三角函数，欧拉公式定义为
（1-13）
假设Fourier算符行列数为4，结合公式（1-12）和公式（1-13），则定义Fourier算符F为
（1-14）
展开
