旅行路线优化
假设你需要访问多个城市,每个城市访问一次并最终返回起点, 怎样找到总距离最短的路线?
设置你的问题
城市位置自动生成。你可以调整城市数量,也可以重新生成一组城市位置。
QPRIMORA 如何把现实问题转成量子问题
真正关键的是用户提出的现实目标,与量子处理器最终执行的计算之间, 需要经过怎样的表示、约束和原语映射。
逐步查看 QPRIMORA 如何完成转换
点击下面各层,可以看到一个“寻找最短旅行路线”的现实需求, 如何逐步变成数学优化问题,再转化成量子计算能够处理的结构。
A
DECISION VARIABLES
如何用二进制变量描述一条路线?
+
对于每一个城市 i 和路线中的每一个访问位置 t, QPRIMORA 定义一个二进制决策变量:
当 xi,t = 1 时,表示城市 i 出现在路线的第 t 个位置; 否则为 0。
B
CONSTRAINTS
怎样保证二进制结果是一条合法路线?
+
对于任意城市 i,只能有一个访问位置对应的变量等于 1。
在路线的任意位置 t,只允许一个城市出现。
C
OBJECTIVE FUNCTION
怎样告诉计算系统什么叫“更好的路线”?
+
在所有合法路线中,我们希望相邻访问城市之间的总距离最小。
D
QUBO
把目标函数与约束合并为一个优化模型
+
QPRIMORA 可以把路线距离和违反约束产生的惩罚项, 统一写入一个 Quadratic Unconstrained Binary Optimization 模型:
矩阵 Q 同时编码了城市距离信息和违反路线约束时需要付出的惩罚。
E
COST HAMILTONIAN
QUBO 怎样进入量子计算层?
+
二进制变量可以进一步映射为量子比特算符:
代入以后,QUBO 的目标函数可以转换为 Cost Hamiltonian HC。能量越低的量子状态,对应成本越低的候选路线。
F
QAOA + VIRTUAL QPU
量子优化路径怎样产生候选路线?
+
量子优化路径并不是简单地“计算出一条路线”, 而是尝试改变不同候选状态出现的概率, 让更优的解在测量时以更高概率出现。
同一个问题,两条计算路径
Virtual QPU
为什么城市增加后问题会迅速变难?
随着城市数量增加,可能路线数量会以极快速度增长。 下面用 n! 直观展示组合空间的增长速度。
本网站的 Virtual QPU 运行在经典服务器上,因此这里测得的运行时间 不能被解释为真实量子硬件的速度优势。本实例展示的是现实优化问题如何经过 问题表示、Primitive 映射并进入量子优化计算路径。目前并没有证据表明 QAOA 对旅行商问题已经具有普遍成立的实际量子加速优势。
从现实需求到 QPU 执行
QPRIMORA 的目标,是让用户描述“我要解决什么”, 而不是要求用户描述“QPU 应该执行什么”。