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

Feasible-Space Dilution and Objective Alignment in Shallow Penalty-X QAOA: A Controlled RCSP Study

Zhilin Chen

Published Oct 15, 2026• 0 citations
PDF (CC BY)Publisher

Abstract

Abstract Purpose : Poor feasible sampling in full-space Penalty-X quantum approximate optimization algorithm (QAOA) can reflect representation-induced dilution, classical optimizer inadequacy, objective misalignment, or limited ansatz capacity. We separate these explanations on a controlled routing benchmark. Methods : Exact-statevector experiments use 140 resource-constrained shortest-path tasks and a scale-controlled Hamiltonian. Exact depth embeddings diagnose optimizer inadequacy. A frozen discovery/held-out design compares mean-energy training (O0), an exact-feasibility capacity control (O2), and conditional value at risk (CVaR)-0.10 (O3), with post-hoc depth, optimizer, tail-fraction, and finite-shot checks. Results : O2 showed that the fixed ansatz could reach feasible mass not induced by O0. On 84 held-out tasks from 15 graphs, O3 improved graph-level log-feasibility gain over O0 by +0.3547 decades and was non-inferior to O2: the O3–O2 effect was −0.0086, with lower bound −0.0360 above the frozen −0.10 margin. Certified nested failures occurred under COBYLA, Nelder–Mead, and SLSQP. Fixed-endpoint sampling was stable, whereas both finite-shot retraining intervals crossed zero. Conclusion : Optimizer inadequacy and objective misalignment are distinct under the tested diagnostics, and CVaR approaches the mechanistic O2 capacity control on held-out graphs. The classically tractable study supports no quantum-advantage or extrapolative scaling claim and does not test hardware noise.

DOI
10.21203/rs.3.rs-10948914/v1

Related papers

Improving QAOA feasibility and hardware performance for vehicle routing via linear chain and ramp schedules

Talha Azfar, Ruimin Ke

The Quantum Approximate Optimization Algorithm (QAOA) is difficult to deploy on near-term hardware for constrained routing problems because feasibility constraints produce dense interaction graphs, deep transpiled circuits, and costly parameter search. We study this challenge for Vehicle Routing Problem (VRP) instances using a hardware-aware QAOA workflow that combines linear-ramp parameter initialization, Conditional Value-at-Risk (CVaR) optimization, and a Linear-Chain QAOA (LC-QAOA) surrogate that retains local ZZ interactions to reduce two-qubit depth. A matched full-QAOA versus LC-QAOA feasibility comparison is performed for 4-node instances, while the 5- and 6-node experiments characterize circuit executability and low-probability optimum recovery at the tested depths. In 4-node hardware runs, LC-QAOA increases mean feasible-sample probability from 0.182% to 0.917% and mean optimum-sample probability from 0.045% to 0.239%, giving approximately \(5\times\) improvement over full QAOA. At 6 nodes, a full-QAOA circuit at \(p=1\) already has large transpiled two-qubit depth, while LC-QAOA remains executable and samples CPLEX-certified optima in selected hardware runs at depths p =10–13, albeit with low optimum probability. Overall, the results identify LC-QAOA as a hardware-efficient surrogate heuristic that trades Hamiltonian completeness for lower depth and improved feasible-solution sampling on noisy quantum hardware.

Scientific Reports•Sep 10, 2026•3 citations

Beyond Feasibility: Finite-Depth Accessibility in Constrained QAOA

Rushikesh Ubale, Gregory T. Byrd, Yasar Mulani +1 more

