One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.
翻译:量子麻醉器的核心应用之一是找到解决Ising问题的办法。但是,适当的问题是,需要提出问题,以便一方面尊重硬件的具体限制,另一方面代表实际要解决的原始问题。我们从分析角度评价这种嵌入的问题的充分要求,并将它们转化为线性优化问题。一个旨在尽量减少最大绝对问题参数的客观功能是解决Anners的精确问题。由于一些限制的冗余,我们可以表明,在嵌入的脊椎诱导树木的标准嵌入环境中,正式的大规模优化问题可以减少并最终在混合时间最终解决。这样就可以在实际设置中形成与嵌入的嵌入的Is问题相当的相似的问题。