GDMCTS-QAS: Graph based Dynamic Monte Carlo Tree Search for Quantum Architecture Search

📝 备注
一句话概括本文核心：我们提出一个全新的量子线路自动搜索架构，用 DAG 图表示量子线路层，利用合理的方法大幅降低了搜索空间，并结合改良的 Monte Carlo Tree Search 方法，在同一个框架下测试了 VQE、QML、MaxCut 三种自动化设计量子线路任务，找到的线路比手工设计的线路更浅、更准、双比特门更少。 🎉🎉🎉

一、如何自动设计量子线路呢？

1. 手工设计量子线路的困境

假设你是一个计算机专业的硕士生，而你此前并没有量子力学和量子计算的知识基础（正是本人😭），而你的研究方向是量子计算和量子机器学习。有一天，你的导师突然问你：“能不能设计一个量子线路，用于解决 MNIST 手写数字二分类问题？” 此时你一脸懵逼，回答：“我不会啊！！我只会用传统 CNN ！！”

因为传统 CNN 只需设计一系列的卷积层、池化层、全连接层和不同的激活函数即可，训练过程让它自己慢慢折腾即可。而量子线路你需要设定线路的深度是多少？不同层放量子门型又是什么？哪里放旋转门？哪里放纠缠门？头都大了😆，即使你是量子计算的专家，也不敢保证他们手工设计出来的量子线路稳定又有效。

手工设计通常依赖研究者的直觉：我觉得这里用 $Ry$，我觉得这里加 $CNOT$，我觉得堆 3 层 entanglement layer，我觉得这个 ansatz 应该有效。但问题是，不同任务需要的线路结构可能完全不同。比如 MNIST 二分类、量子化学基态能量估计、组合优化、量子态分类，它们对线路的要求不一样。一个在 MNIST 上有效的线路，不一定在别的任务上有效。

一个量子线路可以由很多因素决定：

量子比特数
量子门类型
门的顺序
门作用在哪些 qubit 上
纠缠连接方式
线路深度
参数共享方式
测量方式
硬件拓扑约束

哪怕只考虑几个 qubit，可能的线路组合也非常多，组合数量会迅速爆炸，是指数级别增长的。所以，自动设计量子线路很有必要，靠人工设计量子线路不知要设计到猴年马月😓

2. 自动设计量子线路的步骤

自动化搜索量子线路的第一步，是把“设计线路”形式化成一个搜索问题。

一个量子线路可以看成一串操作：

1
2
3
4
5
第 1 步：在 q0 上放 Ry 门
第 2 步：在 q1 上放 Rz 门
第 3 步：在 q0 和 q1 之间放 CNOT
第 4 步：在 q2 上放 Rx 门
……

也就是说，设计线路本质上是在不断回答几个问题：选什么量子门？放在哪些 qubit 上？放在第几层？要不要加纠缠？线路什么时候停止？

于是，量子线路搜索可以被看成：

1
2
3
4
5
6
7
8
9
从空线路开始
    ↓
一步步添加量子门
    ↓
形成候选量子线路
    ↓
训练并评估性能
    ↓
保留更好的线路

用一句话说：

自动化量子线路搜索，就是让算法在巨大的线路结构空间中，自动寻找高性能、低成本、硬件友好的量子线路。

I. 先定义搜索空间：算法能选什么？

自动化搜索不是凭空搜索。我们首先要告诉算法：你可以从哪些“积木”里搭线路。

这些积木通常包括：

1
2
3
4
5
6
单比特门：Rx, Ry, Rz, H
双比特门：CNOT, CZ, iSWAP
可训练参数门：Ry(θ), Rz(θ)
测量方式：测量 q0，或者测量多个 qubit
纠缠模式：线性、环形、全连接、硬件拓扑连接
线路深度限制：最多几层

比如一个简单搜索空间可以是：

1
2
3
4
Gate set = {Rx, Ry, Rz, CNOT}
最大深度 = 6
量子比特数 = 4
只允许相邻 qubit 使用 CNOT

这样搜索算法就不会乱来。它不会生成硬件上无法执行的线路，也不会无限制地堆门。

II. 再定义评价指标：什么叫“好线路”？

自动化搜索的关键不只是“找到能跑的线路”，而是要定义什么叫“好”。

对于 MNIST 二分类，最直接的目标是：分类准确率越高越好。但量子线路不能只看准确率。因为线路太深、双比特门太多，在真实量子硬件上很容易被噪声毁掉。

所以更合理的评价指标通常是多目标的：

1
2
3
4
5
6
7
准确率高
线路深度浅
双比特门数量少
参数数量少
符合硬件拓扑
训练稳定
噪声鲁棒性好

可以写成一个综合得分：

$$ Score = Accuracy - \lambda_1 \cdot Depth - \lambda_2 \cdot CNOTs - \lambda_3 \cdot Parameters $$

意思是：准确率越高，分数越高；线路越深、$CNOT$ 越多、参数越多，分数越低。这样搜索出来的线路不会只是“很准但很臃肿”，而是更接近真正可用的量子线路。

