基于变分量子电路的量子机器学习算法综述

于瑞祺; 张鑫云; 任爽

doi:10.7544/issn1000-1239.202330979

基于变分量子电路的量子机器学习算法综述

北京交通大学计算机科学与技术学院　北京　100044

基金项目: 国家自然科学基金项目（62072025）

详细信息

作者简介:
于瑞祺: 2002年生. 硕士研究生. 主要研究方向为量子计算、机器学习

张鑫云: 1997 年生. 博士. CCF 会员. 主要研究方向为机器学习、3维计算机视觉量子计算

任爽: 1981 年生. 博士，副教授，博士生导师. CCF会员. 主要研究方向为机器学习、量子计算、3D计算机视觉

通讯作者:
任爽（sren@bjtu.edu.cn）

中图分类号: TP18
计量
- 文章访问数: 131
- HTML全文浏览量: 38
- PDF下载量: 49
出版历程
- 收稿日期: 2023-12-04
- 修回日期: 2024-11-18
- 录用日期: 2025-01-08
- 网络出版日期: 2025-01-08

A Review of Quantum Machine Learning Algorithms Based on Variational Quantum Circuit

School of Computer Science & Technology, Beijing Jiaotong University, Beijing 100044

Funds: This work was supported by the National Natural Science Foundation of China (62072025).

More Information

Author Bio:
Yu Ruiqi: born in 2002. Master candidate. His main research interests include quantum computing and machine learning

Zhang Xinyun: born in 1997. PhD. Member of CCF. His main research interests include machine learning, 3D computer vision, and quantum computing

Ren Shuang: born in 1981. PhD, associate professor, PhD supervisor. Member of CCF. His main research interests include machine learning, quantum computing, and 3D computer vision

摘要

摘要:
随着数据规模的增加，机器学习的重要性与影响力随之增大. 借助量子力学的原理能够实现量子计算，结合量子计算和机器学习形成的量子机器学习算法对经典机器学习算法理论上能够产生指数级的加速优势. 部分经典算法的量子版本已经被提出，有望解决使用经典计算机难以解决的问题. 当前受量子计算硬件所限，可操控的量子比特数目和噪声等因素制约着量子计算机的发展. 短期内量子计算硬件难以达到通用量子计算机需要的程度，当前研究重点是获得能够在中等规模含噪声量子（noisy intermediate-scale quantum，NISQ）计算设备上运行的算法. 变分量子算法是一种混合量子-经典算法，适合应用于当前量子计算设备，是量子机器学习领域的研究热点之一. 变分量子电路是一种参数化量子电路，变分量子算法利用其完成量子机器学习任务. 变分量子电路也被称为拟设或量子神经网络. 变分量子算法框架主要由5个步骤组成：1）根据任务设计损失函数和量子电路结构；2）将经典数据预处理后编码到量子态上，量子数据可以省略编码；3）计算损失函数；4）测量和后处理；5）优化器优化参数. 在此背景下，综述了量子计算基础理论与变分量子算法的基础框架，详细介绍了变分量子算法在量子机器学习领域的应用及进展，分别对量子有监督学习、量子无监督学习、量子半监督学习、量子强化学习以及量子电路结构搜索相关模型进行了介绍与对比，对相关数据集及相关模拟平台进行了简要介绍和汇总，最后提出了基于变分量子电路量子机器学习算法所面临的挑战及今后的研究趋势.
- 量子计算 /
- 量子机器学习 /
- 变分量子算法 /
- 量子神经网络 /
- 量子深度学习 /
- 量子强化学习
Abstract:
As the scale of available data increases, the importance and impact of machine learning grows. It has been found that quantum computing can be realized with the help of the principles of quantum mechanics, and the quantum machine learning algorithm formed by combining quantum computing and machine learning can theoretically produce exponential acceleration advantages over classical machine learning algorithms. Quantum versions of many classical algorithms have been proposed and they may solve problems that are difficult to classical computers. At present, limited by the quantum computing hardware, the number of controllable qubits, noise, and other factors restrict the development of quantum computers. Quantum computing hardware is unlikely to reach the level needed for universal quantum computers in the short term, and current research focuses on the algorithms that can run on noisy intermediate-scale quantum (NISQ) computers. Variational quantum algorithms (VQAs) are hybrid quantum classical algorithms which are suitable for current quantum computing devices. Related research is one of the research hotspots in the field of quantum machine learning. Variational quantum circuits (VQCs) are parameterized quantum circuits (PQCs) used in variational quantum algorithms to solve quantum machine learning tasks. It is also be called Ansatz and quantum neural networks (QNNs). The framework of variational quantum algorithm mainly contains five steps: 1) Designing the loss function according to the task. Designing parameterized quantum circuits as model and initializing parameters. 2) Embedding classical data. The classical data is pre-processed and encoded to the quantum state. If quantum data is used as input, it only needs to be pre-processed without encoding. 3) Calculating the loss function through parameterized quantum circuit. This step is where quantum advantage comes in. 4) Measuring and post-processing. Through quantum measurement operation, the quantum superposition state wave packet collapses into classical state. The classical data can be obtained after post-processing. 5) Optimizing the parameters. Updating parameters and optimizing the model with classical optimization algorithms and then returning to step 3 until the loss function converges after several iterations. We can obtain a set of optimal parameters. The final result is the output of the optimal model. This paper reviews the basic theory of quantum computing and the basic framework of variational quantum algorithm, and further introduces the application and progress of variational quantum algorithm in the field of quantum machine learning, then reviews supervised quantum machine learning including quantum classifiers, unsupervised quantum machine learning including quantum circuit born machine, variational quantum Boltzmann machine and quantum autoencoder, semi-supervised quantum learning including quantum generative adversarial network, quantum reinforcement learning, and quantum circuit architecture search in detail. Next, this paper compares the models and analyses their advantages and disadvantages, and briefly discusses and summarizes the related datasets and simulation platforms that can reproduce the introduced models. Finally, this paper puts forward the challenges and future research trends of quantum machine learning algorithms based on variational quantum circuit.
- quantum computing /
- quantum machine learning /
- variational quantum algorithm /
- quantum neural network /
- quantum deep learning /
- quantum reinforcement learning

HTML全文

电子设备广泛应用于与国家基础设施和民众生活紧密相关的各项领域. 在这些设备中，印刷电路板（printed circuit board，PCB）被誉为“电子产品之母”. PCB不仅为电子元器件提供了电子元器件的支持和电气连接，还承担着电路的载体角色，是电子设备不可或缺的核心组成部分^[1].

当前，随着集成电路技术的迅猛发展，PCB复杂度也在显著增加. 这种复杂度体现在多个方面：不断增加的线网（net）和引脚（pin）数量、多达十数层的PCB层数、极高的引脚密度、独特的物理限制以及高速PCB设计所带来的信号完整性问题^[1]等等，这就使得无法像过去那样仅仅使用人工对设计规则予以逐一检查，因此，以往那种籍由个人经验进行的PCB手工布线成为了一项耗时且容易出错的工作^[2]，传统的设计流程变得不再适用^[3-5]. 有鉴于此，复杂的PCB设计现多依赖于电子设计自动化（electronic design automation，EDA）工具处理以实现布线效率的优化，以最大限度地满足电子设计周期的需求^[6-8]. 利用EDA进行的PCB设计，通常包括原理图绘制、结构设计、布局、布线等流程^[9]. 其中布线问题是最为关键的问题之一^[10-11].

在具有复杂线网的PCB电路布线问题中，群组布线问题尤为重要. 此问题涉及将人工指定的多个线网视作群组，继而将它们以彼此相邻、长度相近的布线方式加以连接. 如何在不违反设计规则约束（design rule constraints，DRC）的条件下有效利用有限的布线空间并提高布线成功率是群组布线需要研究的关键问题.

本文主要贡献如下：

1）在使用Hanan网格方法构图后，在构图过程中引入一种面合并算法以及合并边方法以缩减原始Hanan网格的规模，在有效减少后续构建带权有向图的复杂度的同时，解决了传统方法得到的网格构图通常有一定量冗余信息的问题；

2）提出一种基于带权有向图的群组布线算法，利用得到的合并边及其位置关系等信息构建带权有向图，实现对群组布线问题的数学建模，从而克服传统网格化方法易受网格精度以及网格数量限制的缺陷；

3）提出一种与路径规划算法相适配的详细布线算法，将详细布线问题分解为多种基本情形考虑，设计数种基本线形以应对各种可能的布线情形，使算法具备实际应用价值，避免详细布线算法与路径规划算法不适配的问题.

1. 相关工作

PCB布线问题通常可被划为逃逸布线（escape routing）与区域布线（area routing）2个阶段^[12]，逃逸布线阶段主要负责将线网从引脚布线至组件边界，区域布线阶段则负责对逃逸至组件边界的线网进行连接，而群组布线一般在区域布线阶段进行. 群组布线问题就具体场景而言，又可简化为若干子问题，典型的有总线布线. 总线布线与群组布线的区别在于，它会在布线前预先进行分组，将预计需要一起布线的线网划分为一组总线^[13]，而群组布线可以在布线时确定群组，也可以进行交互式布线，具有较大的灵活性. 印刷电路板群组布线是商业布线工具中重要的组成部分，然而，关于印刷电路板群组布线问题的相关研究却鲜少出现在近年来的公开文献当中，因而对该问题的研究只能参考其子问题总线布线. 对于总线布线而言，其中一种分类依据是根据布线时有无轨道约束划分为有轨道和无轨道总线布线问题. 由于未经总线分组，可能存在群组中线网较多的情况，这将导致群组中线网所占用的总线宽比原先总线布线中各总线组分别占据的线宽更大，从而给实际布线带来新的挑战.

有些研究不针对特定阶段的布线问题，而是专注于更一般的印刷电路板自动布线问题. 如Lin等人^[3]提出了一种具有并发分层布线功能的全阶段印刷电路板布线方法，该方法基于布尔可满足性问题（boolean satisfiability problem，SAT），但是该方法只适用于解决球栅阵列（ball grid array，BGA）封装的印刷电路板布线问题^[14]. Lin等人^[4]则提出了一种全板布线算法，在构图阶段使用了均分网格，可以对非BGA封装进行布线，并且可以进行多层差分对布线. 但是该方法在复杂情况下的布通率难以达到100%^[14]. He等人^[15]提出了一种2阶段印刷电路板布线算法，该算法的2个阶段分别为基于蒙特卡洛树搜索^[16]（Monte Carlo tree search，MCTS）的全局布线和基于A*的详细布线，能够进行BGA和非BGA封装布线. 但是该方法是一种布线仿真方法，所使用的例子为简化后的现实电路，是一种理想化的场景，因而无法直接应用于复杂的工业界样例^[17].

印刷电路板有轨道总线布线问题只允许在给定的布线轨道上进行布线. 对于这一问题，Hsu等人^[18]提出了一种基于有向无环图（directed acyclic graph，DAG）的总线布线算法. 算法利用最长公共子序列（longest common subsequence, LCS）、Dijkstra算法以及拆线重布的方法优化布线. 然而，该算法的问题在于，可能会产生大量的间距违规，并且在初始拥塞区域过多时，无法有效消除拥塞^[19]. Zhang等人^[20]提出了一种基于迷宫布线和SAT的总线布线算法. 基于多级框架的总线布线器MARCH^[21]是一种基于并发和多层次方案的总线迷宫布线方法，它由粗粒度的拓扑感知路径规划和细粒度的轨道分配组成，应用了有效的拆线布线方案. Kim等人^[22]提出了一种拓扑感知总线布线算法，使用专门针对总线级别的3D平铺网格进行布线拓扑生成. 但是这些算法大都聚焦于有轨道总线布线问题，具有一定的特殊性，通常难以扩展到更加一般的无轨道约束总线布线问题.

近年来，也有几种算法被提出以解决无轨道约束的某些总线布线问题，它们通常需要依赖网格来进行路径规划和实际布线. 其中一些算法事先预置均分网格：Cheng等人^[23]提出了一种考虑障碍物的长度匹配总线布线算法，该算法利用先深度优先搜索后广度优先搜索的思想进行布线，并在流程中加入了拆线重布环节. Yan等人^[24-25]提出了基于长度匹配的总线布线算法，利用带权无向图表示区域之间的布线资源，并使用最大流算法寻找线网匹配. 上述算法将特殊设计约束即长度匹配约束作为考虑重点.

另一些算法则构建Hanan网格：Kong等人^[26]通过构建冲突图和更新Hanan网格来规划路径，使用关键割减少拥塞.Wu等人^[27]采用整数线性规划（integer linear programming，ILP）方法，在动态的Hanan网格图上完成全局总线布线，该算法同样利用关键割方法解决拥塞问题.ILP方法可以提供总线布线的全局视图，但可能需要相当长的时间^[28].

为解决群组布线问题，本文提出一种使用面合并算法缩减Hanan网格规模，利用基于带权有向图的群组布线算法，在有效表示电路板上的布线资源的同时避免传统网格方法易受网格精度和数量限制的缺陷. 同时采用具有多线避让功能的启发式搜索算法，该搜索算法在自动布线的同时也支持人工引导布线方向，这在有效降低时间开销的同时保证了布线质量. 最后算法使用了一种适用于所提出的路径规划算法的详细布线算法，该方法具有较高的运行效率.

2. 问题描述

首先输入一组需要进行群组布线的双端线网（net） $\mathcal{N}$ ，以及这些线网所包含的一组引脚（pin） $\mathcal{P}$ ，还有印刷电路板上的一系列障碍物如过孔（via）、禁行区等，印刷电路板的分层信息，此外还有一系列设计规则约束等. 给定双端线网的每对引脚必须在不违反设计规则约束的前提下相互连接. 印刷电路板群组布线问题需要遵循的设计规则约束如下：

