QPRIMORA · QUANTUM COMPUTING DEMO

旅行路线优化

Travelling Salesman Problem · TSP

假设你需要访问多个城市,每个城市访问一次并最终返回起点, 怎样找到总距离最短的路线?

这个实例重点展示的不是“量子计算一个答案”, 而是 QPRIMORA 如何把现实世界的问题逐步转换为可映射到量子计算的表示。
01 · YOUR PROBLEM

设置你的问题

6

城市位置自动生成。你可以调整城市数量,也可以重新生成一组城市位置。

当前问题地图
02 · QPRIMORA TRANSFORMATION

QPRIMORA 如何把现实问题转成量子问题

真正关键的是用户提出的现实目标,与量子处理器最终执行的计算之间, 需要经过怎样的表示、约束和原语映射。

REAL-WORLD PROBLEM 访问全部城市并最小化总距离
↓
DECISION VARIABLES x(i,t) 城市 i 是否在第 t 步被访问
↓
CONSTRAINTS 每一步一个城市 · 每个城市一次
↓
OBJECTIVE Min Σ distance(i,j)
↓
REPRESENTATION QUBO Quadratic Unconstrained Binary Optimization
↓
QPRIMORA PRIMITIVE Combinatorial Optimization
QPRIMORA · INSIDE THE TRANSFORMATION

逐步查看 QPRIMORA 如何完成转换

点击下面各层,可以看到一个“寻找最短旅行路线”的现实需求, 如何逐步变成数学优化问题,再转化成量子计算能够处理的结构。

A
DECISION VARIABLES 如何用二进制变量描述一条路线?
+

对于每一个城市 i 和路线中的每一个访问位置 t, QPRIMORA 定义一个二进制决策变量:

xi,t ∈ {0,1}

当 xi,t = 1 时,表示城市 i 出现在路线的第 t 个位置; 否则为 0。

当前问题 6 个城市
↓
36 个二进制变量
n × n
B
CONSTRAINTS 怎样保证二进制结果是一条合法路线?
+
CONSTRAINT 1 每个城市只能访问一次
Σt xi,t = 1

对于任意城市 i,只能有一个访问位置对应的变量等于 1。

CONSTRAINT 2 路线中的每个位置只能有一个城市
Σi xi,t = 1

在路线的任意位置 t,只允许一个城市出现。

二进制变量 + 约束条件 → 合法路线
C
OBJECTIVE FUNCTION 怎样告诉计算系统什么叫“更好的路线”?
+

在所有合法路线中,我们希望相邻访问城市之间的总距离最小。

min   Σi,j,t di,j xi,t xj,t+1
di,j 城市 i 与城市 j 之间的距离
x 路线决策变量
D
QUBO 把目标函数与约束合并为一个优化模型
+

QPRIMORA 可以把路线距离和违反约束产生的惩罚项, 统一写入一个 Quadratic Unconstrained Binary Optimization 模型:

E(x) = Distance(x) + A · ConstraintPenalty(x)
INPUT x ∈ {0,1}n²
→
QUBO xᵀQx
→
GOAL min E(x)

矩阵 Q 同时编码了城市距离信息和违反路线约束时需要付出的惩罚。

E
COST HAMILTONIAN QUBO 怎样进入量子计算层?
+

二进制变量可以进一步映射为量子比特算符:

xi = (1 − Zi) / 2

代入以后,QUBO 的目标函数可以转换为 Cost Hamiltonian HC。能量越低的量子状态,对应成本越低的候选路线。

QUBO → Ising form → HC → 低能量状态
F
QAOA + VIRTUAL QPU 量子优化路径怎样产生候选路线?
+
1 准备量子状态
→
2 执行 Cost / Mixer 层
→
3 调整参数
→
4 重复测量
→
5 候选解概率分布
这里最重要的概念

量子优化路径并不是简单地“计算出一条路线”, 而是尝试改变不同候选状态出现的概率, 让更优的解在测量时以更高概率出现。

03 · TWO COMPUTATION PATHS

同一个问题,两条计算路径

CLASSICAL

普通计算

城市坐标 ↓ 枚举候选路线 ↓ 计算路线距离 ↓ 选择最短路线
QUANTUM PATH

Virtual QPU

QUBO ↓ Cost Hamiltonian ↓ QAOA ↓ Virtual QPU ↓ Measurement ↓ 候选路线
04 · WHY SCALE MATTERS

为什么城市增加后问题会迅速变难?

随着城市数量增加,可能路线数量会以极快速度增长。 下面用 n! 直观展示组合空间的增长速度。

5 个城市 120
10 个城市 3,628,800
15 个城市 1.31 × 10¹²
20 个城市 2.43 × 10¹⁸
科学说明

本网站的 Virtual QPU 运行在经典服务器上,因此这里测得的运行时间 不能被解释为真实量子硬件的速度优势。本实例展示的是现实优化问题如何经过 问题表示、Primitive 映射并进入量子优化计算路径。目前并没有证据表明 QAOA 对旅行商问题已经具有普遍成立的实际量子加速优势。

QPRIMORA ARCHITECTURE

从现实需求到 QPU 执行

现实问题 → Representation → Primitive → Algorithm → Compiler → Virtual QPU → Real QPU

QPRIMORA 的目标,是让用户描述“我要解决什么”, 而不是要求用户描述“QPU 应该执行什么”。