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 Access

An Ising Machine Approach to the Personalized Course Selection Problem

Takeru Ota, Keisuke Fukada, Nozomu Togawa

Published Jan 1, 2025• 0 citations
Publisher

Abstract

A combinatorial optimization problem is a problem finding an optimal combination of variables that maximizes or minimizes an objective function while satisfying given constraints. Such problems arise in various fields, including transportation and communication. Many combinatorial optimization problems are NP-hard, meaning that the number of possible combinations grows exponentially as the number of variables increases. As a result, it is often difficult to solve large-scale combinatorial optimization problems for conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. One real-world example of a combinatorial optimization problem isuniversity course selection. Many students manually choose their courses, but this process is time consuming and labor intensive due to the large number of available options. To address this, in this paper, we formulate course selection as a combinatorial optimization problem, which we define as a Personalized Course Selection Problem (PCSP). To solve it efficiently, we use an Ising machine, a specialized computer designed for combinatorial optimization. We propose a Quadratic Unconstrained Binary Optimization (QUBO) formulation for solving PCSP and solve the problem with an Ising machine. Experimental evaluations demonstrate that, for the largest instance tested, the proposed method solves the problem 20X times faster than the conventional simulated annealing while achieving the same total course cost.

DOI
10.1109/access.2025.3603606

Related papers

Personalized Course Selection Optimization Using an Ising Machine

Takeru Ota, Keisuke Fukada, Nozomu Togawa

Many students spend a lot of time and effort manually selecting courses, due to the large number of candidate courses offered by universities. We regard course selection as a combinatorial optimization problem and define it as an NP-hard problem. In this paper, we propose a QUBO (Quadratic Unconstrained Binary Optimization) formulation for solving the course selection problem, and solve the problem with an Ising machine. Experimental evaluations demonstrate that for the instance with the largest number of courses, our approach solves a personalized course selection problem 20X times faster than the conventional simulated annealing.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•4 citations

Personalized Course Selection Optimization Using QAOA

Takeru Ota, Keisuke Fukada, Tatsuhiko Shirai +1 more

Quantum approximate optimization algorithm (QAOA) is an algorithm for solving combinatorial optimization problems (COP), which can be implemented on gate based quantum computers. However, many practical COPs such as a personalized course selection problem (PCSP) have not been solved by QAOA yet. In this paper, we solve a PCSP using QAOA by transforming the problem into a quadratic unconstrained binary optimization (QUBO), and investigate the solution properties when the weight of the problem's constraint is changed. Experimental evaluations demonstrate that tuning the weight value improves the probability of obtaining optimal solutions and reduces the energy expectation value averaged over the obtained feasible solutions.

International Conference on Consumer Electronics•Jan 11, 2025•0 citations

A Constraint Partition Method for Combinatorial Optimization Problems

Makoto Onoda, Kazuhiko Komatsu, Masahito Kumagai +2 more

Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 18, 2023•2 citations

Ising Machine Approach to the Lecturer–Student Assignment Problem

Sora Tomita, Tatsuhiko Shirai, Nozomu Togawa

Ising machines are efficient solvers for combinatorial optimization problems (COPs). After mapping COPs to Quadratic Unconstrained Binary Optimization (QUBO) problems, Ising machines search for the lowest energy solution of the QUBO corresponding to the optimal solution of the COP. Herein we propose an efficient method to formulate a lecturer–student assignment problem as a QUBO problem. In this problem, the sets of subjects, lecturers, students, lecturers’ teachable subjects, and students’ required subjects are given. To minimize lecture costs, the number of lecturers in charge of students must be minimized. The number of combinations drastically increases as the number of lecturers or students increases. Using these results, we theoretically prove the optimality, i.e., the formulated QUBO takes the lowest energy if and only if the students are optimally assigned to the lecturers. Additionally, we demonstrate that an Ising machine outperforms simulated annealing in terms of solution quality and execution time.

IEEE Access•Jan 1, 2024•2 citations

Solving Task-Select Problems Using a Quantum Annealer

Koki Mita, Yuta Yachi, Keisuke Fukada +1 more

To tackle environmental and social challenges, we face numerous tasks that need to be solved. However, due to limited time and resources, it is unrealistic to solve all tasks. Therefore, prioritizing tasks to ensure efficient handling and meeting criteria is essential. When the number of tasks is large, prioritizing the optimal combination of tasks on classical computers becomes highly time-consuming. We define this pri-oritization as a combinatorial optimization problem, termed the task-select problem, and address it using a quantum annealer. A quantum annealer is specialized hardware designed to efficiently solve combinatorial optimization problems by transforming them into Quadratic Unconstrained Binary Optimization (QUBO) problems. In this paper, we propose a QUBO formulation for the task-select problem. Experimental evaluations demonstrate that our approach enables solving the task-select problem with up to 100 items using a real quantum annealer.

