We propose a post-processing variationally scheduled quantum algorithm (pVSQA) for solving constrained combinatorial optimization problems (COPs). COPs are typically transformed into ground-state search problems of the Ising model on a quantum annealer or gate-based quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. pVSQA on a simulator shows that a small number of variational parameters is sufficient to achieve a (near-)optimal performance within a predetermined operation time. Then building upon the simulator results, we implement pVSQA on a quantum annealer and a gate-based quantum device. The experimental results demonstrate the effectiveness of our proposed method.
We propose a post-processing variationally scheduled quantum algorithm (pVSQA) for solving constrained combinatorial optimization problems (COPs). COPs are typically transformed into ground-state search problems of the Ising model on a quantum annealer or gate-based quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. pVSQA on a simulator shows that a small number of variational parameters is sufficient to achieve a (near-)optimal performance within a predetermined operation time. Then building upon the simulator results, we implement pVSQA on a quantum annealer and a gate-based quantum device. The experimental results demonstrate the effectiveness of our proposed method.
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.
This study investigates the graph partitioning problem as a constrained combinatorial optimization problem and evaluates the effectiveness of the Postprocessing Variationally Scheduled Quantum Algorithm(pVSQA)on the instances of up to 30 qubits. We executed pVSQA using Fujitsu's highperformance quantum simulator in a single-node configuration and compared its performance with the conventional Quantum Approximate Optimization Algorithm (QAOA). Experimental results on various instances show that pVSQA consistently outperforms QAOA in terms of feasibility and optimality, successfully obtaining optimal solutions even for30-qubit instances. The study also demonstrates that Fujitsu's quantum simulator is effective for the stable execution of large-scale quantum circuits.
A range of quantum algorithms, especially those leveraging variational parameterization and circuit-based optimization, are being studied as alternatives for solving classically intractable combinatorial optimization problems (COPs). However, their applicability is limited by hardware constraints, including shallow circuit depth, limited qubit counts, and noise. To mitigate these issues, we propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of COPs, while preserving problem structure. Our approach introduces three key ideas: (i) constraint-aware shrinking that prevents merges that will likely violate problem-specific feasibility constraints, (ii) a verification-and-repair pipeline to correct infeasible solutions post-optimization, and (iii) adaptive strategies for recalculating correlations and controlling the graph shrinking process. We apply our approach to three standard benchmark problems: Multidimensional Knapsack (MDKP), Maximum Independent Set (MIS), and the Quadratic Assignment Problem (QAP). Empirical results show that our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances. These findings demonstrate a scalable pathway for applying near-term quantum algorithms to classically challenging constrained optimization problems.
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.
Abstract We introduce a novel hybrid quantum–classical variational optimization method for unconstrained binary combinatorial optimization problems on gate-model quantum computers, integrating a custom variational ansatz, staged feedback-based dual variational parameter update strategies, efficient parametric compilation, automated error suppression during hardware execution, and scalable O( n ) classical post-processing to correct for bitflip errors. Without this integrated approach, we show that standard circuit execution at scale produces output indistinguishable from random sampling, establishing the necessity of each pipeline component. We benchmark the method on IBM superconducting quantum computers for several optimization problems drawn from NP-hard problem classes, where the optimization is conducted on hardware with no use of classical simulation or prior knowledge of the solution. For Max-Cut on random regular graphs with topologies not matched to device connectivity, the method achieves approximation ratios (AR) of 100% for unweighted 3-regular graphs up to 156 nodes, weighted regular graphs up to 80 nodes, and weighted 7-regular graphs up 50 nodes. Applied to higher-order binary optimization, the method finds the ground state energy of 127- and 156-qubit spin-glass models matched to device topology with linear, quadratic, and cubic interaction terms, achieving ARs of at least 99.5% across all instances tested. The method consistently outperforms a classical local solver across all problems. Where published results on identical problem instances are available, our method demonstrates competitive or superior performance. These results demonstrate that an appropriately engineered variational approach enables gate-model quantum computers to produce high-quality solutions for binary optimization problems drawn from NP-hard problem classes at the 156-qubit scale, where naïve implementations are insufficient for good performance.
Constrained combinatorial optimization problems are challenging for quantum computing, particularly at utility-relevant scales and on near-term hardware. At the same time, these problems are of practical significance in industry; for example, the Unit Commitment (UC) problem in energy systems involves complex operational constraints. To address this challenge, we apply copula-QAOA (cop-QAOA), a hardware-efficient approach for constrained optimization to a single-period UC that can be reduced to a one-dimensional knapsack. Cop-QAOA biases the quantum state toward feasible solutions using constant-depth mixers and appropriately biased initial states. We implement our benchmark on problem instances that are confirmed to be hard for classical solvers such as Gurobi. Our results show that cop-QAOA often finds solutions better than a lazy greedy baseline and very close to, and in some instances surpasses, those obtained by Gurobi, with only a few QAOA rounds. This work presents the largest successful demonstration of the knapsack problem on IBM Quantum hardware using up to 150 qubits, and more generally, the largest demonstration of constrained combinatorial optimization where constraints are enforced via shallow mixers.