III. 核心流程：生成、训练、评估、更新

一个典型的自动化量子线路搜索流程可以写成这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
空线路
  ↓
添加量子门
  ↓
候选线路
  ↓
训练参数θ
  ↓
验证集评估
  ↓
搜索算法决定下一步怎么走
  ↓
输出最优线路

这里要注意一点：搜索线路结构 和 训练线路参数 是两个层次的问题。

结构搜索回答的是：这个门该不该放？放在哪？线路长什么样？

参数训练回答的是：这个 $Ry(θ)$ 的 $θ$ 应该是多少？这个 $Rz(θ)$ 的 $θ$ 应该是多少？

所以完整流程其实是一个双层优化问题：

内层优化线路参数，给定一个量子线路结构 $\mathcal{A}$，我们先训练它的参数：

$$ \theta^{*}(\mathcal{A}) = \arg\min_{\theta} \mathcal{L}_{\mathrm{train}}(\theta,\mathcal{A}) $$

意思是：如果线路结构已经固定，那么就像训练普通神经网络一样，优化其中的参数 $\theta$，让训练集 loss 尽可能小。

外层优化线路结构，给定一个量子线路结构 $\mathcal{A}$，先训练出最优参数 $\theta^{*}$，再训练结构：

$$ \mathcal{A}^{*} = \arg\min_{\mathcal{A}\in\Omega} \mathcal{L}_{\mathrm{val}} \left( \theta^{*}(\mathcal{A}), \mathcal{A} \right) $$

在验证集上评估它的效果，最后选择验证集表现最好的线路结构。

二、为什么不用传统蒙特卡洛树搜索？

1. 传统蒙特卡洛树搜索的流程

I. 蒙特卡洛树搜索的背景

蒙特卡洛树搜索 (Monte Carlo Tree Search)，简称 MCTS，是一类用于解决序列决策问题的启发式搜索算法。它最早在博弈 AI 中被广泛使用，例如围棋、国际象棋、将棋等问题，后来也扩展到规划、程序合成、神经网络结构搜索、量子线路搜索等任务中。传统搜索方法，例如深度优先搜索、广度优先搜索、极小极大搜索，通常会遇到一个问题：搜索空间太大，无法完整遍历。例如围棋中每一步都有大量可能落子，若穷举所有局面，计算量会呈指数级增长。

MCTS 的核心思想是：

不直接遍历整棵搜索树，而是通过大量随机模拟，逐步把计算资源集中到更有希望的分支上。

它结合了两类思想：

一是 树搜索，即把决策过程表示成一棵树，节点表示状态，边表示动作。

二是 蒙特卡洛采样，即通过随机模拟估计某个状态或动作的长期收益。

因此，MCTS 特别适合以下问题：

搜索空间巨大；
很难手工设计精确评价函数；
可以通过模拟或实验获得某个方案的收益；
需要在探索新方案和利用已有好方案之间取得平衡。

在量子线路搜索、神经架构搜索这类任务中，也可以把一个“部分结构”看成树上的节点，把“追加一个操作/一层结构”看成动作，然后用 MCTS 搜索高性能结构。

II. 蒙特卡洛树的基本建模

在 MCTS 中，搜索过程通常被建模为一棵树：

节点 $s$：表示当前状态；
边 $a$：表示从状态 $s$ 采取的动作；
子节点 $s’$：表示执行动作后的新状态；
奖励 $R$：表示一次完整模拟得到的结果；
访问次数 $N(s)$：节点 $s$ 被访问的次数；
累积收益 $W(s)$：节点 $s$ 经过多次模拟得到的总收益；
平均收益 $Q(s)$：节点的经验价值。

节点的平均收益通常定义为：

$$ Q(s)=\frac{W(s)}{N(s)} $$

其中，$Q(s)$ 越大，说明该节点对应的状态在过去模拟中表现越好。

III. 传统蒙特卡洛树搜索的四个阶段

MCTS 的一次完整迭代通常包含四个阶段：

选择 Selection → 扩展 Expansion → 模拟 Simulation/Rollout → 回传 Backpropagation

经过大量迭代后，算法会选择访问次数最多或平均收益最高的动作作为最终决策。

MCTS四个阶段

a. Selection，选择阶段

选择阶段的目标是：

从根节点出发，沿着当前搜索树向下走，选择一个最值得继续探索的节点。

如果只选择当前平均收益最高的节点，算法容易陷入局部最优；如果完全随机选择，又会浪费大量计算资源。因此 MCTS 需要在两者之间平衡：

Exploitation：优先选择当前表现好的分支；
Exploration：适当尝试访问次数少、不确定性大的分支。

传统 MCTS 中最常见的选择策略是 UCT，Upper Confidence Bound applied to Trees。

$UCT(s,a)=Q(s,a)+c\sqrt{\frac{\ln N(s)}{N(s,a)}}$

其中：

