论文标题
关于二次无约束二进制优化问题的硬度
On the hardness of quadratic unconstrained binary optimization problems
论文作者
论文摘要
我们使用精确的枚举来表征次数不到21个变量的二进制二进制优化问题的解决方案，这些解决方案的锤子距离分布到近距离解决方案。我们还使用D-Wave Advantage 5.1量子退火器执行实验，解决了多达170个可变的，二次无约束的二进制优化问题的许多实例。我们的结果表明，表征D波员工成功概率以解决QUBO的指数与基于针对小问题实例计算的锤距离分布的预测非常相关。
We use exact enumeration to characterize the solutions of quadratic unconstrained binary optimization problems of less than 21 variables in terms of their distributions of Hamming distances to close-by solutions. We also perform experiments with the D-Wave Advantage 5.1 quantum annealer, solving many instances of up to 170-variable, quadratic unconstrained binary optimization problems. Our results demonstrate that the exponents characterizing the success probability of a D-Wave annealer to solve a QUBO correlate very well with the predictions based on the Hamming distance distributions computed for small problem instances.
