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

Chinese Control Conference (CCC)

Simulated Ising Annealing Algorithm with Gaussian Augmented Hamiltonian Monte Carlo

Langyu Li, Hao Wang, Zhixin Xie, Zixuan Liu, Wei Cui, Yu Pan

Published Jul 24, 2023• 2 citations
Publisher

Abstract

A numerical technique called Simulated Ising Annealing (SIA) uses digital computers to obtain approximations of the ground states of Ising models. The quadratic unconstrained binary optimization (QUBO) problem in combinatorial optimization, which is challenging to solve through exhaustive search, has significant linkages to the Ising model. Therefore, SIA's main objective is to identify a better solution in finite iterations. In order to enhance the performance of the simulated annealing procedure, we adopt a Gaussian augmented Hamiltonian Monte Carlo (GAHMC) method in this study. We contrasted our algorithm with Gibbs sampling and local quantum annealing method. Finally, we discuss its application on QUBO problem.

DOI
10.23919/ccc58697.2023.10240679

Related papers

An Ising Computer Based on Simulated Quantum Annealing by Path Integral Monte Carlo Method

Takuya Okuyama, Masato Hayashi, Masanao Yamaoka

In the near future, one of the main processes is solving large combinatorial optimization problems. However, the performance growth of von Neumann architecture will slow due to the end of semiconductor scaling. To resolve this problem, we propose an Ising computer that maps the optimization problems to the ground state search of Ising models. We previously proposed a computer that finds the ground state of Ising models by simulated annealing (SA) approximately. Though the solution quality of the previous prototype is comparable to that of SA, enhancing the solution quality will be required to solve real-world applications. In this paper, we present our FPGA-based Ising computer that executes simulated quantum annealing by using a path integral quantum Monte Carlo method for Ising models on a 48-by-48 king graph with 8-bit couplings. We also propose a shared random number supply, which contributes to decrease the number of random number generators to two. Experimental results indicate that the proposed Ising computer is more than 15 times faster to obtain 99.9%-solution with a probability of 99% than SA running on a state-of-the-art CPU.

IEEE International Conference on Rebooting Computing (ICRC)•Nov 1, 2017•47 citations

Multi-Objective Optimization Technique Based on QUBO and an Ising Machine

Hiroshi Ikeda, Takashi Yamazaki

With an increase in the complexity of society, solving multi-objective optimization problems (MOPs) has become crucial. In this study, we introduced a novel method called “quadratic unconstrained binary optimization based on the weighted normal” for solving MOPs using Ising machines, such as quantum annealing and digital annealer (DA), in the field of combinatorial optimization. The proposed method applies the penalty-based boundary intersection method to Ising machines under a setting limited to linear objective functions and maximizes the speed and performance of the DA, which is a quadratic unconstrained binary optimization-specific solver. We demonstrated the effectiveness of the proposed method by solving a real-world problem with a nonconvex shaped Pareto front (component combination problem). The results suggested that the proposed method could handle both convex- and nonconvex-shaped Pareto fronts, expanding the potential applications of Ising machines to solving complex MOPs. This development could significantly enhance decision-making processes, particularly in achieving sustainable development goals.

IEEE Access•Jan 1, 2024•5 citations

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•10 citations

Quantum Annealing via Path-Integral Monte Carlo With Data Augmentation

Jianchang Hu, Yazhen Wang

This article considers quantum annealing in the Ising framework for solving combinatorial optimization problems. The path-integral Monte Carlo simulation approach is often used to approximate quantum annealing and implement the approximation by classical computers, which refers to simulated quantum annealing (SQA). In this article, we introduce a data augmentation scheme into SQA and develop a new algorithm for its implementation. The proposed algorithm reveals new insights on the sampling behaviors in SQA. Theoretical analyses are established to justify the algorithm, and numerical studies are conducted to check its performance and to confirm the theoretical findings. Supplementary materials for this article are available online.

Journal of Computational and Graphical Statistics•Sep 1, 2020•4 citations

Optimization Via Open System Quantum Annealing

Sergio Boixo, Robert F. Lucas, Daniel A. Lidar +2 more

Abstract : Many computationally challenging problems can be reduced to Quadratic Unconstrained Binary Optimization (QUBO), which can be solved by a quantum evolution from a strong transverse field to a spin glass Hamiltonian (also known as quantum annealing or QA). We have examined open system QA, using theoretical and experimental techniques to deepen our understanding of open system QA by situating it in the context of related, well studied classical and quantum problems. We have explored and elucidated the significance of tunneling in QA with Path Integral Monte Carlo. We have also provided signatures of quantum behavior of QA against closely related simulated annealing implementations, analytically, numerically, and experimentally. We have carried out a comprehensive comparison of geometrically-local open-system QA and classical solvers for computationally hard problems such as MAX-2-SAT. We have exploited and further developed a graph-theoretical mapping between the Ising spin glass partition function and circuit model decision problems, discovered in a previous ARO Quantum Algorithms funded project. We have made significant progress on error correction techniques for QA, both theoretically and experimentally, and in demonstration of quantum speedup.

•Jan 7, 2016•0 citations

A Novel Classical-Ising Hybrid Annealing Method with QUBO Model Cutting

Yuta Atobe, Masashi Tawada, Nozomu Togawa

