On Quantum Computing for Mixed-Integer Programming
On Quantum Computing for Mixed-Integer Programming
复制标题
混合整数规划的量子计算
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
P. Graf
中科院分区：
文献类型：
--
作者：
Chin;E. Jones;P. Graf
量子计算（QC）作为一种新的计算资源正在兴起，对于某些类型的优化问题，它可能优于传统计算（CC）。然而，原则上量子计算只能解决无约束的二进制规划问题，而混合整数线性规划（MIP）在实际中最受关注。我们试图通过开发一种新的混合整数线性规划方法来弥合量子计算能力与实际应用之间的差距。其思路是将混合整数线性规划分解为二进制规划和线性规划（LP）问题，分别由量子计算和传统计算来解决。我们形式化了一种分解方法，确保通过足够数量的来回迭代，该算法能够达到原始混合整数线性规划问题的最优解。该算法在2000Q的D - Wave量子处理单元（QPU）上进行了测试，并被证明对小规模测试案例是有效的。
Quantum computing (QC) is emerging as a new computing resource that could be superior to conventional computing (CC) for certain classes of optimization problems. However, in principle QC can only solve unconstrained binary programming problems, while mixed-integer linear programming (MIP) is of most interest in practice. We attempt to bridge the gap between the capability of QC and real-world applications by developing a new approach for MIP. The idea is decomposing the MIP into binary programming and linear programming (LP) problems, which are respectively solved by QC and conventional computing. We formalize a decomposition approach that ensures that with a sufficient number of back and forth iterations, the algorithm can reach the optimal solution of the original MIP problem. The algorithm is tested on a 2000Q D-Wave quantum processing units (QPU) and is shown to be effective for small-scaled test cases.