论文标题
使用并联量子退火解决更大的最大集团问题
Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
论文作者
论文摘要
量子退火有可能发现NP-硬问题问题的低能解决方案，这些解决方案可以表示为二次不受约束的二进制优化问题。但是，我们在这项工作中考虑的D-Wave系统制造的量子退火器的硬件是稀疏的，并且是较少的尺寸（按数千吨数的顺序），因此需要将逻辑问题限制到物理Qubit硬件上。相对较小的硬件尺寸和次要装修的必要性的组合可能意味着在当前的量子退火器上不可能解决大型优化问题。在这项研究中，我们表明，将平行量子退火与图形分解相结合的混合方法使人们可以准确解决更大的优化问题。我们将方法应用于最大总集合问题，最多120个节点和6395个边缘。
Quantum annealing has the potential to find low energy solutions of NP-hard problems that can be expressed as quadratic unconstrained binary optimization problems. However, the hardware of the quantum annealer manufactured by D-Wave Systems, which we consider in this work, is sparsely connected and moderately sized (on the order of thousands of qubits), thus necessitating a minor-embedding of a logical problem onto the physical qubit hardware. The combination of relatively small hardware sizes and the necessity of a minor-embedding can mean that solving large optimization problems is not possible on current quantum annealers. In this research, we show that a hybrid approach combining parallel quantum annealing with graph decomposition allows one to solve larger optimization problem accurately. We apply the approach on the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.
