Effectively encoding satisfiability problems into Ising models for quantum annealing
Xiaotian Li, Koji Nakano, Victor Parque, Yasuaki Ito, Takumi Kato, Yuya Kawamata, Kai Li · International Journal of Parallel Emergent and Distributed Systems · 2024
Ising Models, defined by quadratic objective functions (or Hamiltonians), enable to use quantum annealers to search for optimal or near-optimal solutions of satisfiability problems. However, current quantum annealers have limited resolution, meaning that small or closely-valued coefficients in the Hamiltonian may be obscured by flux noise, leading to a degradation in the performance of quantum annealing. In this paper, we propose a novel design methodology for encoding satisfiability problems into Ising models via Integer Linear Programming. Experimental results show that our method can effectively reduce the resolution requirements for quantum annealers.