Constraint-preserving mixers keep QAOA within a feasible subspace, but feasibility and global mixer connectivity do not determine which feasible configurations are available to a particular shallow circuit. We study constrained QAOA at the level of the circuit actually executed: a specified feasible initial state, finite depth, and finite schedule of mixer interactions. We define the finite-depth accessible set $R_p(M,x_0)$ and show that the computational-basis support of the ideal QAOA circuit is contained within it. This gives a parameter-independent objective ceiling $f_R^\star=\max_{x\in R_p}f(x)$ and a normalized reachable-quality diagnostic $Q_R$, separating accessible volume from the objective quality contained within it. We evaluate this framework using resource-matched block-local XY mixer schedules for constrained portfolio optimization and synthetic block-constrained quadratic problems. Across 207 favorable-tail CVaR QAOA configurations, $Q_R$ shows the strongest association with realized shallow-QAOA performance among the structural diagnostics considered, with Pearson and Spearman correlations of $0.7003$ and $0.8057$; the relationship remains positive under controlled and dependence-aware analyses. The distinction persists across changes in feasible initialization, portfolio size, and objective family. A compilation-only study further shows that, for the dense portfolio Hamiltonians considered here, phase-separator routing dominates the compiled two-qubit resource scale, while mixer schedules with comparable compiled two-qubit cost can exhibit markedly different finite-depth accessible quality. These results motivate objective-relevant finite-depth accessibility as a complementary diagnostic for resource-bounded constrained QAOA.

quant-pharXiv:2610.00736•Oct 2, 2026•1 citation

Optimize the Optimization: QPU-Efficient Quantum Graph Optimization through HPC-First Experimentation

David Vesterlund

Abstract This paper studies how much Quantum Processing Unit (QPU) work can be avoided while preserving optimization quality in the Quantum Approximate Optimization Algorithm (QAOA). Using exact statevector simulation of QAOA on six graph optimization problems across seven graph families, three baselines are compared: a naive QPU-centric workflow with 30 quantum evaluations, a best-practice workflow that separates classical parameter optimization from a single QPU evaluation, and a classical-only solver. Six QPUminimization strategies are evaluated: preprocessing, pretraining, surrogate modeling, adaptive stopping, adaptive shots, and measurement reuse. Quality is measured using normalized expected value rather than the saturated best-of-b metric. The key findings are: the best-practice baseline achieves 510- to 2070-fold shot reduction across 8 to 16 qubits with at most 0.4 percent quality loss relative to naive QAOA; quality improves with QAOA depth from 0.82 to 0.91 while the gap between naive and best-practice remains negligible; four of six strategies achieve 100 percent quality retention at depth 3; quality is stable across graph families ranging from 0.77 to 0.87; and a structural predictor achieves perfect prediction on held-out graph families. These results support the thesis that the required QPU budget is a structured, predictable function of the problem instance and workflow policy, rather than a fixed algorithmic constant.

•Oct 13, 2026•0 citations

Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing

Yuan-Zheng Lei, Yaobang Gong, Xianfeng Terry Yang +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a leading framework for quantum combinatorial optimization. The Vehicle Routing Problem (VRP), a core problem in logistics and transportation, is a natural application target, but it poses a major feasibility challenge for standard QAOA because feasible solutions occupy only a tiny fraction of the search space, and the conventional Pauli-$X$ mixer can disrupt partial solution structures that satisfy key local constraints. To address this issue, we propose a constraint-aware QAOA framework with two complementary components. First, we design a lightweight initialization strategy that encodes a selected subset of simple yet informative local one-hot constraints into the initial state, thereby reducing the initial superposition space and increasing the probability mass on states with important local structure. Second, we introduce a hybrid XY-$X$ mixer that preserves the constraint structure imposed at initialization while retaining exploratory flexibility over the remaining unconstrained degrees of freedom during QAOA evolution. We evaluate the proposed framework against standard QAOA under three progressively more realistic regimes: ideal statevector simulation, finite-shot sampling, and noisy finite-shot sampling. Across all regimes, the proposed method consistently achieves lower average energy and higher feasible-solution ratios than standard QAOA, indicating more effective guidance toward structurally valid, lower-cost VRP solutions. However, the performance gap narrows in the noisy regime. Because this setting adopts a hardware-inspired error model based on near-best-reported laboratory-level qubit gate and readout fidelities, the observed attenuation suggests that the practical advantage of the more structured mixer is likely to grow as quantum hardware improves and error rates decline.

