为若干线性限制建设司机汉密尔顿人 (Constructing Driver Hamiltonians for Several Linear Constraints)

from arxiv, 20 pages, 2 figures. Major editing of section V, with more thorough proofs and more clear definitions to help clarify the text. Small changes in other sections, including a more clear reduction between ILP-QCOMMUTE and EQUAL SUBSET SUM

Recent advances in the field of adiabatic quantum computing and the closely related field of quantum annealers has centered around using more advanced and novel Hamiltonian representations to solve optimization problems. One of these advances has centered around the development of driver Hamiltonians that commute with the constraints of an optimization problem - allowing for another avenue to satisfying those constraints instead of imposing penalty terms for each of them. In particular, the approach is able to use sparser connectivity to embed several practical problems on quantum devices than other common practices. However, designing the driver Hamiltonians that successfully commute with several constraints has largely been based on strong intuition for specific problems and with no simple general algorithm to generate them for arbitrary constraints. In this work, we develop a simple and intuitive algebraic framework for reasoning about the commutation of Hamiltonians with linear constraints - one that allows us to classify the complexity of finding a driver Hamiltonian for an arbitrary set of constraints as NP-hard.

翻译：诊断量子计算领域的最新进展和量子annealers领域密切相关的量子计算领域最近的进展集中在利用更先进和新的汉密尔顿式代表来解决优化问题,其中一项进展集中在发展驾驶汉密尔顿人,他们与优化问题的限制交替使用另一种途径来满足这些限制,而不是对每一种限制施加惩罚。特别是,这种方法能够利用较稀少的连通性,在量子装置上嵌入一些实际问题,而不是其他常见做法。然而,设计驾驶汉密尔顿人成功通勤的驾驶员主要基于对具体问题的强烈直觉,没有简单的通用算法来产生任意限制。在这项工作中,我们开发了一个简单和直观的代数框架,用于推理对具有线性限制的汉密尔顿人进行减刑,从而使我们能够将寻找驾驶汉密尔顿人的复杂程度归为任意的制约。