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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Physical Properties of Error Reduction Algorithms for Ising Machines

Kanta Hino, Shu Tanaka

Published Sep 15, 2024• 2 citations
Publisher

Abstract

Ising machines are expected to be dedicated computers that are capable of efficiently searching for good solutions to combinatorial optimization problems. When solving combinatorial optimization problems with an Ising machine, the objective function and constraints of the combinatorial optimization problems are expressed using the Ising model. Then, the low-energy states of the Ising model are searched by the internal algorithms of Ising machines. Typical internal algorithms are Simulated Annealing (SA) and Quantum Annealing (QA). Both algorithms exhibit stochastic behavior, so the final solution may contain errors. Therefore, it is an essential issue in the field of Ising machines to reduce errors as much as possible. A previous study proposed an error reduction method for QA machines, namely the Quantum Annealing Correction (QAC) model. This method reduces error by introducing penalty interaction and performing a specific decoding method. Building on these valuable insights, we proposed an alternative error reduction method, the stacked model. To verify the effectiveness, we examined on the relationship between the penalty interaction and the success probability of the QAC model and the stacked model on SA. The obtained results differ from the facts observed in QA. In summary, a decoding method different from the one considered effective in QA was found to be effective in SA. This result suggests that when considering an appropriate error reduction method, it is necessary to consider the internal algorithm of the Ising machine.

DOI
10.1109/qce60285.2024.10342

Related papers

Error Reduction via Inter-Replica Interactions for Ising Machines

Tetsuro Abe, Kanta Hino, Shu Tanaka

Ising machines, quantum annealing (QA) machines, are promising for solving combinatorial optimization problems at high speed. Problems are formulated as Ising models where optimal solutions correspond to ground states, but stochastic noise often causes deviations, necessitating error reduction strategies. The quantum annealing correction (QAC) model introduces penalty spins to favor consistent solutions across replicas and has shown effectiveness in QA, but its behavior under simulated annealing (SA) remains insufficiently understood. This study systematically evaluates the stacked model, a recently proposed error reduction method, against QAC-based and simple parallelization approaches in SA. Our results demonstrate that, even for large-scale systems, the stacked model consistently outperforms alternatives as the number of replicas increases, maintaining relatively high success probability through spontaneous replica alignment via structured coupling. These findings highlight the stacked model as a scalable and error reduction framework for Ising-based optimization.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Quantum optimization with linear Ising penalty functions for customer data science

Puya Mirkarimi, Ishaan Shukla, David C. Hoyle +2 more

Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behavior of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective. Published by the American Physical Society 2024

arXiv:2404.05467•Physical Review Research•Dec 5, 2024•15 citations

How to Reduce the Bit-Width of an Ising Model by Adding Auxiliary Spins

Daisuke Oku, Masashi Tawada, Shu Tanaka +1 more

Annealing machines have been developed as non-von Neumann computers aimed at solving combinatorial optimization problems efficiently. To use annealing machines for solving combinatorial optimization problems, we have to represent the objective function and constraints by an Ising model, which is a theoretical model in statistical physics. Further, it is necessary to transform the Ising model according to the hardware limitations. In the transformation, the process of effectively reducing the bit-widths of coefficients in the Ising model has hardly been studied so far. Thus, when we consider the Ising model with a large bit-width, a naive method, which means right bit-shift, has to be applied. Since it is expected that obtaining highly accurate solutions is difficult by the naive method, it is necessary to construct a method for efficiently reducing the bit-width. This article proposes methods for reducing the bit-widths of interaction and external magnetic field coefficients in the Ising model and proves that the reduction gives theoretically the same ground state of the original Ising model. The experimental evaluations also demonstrate the effectiveness of our proposed methods.

IEEE Transactions on Computers•Dec 15, 2020•25 citations

Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

Tatsuhiko Shirai, Nozomu Togawa

We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.

IEEE Transactions on Computers•Jan 24, 2023•13 citations

Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer

Shuta Kikuchi, Nozomu Togawa, Shu Tanaka

Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.

arXiv:2306.06589•Journal of the Physical Society of Japan•Nov 10, 2023•8 citations

イジングマシンのハードウェア制限緩和アルゴリズムの提案 (本文)

シュウタ キクチ, Shuta Kikuchi, 脩太 菊池

Algorithms for mitigating hardware restrictions in Ising machinesCombinatorial optimization problems is a category of problems which find the optimal combination of decision variables to minimize or maximize the objective function for given constraints.Ising machines, including quantum annealing machines and non-quantum type Ising machines, have attracted attention as accurate and efficient solvers for combinatorial optimization problems.However, the performance of Ising machines is limited because of hardware restrictions.This study proposes algorithms to overcome or mitigate these hardware restrictions and provide theoretical analysis of the algorithms.This thesis consists of five chapters.Chapter 1 introduces the research background and objectives.Chapter 2 presents basic knowledge, including methods to formulate combinatorial optimization problems in the Ising model, hardware restrictions, and internal algorithms such as Simulated Annealing (SA) and Quantum Annealing (QA), following the flow of solving combinatorial optimization problems with Ising machines.Chapter 3 describes a method to mitigate bit-width restriction.The study found a difference in the dynamical processes of the Ising model with SA before and after bit-width reduction.Thus, the SA parameters that align the dynamical processes of the reduced bit-width Ising model with the original Ising model, based on statistical mechanics analysis and these results.Chapter 4 describes a method to mitigate the problem size restrictions for quantum annealing machines.This study explains a hybrid optimization method that combines the larger problem size capability of non-quantum type Ising machines with the high-speed solution finding capability of quantum annealing machines.The performance of this hybrid method is evaluated using simulations with SA as the non-quantum type Ising machine and D-Wave Advantage as the quantum annealing machine.These simulations evaluate solution accuracy for problem sizes both feasible and infeasible for the quantum annealing machine, along with the parameter dependence of the hybrid method.In addition, simulations are performed with SA and QA using the master equation and the Schrödinger equation to evaluate the properties revealed by these simulations and the potential capabilities of the hybrid method.Chapter 5 describes the conclusions of this study and prospects.

