Hard combinatorial problems and minor embeddings on lattice graphs
Hard combinatorial problems and minor embeddings on lattice graphs
复制标题
硬组合问题和格子图上的小嵌入
DOI：
10.1007/s11128-019-2323-5
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
A. Lucas
中科院分区：
文献类型：
--
作者：
A. Lucas
如今，硬件约束是量子绝热优化算法的一个重要限制：在存在噪声耦合常数的情况下，计算问题被表述为二次无约束二元优化（QUBO），并且QUBO的交互图需要有效的次要嵌入到二维非平面晶格图中。我们描述了为 NP 完全/硬组合问题构建 QUBO 的新策略，解决了当今硬件的这两个挑战。我们的结果包括渐近改进的数字划分嵌入、填充背包、图形着色和查找哈密顿循环。这些嵌入也可以通过减少计算量来找到。我们用于数字划分的新嵌入可能在未来的量子退火硬件上更有效。虽然我们专注于将问题嵌入到 Chimera 晶格中，但我们使用的技术及其局限性可以推广到任何非平面晶格图。
Today, hardware constraints are an important limitation on quantum adiabatic optimization algorithms: Computational problems are formulated as quadratic unconstrained binary optimization (QUBO) in the presence of noisy coupling constants, and the interaction graph of the QUBO needs an effective minor embedding into a two-dimensional non-planar lattice graph. We describe new strategies for constructing QUBOs for NP-complete/hard combinatorial problems that address both of these challenges for present-day hardware. Our results include asymptotically improved embeddings for number partitioning, filling knapsacks, graph coloring, and finding Hamiltonian cycles. These embeddings can also be found with reduced computational effort. Our new embedding for number partitioning may be more effective on future quantum annealing hardware. While we focus on embedding problems onto Chimera lattices, the techniques we use, along with their limitations, generalize to any non-planar lattice graph.