跳转至

基于子图同构的量子电路映射算法

本节将介绍如何使用子图同构选择量子电路映射比特，此方法仅适用于量子比特连接结构中存在可完全匹配的子图情况。

算法原理

该算法是一种基于经典图同构算法VF2的量子电路映射方法，专门用于处理量子电路拓扑与硬件物理拓扑存在严格子图同构关系的场景，即以下两种情况：

  • 当量子电路拓扑图与硬件拓扑图完全匹配时

  • 当量子电路拓扑图是硬件拓扑图的子图时

图同构基础

本映射算法中描述的子图同构关系在数学上称为子图单射同构（Subgraph Monomorphism），定义如下：

给定两个图 \(G_1 = (V_1, E_1)\) ， \(G_2 = (V_2, E_2)\) ，若存在单射函数 \(f: V_1 -> V_2\) 满足： ∀(u,v)∈E₁ ⇔ (f(u),f(v))∈E₂

    1. 顶点映射的单射性

$$ \forall u, v \in V_1, \ u \neq v \Rightarrow f(u) \neq f(v) $$

    1. 边关系的完全保持

$$ \forall (u,v) \in E_1 \Rightarrow (f(u), f(v)) \in E_2 $$

此时称 \(G_1\) 是 \(G_2\) 的子图单射同构。

量子映射转化

在量子环境下， \(G_1\) 通常指电路拓扑：

  • 顶点：逻辑量子比特位

  • 边：双比特门操作

  • 边权重：电路中同一对比特之间的双比特门操作数在电路中总双比特门数中的占比

\(G_2\) 通常指硬件拓扑：

  • 顶点：物理量子比特位

  • 顶点权重：物理量子比特的单比特门保真度

  • 边：允许直接耦合的两比特门

  • 边权重：一对物理量子比特之间的双比特门保真度

考虑保真度

由于在物理拓扑上的同结构子图可能存在多个，因此在考虑选择映射区域和映射策略时会充分考虑物理拓扑的保真度，评分方式：

  • 顶点评分：子图中所有物理量子比特的单比特门保真度的均值

  • 边评分：获取映射关系后，若硬件提供了双比特门的保真度数据，则对电路中每对逻辑量子位的交互，累加其保真度与权重的乘积

  • 最终评分：电路中单比特门在所有门中的占比 * 顶点评分 + 电路中双比特门在所有门中的占比 * 边评分

最终会选择评分最高的映射作为最终映射策略。

代码实例

以以下电路和拓扑为例，运行 VF2 映射算法

from QuICT.core import Circuit, Layout
from QuICT.core.gate.gate import CX
from QuICT.qcda.mapping import VF2Mapping

layout = Layout.load_file("example/layout/ibmq_lima.json")
print(layout)

该拓扑形式为：

ibmq_lima with 5 qubits.
0  <->  1, with error rate 1.0
1  <->  2, with error rate 1.0
1  <->  3, with error rate 1.0
3  <->  4, with error rate 1.0

circuit = Circuit(5)
CX | circuit([0, 2])
CX | circuit([1, 2])
CX | circuit([3, 1])
circuit.draw(method="command", flatten=True)

映射前的原电路：

q_0: |0>──■───────────────
          │         ┌────┐
q_1: |0>──┼─────■───┤ cx ├
        ┌─┴──┐┌─┴──┐└─┬──┘
q_2: |0>┤ cx ├┤ cx ├──┼───
        └────┘└────┘  │
q_3: |0>──────────────■───

vf2 = VF2Mapping(layout)
circuit_map = vf2.execute(circuit)
circuit_map.draw(method="command", flatten=True)

映射后的电路：

q_0: |0>──■───────────────
        ┌─┴──┐┌────┐
q_1: |0>┤ cx ├┤ cx ├──────
        └────┘└─┬──┘┌────┐
q_3: |0>────────■───┤ cx ├
                    └─┬──┘
q_4: |0>──────────────■───