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

Science

Taking the pulse of optimization

I. S. Osborne

Published Nov 3, 2016• 0 citations
Publisher

Abstract

Optical Processing
Finding the optimum solution of multiparameter or multifunctional problems is important across many disciplines, but it can be computationally intensive. Many such problems defined as computationally difficult can be mathematically mapped onto the so-called Ising problem, which
DOI
10.1126/science.354.6312.593-m

Related papers

Solving complex optimization problems with a coherent Ising machine

Hiroki Takesue, Takahiro Inagaki, Toshimori Honjo

SPIE Newsroom•Jul 19, 2017•0 citations

A fully programmable 100-spin coherent Ising machine with all-to-all connections

Peter L. McMahon, Alireza Marandi, Yoshitaka Haribara +11 more

Taking the pulse of optimization Finding the optimum solution of multiparameter or multifunctional problems is important across many disciplines, but it can be computationally intensive. Many such problems defined as computationally difficult can be mathematically mapped onto the so-called Ising problem, which looks at finding the minimum energy configuration for an array of coupled spins. Inagakiet al.and McMahonet al.show that an optical processing approach based on a network of coupled optical pulses in a ring fiber can be used to model and optimize large-scale Ising systems. Such a scalable architecture could help to optimize solutions to a wide range of complex problems. Science, this issue pp. 603 and 614

Science•Oct 21, 2016•703 citations

Progress in optical information processing

J. Shimada

IEEE Journal of Quantum Electronics•Sep 1, 1975•0 citations

A Constrained Graph Coloring Solver Based on Ising Machines

Soma Kawakami, Yosuke Mukasa, Siya Bao +5 more

Optimum or quasi-optimum solutions of combinatorial optimization problems can be efficiently found by using Ising machines. The graph coloring problem (GCP) is known as a difficult combinatorial problem. Given a graph, each vertex should be assigned a color and any two vertices connected by an edge must not be colored the same. Although methods to map the GCP onto the Ising model are proposed, none of them considers minimizing the number of colors. In this paper, we propose a mapping method of the GCP including minimizing the number of colors and additional constraints to the QUBO (Quadratic Unconstrained Binary Optimization) model. As well as the constraint terms for the GCP, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two more additional terms so that our proposed method can be applicable to practical consumer applications. The experimental evaluations on an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared with the existing baseline method. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

International Conference on Consumer Electronics•Jan 6, 2023•2 citations

Ising-Machine-Based Solver for Constrained Graph Coloring Problems

Soma Kawakami, Yosuke Mukasa, Siya Bao +5 more

Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Sep 11, 2023•3 citations

A programmable optoelectronic Ising machine for direct third-order optimization

Xuelong Ma, Zhentong Li, Qi Chen +8 more

Optics Express•Oct 28, 2026•0 citations
Taking the pulse of optimization Finding the optimum solution of multiparameter or multifunctional problems is important across many disciplines, but it can be computationally intensive. Many such problems defined as computationally difficult can be mathematically mapped onto the so-called Ising problem, which looks at finding the minimum energy configuration for an array of coupled spins. Inagakiet al.and McMahonet al.show that an optical processing approach based on a network of coupled optical pulses in a ring fiber can be used to model and optimize large-scale Ising systems. Such a scalable architecture could help to optimize solutions to a wide range of complex problems. Science, this issue pp. 603 and 614
Optimum or quasi-optimum solutions of combinatorial optimization problems can be efficiently found by using Ising machines. The graph coloring problem (GCP) is known as a difficult combinatorial problem. Given a graph, each vertex should be assigned a color and any two vertices connected by an edge must not be colored the same. Although methods to map the GCP onto the Ising model are proposed, none of them considers minimizing the number of colors. In this paper, we propose a mapping method of the GCP including minimizing the number of colors and additional constraints to the QUBO (Quadratic Unconstrained Binary Optimization) model. As well as the constraint terms for the GCP, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two more additional terms so that our proposed method can be applicable to practical consumer applications. The experimental evaluations on an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared with the existing baseline method. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.
Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.