Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

本文证明，在变分量子算法中使用夸特（整数）编码而非传统的量子比特（二进制）编码，可显著降低资源需求和模拟运行时间，同时在现实电动汽车车队管理问题上实现相当或更优的优化性能。

要点

想象一下，你是一家小型电动出租车车队的经理。你每天有两项主要任务：

1. 为车辆充电：你需要决定何时将车辆插入电网（充电）或让车辆向电网反向供电（放电），以节省成本。
2. 分配行程：你需要决定哪辆车负责哪位乘客的行程。

这是一个难题。如果将错误的车辆分配给某次行程，或在错误的时间充电，可能会导致电池耗尽或违反电网规则。完美解决这个难题对计算机来说非常困难，尤其是当你将量子物理的规则也加入其中时。

本文是本田研究所（Honda Research Institute）和莱顿大学（Leiden University）的研究人员提交的一份报告，他们提出了一个简单的问题："我们如何将这个难题‘翻译’成量子计算机的语言，这一点重要吗？"

他们测试了两种不同的“语言”（编码方式），以观察哪一种能帮助量子计算机更快、更好地解决问题。

两种语言：“量子比特”与“量子位”

为了理解他们的实验，想象你正在尝试向机器人描述一系列行程。

1. 旧方法：“量子比特”语言（二进制开关）
想象一个电灯开关。它要么开，要么关。

• 在这种方法中，研究人员为每一对可能的车辆与行程组合都使用了一个独立的电灯开关。
• 如果你有 3 辆车和 2 次行程，你需要 6 个开关。如果某个开关是“开”的，就意味着“车 1 负责行程 A"；如果是“关”的，则意味着不是这样。
• 问题所在：这创造了一个巨大且杂乱的、布满开关的房间。计算机必须检查数百万种组合，其中大多数都是无意义的（例如“车 1 负责行程 A"和“车 2 负责行程 A"同时发生）。计算机浪费了大量时间去检查这些不可能的场景。

2. 新方法：“量子位”语言（多档位旋钮）
想象一个调光开关或可以指向多个数字的旋钮，而不仅仅是 0 或 1。

• 在这种方法中，他们不是使用许多开关，而是为每次行程使用一个旋钮。
• 如果旋钮指向"1"，意味着“车 1 负责这次行程”；如果指向"2"，意味着“车 2"；如果指向"0"，意味着“没有车辆负责这次行程”。
• 优势：这要直接得多。你不需要检查两辆车是否在争夺同一次行程；旋钮在物理上无法同时指向两辆车。它缩小了计算机需要搜索的“房间”大小。

实验：与时间的赛跑

研究人员运行了他们量子计算机的模拟（一种“状态向量模拟”，相当于完美、无噪声的预演），以观察这两种语言的表现。他们设置了许多随机场景，包含不同数量的车辆、行程和时间段。

以下是他们的发现：

• 搜索空间缩小：“量子位”（旋钮）方法将搜索空间的大小呈指数级缩减。想象一下在干草堆里找一根针。量子比特方法给你的干草堆有一座山那么大。而量子位方法给你的干草堆只有一个鞋盒那么大。
• 结果更快：因为“鞋盒”要小得多，模拟运行速度快得多。量子位方法找到解决方案所需的时间显著减少。
• 质量更高：令人惊讶的是，量子位方法不仅运行得更快，而且找到了更好或同等的解决方案。它找到的解决方案更接近完美答案，且结果更加一致（更少“抖动”或随机性）。
• “深度”问题：他们尝试通过向算法添加更多层（深度）来让量子计算机“思考”得更深入。通常，思考得更深入会有所帮助。但在这里，随着深度增加，量子比特方法反而变得困惑，表现更差，这可能是因为它有太多变量需要处理，导致计算机过早停止优化。而量子位方法即使在问题变得更加复杂时，依然保持稳定和稳健。

结论

该论文得出结论，对于涉及调度和分配任务的问题（例如将电动车分配给行程），使用**量子位（旋钮）方法比传统的量子比特（开关）**方法要明智得多。

这就像为旅行打包行李：

• 量子比特：你带着一箱一只只单独的袜子，试图把它们塞进一个盒子里。你浪费了空间和时间。
• 量子位：你带着一捆折叠整齐的袜子。它完美契合，占用空间更小，你可以瞬间拿到它。

研究人员建议，对于拥有众多选项的现实世界调度问题，使用这些“多值”量子旋钮（量子位）是一条切实可行且高效的前进道路，既能节省时间，又能节省计算能力。

技术摘要

技术摘要：比较用于电动汽车充电与行程分配问题的量子比特与量子位编码