1）由2点确定的最短轨迹即最小线长必须大于等于允许的最小线宽；

2）走线必须满足线与线之间、线与各种障碍物之间的最小线间距；

3）同层的走线之间不允许存在交叉；

4）走线拐角角度必须是135°且走线方向必须与印刷电路板板的x轴呈45°的整数倍；

5）所有引脚的走线尽量汇聚；

6）所有引脚的走线拓扑尽量相似；

7）所有引脚的走线长度尽量相近.

该问题的目标是在不违反设计规则约束的前提下，最大化连接的线网对数，即布通率尽可能的高；在此基础上，布线时间尽可能的短.

3. 群组布线算法

群组布线算法流程如图1所示. 首先，构建Hanan网格图，并在构建完成后对它进行边合并. 接着，利用前述得到的合并边信息构建带权有向图，完成对电路板上布线资源的表示. 然后，利用一种具有多线避让功能的启发式搜索算法来进行布线的边序列搜索，继而进行路径规划. 最后，通过将布线归类为数种可能的情况分别考虑，完成详细布线并得到群组布线的最终结果. 在详细布线步骤前，若线网未规划完毕，就会重新进行启发式搜索，直到完成所有失败线网的路径规划为止.

图 1 群组布线算法流程

Figure 1. Grouping routing algorithm flow

下载: 全尺寸图片幻灯片

3.1 构建Hanan网格图

为了能够有效记录PCB中的各种布线资源，例如各器件、各障碍物的大小和坐标，以及它们之间的相互位置关系等，传统的做法是将它们以网格图的方式加以表示. 典型的网格图有Hanan网格图. 在几何学中，对平面中有限点的集合构造Hanan网格将会对集合中的每个点构造横线以及竖线^[29]. 而在实际应用中，Hanan网格在构图时会对点集中的每个点进行横向或是纵向延伸，直到延伸线碰触到其他器件的边界抑或是PCB板边界为止. 器件如焊盘、通孔的边界会在考虑器件与走线之间的最小间距之后以矩形包围盒的方式予以体现. 随后，在构图结束时，该方法便能够得到顶点、边以及网格之间的邻接关系.

3.2 基于Hanan网格图的面合并以及合并边

Hanan网格图，构建示意图如(a)所示. 从示意图中不难看出，Hanan网格构图存在有易受网格精度影响的缺陷. 以Hanan网格 ${c}_{1}$ 也即面 ${c}_{1}$ 为例，显然当走线线宽超过该网格的宽度时，走线便无法从竖直方向顺利通过，因而对布线资源造成了浪费. 更糟糕的是，当网格的划分越稠密时，这一问题便会越明显，在极端情况下甚至可能存在无法布线的情况. 有鉴于此，本文提出了构造基于Hanan网格图的面合并以及合并边算法以克服这一缺陷.

图 2 网格构建示意图

Figure 2. Diagram of grid construction

下载: 全尺寸图片幻灯片

为了有效缩减问题规模，需要对Hanan网格图进行面合并. 算法首先需要确定面合并的顺序，不失一般性，算法按从左到右，自下而上的顺序进行面合并. 假设整体布线方向为水平方向. 以下给出面合并算法，算法从对角线、纵向以及横向3个方向尝试进行面合并，在面合并遇到障碍物或是相邻面存在宽度小于线宽与线间距之和时停止.

面合并算法步骤如算法1所示：

算法1. 面合并算法.

输入：Hanan网格图 $H$ ；

输出：面合并后的Hanan网格图 ${H}'$ .

① 设图 $H$ 中所有面的集合为 $F$ ，设图 $H$ 中所有障碍物包围盒的边集合为 $Ob$ ，设由面的左下角坐标组成的最小优先队列 $Q\ne \varnothing$ ，设ℓ=1；

② while ℓ≤3

③ 　for $f\in F$

④ 　　if 当前面 $f$ 的任意一条边 $e$ 与 $Ob$ 中的所有边 $obst$ 都不存在相交 then

⑤ 　　　 $Q\leftarrow Q.push\left(\left\langle{{f}_{lbx},{f}_{lby}}\right\rangle\right)$ ；

⑥ 　　end if

⑦ 　end for

⑧ 　while $Q\ne \varnothing$

⑨ 　　选择 $Q$ 中队首元素对应的面 $f$ ，面 $f$ 的左下角坐标为 ${f}_{lb}\left\langle{{f}_{lbx},{f}_{lby}}\right\rangle$ ，右上角坐标为 ${f}_{rt}\left\langle{{f}_{rtx},{f}_{rty}}\right\rangle$ ，它们之间构成区域 $area$ ；

⑩ 　end while

⑪ 　while 当前区域 $area$ 内的面均存在于 $Q$ 中

⑫ 　　if 当前区域的相邻面的长或宽不大于线宽与线间距之和 then

⑬ 　　　break；

⑭ 　　else

⑮ 　　　if ℓ=1 then

⑯ 　　　　根据图 $H$ 的邻接关系寻找位 $\text { area }$ 斜右上方的面 ${f}_{rt}'$ ，该面左下角顶点与 $area$ 右上方顶点重合. 令 ${f}_{rt}'$ 的右上角坐标为 ${f}_{rt}'\left\langle{{f}_{rtx}',{f}_{rty}'}\right\rangle$ ，若 ${f}_{lb}$ 与 ${f}_{rt}'$ 围成的区域中的面均存在于 $Q$ 中，则 ${f}_{lb}$ 与 ${f}_{rt}'$ 之间构成区域 $area$ ；

⑰ 　　　end if

⑱ 　　　if ℓ=2 then

⑲ 　　　　根据图 $H$ 的邻接关系寻找与 $area$ 正上方的面 $f'_{{{top}}}$ ，该面右下角顶点与 $area$ 右上方顶点重合. 令 $f'_{{{top}}}$ 的右上角坐标为 $f'_{{{top}}}$ 〈 $f'_{rtx}, f'_{rty}$ 〉，若 ${f}_{lb}$ 与 ${f}_{rt}'$ 围成的区域中的面均存在于 $Q$ 中，则 ${f}_{lb}$ 与 ${f}_{rt}'$ 之间构成区域 $area$ ；

⑳ 　　　end if

㉑　　　if ℓ=3 then

㉒　　　　根据图 $H$ 的邻接关系寻找与 $area$ 正右方的面 $f'_{{{right}}}$ ，该面左上角顶点与 $area$ 右上方顶点重合. 令 $f'_{{right}}$ 的右上角坐标为 $f'_{{right}}$ 〈 $f'_{rtx}, f'_{rty}$ 〉，若 ${f}_{lb}$ 与 $f'_{{{rt}}}$ 围成的区域中的面均存在于 $Q$ 中，则 ${f}_{lb}$ 与 ${f}_{rt}'$ 之间构成区域 $area$ ；

㉓　　　end if

㉔　end while

㉕　　　让包含在 $area$ 中的面f从 $Q$ 中出队；

㉖　　　if (区域包含的面f个数)>1 then

㉗　　　　根据 $area$ 更新集合 $F$ ，将区域作为合并面，更新图 $H$ 中区域包含的所有面的邻接关系；

㉘　　　end if

㉙　　　ℓ++；

㉚end while

㉛return 合并面后的Hanan网格图 ${H}'$ .

算法1步骤②的循环在常数项时间内可以完成. 算法在步骤③~⑦使用了1次循环，时间复杂度为 $O\left(n\right)$ . 而算法的主要时间花费则集中在步骤⑧~㉘中所包含的步骤，它包含了2次循环，最坏时间复杂度为 $O\left({n}^{2}\right)$ . 综上，算法的整体时间复杂度为 $O\left({n}^{2}\right)$ .

当整体布线方向为竖直方向时，只需将算法1中的步骤⑱㉑交换即可. 假设图2(a)中线段AA'以及线段BB'的长度小于线宽与线间距之和，其他部分除非长度与它们相等，否则长度均大于线宽与线间距之和. 根据上述算法，首先在(a)中选择位于左下角的Hanan网格 ${c}_{3}$ ，继而沿对角线向右上方进行扩展. 由于扩展后得到的合并面 $m{c}_{1}$ ，其相邻面 ${c}_{2}$ 的宽度小于线宽与线间距之和，因此此次合并无效. 而在扫描至Hanan网格 ${c}_{4}$ 时，根据算法将其扩展至合并面 ${mc}_{2}$ ，在检查后发现此次合并有效，因此合并面 ${mc}_{2}$ 便能够得到保留.

而传统的Hanan网格构图，只能在构图结束后得到合并边中的数段短边，以(b)为例，在Hanan点 ${v}_{1}$ ， ${v}_{2}$ 之间，它仅仅能得到其中的8段短边，这将对后续的布线规划造成困难. 有鉴于此，本文提出了一种边合并方法. 该方法将障碍物包围盒或者边界线都视为障碍物线，以(b)为例，它能够得到以Hanan点 ${v}_{1}$ ， ${v}_{2}$ 为端点的一整条合并边. 该方法的具体步骤如下：

首先，该方法会扫描所有Hanan边，之后，该方法对位于障碍物线之间且具有相同横坐标或纵坐标的线段进行合并，所得到的边即为合并边. 在得到合并边之后，该方法将位于障碍物线之间且具有相同横坐标或纵坐标的线段予以删除. 重复这一过程，该方法便能够得到全部合并边.

3.3 构造带权有向图

这一阶段主要是利用合并边构造带权有向图的算法，将合并边的邻接关系以及通道容量大小保存至有向图中.

算法将所有合并边按照一定顺序进行排序，不失一般性，可将竖直边按照竖直坐标从小到大排序，水平边同理. 随后，算法将排序后的每一条合并边都抽象为有向图 $G$ 中的2个顶点 ${v}_{i1}^{dir1},{v}_{i2}^{\mathrm{d}\mathrm{i}\mathrm{r}2}$ ，以水平边为例，它表示了布线的2个方向，即走线自上而下穿过该边（顶点的方向dir记作up）以及走线自下而上穿过该边（顶点的方向dir记作down），竖直边同理（顶点的方向dir分别记作left，right）. 所有顶点构成顶点的集合 $V(G)$ .

随后，算法从顶点集合 $V(G)$ 中按照排序后的顺序取出顶点对 ${v}_{i}^{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{i}}$ ， ${v}_{j}^{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{j}}$ ，并尝试在它们之间构造边 ${e}_{ij}$ . 它们所对应的合并边记作 ${HE}_{{v}_{j}}$ 及 ${HE}_{{v}_{j}}$ . 构造时遵循以下原则：

1）若 ${HE}_{{v}_{j}}$ 和 ${HE}_{{v}_{j}}$ 相互平行，则有：

diri和dirj方向相反的顶点对之间不能构造边.(a)所示，走线显然无法在从上往下穿过 ${HE}_{{v}_{1}}$ 的同时再从下往上穿过 ${HE}_{{v}_{2}}$ ，因此顶点 ${v}_{1}^{\mathrm{u}\mathrm{p}}$ 和 ${v}_{2}^{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}$ 之间无法构造边.

图 3 顶点对应合并边相互平行时构造边的几种情形

Figure 3. Vertices correspond to several cases in which edges are constructed when merged edges are parallel to each other

下载: 全尺寸图片幻灯片

${HE}_{{v}_{j}}$ 及 ${HE}_{{v}_{j}}$ 之间若不存在相错关系，则它们之间不能构造边. 如(b)所示，走线在穿过 ${HE}_{{v}_{1}}$ 和 ${HE}_{{v}_{2}}$ 的过程中，必然会经过其他顶点对应的合并边（图中未直接画出），因此顶点 ${v}_{1}^{up}$ 和 ${v}_{2}^{up}$ 之间无法构造边.

${HE}_{{v}_{j}}$ 及 ${HE}_{{v}_{j}}$ 之间若为障碍物，则它们之间不能构造边. 示意图如图3(c)所示.

若 ${v}_{i}^{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{i}}$ 或 ${v}_{j}^{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{j}}$ 已经存在相互平行的连边的，不能构造边. 如(d)所示，不妨设此时坐标已经按照y轴坐标从大到小排序（从小到大排序同理），则 ${v}_{1}^{up}$ 和 ${v}_{2}^{up}$ 将先行构造边，该边记作 ${e}_{12}$ . 显然此时在 ${v}_{1}^{up}$ 和 ${v}_{3}^{\mathrm{u}\mathrm{p}}$ 之间便无法再构造边，因为走线在通过 ${v}_{1}^{up}$ 之后，必须先经过 ${v}_{2}^{up}$ 才能到达 ${v}_{3}^{up}$ .

边的容量 $cap\left({e}_{ij}\right)$ 按及 $H E_{v_{j}}$ 之间投影的交叠长度计算. 如(e)所示， ${HE}_{{v}_{1}}$ 在合并边 ${HE}_{{v}_{2}}$ 上的投影为线段AB，线段AB的长度即为边的容量 $cap\left({e}_{ij}\right)$ .

2）若 ${HE}_{{v}_{j}}$ 和 ${HE}_{{v}_{j}}$ 相互垂直，则有：

${HE}_{{v}_{j}}$ 及 ${HE}_{{v}_{j}}$ 之间若不存在交叉关系，则它们之间不能构造边. (a)所示，走线在穿过 ${HE}_{{v}_{1}}$ 和 ${HE}_{{v}_{2}}$ 的过程中，必然会经过其他顶点对应的合并边（(a)未直接画出），因此顶点 ${v}_{1}^{\mathrm{u}\mathrm{p}}$ 和 ${v}_{2}^{\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}}$ 之间无法构造边.

