This study investigates the graph partitioning problem as a constrained combinatorial optimization problem and evaluates the effectiveness of the Postprocessing Variationally Scheduled Quantum Algorithm$(\mathbf{p V S Q A})$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 for$\mathbf{3 0}$-qubit instances. The study also demonstrates that Fujitsu's quantum simulator is effective for the stable execution of large-scale quantum circuits.
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.
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.
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.
Divide-and-conquer variants of the Quantum Approximate Optimization Algorithm (QAOA) provide a promising route for executing combinatorial optimization problems beyond the qubit capacity of near-term quantum devices. However, existing approaches rely on the existence of small vertex separators and fail entirely on dense or highly connected graphs where such decompositions do not exist. We introduce Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property. When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments. The energetic contributions of the removed interactions are rigorously preserved by folding them into linear bias terms in the Ising Hamiltonian of neighboring active qubits. Across graph sizes up to 10,000 vertices and multiple topology families, FrozenLGP achieves 100\% decomposition coverage, compared with 4.6\% for the standard divide-and-conquer baseline on high-connectivity instances. End-to-end MaxCut experiments demonstrate that FrozenLGP preserves approximation quality on instances already solvable by conventional divide-and-conquer QAOA while extending applicability to previously unsupported graphs, and outperforming alternative full-coverage decomposition strategies. Noise simulations further show improved robustness arising from reduced entangling-gate requirements. These results establish FrozenLGP as a topology-robust front end for distributed QAOA on near-term quantum hardware.
Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, it cannot overcome qubit limitation for large-scale problems. Furthermore, the simulation time of QAOA scales poorly with the problem size. We propose a divide-and-conquer QAOA (DC-QAOA) to address the above challenges for graph maximum cut (MaxCut) problem. The algorithm works by recursively partitioning a larger graph into smaller ones whose MaxCut solutions are obtained with small-size noisy intermediate-scale quantum computers. The overall solution is retrieved from the subsolutions by applying the combination policy of measurement distribution reconstruction (MDR). The solution quality depends on the graph partitioning algorithm and MDR policy. Multiple partitioning and reconstruction methods are proposed and compared. Results are evaluated by metrics, such as quantum program runtime, measurement expectation value (EV), and approximation ratio (AR). The results show that DC-QAOA achieves 97.14% AR (20.32% higher than classical counterpart), and 94.79% EV (15.80% higher than quantum annealing). DC-QAOA solves large-scale graph instances with a polynomial rate or returns unsuccessful partition if graph connectivity requirement is not fulfilled otherwise.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.