Experimenting with D-Wave Quantum Annealers on Prime Factorization problems

AI4S QNN VQAO
2024年06月11日
本文基于我们最近发表的一篇论文,其中我们提出了一种通过量子退火进行质因数分解(PF)的新方法,在该方法中,8,219,999 = 32,749x251是我们能够分解的最高质数乘积,据我们所知,这是迄今为止通过量子设备分解的最大数字。然而,导致这些结果的一系列退火实验并没有遵循直线路径;相反,它们涉及到一个复杂的试错过程,充满了失败或部分失败的尝试和回溯,最终才使我们找到了成功的退火策略。在本文中,我们深入探讨了我们实验决策背后的原因,并介绍了我们在构思最终策略之前采取的一些尝试。这还涉及到一些我们研究过的想法、技术和策略,虽然最终证明与我们采用的那些相比较劣,但可能会为D-Wave用户和实践者提供一些见解。特别是,我们展示了以下见解:($i$)不同的初始化技术会影响性能,其中流量偏置在针对局部结构嵌入时是有效的;($ii$)与依赖于全局嵌入的问题相比,链强度对于局部结构嵌入的影响较小;($iii$)链断和激发CFAs之间存在权衡,建议采用基于模块而不是单个量子比特的逐步退火偏移补救方法。因此,通过分享我们的经验细节,我们旨在为量子退火的不断发展提供见解,并帮助人们访问和有效使用D-Wave量子退火器。
This paper builds on top of a paper we have published very recently, in which we have proposed a novel approach to prime factorization (PF) by quantum annealing, where 8,219,999=32,749x251 was the highest prime product we were able to factorize -- which, to the best of our knowledge is the largest number which was ever factorized by means of a quantum device. The series of annealing experiments which led us to these results, however, did not follow a straight-line path; rather, they involved a convoluted trial-and-error process, full of failed or partially-failed attempts and backtracks, which only in the end drove us to find the successful annealing strategies. In this paper, we delve into the reasoning behind our experimental decisions and provide an account of some of the attempts we have taken before conceiving the final strategies that allowed us to achieve the results. This involves also a bunch of ideas, techniques, and strategies we investigated which, although turned out to be inferior wrt. those we adopted in the end, may instead provide insights to a more-specialized audience of D-Wave users and practitioners. In particular, we show the following insights: ($i$) different initialization techniques affect performances, among which flux biases are effective when targeting locally-structured embeddings; ($ii$) chain strengths have a lower impact in locally-structured embeddings compared to problem relying on global embeddings; ($iii$) there is a trade-off between broken chain and excited CFAs, suggesting an incremental annealing offset remedy approach based on the modules instead of single qubits. Thus, by sharing the details of our experiences, we aim to provide insights into the evolving landscape of quantum annealing, and help people access and effectively use D-Wave quantum annealers.
许愿