FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing
FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing
复制标题
DOI：
10.1109/qce53715.2022.00030
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Phuc Thai;M. Thai;Tam Vu;Thang N. Dinh
中科院分区：
文献类型：
--
作者：
Phuc Thai;M. Thai;Tam Vu;Thang N. Dinh
量子退火（QA）将优化问题编码为哈密顿量，仍然是唯一的近期量子计算范式，为现实世界的应用提供足够多的量子位。为了在现有的量子退火器上适应更大的优化实例，将哈密顿量减少到更小的等效哈密顿量提供了一种有前途的方法。不幸的是，现有的减少技术要么是计算昂贵的或在实践中无效。为此，我们引入了一个新的概念，不可分的组，定义为量子比特的一个子集的哈密顿量，获得相同的值在最佳解决方案。我们相应地发展了不可分离性理论，并提出了FastHare，一种高效的约简方法。FastHare迭代地检测不可分离的组并将其合并为单个量子位。对于用户定义的参数α，它在可证明的最坏情况下的时间复杂度仅为O（αn2）。我们对约简可行性的广泛基准测试是在合成哈密顿算子和MQLIB库中的3000多个实例上完成的。结果表明，FastHare优于屋顶对偶，在D-Wave的库中实现的减少。它展示了高水平的有效性，平均节省62%的量子位和0.3s的处理时间，提倡将哈密顿约简作为QA的廉价必要条件。
Quantum annealing (QA) that encodes optimization problems into Hamiltonians remains the only near-term quantum computing paradigm that provides sufficient many qubits for real-world applications. To fit larger optimization instances on existing quantum annealers, reducing Hamiltonians into smaller equivalent Hamiltonians provides a promising approach. Unfortunately, existing reduction techniques are either computationally expensive or ineffective in practice. To this end, we introduce a novel notion of non-separable group, defined as a subset of qubits in a Hamiltonian that obtains the same value in optimal solutions. We develop non-separability theory accordingly and propose FastHare, a highly efficient reduction method. FastHare, iteratively, detects and merges non-separable groups into single qubits. It does so within a provable worst-case time complexity of only O(αn2), for some user-defined parameter α. Our extensive benchmarks for the feasibility of the reduction are done on both synthetic Hamiltonians and 3000+ instances from the MQLIB library. The results show FastHare outperforms the roof duality, the implemented reduction in D-Wave’s library. It demonstrates a high level of effectiveness with an average of 62% qubits saving and 0.3s processing time, advocating for Hamiltonian reduction as an inexpensive necessity for QA.