Quantum Optimization of Fully Connected Spin Glasses
Quantum Optimization of Fully Connected Spin Glasses
复制标题
DOI：
10.1103/physrevx.5.031040
复制
发表时间：
2015-09-18
影响因子：
12.5
通讯作者：
Smelyanskiy, Vadim
中科院分区：
文献类型：
--
作者：
Venturelli, Davide;Mandra, Salvatore;Smelyanskiy, Vadim
许多 NP 难题可以被视为寻找无序的高度连接的伊辛自旋玻璃的基态的任务。如果通过量子退火寻求解决方案，通常需要通过小图嵌入技术在退火器的硬件中表示这些图，生成最终的哈密顿量，该哈密顿量由铁磁束缚自旋的耦合链组成，其结合能是自由参数。为了研究嵌入对感兴趣问题的影响，具有随机 +/- 1 耦合的完全连接的 Sherrington-Kirkpatrick 模型在 D-Wave Two (TM) 退火器上进行编程，使用多达 270 个在 Chimera 型图上交互的量子位。我们提出了在 Chimera 图中编码 Sherrington-Kirkpatrick 问题的最佳嵌入方案。结果表明，嵌入参数的最佳选择可能与嵌入问题中自旋玻璃相的出现有关，而该问题的存在以前是不确定的。这种最佳参数设置允许量子退火器的性能与优化的模拟退火算法竞争（并且在没有模拟控制误差的情况下可能优于）。
Many NP-hard problems can be seen as the task of finding a ground state of a disordered highly connected Ising spin glass. If solutions are sought by means of quantum annealing, it is often necessary to represent those graphs in the annealer's hardware by means of the graph-minor embedding technique, generating a final Hamiltonian consisting of coupled chains of ferromagnetically bound spins, whose binding energy is a free parameter. In order to investigate the effect of embedding on problems of interest, the fully connected Sherrington-Kirkpatrick model with random +/- 1 couplings is programmed on the D-Wave Two (TM) annealer using up to 270 qubits interacting on a Chimera-type graph. We present the best embedding prescriptions for encoding the Sherrington-Kirkpatrick problem in the Chimera graph. The results indicate that the optimal choice of embedding parameters could be associated with the emergence of the spin-glass phase of the embedded problem, whose presence was previously uncertain. This optimal parameter setting allows the performance of the quantum annealer to compete with (and potentially outperform, in the absence of analog control errors) optimized simulated annealing algorithms.