Solving combinatorial optimization problems on near-term quantum devices has gained a lot of attention in recent years. Currently, most studies have focused on single-objective problems, whereas many real-world applications need to consider multiple, mostly conflicting objectives, such as cost and quality. We present a variational quantum optimization algorithm to solve discrete multiobjective optimization problems on quantum computers. The proposed quantum multiobjective optimization (QMOO) algorithm incorporates all cost Hamiltonians representing the classical objective functions in the quantum circuit and produces a quantum state consisting of Pareto-optimal solutions in superposition. From this state, we retrieve a set of solutions and utilize the widely applied hypervolume indicator to determine its quality as an approximation to the Pareto front. The variational parameters of the QMOO circuit are tuned by maximizing the hypervolume indicator in a quantum-classical hybrid fashion. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives. We investigate the influence of the classical optimizer and the circuit depth, and compare them to results from classical optimization algorithms. We find that the algorithm is robust to shot noise and produces good results with as few as 128 measurement shots in each iteration. These promising results open the possibility to run the algorithm on near-term quantum hardware.
Solving combinatorial optimization problems on near-term quantum devices has gained a lot of attention in recent years. Currently, most studies have focused on single-objective problems, whereas many real-world applications need to consider multiple, mostly conflicting objectives, such as cost and quality. We present a variational quantum optimization algorithm to solve discrete multiobjective optimization problems on quantum computers. The proposed quantum multiobjective optimization (QMOO) algorithm incorporates all cost Hamiltonians representing the classical objective functions in the quantum circuit and produces a quantum state consisting of Pareto-optimal solutions in superposition. From this state, we retrieve a set of solutions and utilize the widely applied hypervolume indicator to determine its quality as an approximation to the Pareto front. The variational parameters of the QMOO circuit are tuned by maximizing the hypervolume indicator in a quantum-classical hybrid fashion. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives. We investigate the influence of the classical optimizer and the circuit depth, and compare them to results from classical optimization algorithms. We find that the algorithm is robust to shot noise and produces good results with as few as 128 measurement shots in each iteration. These promising results open the possibility to run the algorithm on near-term quantum hardware.
Finding optimal solutions of conflicting objectives is a daily matter in many industrial applications, with multi-objective optimization trying to find the best solutions to them. The advent of quantum computing has led to researchers wondering if the promised exponential advantage can be obtained for these problems by variational quantum multi-objective optimization (QMOO) algorithm. Here, we improve it by introducing a Pareto Archive and dominated solutions substitution, clearly improving in hyper-volume convergence at additional quantum and classical cost. We propose the use of RMNK-landscapes as a unifying testbed for benchmarking QMOO, as it is common in classical multi-objective field. By devising a generic classical-to-quantum mapping of these landscapes, we perform a numerical hyperparameter tuning of QMOO, significantly enhancing its performance. Finally, we compare QMOO against well-known classical solvers for multi-objective tasks, NSGA-II/III, showing comparable results in small instances. Our results demonstrate that QMOO, when carefully tuned for the task at hand, might be advantageous on harder problems than its classical counterparts.
Abstract Combinatorial optimization problems are ubiquitous in industry. In addition to finding a solution with minimum cost, problems of high relevance involve a number of constraints that the solution must satisfy. Variational quantum algorithms (VQAs) have emerged as promising candidates for solving these problems in the noisy intermediate-scale quantum stage. However, the constraints are often complex enough to make their efficient mapping to quantum hardware difficult or even infeasible. An alternative standard approach is to transform the optimization problem to include these constraints as penalty terms, but this method involves additional hyperparameters and does not ensure that the constraints are satisfied due to the existence of local minima. In this paper, we introduce a new method for solving combinatorial optimization problems with challenging constraints using VQAs. We propose the multi-objective variational constrained optimizer (MOVCO) to classically update the variational parameters by a multiobjective optimization performed by a genetic algorithm. This optimization allows the algorithm to progressively sample only states within the in-constraints space, while optimizing the energy of these states. We test our proposal on a real-world problem with great relevance in finance: the cash handling problem. We introduce a novel mathematical formulation for this problem, and compare the performance of MOVCO versus a penalty based optimization. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima that do not satisfy any of the mandatory constraints.
Abstract This paper presents methodological improvements to variational quantum algorithms (VQAs) for solving multicriteria optimization problems. We introduce two key contributions. First, we reformulate the parameter optimization task of VQAs as a multicriteria problem, enabling the direct use of classical algorithms from various multicriteria metaheuristics. This hybrid framework outperforms the corresponding single-criteria VQAs in both average and worst-case performance across diverse benchmark problems. Second, we propose a method that augments the hypervolume-based cost function with coverage-oriented indicators, allowing explicit control over the diversity of the resulting Pareto front approximations. Experimental results show that our method can improve coverage by up to 40% with minimal loss in hypervolume. Our findings highlight the potential of combining quantum variational methods with classical population-based search to advance practical quantum optimization.
The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, that is, the set of all Pareto-optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. Here we use a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum-cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with matrix product state numerical simulation, and show its potential to outperform classical approaches. This study explores the use of quantum computing to address multi-objective optimization challenges. By using a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of multi-objective weighted max-cut problems, the authors demonstrate promising results—both in simulation and on IBM Quantum hardware—surpassing classical approaches.
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.
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.