问题陈述
本文探讨了管理电动汽车（EV）车队的约束优化问题。这涉及两个耦合的决策过程：在离散时间范围 $T$ 内调度 $N_{EV}$ 辆车的双向（或单向）充电，并将这些车辆分配给 $R$ 个客户行程请求。目标是在满足严格运行约束（包括电池荷电状态（SOC）限制、行程重叠、电网功率边界，以及车辆在服务行程时不能充电的要求）的同时，最小化充电成本。

研究的核心挑战在于，行程分配变量的编码选择如何影响变分量子算法（VQAs），特别是量子近似优化算法（QAOA）的资源需求和优化行为。作者比较了两种不同的表示方法：

1. 二进制（量子比特）编码：为每个 EV-行程对使用一个二进制变量（$r_{n,i} \in \{0,1\}$）。这需要显式约束来确保每个行程最多由一辆 EV 服务，且重叠的行程不会被分配给同一辆车。
2. 整数（量子位）编码：为每个行程使用一个整数变量（$q_i \in \{0, \dots, N_{EV}\}$），其值直接指定分配的 EV（或未服务状态）。这种编码本质上满足了“每行程一辆 EV"的约束，无需对分配施加显式的二进制约束。

方法论
作者使用 QAOA 构建问题模型。两种编码均使用量子位变量表示充电功率水平（$l_{n,t}$），但在行程分配的计算基上有所不同。

• 哈密顿量构建：经典成本函数和约束被提升为计算基中的对角算子。约束（例如 SOC 限制、行程期间禁止充电）通过添加到成本哈密顿量中的非线性惩罚项来强制执行。
• 模拟：研究采用精确态矢量模拟来对算法进行基准测试。为了模拟真实的硬件限制，成本函数的期望值使用有限数量的测量次数（$M=256$）进行估计，而非精确计算。
• 优化：经典优化器（Powell 方法）通过改变 QAOA 参数（$\gamma, \beta$）来最小化成本函数。研究针对每个问题类别运行了 10 个随机实例，每个实例进行 10 次优化运行，使用固定的 200 次内部优化器迭代预算。
• 测试案例：分析了两类问题：
  • 双向充电：3 辆 EV，2 个时间步，2 个行程，3 个充电级别（$d=3$）。
  • 单向充电：2 辆 EV，3 个时间步，可变行程数（$R=2,3,4$），2 个充电级别（$d=2$）。

主要贡献与结果
本文从多个指标对两种编码进行了比较分析：

1. 希尔伯特空间缩减：与二进制（量子比特）编码相比，整数（量子位）编码指数级地减少了希尔伯特空间的维度。配置比率由 $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$ 给出。对于测试实例，这将搜索空间从数万个状态减少到数千个状态。
2. 优化性能：
   • 平均能隙：量子位编码始终实现与量子比特编码相当或略优的平均能隙。
   • 方差：量子位结果在不同运行中表现出的能隙方差显著更低。
   • 成功概率：找到全局最优解的运行比例以及采样到的可行状态比例，对于量子位编码通常更高或更稳定。
3. 运行时间与收敛性：
   • 模拟运行时间：由于希尔伯特空间较小，量子位编码所需的模拟运行时间大幅缩短（与电路深度呈线性关系，但系数小得多）。
   • 层深行为：随着 QAOA 深度（$L$）的增加，量子比特编码的性能下降比量子位编码更为显著。作者将此归因于变分参数数量的增加，使得在固定的迭代预算内，优化景观更难导航。量子位编码对经典优化器的过早终止具有更强的鲁棒性。
4. 成本景观：由于不可行状态的比例较大（这些状态会产生高额惩罚成本），与量子位编码相比，量子比特编码的成本景观显示出更大的能量尺度和更高的振荡频率。

意义与主张
本文主张，量子位原生编码为在变分量子优化中解决整数和多值调度问题提供了一条实用途径。其主要意义在于证明，通过量子位直接表示离散多值变量，而不是将其扩展为二进制量子比特，可以带来以下优势：

• 在希尔伯特空间维度上实现指数级资源节省。
• 在经典模拟中降低计算开销（作为表示复杂性的代理）。
• 在优化过程中提高鲁棒性，特别是在可行解稀疏的高度约束机制中。

作者指出，虽然该研究使用了态矢量模拟，但这种紧凑的表示法暗示了通过减少约束处理和逻辑变量映射的开销，可能为硬件实现带来潜在益处。他们得出结论，对于约束调度问题，量子位编码是一种更优的选择，它在大幅减少资源需求的同时，保持或提升了优化性能。本文谦逊地建议，未来的工作应在更大的实例和实际量子硬件上测试这些趋势，以验证这些优势是否在模拟之外依然存在。