cs.ETCross-listedarXiv:2604.07218•Transportation Research Part C Emerging Technologies•Apr 9, 2026•0 citations

Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs

Chinonso Onah, Roman Firt, Kristel Michielsen

We introduce the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA), a shallow, constraint-aware ansatz that operates inside the one-hot product space [n]^m, where m is the number of blocks and each block is initialized in an n-qubit W_n state. We give an ancilla-free, depth-optimal encoder that prepares W_n using n-1 two-qubit rotations per block, and a two-local block-XY mixer that preserves the one-hot manifold and has a constant spectral gap on the one-excitation sector. At the level of expressivity, we establish per-block controllability, implying approximate universality per block. At the level of distributional behavior, we show that, after natural block and symbol permutation twirls, shallow CE-QAOA realizes an encoded unitary 1-design and supports approximate second-moment (2-design) behavior; combined with a Paley-Zygmund argument, this yields finite-shot anticoncentration guarantees. Algorithmically, we wrap constant-depth sampling with a deterministic feasibility checker to obtain a polynomial-time hybrid quantum-classical solver (PHQC) that returns the best observed feasible solution in O(S n^2) time, where S is a polynomial shot budget. We obtain two advantages. First, when CE-QAOA fixes r >= 1 locations different from the start city, we achieve a Theta(n^r) reduction in shot complexity even against a classical sampler that draws uniformly from the feasible set. Second, against a classical baseline restricted to raw bitstring sampling, we show an exp(Theta(n^2)) minimax separation. In noiseless circuit simulations of traveling salesman problem instances with n in {4,...,10} locations from the QOPTLib benchmark library, we recover the global optimum at depth p = 1 using polynomial shot budgets and coarse parameter grids defined by the problem size.

cs.ETCross-listedarXiv:2511.14296•Nov 19, 2025•12 citations

State-Metric Mismatch in Shallow QAOA: Non-Monotonic Relations Between Expected Energy and Constraint Feasibility

Kim, Min-Gi

This preprint studies whether expected-energy improvement guarantees improved constraint feasibility in a shallow QAOA setting. A frozen six-point, 24-variable, K=5, p=1 simulation panel is audited across all 15 pairwise comparisons. Five pairs show opposite directional changes between expected energy and P(K=5), while ten are aligned. The 5/15 count is explicitly descriptive because the pairs are dependent. A separate high-contrast transition is retained only as an illustration. The paper distinguishes finite-shot simulator evidence from exact statevector and physical-QPU evidence, removes a non-preregistered illustrative threshold from the primary analysis, and makes no quantum-advantage or universal-QAOA claim.