图 4 顶点对应合并边相互垂直时构造边的几种情形

Figure 4. Several cases of constructing edges when vertices correspond to merging edges perpendicular to each other

下载: 全尺寸图片幻灯片

${HE}_{{v}_{i}}$ 及 ${HE}_{{v}_{j}}$ 之间若存在障碍物，则它们之间不能构造边；示意图如图4(b)所示.

${HE}_{{v}_{i}}$ 及 ${HE}_{{v}_{j}}$ 之间若相交，则交叉点将线段 ${HE}_{{v}_{i}}$ 及 ${HE}_{{v}_{j}}$ 分割为4个部分，分别记做 ${HE}_{{v}_{i1}}$ ， ${HE}_{{v}_{i2}}$ 以及 ${HE}_{{v}_{j1}}$ ， ${HE}_{{v}_{j2}}$ . 每条走线每次有且可能通过其中2条线段所围成的区域. 不失一般性，不妨设走线可能通过的其中2条线段为 ${HE}_{{v}_{i1}}$ 以及 ${HE}_{{v}_{j1}}$ . 边的容量 $cap\left({e}_{ij}\right)$ 按 ${HE}_{{v}_{i1}}$ 和 ${HE}_{{v}_{j1}}$ 长度的最小值计算. 图4(c)所示，交叉点D将线段AA'以及线段BB'分割为AD，DA'，BD，DB'，根据合并边所允许走线的通过方向不难得出，走线将会自上往下穿过线段AD继而从左向右穿过线段DB'，此时便能够得到边的容量 $cap\left({e}_{ij}\right)$ 即是线段AD以及线段DB'两者长度中的较小者.

为了有效缩减问题规模，算法在实际构造边时进行了一定简化. 首先根据起终点器件的坐标分布，确定整体布线方向. 以整体布线方向从左到右为例，在实际构造带权有向图时可以省略构造表示允许走线从右往左穿过的合并边的顶点. 其他方向同理.

为了实现群组布线的聚集效果，在自动布线流程中引入了一种自动生成引导线的方法. 所谓引导线是一条曲线，在实际布线过程中，算法希望所有走线的路径都能够尽可能地贴近引导线. 在通常的PCB设计中，起终点都是相互分离的. 因此，可以计算所有器件起始和终点引脚中心点的均值坐标，式如下所示：

$X=\dfrac{\displaystyle\sum\limits_{i=1}^{n}{x}_{i}}{n} ,$

(1)

$Y=\dfrac{\displaystyle\sum\limits_{i=1}^{n}{y}_{i}}{n} ,$

(2)

然后，便能够利用这2个坐标确定一条引导线.图5(a)所示，算法在双端线网的2个引脚之间创建了一条引导线，它是连接2个引脚中心的一条直线.

图 5 引导线示意图

Figure 5. Diagram of guidelines

下载: 全尺寸图片幻灯片

对于合并边的权重，做出如下规定：1）与引导线相交的合并边的权重规定为0，以(b)为例，合并边 ${HE}_{v2}$ ， ${HE}_{v3}$ ， ${HE}_{v5}$ ， ${HE}_{v6}$ ， ${HE}_{v7}$ 的权重被设置为0；2）若合并边与引导线不存在交点，如(b)中的 ${HE}_{v1}$ ， ${HE}_{v4}$ ，则计算它们之间的最小距离，且如果这一最小距离大于设置的阈值T，则将该合并边视作障碍物，这将有效加速之后进行的搜索过程. 由此，如果算法能够在顶点 ${{v}_{i}}^{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{i}}$ 与 ${{v}_{j}}^{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{j}}$ 与之间构造边 ${e}_{ij}$ ，则令边 ${e}_{ij}$ 的权重 $weight\left({e}_{ij}\right)$ 为合并边 ${HE}_{vi}$ 和 ${HE}_{vj}$ 的权重之和.

为了能够让群组布线的结果能够灵活适应各种复杂的工业化需求，达到人工预期的良好效果，算法同样支持人工指定引导线. 由于人工指定的引导线通常是一条曲线，因此，实际处理时算法需要根据一定的精度，首先对引导线进行采样，将其转换为多段首尾相接的线段. 图5(c)所示，引导线通过采样，被重新转换为线段AB，BC，CD，DE，EF. 线段化后的引导线的处理方式与自动生成的引导线相同.

最后，算法得到了所有顶点构成的集合 $V\left(G\right)$ ，所有边构成的集合 $E\left(G\right)$ ，所有边的容量以及所有边的权值. 这样算法便得到了基于合并边的带权有向图 $G$ .

展示了在某个简化的局部，完整的带权有向图 $G$ 的构造结果. (a)中，合并边 ${HE}_{v1}$ ， ${HE}_{v2}$ ， ${HE}_{v3}$ 按照规则可以被抽象为(b)所示的带权有向图 $G$ ，其中带权有向边的容量和权重没有具体给出.

图 6 带权有向图G构造结果示意图

Figure 6. Diagram of the construction result of weighted directed graph G

下载: 全尺寸图片幻灯片

3.4 基于启发式搜索算法的边序列搜索

这一阶段算法将会利用启发式的搜索算法，从图 $G$ 中逐线网地寻找连接起点与终点的迹.

首先算法将环绕在起始器件周围，且走线必然穿过的一条合并边标记为起始顶点，同理，算法将环绕在结束器件周围，且走线必然穿过的一条合并边标记为结束顶点. 接着，算法将起始顶点的权重设置为0，在图 $G$ 中以A*搜索的方式不断试探寻找下一顶点，直到寻找到结束顶点为止. 然后，算法对顶点序列进行逆序，从而得到有效的顶点序列. 最后，算法根据有效的顶点序列以及2个顶点确定图中一条有向边的原则，得到有效的边序列. 在A*搜索的过程中，算法如下设置权重：

$F\left(n\right)=aG\left(n\right)+bH\left(n\right)+c\times weight\left(e\right) ,$

(3)

其中 $F\left(n\right)$ 是A*搜索算法的总体代价， $G\left(n\right)$ 是从起始顶点到当前位置的实际路径开销^[30]. $\text{G}\left(n\right)$ 可以通过下列递推式计算得到：

${G\left(n\right)}_{i}={G\left(n\right)}_{i-1}+{cost}_{i} ,$

(4)

其中 ${G\left(n\right)}_{i}$ 表示第1到第 $i$ 段规划路径的实际开销， ${cost}_{i}$ 表示第 $i$ 段规划路径的实际开销. ${cost}_{i}$ 在实际计算中设为第 $i-1$ 段规划路径的终点与当前搜索到的顶点所对应合并边中点的连线长度.

H(n)是估价函数，它是一种启发式函数，表示了从当前位置到终点的预估距离. 对于预估距离的计算，通常会使用曼哈顿距离或是欧几里得距离. 设起点为 $s({x}_{1},{y}_{1})$ ，终点为 $t({x}_{2},{y}_{2})$ ，则曼哈顿距离的定义如下：

${dist}_{Manhattan}\left(s,t\right)=\left|{x}_{1}-{x}_{2}\right|+|{y}_{1}-{y}_{2}| .$

(5)

欧几里得距离的定义如下：

${dist}_{Manhattan}\left(s,t\right)={({x}_{1}-{x}_{2})}^{2}+{({y}_{1}-{y}_{2})}^{2}.$

(6)

为加速计算过程，在算法中，算法选用曼哈顿距离进行计算. 在实际计算中， $H(n)$ 由当前顶点所对应合并边中点到结束顶点的曼哈顿距离得到.

$\text { weight }(e)$ 是边权重，表示的是从上一个顶点到当前搜索顶点的边的权重. $a$ ， $b$ ， $c$ 是常数，算法可以通过改变 $a$ ， $b$ ， $c$ 的值从而强调不同的引导效果.

算法2给出了与数据结构相适配的A*搜索算法，算法从起点开始，不断地搜索出open列表中 $F$ 值最大的顶点，直到达到终点，然后通过回溯得到有效的顶点序列，继而通过2点确定一条边的方式确定有效的边序列：

算法2. A*搜索算法.

输入：图 $G$ ，起始顶点V_start，结束顶点V_end；

输出：由一系列不重复的边组成的集合所表示的一条迹W.

① 设最小优先队列Q_OPEN= $\varnothing$ ，Q_CLOSE= $\varnothing$ ，搜索过程中拜访过的顶点及其前继顶点的集合 V_visited= $\varnothing$ ，有效的顶点集合 $V=\varnothing$ ；

② Q_OPEN. push(〈0,V_start〉)；

③ while Q_OPEN ≠ $\varnothing$

④ 选择 ${F}$ 值F_next最小f同时不是障碍物cap(e_next) 大于线宽与线间距之和的顶点V_next∈Q_OPEN， Q_CLOSE. push(〈F_next,V_next〉)；

⑤ 　V_visited←V_visited∪{V_next→V_cur}；

⑥ 　　if V_next=V_end then

⑦ 　　　while V_next≠V_start

⑧ 　　　V←V∪V_next；

⑨ 　　　根据V_next搜索V_visited得到V_cur=V_next→ V_cur；

⑩ 　　　V_next=V_cur；

⑪ 　　end while

⑫ 　end if

⑬ 　将 $V$ 逆序存放 ${ reverse (V) }$ ；

⑭ 　设v_i=V_start；

⑮ 　for v∈V

⑯ 　　if v≠V_start

⑰ 　　　设 ${v}_{i}=v$ ；

⑱ 　　　根据 ${v}_{i}$ ， ${v}_{j}$ 搜索 $G$ 得到边 ${E}_{ij}$ ；

⑲ 　　　 $W\leftarrow W\cup {E}_{ij}$ , ${v}_{i}{=v}_{j}$ ；

⑳ 　　　return W,找到有效路径序列；

㉑　　else

㉒　　　计算顶点V_next的所有邻接节点 negis(V_next)的 $F$ ；

㉓　　for neig∈neigs

㉔　　　Q_OPEN←Q_OPEN.push(〈neig,F_neig〉)；

㉕　　end for

㉖　end for

㉗ end while

㉘ return 未找到有效路径序列.

在结束一次路径搜索后，需要对得到的边序列中所包含的每条边的容量进行更新. 在对所有起始顶点重复上述搜索过程后，便能得到所有线网的有效路径规划顶点序列以及有效路径规划边序列，它们分别代表了走线将会穿过的合并边的序列以及这些合并边之间的位置关系.

3.5 路径规划

这一阶段算法对路径规划得到的顶点序列以及边序列，通过限制关系在各个顶点所对应的合并边上进行取点，得到的点集就是路径规划.

除开始顶点以及结束顶点以外，算法每次取出与当前顶点邻接的前后2条边. 由于带权有向图 $G$ 中的每条边由2个顶点确定，而每个顶点则对应了构图中的1条实际合并边，因此，实际上算法每次取出的是构图中的3条合并边，而它们之间的位置关系对取点位置有着不同限制.

现对取点时存在的几种限制关系进行讨论. 如图7所示，假设布线整体方向为从左向右，显然3条合并边之间存在相互平行、前2条边平行而当前边与后一条边垂直、前2条边垂直而当前边与后一条边平行、当前边与前后2条边都垂直4种情况. 图7(a)展示的是3条合并边相互平行的情况，布线方向如图7所示. 在这种情况下，算法需要在边序列中向后寻找一条与它们相互垂直的合并边. 设curredge_start.x当前合并边终点的横坐标， $crossedge.y$ 为位于序列之后，且与当前合并边相互垂直的第1条合并边的横坐标， $\mathrm{m}\mathrm{i}\mathrm{n}$ 定义为取括号内两者的最小值. 则取点范围为

图 7 取点的几种限制关系示意图

Figure 7. Schematic diagram of several limiting relationships of acquisition points

下载: 全尺寸图片幻灯片

${P}_{range}=[{curedge}_{start}.x,\mathrm{m}\mathrm{i}\mathrm{n}({curedge}_{end}.x, crossedge.x\left)\right].$

(7)

(b)展示的是前2条边平行而当前边与后一条边垂直的情况. 设 $nextedge.x$ 为下一条合并边的横坐标，在这种情况下，此时的取点范围为

${P}_{range}=[{curedge}_{start}.x,\mathrm{m}\mathrm{i}\mathrm{n}({curedge}_{end}.x, nextedge.x\left)\right].$

(8)

(c)展示的是前2条边垂直而当前边与后一条边平行的情况. 设 $preedge.x$ 为上一条合并边的横坐标， $\mathrm{m}\mathrm{a}\mathrm{x}$ 定义为取括号内两者的最大值，在这种情况下，此时的取点范围为.

${P}_{range}=[\mathrm{max}\left(preedge.x,{curedge}_{start}.x\right) ,{curedge}_{end}.x] .$

(9)

图7(d)展示的是当前边与前后2条边都垂直的情况. 在这种情况下，此时的取点范围为

$\begin{split} {P}_{range}=\;&[\mathrm{max}\left(preedge.x,{curedge}_{start}.x\right) ,\\ &\mathrm{min}\left({curedge}_{end}.x,nextedge.x\right)] .\end{split}$

(10)