Most quantum annealers, or Ising machines have the hardware limitations in its qubit size and thus the computable problem size is much limited. This paper proposes a novel classical-Ising hybrid annealing method which virtually extends the computable size of Ising machines based on a theoretical analysis. Given a quadratic unconstrained binary optimization (QUBO) model, the proposed method selects the cutting binary variable that is most likely to have the same value as the ground-state solution. Then, we recursively cut the QUBO model based on the cutting binary variable until we obtain sufficiently small-sized subQUBO models. Experimental evaluations demonstrate that the proposed hybrid annealing method can give much better quasi-ground-state solutions than state-of-the-art existing methods for large-sized QUBO models.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 11, 2024•0 citations
A numerical technique called Simulated Ising Annealing (SIA) uses digital computers to obtain approximations of the ground states of Ising models. The quadratic unconstrained binary optimization (QUBO) problem in combinatorial optimization, which is challenging to solve through exhaustive search, has significant linkages to the Ising model. Therefore, SIA's main objective is to identify a better solution in finite iterations. In order to enhance the performance of the simulated annealing procedure, we adopt a Gaussian augmented Hamiltonian Monte Carlo (GAHMC) method in this study. We contrasted our algorithm with Gibbs sampling and local quantum annealing method. Finally, we discuss its application on QUBO problem.
In the near future, one of the main processes is solving large combinatorial optimization problems. However, the performance growth of von Neumann architecture will slow due to the end of semiconductor scaling. To resolve this problem, we propose an Ising computer that maps the optimization problems to the ground state search of Ising models. We previously proposed a computer that finds the ground state of Ising models by simulated annealing (SA) approximately. Though the solution quality of the previous prototype is comparable to that of SA, enhancing the solution quality will be required to solve real-world applications. In this paper, we present our FPGA-based Ising computer that executes simulated quantum annealing by using a path integral quantum Monte Carlo method for Ising models on a 48-by-48 king graph with 8-bit couplings. We also propose a shared random number supply, which contributes to decrease the number of random number generators to two. Experimental results indicate that the proposed Ising computer is more than 15 times faster to obtain 99.9%-solution with a probability of 99% than SA running on a state-of-the-art CPU.
With an increase in the complexity of society, solving multi-objective optimization problems (MOPs) has become crucial. In this study, we introduced a novel method called “quadratic unconstrained binary optimization based on the weighted normal” for solving MOPs using Ising machines, such as quantum annealing and digital annealer (DA), in the field of combinatorial optimization. The proposed method applies the penalty-based boundary intersection method to Ising machines under a setting limited to linear objective functions and maximizes the speed and performance of the DA, which is a quadratic unconstrained binary optimization-specific solver. We demonstrated the effectiveness of the proposed method by solving a real-world problem with a nonconvex shaped Pareto front (component combination problem). The results suggested that the proposed method could handle both convex- and nonconvex-shaped Pareto fronts, expanding the potential applications of Ising machines to solving complex MOPs. This development could significantly enhance decision-making processes, particularly in achieving sustainable development goals.
Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.
This article considers quantum annealing in the Ising framework for solving combinatorial optimization problems. The path-integral Monte Carlo simulation approach is often used to approximate quantum annealing and implement the approximation by classical computers, which refers to simulated quantum annealing (SQA). In this article, we introduce a data augmentation scheme into SQA and develop a new algorithm for its implementation. The proposed algorithm reveals new insights on the sampling behaviors in SQA. Theoretical analyses are established to justify the algorithm, and numerical studies are conducted to check its performance and to confirm the theoretical findings. Supplementary materials for this article are available online.
Abstract : Many computationally challenging problems can be reduced to Quadratic Unconstrained Binary Optimization (QUBO), which can be solved by a quantum evolution from a strong transverse field to a spin glass Hamiltonian (also known as quantum annealing or QA). We have examined open system QA, using theoretical and experimental techniques to deepen our understanding of open system QA by situating it in the context of related, well studied classical and quantum problems. We have explored and elucidated the significance of tunneling in QA with Path Integral Monte Carlo. We have also provided signatures of quantum behavior of QA against closely related simulated annealing implementations, analytically, numerically, and experimentally. We have carried out a comprehensive comparison of geometrically-local open-system QA and classical solvers for computationally hard problems such as MAX-2-SAT. We have exploited and further developed a graph-theoretical mapping between the Ising spin glass partition function and circuit model decision problems, discovered in a previous ARO Quantum Algorithms funded project. We have made significant progress on error correction techniques for QA, both theoretically and experimentally, and in demonstration of quantum speedup.
Most quantum annealers, or Ising machines have the hardware limitations in its qubit size and thus the computable problem size is much limited. This paper proposes a novel classical-Ising hybrid annealing method which virtually extends the computable size of Ising machines based on a theoretical analysis. Given a quadratic unconstrained binary optimization (QUBO) model, the proposed method selects the cutting binary variable that is most likely to have the same value as the ground-state solution. Then, we recursively cut the QUBO model based on the cutting binary variable until we obtain sufficiently small-sized subQUBO models. Experimental evaluations demonstrate that the proposed hybrid annealing method can give much better quasi-ground-state solutions than state-of-the-art existing methods for large-sized QUBO models.