.png){kind=icon}
返回
A quantum constraint generation framework for binary linear programs
.png){kind=icon}
OA
AI
DOI：10.1140/epjqt/s40507-025-00364-z.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们提出了一种新的方法，利用量子计算机进行二元线性规划（BLP），该方法可以扩展到一般的整数线性规划（ILP）。量子优化算法，无论是混合的还是仅量子算法，目前都是通用的、独立的ILP求解器。然而，要考虑它们具有实际应用价值，我们期望它们能超越当前最先进的经典求解器。这种期望对量子算法来说是不公平的：在经典的ILP求解器中，经过数十年的发展，许多不同的算法协同工作，形成了一个稳健的系统以获得最佳结果。这是我们希望现在通过我们的量子“求解器”方案所遵循的方法。在本研究中，我们将任何合适的量子优化算法封装到一个受量子启发的经典约束生成框架中。首先，我们通过移除所有约束来松弛问题，并将其编码为量子优化子程序的Ising哈密顿量。然后，通过从子程序的解态中采样，我们获得关于初始问题中约束违反的信息，从而决定需要将哪些耦合项引入哈密顿量。这些耦合项对应于初始二元线性规划的约束。接着，我们再次对新哈密顿量进行优化，直到达到可行解，或满足其他停止条件。由于可以决定在单步中向哈密顿量添加多少约束，我们的算法至少与它封装的（混合）量子优化算法一样高效。我们通过在小规模最小成本精确覆盖问题实例上的结果来支持我们的主张。
Keyword:
Constraint generation
Quantum optimization
Binary linear programming
期刊
IF:
5.6
论文数:
539
被引数:
1.1K
机构
引用论文
Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution.png)
NATURE PHYSICS
NATURE PHYSICSIF18.4
PREAI
分享收藏A variational eigenvalue solver on a photonic quantum processor光子量子处理器上的变分特征值求解器NATURE COMMUNICATIONS
OAAI
NATURE COMMUNICATIONSIF15.7
OAAI分享收藏分享收藏From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz从量子近似优化算法到量子交替算子AnsatzAlgorithmsOAAI
AlgorithmsIF0
OAAI分享收藏
查看更多内容