以布线整体方向从左向右为例，若上一个取点在当前合并边上的投影点落在所允许的取点范围之内，那么优先将其作为选点. 如所示，根据这一原则，在合并边 $H E_{2}$ 上，算法选择点 ${v}_{1}$ 的投影点 $v_{2}$ 作为选点. 如果此时的取点范围包括了边界，则考虑在边界的另一端进行取点. 若以上条件均不满足，则算法需要在相对于走线穿过的方向而言，合并边上所允许的取点范围之内尽量靠右的位置进行取点，间隔一个线宽与线间距之和的距离，以最大限度地减少布线空间的浪费. 实际判断取点位置是否为布线方向右侧时，算法首先将布线方向分为东、南、西、北、东南、西南、东北、西北8个方向，以图9为例，当前布线穿过方向显然为东北，此时以一斜率为1且朝向x，y轴正半轴的方向向量dir表示. 然后，在合并边AB上取中点M，然后分别取中点M到2端点A，B的方向向量，分别记做MA以及MB. 现在分别计算叉积dot₁以及dot₂：

图 8 路径规划以及详细布线示意图

Figure 8. Diagram of path planning and detailed routing

下载: 全尺寸图片幻灯片

图 9 向量与相对位置判断示意图

Figure 9. Diagram of vector and relative position judgment

下载: 全尺寸图片幻灯片

${\boldsymbol{d}\boldsymbol{o}\boldsymbol{t}}_{1}=\boldsymbol{d}\boldsymbol{i}\boldsymbol{r}\times \boldsymbol{M}\boldsymbol{A} \text{，}$

(11)

${\boldsymbol{d}\boldsymbol{o}\boldsymbol{t}}_{2}=\boldsymbol{d}\boldsymbol{i}\boldsymbol{r}\times \boldsymbol{M}\boldsymbol{B} .$

(12)

接着判断叉积dot₁, dot₂的正负，若叉积为正，则向量之间的夹角为顺时针，若叉积为负，则为逆时针. 算法规定与dir之间夹角呈顺时针的向量，它所指向的方向为布线方向的右侧. 显然图9中MB方向为布线方向的右侧.

以为例，根据这一原则，在合并边 $H E_{3}$ 上，算法将取点范围内尽量靠近右侧的点 $v_{3}$ 作为选点. 考虑到同一条合并边可能会被多条走线穿过，所以算法在每次取点时都必须与上一条穿过该合并边的走线的取点保持一个线宽与线间距之和的距离. 重复上述过程，算法便能够得到所有线网的路径规划序列，它们以点集的形式予以表示.

3.6 详细布线

路径规划阶段得到了所有线网完整的路径规划序列，但是这样的路径规划的直接连线结果违反了DRC.以图8为例，此时路径规划后的走线角度并非135°. 因此，算法需要在此基础上进行详细布线，以得到最终满足DRC的布线结果.

算法每次所要处理的是路径规划序列中的一段线，显然这一段线是由2个点确定的. 算法将需要详细布线的一条线段的起点定义为入点，而相应的终点则定义为出点.

为了缩减问题规模，算法将详细布线所面临的场景分为了2种最为基本的情形：2条合并边之间相互平行以及2条合并边之间相互垂直. 不妨设此时的路径规划线段走向为自左向右，对于2条合并边之间相互平行的情形又可细分为2种情况：一是入点与出点的纵坐标相同（如中的点 ${v}_{1}$ ， $v_{2}$ ）. 此时不做任何调整，直接进入下一段线的详细布线环节. 二是入点与出点的纵坐标不同（如中的点 $v_{8}$ ， $v_{9}$ ）. 对于这类情况，算法首先利用入点与出点的坐标信息构造布线矩形区域，该矩形区域需要恰好包含这2个点. 由于先前构造带权有向图时对连边之间存在障碍物的情形进行了限制，因此，该矩形区域内不可能存在任何障碍物. 然后，算法在矩形区域内进行详细布线. 详细布线时遵循面积最小原则，即出点顺时针沿着矩形边界到达入点所走过的路径，以及经由详细布线后所得到的线段，它们之间所围成的多边形面积必须尽可能小. 显然，算法需要让转折的长度尽可能小，在考虑到DRC中的最小线长限制后，让转折的长度取最小线宽即可.

对于2条合并边之间相互垂直的情形，不失一般性的，设此时的路径规划线段走向为自左向上（如中的点 $v_{2}$ ， $v_{3}$ ）. 对于这类情况，处理方法与2条合并边之间相互平行且入点与出点纵坐标不同的情况类似.

布线完成后检查起点线段与上一线段的终点线段之间是否为直角，若是，则在起点线段开始处增加一转折，转折的长度同样取最小线宽即可.

对于其他走向的路径规划线段，算法在参照上述处理方法的同时进行相应的坐标变换即可. 在对所有路径规划线段应用详细布线算法后，便能够得到完整的符合DRC的详细布线结果.

4. 实验结果及分析

算法使用C++作为编程语言进行实现. 所有实验都在配备了Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40 GHz和128 GB内存的单台服务器上进行. 表1展示了来自于工业界的基准用例. 其中PCB5在PCB4的基础上将线网划分为了2个群组. PCB9仅用于测试分层效果.

表 1 基准印刷电路板设计统计

Table 1. Benchmark Printed Circuit Board Design Statistics

设计	引脚数	焊盘数	过孔数	未布线线网数	总线群组组数
PCB1	10	10	0	5	1
PCB2	10	10	5	5	1
PCB3	16	32	22	8	1
PCB4	20	40	31	10	1
PCB5	20	40	31	10	2
PCB6	30	163	12	15	5
PCB7	84	172	86	42	3
PCB8	140	286	173	140	4
PCB9	6	12	12	3	1

下载: 导出CSV

| 显示表格

群组布线的布线质量可以通过采用一些评价指标进行评价. 群组布线的布线代价的计算方法由式(13)给出：

${C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}=\alpha {C}_{W}+\beta {C}_{S}+\gamma {C}_{C} .$

(13)

式(13)中的总体布线代价 ${C_{{\text{total}}}}$ 由3个部分加权求和得到，在不考虑DRV的情况下， ${C_{{\text{total}}}}$ 的值越小则说明群组布线的布线效果越好. 式中的 $\alpha$ ， $\beta$ ， $\gamma$ 表示权重，可取1，1，1，所有群组的线长相似性代价 ${C_W}$ 、线段数代价 ${C_S}$ 、紧凑性代价 ${C_C}$ 的计算式的计算方法分别由式(14)~(16)所示：

${C}_{W}=\dfrac{\displaystyle\sum\limits_{i=1}^{n}\frac{\mathrm{m}\mathrm{a}\mathrm{x}({WL}_{W}^{i})}{\mathrm{m}\mathrm{i}\mathrm{n}({WL}_{W}^{i})}}{n} ,$

(14)

${C}_{S}=\dfrac{\displaystyle\sum\limits_{i=1}^{n}\frac{max({N}_{S}^{i})}{min({N}_{S}^{i})}}{n} ,$

(15)

${C}_{C}=\dfrac{\displaystyle\sum\limits_{i=1}^{n}\frac{\mathrm{m}\mathrm{i}\mathrm{n}({W}_{S}^{i})}{{\widehat{W}}_{S}}}{n} ,$

(16)

其中式(14)中 ${C}_{W}$ 由每个群组 $i$ 的单独相似性代价累加得到， $n$ 则代表了当前布线输入的群组数. ${{\mathrm{max}}⁡}({WL}_{W}^{i})$ 表示的是群组 $i$ 中线长最长的线网的线长， $\mathrm{m}\mathrm{i}\mathrm{n}({WL}_{W}^{i})$ 表示的是群组 $i$ 中线长最短的线网的线长. ${C}_{W}$ 的值越小则所有群组线网的整体布线线长越接近.

式(15)中 $i$ 和 $n$ 的含义同式(14). $\text{max}({N}_{S}^{i})$ 表示群组 $i$ 中所包含的线段的数量最多的线网的段数， $min({N}_{S}^{i})$ 表示群组 $i$ 中的段数下界，取群组 $i$ 中所有线网段数中的最小值即可. ${C}_{S}$ 的值越小则布线的拓扑相似性越高.

式(16)中 $i$ 和 $n$ 的含义同式(14). $\text{m}\mathrm{i}\mathrm{n}({W}_{S}^{i})$ 表示群组 $i$ 中线段S所占据的宽度的最小值，计算 ${W}_{S}$ 时需要分别计算群组 $i$ 中最外层的2个线网与线段 $s$ 的最小距离，两者中的较小者即为 $\mathrm{m}\mathrm{i}\mathrm{n}({W}_{S}^{i})$ . ${\widehat{W}}_{S}$ 则取线网的线宽与线间距之和. ${C}_{C}$ 的值越小则布线的汇聚程度越高，而更高的汇聚程度能够有效地节约布线空间，从而尽可能减少给后续布线带来的困难.

将本文算法与2个最先进的布线器FreeRouting以及Cadance Allegro进行比较.2个布线器都使用了默认设置，并在实验中应用了相同的设计输入以及DRC. 而本文方法采用的是默认生成引导线的模式. 本文选择了组件之间相互远离的基准用例，以便清楚地展示布线结果. 表3中的方法1、方法2分别代表了FreeRouting以及Cadance Allegro的布线结果. 通过比较3款布线器的布通率即正确地完成布线的线网占总线网数的比率^[31]、运行时间和违反设计规则（design rule violation，DRV）的次数总结了实验结果. 请注意，表3中的连字符表示设计无法在软件上运行，或者运行时间超过1 h. 如表3所示，本文方法在布通率、运行时间和DRV的次数方面优于FreeRouting和Allegro. 值得注意的是，本文方法以及Cadence Allegro可以完成总线或群组布线，而FreeRouting只能完成单线布线. 此外，Cadence Allegro以及FreeRouting无法在实际布线前进行相应的路径规划，这往往会导致一系列拥塞问题，继而在布线过程中需要频繁地进行拆线重布，这造成了大量的时间浪费. 更糟糕的是，FreeRouting在一些布线发生拥塞的情况下会尝试设置过孔，从而进行跨层布线，这种做法将会使PCB板层数增加，从而导致制造成本与制造难度大大增加.

表 2 各方法的布线结果比较

Table 2. Comparison of Routing Results Between Method 1, Method 2 and the Method in This Paper

设计	布通率 /%			运行时间 /s			DRV次数
设计	方法1	方法2	本文方法	方法1	方法2	本文方法	方法1	方法2	本文方法
PCB1	100	100	100	0.03	0.008	0.001	0	0	0
PCB2	100	100	100	0.11	0.025	0.003	0	0	0
PCB3	100	100	100	0.7	0.19	0.023	1	0	0
PCB4	100	100	100	1.5	0.35	0.041	3	0	0
PCB5	100	100	100	1.5	0.37	0.048	3	0	0
PCB6	93.3	100	100	8.2	2.4	0.21	7	0	0
PCB7	57.1	97.6	100	94.7	13.2	2.1	15	2	0
PCB8	-	64.8	100	-	109.7	16.4	-	106	0
“-”表示未布通

下载: 导出CSV

| 显示表格

表 3 各方法的群组布线性能指标比较

Table 3. Comparison of Group Routing Performance Metrics Between Method 1, Method 2 and the Method in This Paper

