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.
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.
Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm capable of solving combinatorial optimization problems on gate-based quantum computers. Postprocessing Variationally Scheduled Quantum Algorithm (pVSQA) is an enhanced approach that combines a quantum variational algorithm like QAOA with a postprocessing step that transforms infeasible solutions into feasible ones. Compared to QAOA, pVSQA can more efficiently solve constrained combinatorial optimization problems. In this paper, we define the personalized course selection problem (PCSP), which involves finding the optimal combination of courses for a student, and then propose a method that integrates a postprocessing algorithm into pVSQA to effectively solve PCSP. Experimental results show that, compared to conventional QAOA, pVSQA significantly improves both the probability to obtain feasible solutions and the energy expectation among feasible solutions.
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.
Quantum computers are expected to offer advantages in solving optimization problems challenging for classical computers. Quadratic Unconstrained Binary Optimization (QUBO) problems represent an important class of problems with relevance in finance and logistics. The Quantum Approximate Optimization Algorithm (QAOA) is a prominent candidate for solving QUBO problems on near-term quantum devices. In this paper, we evaluate the performance of both the standard QAOA and the adaptive derivative assembled problem tailored QAOA (ADAPT-QAOA) to solve QUBO problems of varying sizes and hardnesses for financial feature selection problems. Our main observation is that ADAPT-QAOA achieves substantially higher approximation ratios than standard QAOA for harder feature-selection problems (α = 0.6) with statistically significant improvements observed for problem sizes n = 6 and 14. However, the standard QAOA remains competitive for simpler problems. Additionally, we evaluate the practical feasibility and limitations of QAOA through a hardware-aware scaling analysis based on the real-device calibration data for various hardware platforms. We estimate that standard QAOA implementation on superconducting quantum computers provides a shorter time-to-solution compared to trapped-ion devices, while trapped-ion devices yield more favorable error rates. Our findings provide a comprehensive overview of the challenges, trade-offs, and strategies for deploying QAOA-based methods on near-term quantum hardware.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
Combinatorial optimization is a promising area for achieving quantum speedup. The quantum approximate optimization algorithm (QAOA) is designed to search for low-energy states of the Ising model, which correspond to near-optimal solutions of combinatorial optimization problems (COPs). However, effectively dealing with constraints of COPs remains a significant challenge. Existing methods, such as tailoring mixing operators, are typically limited to specific constraint types, like one-hot constraints. To address these limitations, we introduce a method for engineering a compressed space that represents the feasible solution space with fewer qubits than the original. Our approach includes a scalable technique for determining the unitary transformation between the compressed and original spaces on gate-based quantum computers. We then propose compressed space QAOA, which seeks near-optimal solutions within this reduced space, while utilizing the Ising model formulated in the original Hilbert space. Experimental results on a quantum simulator demonstrate the effectiveness of our method in solving various constrained COPs.