Fast Embedding of Constrained Satisfaction Problem to Quantum Annealer with Minimizing Chain Length
Juexiao Su, Lei He · 2017
Recent research has demonstrated promising results in solving constrained satisfaction problem (CSP) using D-Wave quantum annealer. However, the embedding of the CSP suffers drawbacks such as long embedding time in addition to poor quality due to long chains that reduce the ground state probability. To address those issues, we propose an effective embedding technique that reduces the embedding time and minimizes the chain length. We compared to the most recent method published in DAC 2016. Experiments using existing D-Wave 2X quantum annealer show that the proposed embedding technique increases the ground state probability by 29% on average. Furthermore, to demonstrate the efficiency, we embedded large problems onto a predicted C100 D-Wave Chimera architecture. Experimental results show that our approach reduces the run-time by 3.4x on average with reduced longest chain length.