设计	方法1				方法2				本文方法
设计	${C}_{W}$	${C}_{S}$	${C}_{C}$	${C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$	${C}_{W}$	${C}_{S}$	${C}_{C}$	${C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$	${C}_{W}$	${C}_{S}$	${C}_{C}$	${C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$
PCB1	1.04	1.67	4.04	6.75	1.01	1.00	3.50	5.51	1.16	1.67	1.00	3.83
PCB2	1.06	1.67	4.21	6.94	1.12	2.00	1.00	4.12	1.16	1.50	1.00	3.66
PCB3	1.07	2.00	4.36	7.43	1.17	1.50	1.00	3.67	1.29	1.32	1.00	3.61
PCB4	1.05	2.33	4.56	7.94	1.21	1.86	1.00	4.07	1.39	1.35	1.00	3.74
PCB5	1.05	2.33	4.56	7.94	1.14	2.00	1.00	4.14	1.17	1.22	1.00	3.39
PCB6	1.34	2.75	3.98	8.07	1.40	2.50	1.00	4.90	1.37	2.40	1.00	4.77
PCB7	1.20	2.13	4.29	7.62	1.20	1.82	1.00	4.02	1.18	1.60	1.00	3.78
PCB8	-	-	-	-	1.35	1.90	1.00	4.25	1.37	1.72	1.00	4.09
“-”表示未布通

下载: 导出CSV

| 显示表格

通过使用式(14)~(16)对3款布线器的布线性能指标进行比较. 其中式(13)中α，β，γ的取值分别为1，1，1，它们分别代表了群组布线同一群组中所有线网的布线线长尽量相近、所有线网的布线尽量汇聚以及所有线网的布线拓扑尽量相似的需求. 中 ${C}_{W}$ ， ${C}_{S}$ ， ${C}_{C}$ 分别表示相似性代价、线段数代价、紧凑性代价， ${C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}$ 表示总体布线代价，这些指标的值越小则布线效果越好. 如表3所示，在线长相似性代价方面，由于FreeRouting是以单线布线的布线结果进行对比的，不具备聚集布线的能力，因此通常来说它的线长相似性最好，而Cadence Allegro在自动布线阶段采取的是聚集布线策略，这种策略在进行切角处理后往往会占据大量的布线空间，且在面对复杂例子时难以达到100%的布通率. 本文所提出的算法在某些例子上没有达到最佳的线长相似性，但也在可接受的范围内. 在线段数代价方面，本文提出的算法较优，这也意味着本文方案具有较好的布线拓扑相似性. 在紧凑性代价方面，本文所提出的算法以及Cadence Allegro在面对有障碍物布线时都能保持最优，这也就意味着相邻线网之间都能保持最小线间距，而不具备聚集布线能力的FreeRouting在该指标上与本文所提出的算法以及Cadence Allegro有着较大差距. 本文所提出的算法在总体布线代价方面优于FreeRouting和Cadence Allegro，这就意味着，总体而言，本文所提出的算法对于群组布线问题有着更佳的效果.

图10、图11显示了使用本文方法在PCB4上的布线结果，该示例能够最清晰地展示本文方法的优势. 算法将PCB板上的过孔、焊盘等视作障碍物. 图10中，算法将式(3)中的权重weight(e)设置为0，从而屏蔽了引导线的功能，此时群组走线退化为单线布线. 图11中，算法将式(3)中的权重weight(e)设置为100，从而强调了引导线的引导效果. 此时算法从左侧从上到下第5个焊盘与第6个焊盘中间出发，到右侧从上到下第5个焊盘与第6个焊盘中间中止，自动生成了1条引导线，并在参数设置时强调了引导线的引导作用，这将对这10根线网的路径规划产生汇聚作用，从而满足群组布线的要求. 图12则显示了本文所用方法在复杂例子上的布线结果. 图13显示的是预先分配各引脚的层后，实施群组布线的布线效果，其中左边第1、2行（电子版红色）与第3行（电子版蓝色）矩形焊盘分别位于不同层，图13的走线未发生交叉. 实验结果表明，算法对于PCB设计的群组布线任务是适用且高效的.

图 10 权重weight(e)为0时的PCB4布线结果

Figure 10. PCB4 routing results when weight(e) is 0

下载: 全尺寸图片幻灯片

图 11 权重weight(e)为100时的PCB4布线结果

Figure 11. PCB4 routing results when weight(e) is 100

下载: 全尺寸图片幻灯片

图 12 PCB8布线结果

Figure 12. PCB8 routing results

下载: 全尺寸图片幻灯片

图 13 经预先分层后权重weight(e)为100时PCB9的布线结果

Figure 13. Routing results of PCB9 with weight(e) of 100 after pre-layering

下载: 全尺寸图片幻灯片

5. 总　　结

本文提出了一种用于PCB设计的群组布线算法，该算法考虑了PCB设计中的DRC.算法利用构造带权有向图的方式实现了群组布线问题的数学建模，在有效表示电路板上的布线资源的同时避免了传统网格方法易受网格精度以及网格数量限制的缺陷. 此外，算法采用具有多线避让功能的启发式搜索算法，且算法支持人工指定引导线以引导布线方向，在有效降低时间开销的同时保证了布线质量. 最后，算法提出了一种简洁有效且与本文提出的路径规划算法相适配的群组布线方案. 与FreeRouting和Cadence Allegro相比，实验结果显示了该算法的优越性.

作者贡献声明：邓新国负责方案设计和论文撰写以及修改；张鑫泓负责完成实验、数据分析和论文撰写以及修改；陈家瑞负责方案设计，并修改论文；刘清海提出方案的概念和证明思路；陈传东提出指导意见并参与论文修改.

图 1 变分量子算法示意图

Figure 1. Illustration of variational quantum algorithms

下载: 全尺寸图片幻灯片

图 2 参数化量子电路框架

Figure 2. Parameterized quantum circuits frame

下载: 全尺寸图片幻灯片

图 3 多层参数化量子电路

Figure 3. Multiple parameterized quantum circuits

下载: 全尺寸图片幻灯片

图 4 基于变分量子电路的量子机器学习算法时间线

Figure 4. Timelines of quantum machine learning algorithms based on variational quantum circuit

下载: 全尺寸图片幻灯片

图 5 经典前后处理量子分类器

Figure 5. Quantum classifiers with classical pre-processing and post-processing

下载: 全尺寸图片幻灯片

图 6 TTN 和 MERA 架构

Figure 6. Frame of TTN and MERA

下载: 全尺寸图片幻灯片

图 7 量子卷积神经网络

Figure 7. Quantum convolutional neural network

下载: 全尺寸图片幻灯片

图 8 变分影子量子学习示意图

Figure 8. Illustration of VSQL

下载: 全尺寸图片幻灯片

图 9 单隐藏层 HNN 架构示意图

Figure 9. Illustration of HNN frame with single hidden layer

下载: 全尺寸图片幻灯片

图 10 量子自编码器示意图

Figure 10. Illustration of quantum autoencoder

下载: 全尺寸图片幻灯片

图 11 SQ-VAE示意图

Figure 11. Illustration of SQ-VAE

下载: 全尺寸图片幻灯片

图 12 量子生成式对抗网络

Figure 12. Quantum generative adversarial networks

下载: 全尺寸图片幻灯片

图 13 量子强化学习示意图

Figure 13. Illustration of quantum reinforcement learning

下载: 全尺寸图片幻灯片

图 14 policy-PQC 示意图

Figure 14. Illustration of policy-PQC

下载: 全尺寸图片幻灯片

图 15 量子actor结合经典critic

Figure 15. Quantum actor combines with classical critic

下载: 全尺寸图片幻灯片

表 1 用于量子机器学习模型的设备

Table 1 Device for Quantum Machine Learning

模型	门电路	量子退火机	脉冲电路
分类器	√	×	√
量子卷积神经网络	√	×	×
影子电路	√	×	×
量子玻恩机	√	×	×
量子玻尔兹曼机	√	√	×
量子自编码器	√	√	×
量子生成对抗网络	√	×	×
量子强化学习	√	×	×
量子电路结构搜索	√	×	√
注：“√”表示可以实现的设备，“×”表示不能实现的设备.

下载: 导出CSV

表 2 常用基本量子逻辑门

Table 2 Frequently-Used Quantum Basic Gates

量子逻辑门	符号表示	酉矩阵表示
单位门	I	$\left( {\begin{array}{*{20}{c}} 1&0 \\ 0&1 \end{array}} \right)$
Pauli-X门	X	$\left( {\begin{array}{*{20}{c}} 0&1 \\ 1&0 \end{array}} \right)$
Pauli-Y门	Y	$\left( {\begin{array}{*{20}{c}} 0&{ - {\text{i}}} \\ {\text{i}}&0 \end{array}} \right)$
Pauli-Z门	Z	$\left( {\begin{array}{*{20}{c}} 1&0 \\ 0&{ - 1} \end{array}} \right)$
Hadmard门	H	$\dfrac{{\sqrt 2 }}{2}\left( {\begin{array}{*{20}{c}} 1&1 \\ 1&{ - 1} \end{array}} \right)$
Phase门	S	$\left( {\begin{array}{*{20}{c}} 1&0 \\ 0&{\text{i}} \end{array}} \right)$
交换门	SWAP	$\left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&0&1&0 \\ 0&1&0&0 \\ 0&0&0&1 \end{array}} \right)$
受控非门	CNOT，CX	$\left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \end{array}} \right)$
受控Y门	CY	$\left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&{ - {\text{i}}} \\ 0&0&{\text{i}}&0 \end{array}} \right)$
受控Z门	CZ	$\left( {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&{ - 1} \end{array}} \right)$
Toffoli门	Toffoli，CCNOT	$\left( {\begin{array}{*{20}{c}} 1&0&0&0&0&0&0&0 \\ 0&1&0&0&0&0&0&0 \\ 0&0&1&0&0&0&0&0 \\ 0&0&0&1&0&0&0&0 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&0&0&0&0&1 \\ 0&0&0&1&0&0&1&0 \end{array}} \right)$
Fredkin门	Fredkin，CSWAP	$\left( {\begin{array}{*{20}{c}} 1&0&0&0&0&0&0&0 \\ 0&1&0&0&0&0&0&0 \\ 0&0&1&0&0&0&0&0 \\ 0&0&0&1&0&0&0&0 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&0&1&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&1&0&0&0&1 \end{array}} \right)$

下载: 导出CSV

表 3 经典优化算法及模型使用偏好

Table 3 Classical Optimization Algorithms and Usage Preference of Models

经典优化器	基于梯度	有监督模型	无监督模型	半监督模型	强化学习模型	电路结构搜索
Adam^[37]	是	TTNs^[10,32-33] QCCNN^[38-39] VSQL^[34]	QCBM^[31,40-42], QBM^[14] QAE^[15,43]	QGAN^[19,44-50]	QDQN^[16,51] QActor-critic^[52] QMARL^[53-54]	QuantumNAS^[12] QAS^[55] MQNE^[56]
(mini-batch)SGD^[57]	是	HNN^[58]		QGAN^[59]	QDDQN^[60]
AMSGRAD^[61]	是			QGAN^[50,62]
BFGS/L-BFGS-B^[63-64]	是		QCBM^[40] QAE^[65-66]
Nesterov moment^[67]	是	QCNN^[39]
RMSProp^[68]	是	MPS-VQC^[30]			VQ-DQN^[69]
基于梯度优化的其他模型	是	QCNN^[11,70-71]	QCBM^[41] QBM^[72]	QGAN^[73-74]
PSO^[75]	否		QCBM^[13,76]
SPSA^[77]	否			QGAN^[62]		CRLQAS^[78]
CMA-ES^[79]	否		QCBM^[40,80]
GA^[81]	否		QCBM^[82] QAE^[83]

下载: 导出CSV

表 4 量子机器学习任务常用数据集

Table 4 Frequently Used Datasets of Quantum Machine Learning Tasks

任务	数据集/交互环境
有监督学习	MNIST^{[10,30,32-33,38,70-71,98]}、Iris ^[10,32,58]、BAS^[58]、量子数据^[32]
无监督学习	MNIST^[103]、BAS^{[13,15,31,40,42,72,76]}、金融数据^[41,80]、药物数据QM9^[43]、生成概率分布^{[15,40,82,101]}、量子数据^[101]
半监督学习	MNIST^[19,49-59]、BAS^[19,44-45]、QM9^[47,104]、生成概率分布数据^[46,62]、量子数据^[73]
电路结构搜索	MNIST^[12,55-56]、量子数据^[56]
强化学习	frozen-lake^[69,105]，cart pole^{[16,51-52,105-106]}

下载: 导出CSV

表 5 常用模拟平台及模型

Table 5 Frequently Used Simulators and Models

模拟平台	机构	模型	语言
Qiskit	IBM	HNN^[58]，QGAN^[50]，QBM^[72]	Python
TFQ	Google	TTNs^[32]，MERAs^[32]，VQTN^[10]，QCNN^[70]，QGAN^[107]，QRL^[51]	Python
Pennylane	Xanadu	QTN^[33]，QCNN^[39]，QCBM^[31]，QGAN^[47]，QVAE^[43]， VQ−DQN^[69]，QRL^[52]，QAS^[108]	Python
Torchquantum	MIT	QuantumNAS^[12]，QAE^[15]，QMARL^[53]	Python
Yao	QuantumBFS	MQNE^[56]，QCBM^[40]，QGAN^[44]	Julia
Paddle Quantum	百度	QCL^[84]，VSQL^[34]，QAE^[65]，QGAN^[74]	Python
VQNet	本源量子	VQM^[109]，QCNN^[11,110]，VSQL^[34]，QAE^[65]，QGAN^[50]，VQ-DQN^[69]	C++

下载: 导出CSV

表 6 分类任务上基于变分量子电路的机器学习算法

Table 6 Machine Learning Algorithms Based on Variational Quantum Circuits For Classification Tasks

模型	数据集	任务	环境	量子位	参数量	准确率/%
模型	数据集	任务	环境	量子位	参数量	训练集	测试集
VQM^[98]	MNIST	二分类	模拟	17	136		90
TTN^[32]	Iris	二分类	模拟	4	7		98.92
TTN^[32]	MNIST	二分类	模拟	8	7		97.63
MERA^[32]	MNIST	二分类	模拟	8	11		98.86
Hybrid^[32]（TTN 预训练过的 MERA）	MNIST	二分类	模拟	8	11		98.46
TTN^[32]	合成量子数据集	二分类	模拟	8	7		60.45
PCA-VQC^[30]	MNIST	二分类	模拟	4	12	87.29	87.34
MPS-VQC^[30]	MNIST	二分类	模拟	4	12	99.91	99.44
QTN-VQC^[33]	MNIST	二分类	模拟	8	328		91.43
QTN-VQC^[33]	MNIST	二分类	模拟	12	4464		92.36
QTN-VQC^[33]	MNIST	二分类	模拟	16	600		92.28
VQTN^[10]	Iris	三分类	模拟	2	3		100
VQTN(TTN)^[10]	MNIST	二分类	模拟	8	12		97.80
VQTN(TTN)^[10]	MNIST	二分类	模拟	16	28		97.45
VQTN(MERA)^[10]	MNIST	二分类	模拟	8	18		97.92
VQTN^[10]	MNIST-4	四分类	模拟				82.19
QCNN^[70]	MNIST	十分类	模拟	4	6		95
Noisy QCNN^[71]	MNIST	二分类	模拟	14	46	94.8	96.0
Noisy QCNN^[71]	MNIST	十分类	模拟	14	379	74.2	74.0
Noisy-free QCNN^[71]	MNIST	二分类	模拟	14	46	95.4	96.3
Noisy-free QCNN^[71]	MNIST	十分类	模拟	14	379	75.6	74.3
QCCNN^[38]	Tetri	二分类	模拟	4	16		≈100
QCCNN^[38]	Tetri	四分类	模拟	4	16		≈100
QMLP^[111]	MNIST	十分类	模拟	16	128		75
QMLP^[111](比特翻转)	MNIST	十分类	模拟	16	128		63
QMLP^[111](相位翻转)	MNIST	十分类	模拟	16	128		67
VSQL^[34]	MNIST	二分类	模拟	2	35		99.52
VSQL^[34]	MNIST（1000个样本）	十分类	模拟	9	928		87.39
VSQL^[34]	含噪量子态	二分类	模拟	2			100
VSQL^[34]	不含噪量子态	三分类	模拟	2			100
HNN^[58]	BAS	二分类	模拟	10	20		100
HNN^[58]	BAS	二分类	量子	10	20		33.33
HNN^[58]	Iris	三分类	模拟	10	20	89.88	91.5
HNN^[58]	Iris	三分类	量子	10	20	28.12	37.5
注：数据取相应论文给出的最优模型数据，使用相同数据集相同任务之间仍存在差异，例如 MNIST 数据集二分类任务可以为2个数字的分类、是否为偶数的分类、是否大于4 的分类等，并非完全一致. 模拟环境是指使用经典计算机模拟，量子环境是指使用量子计算机上运行相应算法.