$Q(s,a)$ 表示在状态 $s$ 下采取动作 $a$ 的平均收益；
$N(s)$ 表示父节点 $s$ 被访问的次数；
$N(s,a)$ 表示动作 $a$ 被选择的次数；
$c$ 是探索系数，用于控制探索强度。

这个公式由两部分组成：

$$ Q(s,a) $$

表示利用项，即当前动作过去表现得好不好。

$$ c\sqrt{\frac{\ln N(s)}{N(s,a)}} $$

表示探索项。若某个动作访问次数 $N(s,a)$ 很少，那么这一项较大，算法会更愿意尝试它。随着该动作被访问次数增加，探索项逐渐减小。

所以选择阶段的决策可以写成：

$$ a^*=\arg\max_a\left[Q(s,a)+c\sqrt{\frac{\ln N(s)}{N(s,a)}}\right] $$

这个公式意味着：

这个分支过去表现不错吗？如果不错，就继续利用。这个分支虽然访问少，但可能有潜力吗？如果有，也值得探索。

b.Expansion，扩展阶段

选择阶段会从根节点一路向下，直到遇到一个还没有完全展开的节点。

所谓“没有完全展开”，是指该节点还有一些合法动作没有被尝试过。

在扩展阶段，MCTS 会从这些未尝试动作中选择一个动作，并生成一个新的子节点。

假设当前节点是 $s$，动作集合是：

$$ A(s)=\{a_1,a_2,\dots,a_k\} $$

如果其中动作 $a_i$ 还没有被尝试，那么执行该动作会得到新状态：

$$ s'=T(s,a_i) $$

其中 $T$ 表示状态转移函数。

在棋类游戏中，$s$ 可以是当前棋盘局面，$a_i$ 是一步落子，$s’$ 是落子后的新棋盘。

在量子线路搜索中，$s$ 可以表示当前已经构造出的部分量子线路，$a_i$ 可以表示追加一个量子门或一层候选 Layer，$s’$ 就是扩展后的新线路结构。

扩展阶段的作用是：

把搜索树从已有区域向未知区域扩展，使算法不断发现新的候选方案。

如果没有扩展阶段，MCTS 只能在已有节点之间反复选择，无法探索新的结构。

c. Simulation / Rollout，模拟阶段

扩展出新节点后，MCTS 通常不会立即对整棵子树做精确搜索，而是从这个新节点开始进行一次快速模拟，也叫 Rollout。

模拟阶段的目标是：

从当前新节点出发，用某种默认策略快速走到终止状态，并获得一个奖励值。

设扩展得到的新状态为 $s’$，从 $s’$ 开始按照默认策略 $\pi_{\text{rollout}}$ 采样动作：

$$ a_t \sim \pi_{\text{rollout}}(\cdot|s_t) $$

然后状态不断转移：

$$ s_{t+1}=T(s_t,a_t) $$

直到达到终止状态 $s_T$，得到奖励：

$$ R=G(s_T) $$

其中 $G(s_T)$ 是终止状态的评价函数。

在围棋中，模拟阶段可能是从当前局面随机下到终局，然后根据胜负得到奖励：

$$ R= \begin{cases} 1, & \text{win}\\ 0, & \text{lose} \end{cases} $$

在结构搜索任务中，奖励可以是模型性能，例如准确率、损失函数的负值、线路保真度、能量误差等。也可以加入复杂度惩罚，例如：

$$ R = \text{Accuracy} - \lambda \cdot \text{Cost} $$

其中 $\lambda$ 控制性能和复杂度之间的权衡。

模拟阶段的特点是：它通常不追求非常精确，而是通过大量采样获得统计估计。单次 Rollout 可能很粗糙，但多次 Rollout 后，平均结果可以逐渐反映某个分支的潜力。

需要补充的是，在 MCTS-QAS 中：

Rollout 不是直接进行量子态模拟，而是临时生成一个更完整的候选量子线路；随后 evaluate 会对这个候选线路进行真实的任务评价，通常是在经典量子模拟器或数值后端上完成，而不是默认提交到真实量子硬件。

d. Backpropagation，回传阶段

模拟得到奖励 $R$ 后，MCTS 会把这个结果从新扩展的节点一路向上回传到根节点。

假设这次搜索经过的路径为：

$$ s_0 \rightarrow s_1 \rightarrow s_2 \rightarrow \cdots \rightarrow s_L $$

其中 $s_0$ 是根节点，$s_L$ 是本次扩展或模拟对应的节点。

对于路径上的每个节点 $s_i$，更新访问次数和累积收益：

$$ N(s_i) \leftarrow N(s_i)+1 $$

然后更新平均收益：

$$ Q(s_i)=\frac{W(s_i)}{N(s_i)} $$

如果是按边记录统计量，也可以写成：

$$ N(s_i,a_i) \leftarrow N(s_i,a_i)+1 $$

回传阶段的意义是：

把一次模拟得到的经验反馈给整条决策路径，使之后的选择阶段能够基于新的统计信息做出更好的判断。

也就是说，MCTS 并不是每次独立随机搜索，而是在不断积累经验。访问次数、平均收益和 UCT 值都会随着迭代不断变化。