Reproduce “Ising formulations of many NP problems” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Andrew Lucas

A comprehensive compendium of explicit Ising Hamiltonian formulations is presented for a wide range of NP-complete and NP-hard problems, including all of Karp's 21, showing that these require at most a cubic polynomial number of spins. The research offers practical considerations for implementing these problems on adiabatic quantum optimization devices, addressing challenges like ancilla spin overhead and connectivity.

Key insights

  • All of Karp's 21 NP-complete problems can be explicitly formulated as Ising models, requiring a polynomial number of spins scaling no faster than N³.
  • Effective Ising formulations for complex constraints critically depend on a clear separation of energy scales between penalty terms and objective terms, along with the strategic use of auxiliary spins.
  • Practical implementation on current adiabatic quantum optimization hardware is significantly constrained by factors such as the substantial ancilla spin overhead, the need for wide dynamic range in coupling strengths, and the mismatch between highly connected Ising graphs and sparse hardware architectures.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.