下载: 导出CSV

表 7 QGAN 分类及相关研究

Table 7 Classification of QGANs and Related Researches

任务	生成器	判别器	名称	相关研究
经典	经典	经典	CT-CGCD	文献[126]
经典	经典	量子	CT-CGQD	文献[46, 104, 107]
经典	量子	经典	CT-QGCD	文献[19, 44−49, 59]
经典	量子	量子	CT-QGQD	文献[46, 59]
量子	经典	经典	QT-CGCD	文献[127]
量子	经典	量子	QT-CGQD
量子	量子	经典	QT-QGCD	文献[50, 62]
量子	量子	量子	QT-QGQD	文献[73−74, 124, 128−129]
注：采用文献[125]给出的命名方式，名称中的字母 T，G，D分别表示任务、生成器、判别器. C，Q 分别表示是通过经典还是量子方法完成的. 经典生成器与量子判别器构成的QGAN对于量子数据无法收敛到纳什均衡，无法完成量子任务.

下载: 导出CSV

表 8 量子强化学习算法

Table 8 Quantum Reinforcement Learning Algorithms

模型	测试环境	环境	量子位	参数量	回合数	回报
VQ-DQN^[69]	frozen-lake	模拟	4	28	198	0.9
VQ-DQN(pretrianed)^[69]	frozen-lake	量子	4	28	1	0.95
VQ-DQN^[69]	cognitive-radio	模拟	4	28	10*	100
VQ-DQN(pretrianed)^[69]	cognitive-radio	量子	4	28	1	100
Quantum-DQN^[105]	frozen-lake v0	模拟	4	5层	3100	1.0
Quantum-DQN^[105]	frozen-lake v0	模拟	4	10层	2200	1.0
Quantum-DQN^[105]	frozen-lake v0	模拟	4	15层	1700	1.0
Quantum-DQN^[105]	Cart Pole v0（optimal）	模拟	4	62	186	195
Quantum-DQN^[105]	Cart Pole v0（sub-optimal）	模拟	4	62	3000	176
Quantum Actor-critic^[52]	Cart Pole	模拟	4	36	6000	105
QLSTM-DRQN-1^[16]	Cart Pole（Full Observable）	模拟	8	150	350*	100*
QLSTM-DRQN-1^[16]	Cart Pole（Partially Observable）	模拟	8	146	675*	150*
QLSTM-DRQN-2^[16]	Cart Pole（Full Observable）	模拟	8	270	420*	125*
QLSTM-DRQN-2^[16]	Cart Pole（Partially Observable）	模拟	8	266	750*	100*
QMARL^[53]	Single-Hop Offloading	模拟	4	50	500	−3.0
改进CTDE QMARL^[54]	Smart Factory	模拟	16	54	980	−37.0
注：带*的数值表示原论文中未给出精确数值，本文进行估算后得到的数值. 结果为各论文中给出的最优参数的模型. Quantum-DQN模型中未给出具体参数量，层数与参数量正相关.

下载: 导出CSV

表 9 量子架构搜索算法

Table 9 Quantum Architecture Searching Algorithms

模型	数据集	任务	环境	量子位	最优结构参数量	准确率/%
QuantumNAS^[12]	MNIST	二分类	量子	5	22	95
QuantumNAS^[12]	MNIST	四分类	量子	5	22	75
QuantumNAS^[12]	MNIST	十分类	量子	15		32.5
QuantumNAS^[12]	Fashion-2	二分类	量子	5	22	92
QuantumNAS^[12]	Fashion-4	四分类	量子	5	36	85
MQNE^[56]	MNIST	二分类	模拟	9	106	97
MQNE^[56]	Cancer	二分类	模拟	7	68	94.6
MQNE^[56]	SPT	量子态分类	模拟	8	46	100
QAS^[55]	Fashion-MNIST	二分类	模拟	10		92.4
QAS^[108]	合成数据集（无噪声）^[144]	二分类	模拟	3		>90
QAS^[108]	合成数据集（有噪声）^[144]	二分类	模拟	3		100
CRLQAS^[78]		VQE	模拟
NAPA^[142]		VQE最大割	量子

下载: 导出CSV

参考文献(167)

