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:2302.04162 · Quantum Information Processing

Optimal sufficient requirements on the embedded Ising problem in polynomial time

Elisabeth Lobe, Volker Kaibel

Published Aug 8, 2023• 1 citation
arXivHTMLPDF

Abstract

Abstract One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.

DOI
10.1007/s11128-023-04058-2

Related papers

Practical Evaluation of the optimal embedded Ising problem

Lobe, Elisabeth

Suitable Ising problems for quantum annealers need to be formulated such that they respect the specific hardware restrictions and at the same time represent the original problems which shall actually be solved. This requires to find an embedding into the hardware graph and choose the parameters of the embedded Ising problem in accordance with the precision of the machine. We have developed a method to provide provably equivalent embedded Ising problems with optimal parameters for a given arbitrary Ising problem and a corresponding embedding. The thus formulated optimal embedded Ising problems are compared to the state-of-the-art embedding transformation implemented in the D-Wave API. We investigate the Ising formulations in different scenarios to evaluate the performance of both methods. Meanwhile, we study the influence of the gap parameter of the optimality method. Although in theory, any positive value for this gap parameter suffices for the equivalence of the original and the embedded problem, i.e., for separating the feasible embedded solutions from the infeasible ones, the effective gap for practical setups differs. We show that our method provides better embedded Ising problems for certain constellations in terms of a better coefficient structure of the embedded Ising problem and of a larger success probability in finding the optimal solution of the original problem. The latter is the key factor from the users' point of view for using quantum annealers to solve their problems.

•Mar 18, 2025•0 citations

Scalable embedding of parity constraints in quantum annealing hardware

Michele Cattelan, Jemma Bennett, Sheir Yarkoni +1 more

One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.

arXiv:2405.14746•Physical Review A•Jan 23, 2025•3 citations

Quantum annealing speedup of embedded problems via suppression of Griffiths singularities

Sergey Knysh, Eugeniu Plamadeala, Davide Venturelli

Optimal parameter settings for application problems embedded into hardware graphs is key to practical quantum annealers (QAs). Embedding chains typically crop up as harmful Griffiths phases but can be used as a resource as we show here: to balance out singularities in the logical problem, changing its universality class. A smart choice of embedding parameters reduces annealing times for random Ising chain from $O(exp[c\sqrt{N}])$ to $O({N}^{2})$. Dramatic reduction in time-to-solution for QAs is confirmed by numerics, for which we developed a custom integrator to overcome convergence issues.

arXiv:2006.12731•Physical review. B./Physical review. B•Dec 10, 2020•7 citations

A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines

Daisuke Oku, Kotaro Terada, Masato HAYASHI +3 more

Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.

IEICE Transactions on Information and Systems•Aug 31, 2019•33 citations

Petri Net Modeling for Ising Model Formulation in Quantum Annealing

Morikazu Nakamura, Kohei Kaneshima, Takeo Yoshida

Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation.

arXiv:2107.04304•Applied Sciences•Aug 18, 2021•7 citations

Ising machines as hardware solvers of combinatorial optimization problems

Naeimeh Mohseni, Peter L. McMahon, Tim Byrnes

Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model. The Ising model is of fundamental computational interest because it is possible to formulate any problem in the complexity class NP as an Ising problem with only polynomial overhead. A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications for a wide variety of optimization problems. In this review, we survey the current status of various approaches to constructing Ising machines and explain their underlying operational principles. The types of Ising machines considered here include classical thermal annealers based on technologies such as spintronics, optics, memristors, and digital hardware accelerators; dynamical-systems solvers implemented with optics and electronics; and superconducting-circuit quantum annealers. We compare and contrast their performance using standard metrics such as the ground-state success probability and time-to-solution, give their scaling relations with problem size, and discuss their strengths and weaknesses.

arXiv:2204.00276•Apr 1, 2022•0 citations
Abstract One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.
Suitable Ising problems for quantum annealers need to be formulated such that they respect the specific hardware restrictions and at the same time represent the original problems which shall actually be solved. This requires to find an embedding into the hardware graph and choose the parameters of the embedded Ising problem in accordance with the precision of the machine. We have developed a method to provide provably equivalent embedded Ising problems with optimal parameters for a given arbitrary Ising problem and a corresponding embedding. The thus formulated optimal embedded Ising problems are compared to the state-of-the-art embedding transformation implemented in the D-Wave API. We investigate the Ising formulations in different scenarios to evaluate the performance of both methods. Meanwhile, we study the influence of the gap parameter of the optimality method. Although in theory, any positive value for this gap parameter suffices for the equivalence of the original and the embedded problem, i.e., for separating the feasible embedded solutions from the infeasible ones, the effective gap for practical setups differs. We show that our method provides better embedded Ising problems for certain constellations in terms of a better coefficient structure of the embedded Ising problem and of a larger success probability in finding the optimal solution of the original problem. The latter is the key factor from the users' point of view for using quantum annealers to solve their problems.
One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.
Optimal parameter settings for application problems embedded into hardware graphs is key to practical quantum annealers (QAs). Embedding chains typically crop up as harmful Griffiths phases but can be used as a resource as we show here: to balance out singularities in the logical problem, changing its universality class. A smart choice of embedding parameters reduces annealing times for random Ising chain from O(exp[cN])O(exp[c\sqrt{N}])O(exp[cN​]) to O(N2)O({N}^{2})O(N2). Dramatic reduction in time-to-solution for QAs is confirmed by numerics, for which we developed a custom integrator to overcome convergence issues.
Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.
Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation.
Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model. The Ising model is of fundamental computational interest because it is possible to formulate any problem in the complexity class NP as an Ising problem with only polynomial overhead. A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications for a wide variety of optimization problems. In this review, we survey the current status of various approaches to constructing Ising machines and explain their underlying operational principles. The types of Ising machines considered here include classical thermal annealers based on technologies such as spintronics, optics, memristors, and digital hardware accelerators; dynamical-systems solvers implemented with optics and electronics; and superconducting-circuit quantum annealers. We compare and contrast their performance using standard metrics such as the ground-state success probability and time-to-solution, give their scaling relations with problem size, and discuss their strengths and weaknesses.