Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games

本文介绍并综述了用于组合优化的 QUDO、T-QUDO 和 HOBO 公式，展示了它们的显式编码及其在背包问题、旅行商问题以及各种逻辑游戏等问题的应用，以促进其在量子及量子启发式算法中的使用。

要点

想象一下，你正在试图解决一个庞大而复杂的拼图。在计算机世界中，这被称为组合优化。这就像试图找到一种排列一组物品的最佳方式，以获得最高分数，同时严格遵守规则。

长期以来，计算机被教导使用一种名为QUBO（二次无约束二值优化）的特定语言来解决这些拼图。将 QUBO 想象为一种严格的语言，其中拼图的每一块只能处于两种状态之一：开或关（就像电灯开关）。虽然这对许多事情都有效，但这往往就像试图仅用黑白像素来描述一幅复杂的画作。你必须使用成千上万个微小的开关来表示一种颜色，这使得拼图变得巨大且难以解决。

本文介绍了三种新的、更灵活的“语言”，允许计算机用更丰富的色彩说话，从而使解决这些拼图变得更加容易。作者亚历杭德罗·马塔·阿里（Alejandro Mata Ali）通过著名的数学问题和逻辑游戏展示了这些新语言的工作原理。

以下是三种新语言及其用于测试的游戏的分解：

1. QUDO：用“旋钮”代替“开关”

概念：
在旧的 QUBO 语言中，变量是二值开关（0 或 1）。QUDO（二次无约束 D 值优化）将这些开关升级为旋钮。旋钮不再仅仅是开或关，而是可以设置为从 0 到特定上限的任何数字（就像音量旋钮可以从 0 调到 10）。

类比：
想象你在打包行李箱。

• QUBO 方法： 你必须决定每一只袜子、每一件衬衫和每一双鞋是否打包（1）或不打包（0）。如果你想打包 5 件衬衫，你需要 5 个独立的开关。
• QUDO 方法： 你有一个用于“衬衫”的单一旋钮。你只需将旋钮转到"5"，计算机就知道你要打包五件衬衫。

论文中的示例：

• 背包问题： 这是经典的“什么东西能装进包里”的拼图。论文表明，使用 QUDO 旋钮比使用数百个二值开关来计数你携带的每种物品的数量要高效得多。
• 桥连（Hashiwokakero）： 一种用桥连接岛屿的拼图。由于你可以在岛屿之间建造 0、1 或 2 座桥，旋钮（0、1 或 2）完美契合该问题，而二值开关则需要额外的技巧来计数到 2。

2. T-QUDO：“智能关系”地图

概念：
有时，拼图的规则不仅仅关乎一个旋钮的值，还关乎两个旋钮之间的关系。T-QUDO（张量 QUDO）是一种能够直接理解这些复杂关系的语言。

类比：
想象一个你必须为客人安排座位的派对。

• QUDO： 你可以告诉计算机：“如果客人 A 坐在 1 号椅子上，他就会开心。”
• T-QUDO： 你可以告诉计算机：“如果客人 A 坐在 1 号椅子上且客人 B 坐在 3 号椅子上，客人 A 就会开心。但如果客人 B 坐在 4 号椅子上，客人 A 就会生气。”
  T-QUDO 允许计算机理解这些特定的“如果 - 那么”配对，而无需将它们分解为微小且笨拙的二值步骤。

论文中的示例：

• 旅行商问题： 一名推销员必须恰好访问每个城市一次。T-QUDO 使得表达“如果你在步骤 1 位于城市 A，你就不能在步骤 2 位于城市 A"变得容易。
• N 皇后问题： 目标是在棋盘上放置皇后，使它们互不攻击。T-QUDO 非常自然地处理规则“如果皇后 A 在第 1 行第 3 列，那么皇后 B 就不能在第 2 行第 4 列”。
• 数谜（Kakuro）与密室（Inshi no Heya）： 这些是数字谜题（类似于数独，但涉及求和与求积）。T-QUDO 允许计算机直接检查数字组的和与积，而不是强迫它们进入二值数学。

3. HOBO：“群体拥抱”

概念：
有时，一条规则涉及三个或更多变量同时起作用。HOBO（高阶二值优化）是一种允许变量以群体而非仅以配对形式相互作用的語言。

类比：
想象一场抢椅子游戏。

• 二值/成对： 你只能检查 A 是否坐在 B 旁边。
• HOBO： 你可以检查 A、B 和 C 是否同时坐在一个特定的三角形阵型中。它一次性捕捉了“群体动态”。