[1]	Hilbert M, López P. The world’s technological capacity to store, communicate, and compute information[J]. Science, 2011, 332(6025): 60−65 doi: 10.1126/science.1200970
[2]	Arute F, Arya K, Babbush R, et al. Quantum supremacy using a programmable superconducting processor[J]. Nature, 2019, 574(7779): 505−510 doi: 10.1038/s41586-019-1666-5
[3]	Huang Cupjin, Zhang Fang, Newman M, et al. Classical simulation of quantum supremacy circuits[J]. arXiv preprint, arXiv: 2005.06787, 2020
[4]	Pan Feng, Zhang Pan. Simulating the Sycamore quantum supremacy circuits[J]. arXiv preprint, arXiv: 2103.03074, 2021
[5]	Zhu Qingling, Cao Sirui, Chen Fusheng, et al. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling[J]. Science Bulletin, 2022, 67(3): 240−245 doi: 10.1016/j.scib.2021.10.017
[6]	Feng Congcong, Zhao Bo, Zhou Xin, et al. An enhanced quantum k-nearest neighbor classification algorithm based on polar distance[J]. Entropy, 2023, 25(1): 127 doi: 10.3390/e25010127
[7]	Li Jing, Gao Fei, Lin Song, et al. Quantum k-fold cross-validation for nearest neighbor classification algorithm[J]. Physica A: Statistical Mechanics and Its Applications, 2023, 611: 128435 doi: 10.1016/j.physa.2022.128435
[8]	Cerezo M, Sharma K, Arrasmith A, et al. Variational quantum state eigensolver[J]. NPJ Quantum Information, 2022, 8(1): 113 doi: 10.1038/s41534-022-00611-6
[9]	Zhou Zeqiao, Du Yuxuan, Tian Xinmei, et al. Qaoa-in-qaoa: Solving large-scale maxcut problems on small quantum machines[J]. Physical Review Applied, 2023, 19(2): 024027 doi: 10.1103/PhysRevApplied.19.024027
[10]	Huang Rui, Tan Xiaoqing, Xu Qingshan. Variational quantum tensor networks classifiers[J]. Neurocomputing, 2021, 452: 89−98 doi: 10.1016/j.neucom.2021.04.074
[11]	Cong I, Choi S, Lukin M D. Quantum convolutional neural networks[J]. Nature Physics, 2019, 15(12): 1273−1278 doi: 10.1038/s41567-019-0648-8
[12]	Wang Hanrui, Ding Yongshan, Gu Jiaqi, et al. QuantumNAS: Noise-adaptive search for robust quantum circuits[C]//Proc of the 28th Annual Int Symp on High-Performance Computer Architecture. Piscataway, NJ: IEEE, 2022: 692−708
[13]	Benedetti M, Garcia-Pintos D, Perdomo O, et al. A generative modeling approach for benchmarking and training shallow quantum circuits[J]. NPJ Quantum Information, 2019, 5(1): 45 doi: 10.1038/s41534-019-0157-8
[14]	Zoufal C, Lucchi A, Woerner S. Variational quantum Boltzmann machines[J]. Quantum Machine Intelligence, 2021, 3(1): 7 doi: 10.1007/s42484-020-00033-7
[15]	Wu S R, Li C T, Cheng H C. Efficient data loading with quantum autoencoder[C/OL]//Proc of the 48th Int Conf on Acoustics, Speech and Signal Processing. Piscataway, NJ: IEEE, 2023[2023-09-14]. https://ieeexplore.ieee.org /abstract/document/10096496
[16]	Chen Guoming, Chen Qiang, Long Shun, et al. Quantum convolutional neural network for image classification[J]. Pattern Analysis and Applications, 2023, 26(2): 655−667 doi: 10.1007/s10044-022-01113-z
[17]	Akshay V, Philathong H, Morales M E, et al. Reachability deficits in quantum approximate optimization[J]. Physical Review Letters, 2020, 124(9): 090504 doi: 10.1103/PhysRevLett.124.090504
[18]	Anand A, Alperin-Lea S, Choquette A, et al. Exploring the role of parameters in variational quantum algorithms[J]. arXiv preprint, arXiv: 2209.14405, 2022
[19]	Zhou Nanrun, Zhang Tianfeng, Xie Xinwen, et al. Hybrid quantum classical generative adversarial networks for image generation via learning discrete distribution[J]. Signal Processing: Image Communication, 2023, 110: 116891 doi: 10.1016/j.image.2022.116891
[20]	Romero J, Babbush R, Mcclean J R, et al. Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz[J]. Quantum Science and Technology, 2018, 4(1): 014008 doi: 10.1088/2058-9565/aad3e4
[21]	Bang J, Lim J, Kim M S, et al. Quantum learning machine[J]. arXiv preprint, arXiv: 0803.2976, 2008
[22]	Cerezo M, Arrasmith A, Babbush R, et al. Variational quantum algorithms[J]. Nature Reviews Physics, 2021, 3(9): 625−644 doi: 10.1038/s42254-021-00348-9
[23]	Schuld M, Killoran N. Quantum machine learning in feature Hilbert spaces[J]. Physical Review Letters, 2019, 122(4): 040504 doi: 10.1103/PhysRevLett.122.040504
[24]	Lloyd S, Schuld M, Ijaz A, et al. Quantum embeddings for machine learning[J]. arXiv preprint, arXiv: 2001.03622, 2020
[25]	Schuld M. Supervised quantum machine learning models are kernel methods[J]. arXiv preprint, arXiv: 2101.11020, 2021
[26]	Grover L, Rudolph T. Creating superpositions that correspond to efficiently integrable probability distributions[J]. arXiv preprint, quant-ph/0208112, 2002
[27]	Kitaev A, Webb W A. Wavefunction preparation and resampling using a quantum computer[J]. arXiv preprint, arXiv: 0801.0342, 2008
[28]	Lloyd S. Universal quantum simulators[J]. Science, 1996, 273(5278): 1073−1078 doi: 10.1126/science.273.5278.1073
[29]	Kandala A, Mezzacapo A, Temme K, et al. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets[J]. Nature, 2017, 549(7671): 242−246 doi: 10.1038/nature23879
[30]	Chen S Y C, Huang C M, Hsing C W, et al. Hybrid quantum-classical classifier based on tensor network and variational quantum circuit[J]. arXiv preprint, arXiv: 2011.14651, 2020
[31]	Gong Lihua, Xing Lingzhi, Liu Sihang, et al. Born machine model based on matrix product state quantum circuit[J]. Physica A: Statistical Mechanics and its Applications, 2022, 593: 126907 doi: 10.1016/j.physa.2022.126907
[32]	Grant E, Benedetti M, Cao Shuxiang, et al. Hierarchical quantum classifiers[J]. NPJ Quantum Information, 2018, 4(1): 65 doi: 10.1038/s41534-018-0116-9
[33]	Qi Jun, Yang Chaohan, Chen Pinyu. QTN-VQC: An end-to-end learning framework for quantum neural networks[J]. Physica Scripta, 2023, 99(1): 015111
[34]	Li Guangxi, Song Zhixin, Wang Xin. VSQL: Variational shadow quantum learning for classification[C]//Proc of the 35th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2021: 8357−8365
[35]	Grimsley H R, Economou S E, Barnes E, et al. An adaptive variational algorithm for exact molecular simulations on a quantum computer[J]. Nature Communications, 2019, 10(1): 3007 doi: 10.1038/s41467-019-10988-2
[36]	Bittel L, Kliesch M. Training variational quantum algorithms is NP-hard[J]. Physical Review Letters, 2021, 127(12): 120502 doi: 10.1103/PhysRevLett.127.120502
[37]	Kingma D P, Ba J. Adam: A method for stochastic optimization[J]. arXiv preprint, arXiv: 1412.6980, 2014
[38]	Liu Junhua, Lim K H, Wood K L, et al. Hybrid quantum-classical convolutional neural networks[J]. Science China Physics, Mechanics & Astronomy, 2021, 64(9): 290311
[39]	Hur T, Kim L, Park D K. Quantum convolutional neural network for classical data classification[J]. Quantum Machine Intelligence, 2022, 4(1): 3 doi: 10.1007/s42484-021-00061-x
[40]	Liu Jinguo, Wang Lei. Differentiable learning of quantum circuit born machines[J]. Physical Review A, 2018, 98(6): 062324 doi: 10.1103/PhysRevA.98.062324
[41]	Coyle B, Henderson M, Le J C J, et al. Quantum versus classical generative modelling in finance[J]. Quantum Science and Technology, 2021, 6(2): 024013 doi: 10.1088/2058-9565/abd3db
[42]	Leyton-Ortega V, Perdomo-Ortiz A, Perdomo O. Robust implementation of generative modeling with parametrized quantum circuits[J]. Quantum Machine Intelligence, 2021, 3(1): 17 doi: 10.1007/s42484-021-00040-2
[43]	Li Junde, Ghosh S. Scalable variational quantum circuits for autoencoder-based drug discovery[C]//Proc of the 25th Design, Automation and Test in Europe Conf and Exhibition. Piscataway, NJ: IEEE, 2022: 340−345
[44]	Zeng Jinfeng, Wu Yufeng, Liu Jinguo, et al. Learning and inference on generative adversarial quantum circuits[J]. Physical Review A, 2019, 99(5): 052306 doi: 10.1103/PhysRevA.99.052306
[45]	Situ Haozhen, He Zhimin, Wang Yuyi et al. Quantum generative adversarial network for generating discrete distribution[J]. Information Sciences, 2020, 538: 193−208 doi: 10.1016/j.ins.2020.05.127
[46]	Romero J, Aspuru-Guzik A. Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions[J]. Advanced Quantum Technologies, 2021, 4(1): 2000003 doi: 10.1002/qute.202000003
[47]	Li Junde, Topaloglu R O, Ghosh S. Quantum generative models for small molecule drug discovery[J]. IEEE Transactions on Quantum Engineering, 2021, 2: 3103308
[48]	Herr D, Obert B, Rosenkranz M. Anomaly detection with variational quantum generative adversarial networks[J]. Quantum Science and Technology, 2021, 6(4): 045004 doi: 10.1088/2058-9565/ac0d4d
[49]	Tsang S L, West M T, Erfani S M, et al. Hybrid quantum-classical generative adversarial network for high resolution image generation[J]. IEEE Transactions on Quantum Engineering, 2023, 4: 3102419
[50]	Zoufal C, Lucchi A, Woerner S. Quantum generative adversarial networks for learning and loading random distributions[J]. NPJ Quantum Information, 2019, 5(1): 103 doi: 10.1038/s41534-019-0223-2
[51]	Lockwood O, Si Mei. Reinforcement learning with quantum variational circuit[C]//Proc of the 16th AAAI Conf on Artificial Intelligence and Interactive Digital Entertainment. Menlo Park, CA: AAAI, 2020: 245−251
[52]	Kwak Y, Yun W J, Jung S, et al. Introduction to quantum reinforcement learning: Theory and pennylane-based implementation[C]//Proc of the 12th Int Conf on Information and Communication Technology Convergence. Piscataway, NJ: IEEE, 2021: 416−420
[53]	Yun W J, Kwak Y, Kim J P, et al. Quantum multiagent reinforcement learning via variational quantum circuit design[C]//Proc of the 42nd Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2022: 1332−1335
[54]	Yun W J, Kim J P, Jung S, et al. Quantum multi-agent actor-critic neural networks for internet-connected multirobot coordination in smart factory management[J]. IEEE Internet of Things Journal, 2023, 10(11): 9942−9952 doi: 10.1109/JIOT.2023.3234911
[55]	Zhang Shixin, Hsieh Changyu, Zhang Shengyu, et al. Neural predictor based quantum architecture search[J]. Machine Learning: Science and Technology, 2021, 2(4): 045027 doi: 10.1088/2632-2153/ac28dd
[56]	Lu Zhide, Shen Peixin, Deng Dongling. Markovian quantum neuroevolution for machine learning[J]. Physical Review Applied, 2021, 16(4): 044039 doi: 10.1103/PhysRevApplied.16.044039
[57]	Robbins H, Monro S. A stochastic approximation method[J]. The Annals of Mathematical Statistics, 1951, 22(3): 400−407 doi: 10.1214/aoms/1177729586
[58]	Arthur D. A hybrid quantum-classical neural network architecture for binary classification[J]. arXiv preprint, arXiv: 2201.01820, 2022
[59]	Huang Heliang, Du Yuxuan, Gong Ming, et al. Experimental quantum generative adversarial networks for image generation[J]. Physical Review Applied, 2021, 16(2): 024051 doi: 10.1103/PhysRevApplied.16.024051
[60]	Heimann D, Hohenfeld H, Wiebe F, et al. Quantum deep reinforcement learning for robot navigation tasks[J]. arXiv preprint, arXiv: 2202.12180, 2022
[61]	Reddi S J, Kale S, Kumar S. On the convergence of adam and beyond[J]. arXiv preprint, arXiv: 1904.09237, 2019
[62]	Agliardi G, Prati E. Optimal tuning of quantum generative adversarial networks for multivariate distribution loading[J]. Quantum Reports, 2022, 4(1): 75−105 doi: 10.3390/quantum4010006
[63]	Nocedal J, Wright S J. Numerical Optimization[M]. New York: Springer, 2006
[64]	Zhu Ciyou, Byrd R H, Lu Peihuang, et al. Algorithm 778: LBFGS-B: Fortran subroutines for large-scale bound-constrained optimization[J]. ACM Transactions on mathematical software, 1997, 23(4): 550−560 doi: 10.1145/279232.279236
[65]	Romero J, Olson J P, Aspuru-Guzik A. Quantum autoencoders for efficient compression of quantum data[J]. Quantum Science and Technology, 2017, 2(4): 045001 doi: 10.1088/2058-9565/aa8072
[66]	Bravo-Prieto C. Quantum autoencoders with enhanced data encoding[J]. Machine Learning: Science and Technology, 2021, 2(3): 035028 doi: 10.1088/2632-2153/ac0616
[67]	Sutskever I, Martens J, Dahl G, et al. On the importance of initialization and momentum in deep learning[C]//Proc of the 30th Int Conf on Machine Learning. New York: PMLR, 2013: 1139−1147
[68]	Tieleman T. Lecture 6.5-RMSProp: Divide the gradient by a running average of its recent magnitude[J]. COURSERA: Neural Networks for Machine Learning, 2012, 4(2): 26−31
[69]	Chen S Y C, Yang C H H, Qi Jun, et al. Variational quantum circuits for deep reinforcement learning[J]. IEEE Access, 2020, 8: 141007−141024 doi: 10.1109/ACCESS.2020.3010470
[70]	Oh S, Choi J, Kim J. A tutorial on quantum convolutional neural networks (QCNN)[C]//Proc of the 11th Int Conf on Information and Communication Technology Convergence (ICTC). Piscataway, NJ: IEEE, 2020: 236−239
[71]	Wei Shijie, Chen Yanhu, Zhou Zengrong, et al. A quantum convolutional neural network on NISQ devices[J]. AAPPS Bulletin, 2022, 32(1): 2 doi: 10.1007/s43673-021-00030-3
[72]	Shingu Y, Seki Y, Watabe S, et al. Boltzmann machine learning with a variational quantum algorithm[J]. Physical Review A, 2021, 104(3): 032413 doi: 10.1103/PhysRevA.104.032413
[73]	Chakrabarti S, Huang Yiming, Li Tongyang, et al. Quantum wasserstein generative adversarial networks[C]//Proc of the 33rd Conf on Neural Information Processing Systems (NeurIPS). La Jolla, CA: NIPS, 2019: 6781−6792
[74]	Lloyd S, Weedbrook C. Quantum generative adversarial learning[J]. Physical Review Letters, 2018, 121(4): 040502 doi: 10.1103/PhysRevLett.121.040502
[75]	Kennedy J, Eberhart R. Particle swarm optimization[C]//Proc of ICNN’95. Piscataway, NJ: IEEE, 1995: 1942−1948
[76]	Zhu Daiwei, Linke N M, Benedetti M, et al. Training of quantum circuits on a hybrid quantum computer[J]. Science Advances, 2019, 5(10): eaaw9918 doi: 10.1126/sciadv.aaw9918
[77]	Spall J C. A one-measurement form of simultaneous perturbation stochastic approximation[J]. Automatica, 1997, 33(1): 109−112 doi: 10.1016/S0005-1098(96)00149-5
[78]	Patel Y J, Kundu A, Ostaszewski M, et al. Curriculum reinforcement learning for quantum architecture search under hardware errors[J]. arXiv preprint, arXiv: 2402.03500, 2024.
[79]	Hansen N, Müller S D, Koumoutsakos P. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[J]. Evolutionary Computation, 2003, 11(1): 1−18 doi: 10.1162/106365603321828970
[80]	Alcazar J, Leyton-Ortega V, Perdomo-Ortiz A. Classical versus quantum models in machine learning: Insights from a finance application[J]. Machine Learning: Science and Technology, 2020, 1(3): 035003 doi: 10.1088/2632-2153/ab9009
[81]	Las Heras U, Alvarez-Rodriguez U, Solano E, et al. Genetic algorithms for digital quantum simulations[J]. Physical Review Letters, 2016, 116(23): 230504 doi: 10.1103/PhysRevLett.116.230504
[82]	Kondratyev A. Non-differentiable leaning of quantum circuit Born machine with genetic algorithm[J]. Wilmott, 2021, 2021(114): 50−61
[83]	Ding Yongcheng, Lamata L, Sanz M, et al. Experimental implementation of a quantum autoencoder via quantum adders[J]. Advanced Quantum Technologies, 2019, 2(7/8): 1800065
[84]	Mitarai K, Negoro M, Kitagawa M, et al. Quantum circuit learning[J]. Physical Review A, 2018, 98(3): 032309 doi: 10.1103/PhysRevA.98.032309
[85]	He Guangping. Computing the gradients with respect to all parameters of a quantum neural network using a single circuit[J]. arXiv preprint, arXiv: 2307.08167, 2023
[86]	Li Jun, Yang Xiaodong, Peng Xinhua, et al. Hybrid quantum-classical approach to quantum optimal control[J]. Physical Review Letters, 2017, 118(15): 150503 doi: 10.1103/PhysRevLett.118.150503
[87]	Nakanishi K M, Fujii K, Todo S. Sequential minimal optimization for quantum-classical hybrid algorithms[J]. Physical Review Research, 2020, 2(4): 043158 doi: 10.1103/PhysRevResearch.2.043158
[88]	Parrish R M, Iosue J T, Ozaeta A, et al. A Jacobi diagonalization and Anderson acceleration algorithm for variational quantum algorithm parameter optimization[J]. arXiv preprint, arXiv: 1904.03206, 2019
[89]	Ostaszewski M, Grant E, Benedetti M. Structure optimization for parameterized quantum circuits[J]. Quantum, 2021, 5: 391 doi: 10.22331/q-2021-01-28-391
[90]	Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303−332 doi: 10.1137/S0036144598347011
[91]	Huang H Y, Broughton M, Mohseni M, et al. Power of data in quantum machine learning[J]. Nature Communications, 2021, 12(1): 2631 doi: 10.1038/s41467-021-22539-9
[92]	Caro M C, Huang H Y, Cerezo M, et al. Generalization in quantum machine learning from few training data[J]. Nature Communications, 2022, 13(1): 4919 doi: 10.1038/s41467-022-32550-3
[93]	Chia N H, Gilyén A P, Li T, et al. Samplingbased sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning[J]. Journal of the ACM, 2022, 69(5): 33
[94]	Huang H Y, Kueng R, Torlai G, et al. Provably efficient machine learning for quantum many-body problems[J]. Science, 2022, 377(6613): eabk3333 doi: 10.1126/science.abk3333
[95]	Huang H Y, Broughton M, Cotler J, et al. Quantum advantage in learning from experiments[J]. Science, 2022, 376(6598): 1182−1186 doi: 10.1126/science.abn7293
[96]	Aharonov D, Cotler J, Qi X L. Quantum algorithmic measurement[J]. Nature Communications, 2022, 13(1): 887 doi: 10.1038/s41467-021-27922-0
[97]	Bravyi S, Gosset D, König R. Quantum advantage with shallow circuits[J]. Science, 2018, 362(6412): 308−311 doi: 10.1126/science.aar3106
[98]	Farhi E, Neven H. Classification with quantum neural networks on near term processors[J]. arXiv preprint, arXiv: 1802.06002, 2018
[99]	Chefles A. Quantum state discrimination[J]. Contemporary Physics, 2000, 41(6): 401−424 doi: 10.1080/00107510010002599
[100]	Barnett S M, Croke S. Quantum state discrimination[J]. Advances in Optics and Photonics, 2009, 1(2): 238−278 doi: 10.1364/AOP.1.000238
[101]	Čepaitė I, Coyle B, Kashefi E. A continuous variable Born machine[J]. Quantum Machine Intelligence, 2022, 4(1): 6 doi: 10.1007/s42484-022-00063-3
[102]	Coyle B, Mills D, Danos V, et al. The Born supremacy: Quantum advantage and training of an ising Born machine[J]. NPJ Quantum Information, 2020, 6(1): 60 doi: 10.1038/s41534-020-00288-9
[103]	Rudolph M S, Toussaint N B, Katabarwa A, et al. Generation of high-resolution handwritten digits with an iontrap quantum computer[J]. Physical Review X, 2022, 12(3): 031010 doi: 10.1103/PhysRevX.12.031010
[104]	Kao P Y, Yang Y C, Chiang W Y, et al. Exploring the advantages of quantum generative adversarial networks in generative chemistry[J]. Journal of Chemical Information and Modeling, 2023, 63(11): 3307−3318 doi: 10.1021/acs.jcim.3c00562
[105]	Skolik A, Jerbi S, Dunjko V. Quantum agents in the gym: A variational quantum algorithm for deep Q-learning[J]. Quantum, 2022, 6: 720 doi: 10.22331/q-2022-05-24-720
[106]	Skolik A, Mangini S, Bäck T, et al. Robustness of quantum reinforcement learning under hardware errors[J]. EPJ Quantum Technology, 2023, 10(1): 8 doi: 10.1140/epjqt/s40507-023-00166-1
[107]	Niu M Y, Zlokapa A, Broughton M, et al. Entangling quantum generative adversarial networks[J]. Physical Review Letters, 2022, 128(22): 220505 doi: 10.1103/PhysRevLett.128.220505
[108]	Du Yuxuan, Huang Tao, You Shan, et al. Quantum circuit architecture search for variational quantum algorithms[J]. NPJ Quantum Information, 2022, 8(1): 62 doi: 10.1038/s41534-022-00570-y
[109]	Schuld M, Bocharov A, Svore K M, et al. Circuit-centric quantum classifiers[J]. Physical Review A, 2020, 101(3): 032308 doi: 10.1103/PhysRevA.101.032308
[110]	Henderson M, Shakya S, Pradhan S, et al. Quanvolutional neural networks: Powering image recognition with quantum circuits[J]. Quantum Machine Intelligence, 2020, 2(1): 2 doi: 10.1007/s42484-020-00012-y
[111]	Chu Cheng, Chia N H, Jiang Lei, et al. QMLP: An error-tolerant nonlinear quantum mlp architecture using parameterized two-qubit gates[C/OL]//Proc of the 29th Int Symp on Low Power Electronics and Design. New York: ACM, 2022[2023-11-16]. https://dl.acm.org/doi/abs/10.1145/35 31437.3539719
[112]	Chen S Y C, Huang C M, Hsing C W, et al. An end-to-end trainable hybrid classical-quantum classifier[J]. Machine Learning: Science and Technology, 2021, 2(4): 045021 doi: 10.1088/2632-2153/ac104d
[113]	Pesah A, Cerezo M, Wang S, et al. Absence of barren plateaus in quantum convolutional neural networks[J]. Physical Review X, 2021, 11(4): 041011 doi: 10.1103/PhysRevX.11.041011
[114]	Mcclean J R, Boixo S, Smelyanskiy V N, et al. Barren plateaus in quantum neural network training landscapes[J]. Nature Communications, 2018, 9(1): 4812 doi: 10.1038/s41467-018-07090-4
[115]	Monteiro C A, Gustavo Filho I, Costa M H J, et al. Quantum neuron with real weights[J]. Neural Networks, 2021, 143: 698−708 doi: 10.1016/j.neunet.2021.07.034
[116]	Hu Zhirui, Li Jinyang, Pan Zhenyu, et al. On the design of quantum graph convolutional neural network in the NISQ-era and beyond[C]//Proc of the 40th Int Conf on Computer Design (ICCD). Piscataway, NJ: IEEE, 2022: 290−297
[117]	Shepherd D, Bremner M J. Temporally unstructured quantum computation[J]. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2009, 465(2105): 1413−1439 doi: 10.1098/rspa.2008.0443
[118]	Amin M H, Andriyash E, Rolfe J, et al. Quantum Boltzmann machine[J]. Physical Review X, 2018, 8(2): 021050 doi: 10.1103/PhysRevX.8.021050
[119]	Kieferová M, Wiebe N. Tomography and generative training with quantum Boltzmann machines[J]. Physical Review A, 2017, 96(6): 062327 doi: 10.1103/PhysRevA.96.062327
[120]	Huijgen O,Coopmans L,Najafi P,et al. Training quantum Boltzmann machines with the β-variational quantum eigensolver[J]. Machine Learning:Science and Technology,2024,5(2):025017
[121]	Khoshaman A, Vinci W, Denis B, et al. Quantum variational autoencoder[J]. Quantum Science and Technology, 2018, 4(1): 014001 doi: 10.1088/2058-9565/aada1f
[122]	Huang Changjiang, Ma Hailan, Yin Qi, et al. Realization of a quantum autoencoder for lossless compression of quantum data[J]. Physical Review A, 2020, 102(3): 032412 doi: 10.1103/PhysRevA.102.032412
[123]	Cerezo M, Sone A, Volkoff T, et al. Cost function dependent barren plateaus in shallow parametrized quantum circuits[J]. Nature Communications, 2021, 12(1): 1791 doi: 10.1038/s41467-021-21728-w
[124]	Dallaire-Demers P L, Killoran N. Quantum generative adversarial networks[J]. Physical Review A, 2018, 98(1): 012324 doi: 10.1103/PhysRevA.98.012324
[125]	Tian Jinkai, Sun Xiaoyu, Du Yuxuan, et al. Recent advances for quantum neural networks in generative learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45(10): 12321−12340 doi: 10.1109/TPAMI.2023.3272029
[126]	Goodfellow I, Pouget-Abadie J, Mirza M, et al. Generative adversarial nets[C]//Proc of the 28th Conf on Neural Information Processing Systems (NeurIPS). La Jolla, CA: NIPS, 2014, 2672−2680
[127]	Carleo G, Cirac I, Cranmer K, et al. Machine learning and the physical sciences[J]. Reviews of Modern Physics, 2019, 91(4): 045002 doi: 10.1103/RevModPhys.91.045002
[128]	Hu Ling, Wu Shuhao, Cai Weizhou, et al. Quantum generative adversarial learning in a superconducting quantum circuit[J]. Science Advances, 2019, 5(1): eaav2761 doi: 10.1126/sciadv.aav2761
[129]	Kim L, Lloyd S, Marvian M. Hamiltonian quantum generative adversarial networks[J]. Physical Review Research, 2024, 6(3): 033019 doi: 10.1103/PhysRevResearch.6.033019
[130]	Du Yuxuan, Hsieh M H, Tao Dacheng. Efficient online quantum generative adversarial learning algorithms with applications[J]. arXiv preprint arXiv: 1904.09602, 2019
[131]	Pan Minghua, Wang Bin, Tao Xiaoling, et al. Application of quantum generative adversarial network to the abnormal user behavior detection and evaluation[J]. arXiv preprint, arXiv: 2208.09834, 2022
[132]	Watkins C J, Dayan P. Q-learning[J]. Machine Learning, 1992, 8(3/4): 279−292 doi: 10.1023/A:1022676722315
[133]	Mnih V, Kavukcuoglu K, Silver D, et al. Playing atari with deep reinforcement learning[J]. arXiv preprint, arXiv: 1312.5602, 2013
[134]	Van Hasselt H, Guez A, Silver D. Deep reinforcement learning with double Q-learning[C]//Proc of the 30th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2016: 2094−2100
[135]	Jerbi S, Gyurik C, Marshall S, et al. Parametrized quantum policies for reinforcement learning[C]//Proc of the 35th Annual Conf on Neural Information Processing Systems (NeurIPS). La Jolla, CA: NIPS, 2021: 28362−28375
[136]	Jerbi S, Cornelissen A, Ozols M, et al. Quantum policy gradient algorithms[J]. arXiv preprint, arXiv: 2212.09328, 2022
[137]	Wu Shaojun, Jin Shan, Wen Dingding, et al. Quantum reinforcement learning in continuous action space[J]. arXiv preprint, arXiv: 2012.10711, 2020
[138]	Ostaszewski M, Trenkwalder L M, Masarczyk W, et al. Reinforcement learning for optimization of variational quantum circuit architectures[C]//Proc of the 35th Conf on Neural Information Processing Systems (NeurIPS). La Jolla, CA: NIPS, 2021: 18182−18194
[139]	Wang S, Fontana E, Cerezo M, et al. Noise-induced barren plateaus in variational quantum algorithms[J]. Nature Communications, 2021, 12(1): 6961 doi: 10.1038/s41467-021-27045-6
[140]	Liang Zhiding, Wang Hanrui, Cheng Jinglei, et al. Variational quantum pulse learning[C]//Proc of the 3rd IEEE Int Conf on Quantum Computing and Engineering (QCE). Los Alamitos, CA: IEEE Computer Society, 2022: 556−565
[141]	Meitei O R, Gard B T, Barron G S, et al. Gatefree state preparation for fast variational quantum eigensolver simulations[J]. NPJ Quantum Information, 2021, 7(1): 155 doi: 10.1038/s41534-021-00493-0
[142]	Liang Zhiding, Cheng Jinglei, Ren Hang, et al. NAPA: Intermediate-level variational native-pulse Ansatz for variational quantum algorithms[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024, 43(6): 1834−1847 doi: 10.1109/TCAD.2024.3355277
[143]	Rattew A G, Hu S, Pistoia M, et al. A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver[J]. arXiv preprint, arXiv: 1910.09694, 2019
[144]	Havlíček V, Córcoles A D, Temme K, et al. Supervised learning with quantum-enhanced feature spaces[J]. Nature, 2019, 567(7747): 209−212 doi: 10.1038/s41586-019-0980-2
[145]	Stilck França D, Garcia-Patron R. Limitations of optimization algorithms on noisy quantum devices[J]. Nature Physics, 2021, 17(11): 1221−1227 doi: 10.1038/s41567-021-01356-3
[146]	Chen Yiting, Farquhar C, Parrish R M. Low-rank density-matrix evolution for noisy quantum circuits[J]. NPJ Quantum Information, 2021, 7(1): 61 doi: 10.1038/s41534-021-00392-4
[147]	Sharma K, Khatri S, Cerezo M, et al. Noise resilience of variational quantum compiling[J]. New Journal of Physics, 2020, 22(4): 043006 doi: 10.1088/1367-2630/ab784c
[148]	Skolik A, Mcclean J R, Mohseni M, et al. Layerwise learning for quantum neural networks[J]. Quantum Machine Intelligence, 2021, 3(1): 5 doi: 10.1007/s42484-020-00036-4
[149]	Volkoff T,Coles P J. Large gradients via correlation in random parameterized quantum circuits[J]. Quantum Science and Technology,2021,6(2):025008
[150]	Endo S, Cai Z, Benjamin S C, et al. Hybrid quantumclassical algorithms and quantum error mitigation[J]. Journal of the Physical Society of Japan, 2021, 90(3): 032001 doi: 10.7566/JPSJ.90.032001
[151]	Bilkis M, Cerezo M, Verdon G, et al. A semi-agnostic Ansatz with variable structure for quantum machine learning[J]. arXiv preprint, arXiv: 2103.06712, 2021
[152]	Weber M, Liu Nana, Li Bo, et al. Optimal provable robustness of quantum classification via quantum hypothesis testing[J]. NPJ Quantum Information, 2021, 7(1): 76 doi: 10.1038/s41534-021-00410-5
[153]	Du Yuxuan, Hsieh M H, Liu Tongliang, et al. Quantum noise protects quantum classifiers against adversaries[J]. Physical Review Research, 2021, 3(2): 023153 doi: 10.1103/PhysRevResearch.3.023153
[154]	Liu Junyu, Wilde F, Mele A A, et al. Stochastic noise can be helpful for variational quantum algorithms[J]. arXiv preprint, arXiv: 2210.06723, 2022
[155]	Gentini L, Cuccoli A, Pirandola S, et al. Noise-resilient variational hybrid quantum-classical optimization[J]. Physical Review A, 2020, 102(5): 052414 doi: 10.1103/PhysRevA.102.052414
[156]	Zhang Kaining, Liu Liu, Hsieh M H, et al. Escaping from the barren plateau via Gaussian initializations in deep variational quantum circuits[C]//Proc of the 36th Conf on Neural Information Processing Systems (NeurIPS). La Jolla, CA: NIPS, 2022: 18612−18627
[157]	Cervera-Lierta A, Kottmann J S, Aspuruguzik A. Meta-variational quantum eigensolver: Learning energy profiles of parameterized hamiltonians for quantum simulation[J]. PRX Quantum, 2021, 2(2): 020329 doi: 10.1103/PRXQuantum.2.020329
[158]	Harrow A W, Low R A. Random quantum circuits are approximate 2-designs[J]. Communications in Mathematical Physics, 2009, 291(1): 257−302 doi: 10.1007/s00220-009-0873-6
[159]	Holmes Z, Sharma K, Cerezo M, et al. Connecting Ansatz expressibility to gradient magnitudes and barren plateaus[J]. PRX Quantum, 2022, 3(1): 010313 doi: 10.1103/PRXQuantum.3.010313
[160]	Sharma K, Cerezo M, Cincio L, et al. Trainability of dissipative perceptron-based quantum neural networks[J]. Physical Review Letters, 2022, 128(18): 180505 doi: 10.1103/PhysRevLett.128.180505
[161]	Kashif M, Al-Kuwari S. The impact of cost function globality and locality in hybrid quantum neural networks on NISQ devices[J]. Machine Learning: Science and Technology, 2023, 4(1): 015004 doi: 10.1088/2632-2153/acb12f
[162]	Sim S, Johnson P D, Aspuru-Guzik A. Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms[J]. Advanced Quantum Technologies, 2019, 2(12): 1900070 doi: 10.1002/qute.201900070
[163]	Nielsen M A, Dawson C M, Dodd J L, et al. Quantum dynamics as a physical resource[J]. Physical Review A, 2003, 67(5): 052301
[164]	Jaques S, Rattew A G. Qram: A survey and critique[J]. arXiv preprint, arXiv: 2305.10310, 2023
[165]	Phalak K, Li Junde, Ghosh S. Trainable PQC-based QRAM for quantum storage[J]. IEEE Access, 2023, 11: 51892−51899 doi: 10.1109/ACCESS.2023.3278600
[166]	付祥,郑宇真,苏醒,等. 一种面向含噪中尺度量子技术的量子-经典异构计算系统[J]. 计算机研究与发展,2021,58(9):1875−1896 doi: 10.7544/issn1000-1239.2021.20210368 Fu Xiang, Zheng Yuzhen, Su Xing, et al. A heterogeneous quantum-classical computing system targeting noisy intermediate-scale quantum technology[J]. Journal of Computer Research and Development, 2021, 58(9): 1875−1896 (in Chinese) doi: 10.7544/issn1000-1239.2021.20210368
[167]	Verdon G, Pye J, Broughton M. A universal training algorithm for quantum deep learning[J]. arXiv preprint, arXiv: 1806.09729, 2018