Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2508.06909 · Journal of the Physical Society of Japan

Performance of the Extended Ising Machine for the Quadratic Knapsack Problem

Haruka Akishima, Hirotaka Tamura, Kazue Kudo

Published Aug 8, 2025• 0 citations
arXivHTMLPDF

Abstract

The extended Ising machine (EIM) enhances conventional Ising models, which handle only binary quadratic forms by allowing constraints through real-valued dependent variables. We address the quadratic knapsack problem (QKP), hard to solve using Ising machines when formulated as a quadratic unconstrained binary optimization (QUBO). We demonstrated the EIM's superiority by comparing it with the conventional Ising model-based approach, a commercial exact solver, and a state-of-the-art heuristic solver for QKP.

DOI
10.7566/jpsj.94.095002

Related papers

Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem

Kentaro Ohno, Tatsuhiko Shirai, Nozomu Togawa

Combinatorial optimization has wide applications from industry to natural science. Ising machines bring an emerging computing paradigm for efficiently solving a combinatorial optimization problem by searching a ground state of a given Ising model. Current cutting-edge Ising machines achieve fast sampling of near-optimal solutions of the max-cut problem. However, for problems with additional constraint conditions, their advantages have been hardly shown due to difficulties in handling the constraints. In this work, we focus on benchmarks of Ising machines on the quadratic knapsack problem (QKP). To bring out their practical performance, we propose fast two-stage post-processing for Ising machines, which makes handling the constraint easier. Simulation based on simulated annealing shows that the proposed method substantially improves the solving performance of Ising machines and the improvement is robust to a choice of encoding of the constraint condition. Through evaluation using an Ising machine called Amplify Annealing Engine, the proposed method is shown to dramatically improve its solving performance on the QKP. These results are a crucial step toward showing advantages of Ising machines on practical problems involving various constraint conditions.

arXiv:2403.19175•IEEE Access•Jan 1, 2024•9 citations

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

Matthieu Parizy, Nozomu Togawa

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 7, 2021•16 citations

Performance Comparison of Typical Binary-Integer Encodings in an Ising Machine

Kensuke Tamura, Tatsuhiko Shirai, Hosho Katsura +2 more

The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.

IEEE Access•Jan 1, 2021•56 citations

Self-Adaptive Ising Machines for Constrained Optimization

Corentin Delacour

Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.

arXiv:2501.04971•Design, Automation, and Test in Europe•Mar 31, 2025•1 citation

Performance of Domain-Wall Encoding in Digital Ising Machine

Shuta Kikuchi, Takahashi, Kotaro, Shu Tanaka

To tackle combinatorial optimization problems using an Ising machine, the objective function and constraints must be mapped onto a quadratic unconstrained binary optimization (QUBO) model. While QUBO involves binary variables, combinatorial optimization problems frequently include integer variables, which require encoding by binary variables. This process, known as binary-integer encoding, includes various methods, one of which is domain-wall encoding - a recently proposed approach. Experiments on a quantum annealing machine have demonstrated that domain-wall encoding outperforms the commonly used one-hot encoding in terms of objective function value and the probability of obtaining the optimal solution. In a digital Ising machine, domain-wall encoding required less computation time to reach optimal solutions compared to one-hot encoding. However, its practical effectiveness in digital Ising machines remains unclear. To address this uncertainty, the performance of one-hot and domain-wall encoding methods was evaluated on a digital Ising machine using the quadratic knapsack problem (QKP). The comparison focused on the dependency of penalty coefficient and sensitivity to computation time. Domain-wall encoding demonstrated a higher feasible solution rate when relative penalty coefficients for the two constraint terms were adjusted, a strategy not commonly used in previous studies. Additionally, domain-wall encoding obtained higher performance practical evaluation metrics for QKPs with large knapsack capacities compared to one-hot encoding. Furthermore, it was observed to be more sensitive to computation time than one-hot encoding.

arXiv:2410.11198•Oct 15, 2024•0 citations

A Hybrid Integer Encoding Method for Obtaining High-Quality Solutions of Quadratic Knapsack Problems on Solid-State Annealers

Satoru Jimbo, Daiki Okonogi, Kota Ando +4 more

For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.

IEICE Transactions on Information and Systems•Nov 30, 2022•7 citations
The extended Ising machine (EIM) enhances conventional Ising models, which handle only binary quadratic forms by allowing constraints through real-valued dependent variables. We address the quadratic knapsack problem (QKP), hard to solve using Ising machines when formulated as a quadratic unconstrained binary optimization (QUBO). We demonstrated the EIM's superiority by comparing it with the conventional Ising model-based approach, a commercial exact solver, and a state-of-the-art heuristic solver for QKP.
Combinatorial optimization has wide applications from industry to natural science. Ising machines bring an emerging computing paradigm for efficiently solving a combinatorial optimization problem by searching a ground state of a given Ising model. Current cutting-edge Ising machines achieve fast sampling of near-optimal solutions of the max-cut problem. However, for problems with additional constraint conditions, their advantages have been hardly shown due to difficulties in handling the constraints. In this work, we focus on benchmarks of Ising machines on the quadratic knapsack problem (QKP). To bring out their practical performance, we propose fast two-stage post-processing for Ising machines, which makes handling the constraint easier. Simulation based on simulated annealing shows that the proposed method substantially improves the solving performance of Ising machines and the improvement is robust to a choice of encoding of the constraint condition. Through evaluation using an Ising machine called Amplify Annealing Engine, the proposed method is shown to dramatically improve its solving performance on the QKP. These results are a crucial step toward showing advantages of Ising machines on practical problems involving various constraint conditions.
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.
The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.
Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.
To tackle combinatorial optimization problems using an Ising machine, the objective function and constraints must be mapped onto a quadratic unconstrained binary optimization (QUBO) model. While QUBO involves binary variables, combinatorial optimization problems frequently include integer variables, which require encoding by binary variables. This process, known as binary-integer encoding, includes various methods, one of which is domain-wall encoding - a recently proposed approach. Experiments on a quantum annealing machine have demonstrated that domain-wall encoding outperforms the commonly used one-hot encoding in terms of objective function value and the probability of obtaining the optimal solution. In a digital Ising machine, domain-wall encoding required less computation time to reach optimal solutions compared to one-hot encoding. However, its practical effectiveness in digital Ising machines remains unclear. To address this uncertainty, the performance of one-hot and domain-wall encoding methods was evaluated on a digital Ising machine using the quadratic knapsack problem (QKP). The comparison focused on the dependency of penalty coefficient and sensitivity to computation time. Domain-wall encoding demonstrated a higher feasible solution rate when relative penalty coefficients for the two constraint terms were adjusted, a strategy not commonly used in previous studies. Additionally, domain-wall encoding obtained higher performance practical evaluation metrics for QKPs with large knapsack capacities compared to one-hot encoding. Furthermore, it was observed to be more sensitive to computation time than one-hot encoding.
For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.