论文中的示例：

• 跳棋（Peg Solitaire）： 这是一个通过跳过棋子来移除它们的棋类游戏。一步棋涉及三个特定的位置：起始棋子、被跳过的棋子和落点。HOBO 非常适合在单一步骤中描述这种三方互动，使解决方案更加简洁。

为什么这很重要？

论文认为，虽然这些新语言（QUDO、T-QUDO、HOBO）比旧的二值语言更复杂难学，但它们对于特定类型的问题通常高效得多。

• 更少杂乱： 它们使用更少的变量（更少的“开关”或“旋钮”）来描述相同的问题。
• 更好的硬件： 论文指出，未来的量子计算机（使用“量子位元”qudits 而不仅仅是“量子比特”qubits）正在被构建以原生支持这些语言。通过现在以这种方式制定问题，我们正在为未来的硬件做准备。
• 权衡： 你可以将这些新语言翻译回旧的二值语言（QUBO），但这通常会使问题变得更大、更混乱。这就像将一首诗从英语翻译成一种只有 26 个字母的语言，然后试图强行将其翻译回英语——它会失去其优雅。

总结

这篇论文是数学家和计算机科学家的指南。它说：“停止试图将每个复杂问题强行塞入一个简单的开/关盒子。有时，你需要一个旋钮（QUDO）、一个关系地图（T-QUDO）或一个群体拥抱（HOBO）来高效地解决拼图。”

作者通过选取困难的逻辑游戏（如桥连、N 皇后问题和跳棋），并展示这些新公式如何以比传统方法更少的资源和更清晰的规则来解决它们，从而证明了这一点。

技术摘要

以下是 Alejandro Mata Ali 所著论文《QUDO、张量 QUDO 和 HOBO 形式化介绍：量子位、等价性、背包问题、旅行商问题与组合博弈》的详细技术总结。

1. 问题陈述

组合优化问题（如背包问题、旅行商问题、N 皇后问题）通常是 NP 难的，且缺乏高效的经典解法。虽然**二次无约束二值优化（QUBO）**形式是将这些问题映射到量子硬件（特别是通过 Ising 哈密顿量和 QAOA）的标准方法，但它存在局限性：

• 变量低效性：具有自然多值状态的问题（例如从 $n$ 个物品中选择 $k$ 个）需要二进制编码，这增加了变量数量，并引入了需要惩罚项的无效状态。
• 约束局限性：某些逻辑约束（例如特定值的蕴含关系或特定值的不重合）由于变量的二进制性质（$x_i^2 = x_i$），在标准 QUBO 中难以或无法高效实现。
• 硬件不匹配：新兴的量子技术，如量子位（qudits，d 级量子系统），提供了一种自然表示非二进制变量的方法，但需要超越 QUBO 的优化形式化。

本文探讨了利用量子位和高阶相互作用的更通用形式化的需求，以减少资源开销并简化约束实现。

2. 方法论

作者引入并分析了三种广义优化框架，提供了明确的数学形式化，并展示了它们在经典问题和组合博弈中的应用。

A. 二次无约束 d 元优化（QUDO）

• 定义：QUBO 的推广，其中变量 $x_i$ 是有界的非负整数（$x_i \in \{0, 1, \dots, d_i-1\}$），而非二进制。
• 代价函数：$C(\vec{x}) = \sum_{i \le j} Q_{ij}x_i x_j + \sum D_i x_i$。
• 关键特征：
  • 需要量子位进行直接实现。
  • 允许线性项（不同于纯 QUBO 中的 $x_i^2=x_i$）。
  • 局限性：某些约束（例如“若 $x_i=a$ 则 $x_j \neq b$"）难以实现，因为相互作用项的符号取决于非二进制变量的具体值。
  • 实现：可以使用量子位相位门 $P(\theta)$ 和控制相位门映射到 QAOA。

B. 张量二次无约束 d 元优化（T-QUDO）

• 定义：QUDO 的成对类别推广。它将变量视为类别标签而非数值。
• 代价函数：$C(\vec{x}) = \sum U_i(x_i) + \sum_{i<j} V_{ij}(x_i, x_j)$。
• 关键特征：
  • 使用代价张量 $Q_{i,j, a, b}$ 来定义将值 $a$ 分配给变量 $i$ 并将值 $b$ 分配给变量 $j$ 的代价。
  • 优势：通过轻松实现复杂的逻辑约束（例如特定值的蕴含关系、特定值的不重合），克服了 QUDO 的局限性，而无需依赖算术属性。
  • 编码：可以编码为 HOBO 或 QUBO（通过独热编码或二进制编码），尽管这可能会增加变量数量。