•Sep 9, 2026•0 citations
Abstract Purpose : Poor feasible sampling in full-space Penalty-X quantum approximate optimization algorithm (QAOA) can reflect representation-induced dilution, classical optimizer inadequacy, objective misalignment, or limited ansatz capacity. We separate these explanations on a controlled routing benchmark. Methods : Exact-statevector experiments use 140 resource-constrained shortest-path tasks and a scale-controlled Hamiltonian. Exact depth embeddings diagnose optimizer inadequacy. A frozen discovery/held-out design compares mean-energy training (O0), an exact-feasibility capacity control (O2), and conditional value at risk (CVaR)-0.10 (O3), with post-hoc depth, optimizer, tail-fraction, and finite-shot checks. Results : O2 showed that the fixed ansatz could reach feasible mass not induced by O0. On 84 held-out tasks from 15 graphs, O3 improved graph-level log-feasibility gain over O0 by +0.3547 decades and was non-inferior to O2: the O3–O2 effect was −0.0086, with lower bound −0.0360 above the frozen −0.10 margin. Certified nested failures occurred under COBYLA, Nelder–Mead, and SLSQP. Fixed-endpoint sampling was stable, whereas both finite-shot retraining intervals crossed zero. Conclusion : Optimizer inadequacy and objective misalignment are distinct under the tested diagnostics, and CVaR approaches the mechanistic O2 capacity control on held-out graphs. The classically tractable study supports no quantum-advantage or extrapolative scaling claim and does not test hardware noise.
The Quantum Approximate Optimization Algorithm (QAOA) is difficult to deploy on near-term hardware for constrained routing problems because feasibility constraints produce dense interaction graphs, deep transpiled circuits, and costly parameter search. We study this challenge for Vehicle Routing Problem (VRP) instances using a hardware-aware QAOA workflow that combines linear-ramp parameter initialization, Conditional Value-at-Risk (CVaR) optimization, and a Linear-Chain QAOA (LC-QAOA) surrogate that retains local ZZ interactions to reduce two-qubit depth. A matched full-QAOA versus LC-QAOA feasibility comparison is performed for 4-node instances, while the 5- and 6-node experiments characterize circuit executability and low-probability optimum recovery at the tested depths. In 4-node hardware runs, LC-QAOA increases mean feasible-sample probability from 0.182% to 0.917% and mean optimum-sample probability from 0.045% to 0.239%, giving approximately 5×5\times5× improvement over full QAOA. At 6 nodes, a full-QAOA circuit at p=1p=1p=1 already has large transpiled two-qubit depth, while LC-QAOA remains executable and samples CPLEX-certified optima in selected hardware runs at depths p =10–13, albeit with low optimum probability. Overall, the results identify LC-QAOA as a hardware-efficient surrogate heuristic that trades Hamiltonian completeness for lower depth and improved feasible-solution sampling on noisy quantum hardware.
Constraint-preserving mixers keep QAOA within a feasible subspace, but feasibility and global mixer connectivity do not determine which feasible configurations are available to a particular shallow circuit. We study constrained QAOA at the level of the circuit actually executed: a specified feasible initial state, finite depth, and finite schedule of mixer interactions. We define the finite-depth accessible set Rp(M,x0)R_p(M,x_0)Rp​(M,x0​) and show that the computational-basis support of the ideal QAOA circuit is contained within it. This gives a parameter-independent objective ceiling fR⋆=max⁡x∈Rpf(x)f_R^\star=\max_{x\in R_p}f(x)fR⋆​=maxx∈Rp​​f(x) and a normalized reachable-quality diagnostic QRQ_RQR​, separating accessible volume from the objective quality contained within it. We evaluate this framework using resource-matched block-local XY mixer schedules for constrained portfolio optimization and synthetic block-constrained quadratic problems. Across 207 favorable-tail CVaR QAOA configurations, QRQ_RQR​ shows the strongest association with realized shallow-QAOA performance among the structural diagnostics considered, with Pearson and Spearman correlations of 0.70030.70030.7003 and 0.80570.80570.8057; the relationship remains positive under controlled and dependence-aware analyses. The distinction persists across changes in feasible initialization, portfolio size, and objective family. A compilation-only study further shows that, for the dense portfolio Hamiltonians considered here, phase-separator routing dominates the compiled two-qubit resource scale, while mixer schedules with comparable compiled two-qubit cost can exhibit markedly different finite-depth accessible quality. These results motivate objective-relevant finite-depth accessibility as a complementary diagnostic for resource-bounded constrained QAOA.
Abstract This paper studies how much Quantum Processing Unit (QPU) work can be avoided while preserving optimization quality in the Quantum Approximate Optimization Algorithm (QAOA). Using exact statevector simulation of QAOA on six graph optimization problems across seven graph families, three baselines are compared: a naive QPU-centric workflow with 30 quantum evaluations, a best-practice workflow that separates classical parameter optimization from a single QPU evaluation, and a classical-only solver. Six QPUminimization strategies are evaluated: preprocessing, pretraining, surrogate modeling, adaptive stopping, adaptive shots, and measurement reuse. Quality is measured using normalized expected value rather than the saturated best-of-b metric. The key findings are: the best-practice baseline achieves 510- to 2070-fold shot reduction across 8 to 16 qubits with at most 0.4 percent quality loss relative to naive QAOA; quality improves with QAOA depth from 0.82 to 0.91 while the gap between naive and best-practice remains negligible; four of six strategies achieve 100 percent quality retention at depth 3; quality is stable across graph families ranging from 0.77 to 0.87; and a structural predictor achieves perfect prediction on held-out graph families. These results support the thesis that the required QPU budget is a structured, predictable function of the problem instance and workflow policy, rather than a fixed algorithmic constant.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading framework for quantum combinatorial optimization. The Vehicle Routing Problem (VRP), a core problem in logistics and transportation, is a natural application target, but it poses a major feasibility challenge for standard QAOA because feasible solutions occupy only a tiny fraction of the search space, and the conventional Pauli-XXX mixer can disrupt partial solution structures that satisfy key local constraints. To address this issue, we propose a constraint-aware QAOA framework with two complementary components. First, we design a lightweight initialization strategy that encodes a selected subset of simple yet informative local one-hot constraints into the initial state, thereby reducing the initial superposition space and increasing the probability mass on states with important local structure. Second, we introduce a hybrid XY-XXX mixer that preserves the constraint structure imposed at initialization while retaining exploratory flexibility over the remaining unconstrained degrees of freedom during QAOA evolution. We evaluate the proposed framework against standard QAOA under three progressively more realistic regimes: ideal statevector simulation, finite-shot sampling, and noisy finite-shot sampling. Across all regimes, the proposed method consistently achieves lower average energy and higher feasible-solution ratios than standard QAOA, indicating more effective guidance toward structurally valid, lower-cost VRP solutions. However, the performance gap narrows in the noisy regime. Because this setting adopts a hardware-inspired error model based on near-best-reported laboratory-level qubit gate and readout fidelities, the observed attenuation suggests that the practical advantage of the more structured mixer is likely to grow as quantum hardware improves and error rates decline.
We introduce the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA), a shallow, constraint-aware ansatz that operates inside the one-hot product space [n]^m, where m is the number of blocks and each block is initialized in an n-qubit W_n state. We give an ancilla-free, depth-optimal encoder that prepares W_n using n-1 two-qubit rotations per block, and a two-local block-XY mixer that preserves the one-hot manifold and has a constant spectral gap on the one-excitation sector. At the level of expressivity, we establish per-block controllability, implying approximate universality per block. At the level of distributional behavior, we show that, after natural block and symbol permutation twirls, shallow CE-QAOA realizes an encoded unitary 1-design and supports approximate second-moment (2-design) behavior; combined with a Paley-Zygmund argument, this yields finite-shot anticoncentration guarantees. Algorithmically, we wrap constant-depth sampling with a deterministic feasibility checker to obtain a polynomial-time hybrid quantum-classical solver (PHQC) that returns the best observed feasible solution in O(S n^2) time, where S is a polynomial shot budget. We obtain two advantages. First, when CE-QAOA fixes r >= 1 locations different from the start city, we achieve a Theta(n^r) reduction in shot complexity even against a classical sampler that draws uniformly from the feasible set. Second, against a classical baseline restricted to raw bitstring sampling, we show an exp(Theta(n^2)) minimax separation. In noiseless circuit simulations of traveling salesman problem instances with n in {4,...,10} locations from the QOPTLib benchmark library, we recover the global optimum at depth p = 1 using polynomial shot budgets and coarse parameter grids defined by the problem size.
This preprint studies whether expected-energy improvement guarantees improved constraint feasibility in a shallow QAOA setting. A frozen six-point, 24-variable, K=5, p=1 simulation panel is audited across all 15 pairwise comparisons. Five pairs show opposite directional changes between expected energy and P(K=5), while ten are aligned. The 5/15 count is explicitly descriptive because the pairs are dependent. A separate high-contrast transition is retained only as an illustration. The paper distinguishes finite-shot simulator evidence from exact statevector and physical-QPU evidence, removes a non-preregistered illustrative threshold from the primary analysis, and makes no quantum-advantage or universal-QAOA claim.