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

arXiv:2610.22876

Quantum approximate stochastic combinatorial optimisation

Edric Matwiejew, Paulo E. Santos, Jingbo B. Wang, Ugo Varetto

quant-phSubmitted Oct 16, 2026• Announced Oct 19, 2026• 0 citations
arXivHTMLPDF

Abstract

Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be $\#\mathrm{P}$-hard for a single first-stage candidate. We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than $2^{32}$ configurations. Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation.

Related papers

Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation

Tom Krüger, Wolfgang Mauerer

The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.

arXiv:2408.06493•Quantum•Nov 6, 2025•3 citations

Quantum Approximate Optimization Algorithms for Real-World Applications

Erik Lindberg, Ivan Lindberg

The Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a leading candidate for near-term quantum advantage in combinatorial optimisation, but most evaluations remain confined to synthetic benchmarks such as random MaxCut instances. Translating QAOA to real-world problem instances -- with irregular graph structures, heterogeneous constraint types, and practical scale requirements -- introduces additional challenges including QUBO formulation overhead, hardware embedding costs, and the performance gap between QAOA on structured real instances vs. random benchmarks. This paper presents the Real-World QAOA (RW-QAOA) framework, a systematic methodology for applying QAOA to four real-world application domains: supply chain network optimisation, financial portfolio rebalancing, telecommunications frequency assignment, and traffic signal timing optimisation. RW-QAOA introduces three methodological contributions: a domain-adaptive QUBO formulator (DAQF) encoding real-world constraints as penalised QUBO terms with penalty coefficient auto-tuning; a warm-start initialisation strategy (WSIS) using classical heuristic solutions to seed QAOA parameter search; and a layered noise adaptation protocol (LNAP) adjusting circuit depth based on real-time device calibration data. RW-QAOA is evaluated on real problem instances from industry partners across all four domains on IBM Quantum Eagle (127-qubit). RW-QAOA achieves solution quality within 4.2% of classical exact solvers across all four domains, outperforming classical greedy heuristics by 12.4% (SD = 3.8%) on average. WSIS reduces QAOA parameter convergence iterations by 48.4%. LNAP improves approximation ratio by 8.4pp vs. fixed-depth QAOA under device noise variation.

Quantum Frontiers Journal•Mar 28, 2024•0 citations

Energy Landscapes for the Quantum Approximate Optimisation Algorithm

Choy Boy, David J. Wales

Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary near intermediate-scale quantum (NISQ) era. The quantum approximate optimisation algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of $L$ quantum circuit layers within a corresponding Trotterised ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well-documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here, we employ basin-hopping global optimisation methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyse QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualisations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organisation, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimisation. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima.

arXiv:2401.04784•Jan 9, 2024•1 citation

Quantum algorithms for combinatorial optimization

Vanessa Minouche Dehn

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.

•Jan 1, 2026•0 citations

Energy landscapes for the quantum approximate optimization algorithm

Choy Boy, David J. Wales

Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024

Physical Review A•Jun 3, 2024•7 citations

Quantum-Circuit Framework for Two-Stage Stochastic Programming via QAOA Integrated with a Quantum Generative Neural Network

Taihei Kuroiwa, Daiki Yamazaki, Keita Takahashi +3 more

Two-stage stochastic programming often discretizes uncertainty into scenarios, but scenario enumeration makes expected recourse evaluation scale at least linearly in the scenario count. We propose qGAN-QAOA, a unified quantum-circuit workflow in which a pre-trained quantum generative adversarial network encodes the scenario distribution and QAOA optimizes first-stage decisions by minimizing the full two-stage objective, including expected recourse cost. With the qGAN parameters fixed after training, we evaluate the objective as the expectation value of a problem Hamiltonian and optimize only the QAOA variational parameters. We interpret non-anticipativity as a condition on measurement outcome statistics and prove that the first-stage measurement marginal is independent of the scenario. For uniformly discretized uncertainty, the diagonal operator encoding the uncertainty admits a sparse Pauli-Z expansion via the Walsh--Hadamard transform, yielding polylogarithmic scaling of gate count and circuit depth with the number of scenarios. Numerical experiments on the stochastic unit commitment problem (UCP) with photovoltaic (PV) uncertainty compare the expected cost of the proposed method with classical expected-value and two-stage stochastic programming baselines, demonstrating the effectiveness of qGAN-QAOA as a two-stage decision model.

quant-pharXiv:2512.22434•Dec 30, 2025•0 citations
Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be #P\#\mathrm{P}#P-hard for a single first-stage candidate. We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than 2322^{32}232 configurations. Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation.
The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.
The Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a leading candidate for near-term quantum advantage in combinatorial optimisation, but most evaluations remain confined to synthetic benchmarks such as random MaxCut instances. Translating QAOA to real-world problem instances -- with irregular graph structures, heterogeneous constraint types, and practical scale requirements -- introduces additional challenges including QUBO formulation overhead, hardware embedding costs, and the performance gap between QAOA on structured real instances vs. random benchmarks. This paper presents the Real-World QAOA (RW-QAOA) framework, a systematic methodology for applying QAOA to four real-world application domains: supply chain network optimisation, financial portfolio rebalancing, telecommunications frequency assignment, and traffic signal timing optimisation. RW-QAOA introduces three methodological contributions: a domain-adaptive QUBO formulator (DAQF) encoding real-world constraints as penalised QUBO terms with penalty coefficient auto-tuning; a warm-start initialisation strategy (WSIS) using classical heuristic solutions to seed QAOA parameter search; and a layered noise adaptation protocol (LNAP) adjusting circuit depth based on real-time device calibration data. RW-QAOA is evaluated on real problem instances from industry partners across all four domains on IBM Quantum Eagle (127-qubit). RW-QAOA achieves solution quality within 4.2% of classical exact solvers across all four domains, outperforming classical greedy heuristics by 12.4% (SD = 3.8%) on average. WSIS reduces QAOA parameter convergence iterations by 48.4%. LNAP improves approximation ratio by 8.4pp vs. fixed-depth QAOA under device noise variation.
Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary near intermediate-scale quantum (NISQ) era. The quantum approximate optimisation algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of LLL quantum circuit layers within a corresponding Trotterised ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well-documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here, we employ basin-hopping global optimisation methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyse QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualisations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organisation, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimisation. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima.
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.
Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024
Two-stage stochastic programming often discretizes uncertainty into scenarios, but scenario enumeration makes expected recourse evaluation scale at least linearly in the scenario count. We propose qGAN-QAOA, a unified quantum-circuit workflow in which a pre-trained quantum generative adversarial network encodes the scenario distribution and QAOA optimizes first-stage decisions by minimizing the full two-stage objective, including expected recourse cost. With the qGAN parameters fixed after training, we evaluate the objective as the expectation value of a problem Hamiltonian and optimize only the QAOA variational parameters. We interpret non-anticipativity as a condition on measurement outcome statistics and prove that the first-stage measurement marginal is independent of the scenario. For uniformly discretized uncertainty, the diagonal operator encoding the uncertainty admits a sparse Pauli-Z expansion via the Walsh--Hadamard transform, yielding polylogarithmic scaling of gate count and circuit depth with the number of scenarios. Numerical experiments on the stochastic unit commitment problem (UCP) with photovoltaic (PV) uncertainty compare the expected cost of the proposed method with classical expected-value and two-stage stochastic programming baselines, demonstrating the effectiveness of qGAN-QAOA as a two-stage decision model.