Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine

Matthieu Parizy, Nozomu Togawa

Research output: Contribution to journalArticlepeer-review


The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.

Original languageEnglish
Pages (from-to)1526-1535
Number of pages10
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number11
Publication statusPublished - 2021 Nov


  • Ising machine
  • Ising model
  • knapsack problem
  • visualization

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine'. Together they form a unique fingerprint.

Cite this