Paper Info
Title
Fast Embedding of Constrained Satisfaction Problem to Quantum Annealer with Minimizing Chain Length.
Abstract
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.
Year
DOI
Venue
2017
10.1145/3061639.3062246
DAC
Field
DocType
ISSN
Simulated annealing,Quantum,Data structure,Mathematical optimization,Embedding,Ground state,Computer science,Algorithm,Stationary state
Conference
0738-100X
Citations 
PageRank 
References 
0
0.34
6
Authors
2
Name
Order
Citations
PageRank
Juexiao Su1102.10
Lei He2167.77