International Conference on Consumer Electronics•Jan 11, 2025•0 citations

Trip Planning Based on subQUBO Annealing

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.

IEEE Access•Jan 1, 2023•9 citations
A combinatorial optimization problem is a problem finding an optimal combination of variables that maximizes or minimizes an objective function while satisfying given constraints. Such problems arise in various fields, including transportation and communication. Many combinatorial optimization problems are NP-hard, meaning that the number of possible combinations grows exponentially as the number of variables increases. As a result, it is often difficult to solve large-scale combinatorial optimization problems for conventional classical computers. Recently, Ising machines, including quantum annealers, have gained attention as a promising architecture for efficiently solving combinatorial optimization problems. One real-world example of a combinatorial optimization problem isuniversity course selection. Many students manually choose their courses, but this process is time consuming and labor intensive due to the large number of available options. To address this, in this paper, we formulate course selection as a combinatorial optimization problem, which we define as a Personalized Course Selection Problem (PCSP). To solve it efficiently, we use an Ising machine, a specialized computer designed for combinatorial optimization. We propose a Quadratic Unconstrained Binary Optimization (QUBO) formulation for solving PCSP and solve the problem with an Ising machine. Experimental evaluations demonstrate that, for the largest instance tested, the proposed method solves the problem 20X times faster than the conventional simulated annealing while achieving the same total course cost.
Many students spend a lot of time and effort manually selecting courses, due to the large number of candidate courses offered by universities. We regard course selection as a combinatorial optimization problem and define it as an NP-hard problem. In this paper, we propose a QUBO (Quadratic Unconstrained Binary Optimization) formulation for solving the course selection problem, and solve the problem with an Ising machine. Experimental evaluations demonstrate that for the instance with the largest number of courses, our approach solves a personalized course selection problem 20X times faster than the conventional simulated annealing.
Quantum approximate optimization algorithm (QAOA) is an algorithm for solving combinatorial optimization problems (COP), which can be implemented on gate based quantum computers. However, many practical COPs such as a personalized course selection problem (PCSP) have not been solved by QAOA yet. In this paper, we solve a PCSP using QAOA by transforming the problem into a quadratic unconstrained binary optimization (QUBO), and investigate the solution properties when the weight of the problem's constraint is changed. Experimental evaluations demonstrate that tuning the weight value improves the probability of obtaining optimal solutions and reduces the energy expectation value averaged over the obtained feasible solutions.
Ising machines have attracted much attention in recent years because of their potential in solving combinatorial optimization problems that are difficult to be solved using conventional computers. Ising machines solve the optimization problem that can be transformed into a quadratic unconstrained binary optimization (QUBO) problem. In the case of a problem with constraints, named a constraint problem, an objective function and constraint function with penalty coefficients are combined into a single Hamiltonian of a QUBO problem. When solving a constraint problem, the accuracy of the solution decreases compared to a QUBO problem with an objective function only. This is because penalty coefficients are set to excessively large values to prevent constraint violations. As a result, it becomes difficult to minimize the objective function. To solve this problem, this paper proposes a method that partitions constraint functions and reduces the value of the penalty coefficients. The performance evaluation using the traveling salesperson problem (TSP) with one-hot constraints demonstrates that the proposed method can improve the solution accuracy compared to the conventional method.
Ising machines are efficient solvers for combinatorial optimization problems (COPs). After mapping COPs to Quadratic Unconstrained Binary Optimization (QUBO) problems, Ising machines search for the lowest energy solution of the QUBO corresponding to the optimal solution of the COP. Herein we propose an efficient method to formulate a lecturer–student assignment problem as a QUBO problem. In this problem, the sets of subjects, lecturers, students, lecturers’ teachable subjects, and students’ required subjects are given. To minimize lecture costs, the number of lecturers in charge of students must be minimized. The number of combinations drastically increases as the number of lecturers or students increases. Using these results, we theoretically prove the optimality, i.e., the formulated QUBO takes the lowest energy if and only if the students are optimally assigned to the lecturers. Additionally, we demonstrate that an Ising machine outperforms simulated annealing in terms of solution quality and execution time.
To tackle environmental and social challenges, we face numerous tasks that need to be solved. However, due to limited time and resources, it is unrealistic to solve all tasks. Therefore, prioritizing tasks to ensure efficient handling and meeting criteria is essential. When the number of tasks is large, prioritizing the optimal combination of tasks on classical computers becomes highly time-consuming. We define this pri-oritization as a combinatorial optimization problem, termed the task-select problem, and address it using a quantum annealer. A quantum annealer is specialized hardware designed to efficiently solve combinatorial optimization problems by transforming them into Quadratic Unconstrained Binary Optimization (QUBO) problems. In this paper, we propose a QUBO formulation for the task-select problem. Experimental evaluations demonstrate that our approach enables solving the task-select problem with up to 100 items using a real quantum annealer.
The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.