C. 高阶二值优化（HOBO）

• 定义：使用 $m$ 阶（$m > 2$）多线性伪布尔函数的形式化。
• 代价函数：$C(\vec{y}) = \sum_{S} q_S \prod_{i \in S} y_i$，其中 $y_i \in \{0, 1\}$。
• 关键特征：
  • 允许超过两个变量之间的相互作用。
  • 与 T-QUDO 的关系：T-QUDO 相互作用可以通过将量子位标签二值化编码为 HOBO。
  • 实现：直接适用于支持高阶相互作用的基于量子比特的量子设备，或通过归约技术实现。

3. 主要贡献与案例研究

本文通过将上述形式化应用于背包问题、**旅行商问题（TSP）**和五种组合博弈，验证了这些形式化。

问题	使用的形式化	关键见解/结果
背包问题	QUDO	展示了显著的资源减少。不再使用物品计数的二进制变量，而是每个物品类别使用单个量子位直接表示计数。与 QUBO 相比，减少了所需的变量数量和松弛变量。
Hashiwokakero（桥梁）	QUDO	自然地建模了桥梁连接（0、1 或 2）。使用编码为量子位的辅助流变量来强制执行全局连通性，证明 QUDO 可以精确处理复杂的拓扑约束。
旅行商问题（TSP）	T-QUDO	使用变量 $x_t$ 表示时间步 $t$ 处的节点。“不重复”约束通过成对惩罚项 $\delta_{x_t, x_{t'}}$ 自然处理，避免了对复杂素数编码或庞大二进制矩阵的需求。
N 皇后	T-QUDO	将变量从 $N^2$（二进制网格）减少到 $N$（每行的列索引）。T-QUDO 张量自然地将行、列和对角线约束编码为特定的张量条目，简化了代价函数结构。
Kakuro（数谜）	T-QUDO	结合了 QUDO（用于求和约束）和 T-QUDO（用于不重复约束）。T-QUDO 的类别性质完美地处理了“行/列中数字唯一”的规则。
Inshi no Heya（房间里的数字）	T-QUDO	通过将乘积转换为素数指数的和（一元函数）来处理乘法区域约束，这自然地契合 T-QUDO 框架。
Peg Solitaire（跳棋）	HOBO	将游戏建模为状态序列。移动逻辑（跳过一枚棋子）需要 4 变量相互作用（源、中间、目标、时间），这在 HOBO 中自然表达，无需归约为二次项。

4. 结果

• 资源效率：QUDO 和 T-QUDO 形式化通常比其 QUBO 对应物需要更少的变量。例如，N 皇后问题从 $N^2$ 个二进制变量减少到 $N$ 个量子位。
• 约束灵活性：T-QUDO 允许直接实现逻辑约束（蕴含、不重合），而这些约束在 QUDO/QUBO 中若无辅助变量则显得笨拙或不可能实现。
• 可行性：本文为所有示例提供了明确的代价函数和惩罚项，证明了这些形式化在数学上是合理的且是“精确”的（即有效解的代价为零）。
• 量子实现：作者概述了如何在 QAOA 中实现这些代价函数：
  • QUDO：使用单量子位相位门和双量子位门。
  • T-QUDO：使用受控聚焦相位门。
  • HOBO：使用多控制相位门（或基于辅助量子位的归约）。

5. 意义

• 连接理论与硬件：本文作为利用新兴基于量子位的量子硬件的实用指南，超越了当前以量子比特为中心的研究的二进制限制。
• 算法优化：它表明，根据问题的自然结构选择合适的形式化（QUDO/T-QUDO/HOBO）可以大幅降低优化景观的复杂性，从而可能提高 QAOA 等量子算法的性能。
• 教育框架：通过使用广为人知的游戏和谜题，本文降低了理解复杂的高阶和多值优化形式化的门槛。
• 未来方向：这项工作表明，未来的量子硬件架构应原生支持高阶相互作用和量子位，以便比当前的二进制归约方法更高效地解决组合问题。

总之，本文认为，虽然 QUBO 是一个强大的工具，但QUDO、T-QUDO 和 HOBO为特定类别的组合问题（特别是涉及多值变量或复杂逻辑约束的问题）提供了更优越的效率和表达能力，并且可以直接在下一代量子设备上实现。