•Jan 1, 2023•0 citations
Ising machines are expected to be dedicated computers that are capable of efficiently searching for good solutions to combinatorial optimization problems. When solving combinatorial optimization problems with an Ising machine, the objective function and constraints of the combinatorial optimization problems are expressed using the Ising model. Then, the low-energy states of the Ising model are searched by the internal algorithms of Ising machines. Typical internal algorithms are Simulated Annealing (SA) and Quantum Annealing (QA). Both algorithms exhibit stochastic behavior, so the final solution may contain errors. Therefore, it is an essential issue in the field of Ising machines to reduce errors as much as possible. A previous study proposed an error reduction method for QA machines, namely the Quantum Annealing Correction (QAC) model. This method reduces error by introducing penalty interaction and performing a specific decoding method. Building on these valuable insights, we proposed an alternative error reduction method, the stacked model. To verify the effectiveness, we examined on the relationship between the penalty interaction and the success probability of the QAC model and the stacked model on SA. The obtained results differ from the facts observed in QA. In summary, a decoding method different from the one considered effective in QA was found to be effective in SA. This result suggests that when considering an appropriate error reduction method, it is necessary to consider the internal algorithm of the Ising machine.
Ising machines, quantum annealing (QA) machines, are promising for solving combinatorial optimization problems at high speed. Problems are formulated as Ising models where optimal solutions correspond to ground states, but stochastic noise often causes deviations, necessitating error reduction strategies. The quantum annealing correction (QAC) model introduces penalty spins to favor consistent solutions across replicas and has shown effectiveness in QA, but its behavior under simulated annealing (SA) remains insufficiently understood. This study systematically evaluates the stacked model, a recently proposed error reduction method, against QAC-based and simple parallelization approaches in SA. Our results demonstrate that, even for large-scale systems, the stacked model consistently outperforms alternatives as the number of replicas increases, maintaining relatively high success probability through spontaneous replica alignment via structured coupling. These findings highlight the stacked model as a scalable and error reduction framework for Ising-based optimization.
Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behavior of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective. Published by the American Physical Society 2024
Annealing machines have been developed as non-von Neumann computers aimed at solving combinatorial optimization problems efficiently. To use annealing machines for solving combinatorial optimization problems, we have to represent the objective function and constraints by an Ising model, which is a theoretical model in statistical physics. Further, it is necessary to transform the Ising model according to the hardware limitations. In the transformation, the process of effectively reducing the bit-widths of coefficients in the Ising model has hardly been studied so far. Thus, when we consider the Ising model with a large bit-width, a naive method, which means right bit-shift, has to be applied. Since it is expected that obtaining highly accurate solutions is difficult by the naive method, it is necessary to construct a method for efficiently reducing the bit-width. This article proposes methods for reducing the bit-widths of interaction and external magnetic field coefficients in the Ising model and proves that the reduction gives theoretically the same ground state of the original Ising model. The experimental evaluations also demonstrate the effectiveness of our proposed methods.
We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph κ-partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.
Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.
Algorithms for mitigating hardware restrictions in Ising machinesCombinatorial optimization problems is a category of problems which find the optimal combination of decision variables to minimize or maximize the objective function for given constraints.Ising machines, including quantum annealing machines and non-quantum type Ising machines, have attracted attention as accurate and efficient solvers for combinatorial optimization problems.However, the performance of Ising machines is limited because of hardware restrictions.This study proposes algorithms to overcome or mitigate these hardware restrictions and provide theoretical analysis of the algorithms.This thesis consists of five chapters.Chapter 1 introduces the research background and objectives.Chapter 2 presents basic knowledge, including methods to formulate combinatorial optimization problems in the Ising model, hardware restrictions, and internal algorithms such as Simulated Annealing (SA) and Quantum Annealing (QA), following the flow of solving combinatorial optimization problems with Ising machines.Chapter 3 describes a method to mitigate bit-width restriction.The study found a difference in the dynamical processes of the Ising model with SA before and after bit-width reduction.Thus, the SA parameters that align the dynamical processes of the reduced bit-width Ising model with the original Ising model, based on statistical mechanics analysis and these results.Chapter 4 describes a method to mitigate the problem size restrictions for quantum annealing machines.This study explains a hybrid optimization method that combines the larger problem size capability of non-quantum type Ising machines with the high-speed solution finding capability of quantum annealing machines.The performance of this hybrid method is evaluated using simulations with SA as the non-quantum type Ising machine and D-Wave Advantage as the quantum annealing machine.These simulations evaluate solution accuracy for problem sizes both feasible and infeasible for the quantum annealing machine, along with the parameter dependence of the hybrid method.In addition, simulations are performed with SA and QA using the master equation and the Schrödinger equation to evaluate the properties revealed by these simulations and the potential capabilities of the hybrid method.Chapter 5 describes the conclusions of this study and prospects.