pith. machine review for the scientific record. sign in

arxiv: 2604.07218 · v1 · submitted 2026-04-08 · 💻 cs.ET · quant-ph

Recognition: unknown

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

Nii Attoh-Okine, Xianfeng Terry Yang, Yaobang Gong, Yuan-Zheng Lei

Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:38 UTC · model grok-4.3

classification 💻 cs.ET quant-ph
keywords QAOAVehicle Routing Problemquantum optimizationconstraint awarenesshybrid mixerfeasible solutionscombinatorial optimization
0
0 comments X

The pith

Constraint-aware initialization plus a hybrid XY-X mixer raises the share of feasible vehicle-routing solutions found by QAOA.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a two-part modification to standard QAOA for the vehicle routing problem. A lightweight initial state is prepared that already satisfies a chosen subset of local one-hot constraints, shrinking the search space that the algorithm must explore. A hybrid XY-X mixer is then used during the variational steps so that the preserved local structure is not destroyed while the remaining degrees of freedom can still be mixed. In ideal, finite-shot, and noisy finite-shot simulations the modified algorithm returns lower average energies and higher fractions of feasible routes than ordinary QAOA. The advantage shrinks under the chosen hardware-inspired noise model, but the authors note that further hardware improvements should widen the gap again.

Core claim

Encoding a selected subset of local one-hot constraints directly into the QAOA initial state and then evolving that state with a hybrid XY-X mixer produces lower average energies and higher feasible-solution ratios than standard QAOA across ideal statevector, finite-shot, and noisy finite-shot regimes for the vehicle routing problem.

What carries the argument

Hybrid XY-X mixer that preserves the local one-hot constraints imposed at initialization while still allowing mixing on the remaining unconstrained variables.

If this is right

  • More of the probability mass stays inside the feasible subspace throughout the QAOA evolution.
  • Average energy values drop because the optimizer spends less time on structurally invalid routes.
  • The performance gap between the structured and standard mixers is expected to increase as gate and readout fidelities improve beyond the near-best laboratory values tested.
  • The method supplies a concrete way to inject domain constraints without adding large penalty terms to the cost Hamiltonian.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same initialization-plus-hybrid-mixer pattern could be tried on other combinatorial problems that admit simple local constraints, such as graph coloring or scheduling.
  • If the feasibility advantage survives scaling, the approach may reduce the qubit overhead currently spent on penalty terms in QAOA formulations.
  • Testing on instances whose size exceeds the current experiments would directly check whether the lightweight constraint encoding remains sufficient.

Load-bearing premise

The lightweight encoding of selected local one-hot constraints at initialization together with the hybrid mixer will continue to deliver feasibility gains when problem size grows and when noise models differ from the laboratory-fidelity model used here.

What would settle it

Run the same VRP instances on a device whose gate and readout errors are at least as low as the model in the paper and observe whether the feasible-solution ratio advantage disappears or reverses.

Figures

Figures reproduced from arXiv: 2604.07218 by Nii Attoh-Okine, Xianfeng Terry Yang, Yaobang Gong, Yuan-Zheng Lei.

Figure 1
Figure 1. Figure 1: Bloch sphere representation of a qubit measurement probabilities in the computational basis. The Pauli-Y gate combines a bit-flip with a phase shift and corresponds to a rotation about the y axis on the Bloch sphere. The Hadamard gate is widely used to create superposition, for example H|0⟩ = |+⟩ and H|1⟩ = |−⟩ (as illustrated in (11)). X|0⟩ = " 0 1 1 0# "1 0 # = " 0 1 # = |1⟩ X|1⟩ = " 0 1 1 0# "0 1 # = " … view at source ↗
Figure 2
Figure 2. Figure 2: QAOA Pipeline (Adapted from Azfar et al. (2025)) 13 [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Problem Graph which means that exactly one outgoing link must be selected from node 1. Under the ordering in (24), this constraint involves the third and fourth qubits only. Without imposing the constraint, these two positions admit all 2 2 = 4 computational-basis configurations. After enforcing the constraint, however, only two assignments remain admissible, namely |01⟩(3,4) and |10⟩(3,4). A natural const… view at source ↗
Figure 4
Figure 4. Figure 4: Relations of constraints. Each link refers to a one-hot constraint among two variables. [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Performance comparison across the three experimental regimes. [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Sensitivity of the proposed method to the mixing parameter [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Standard QAOA circuit (Initial) q0 q1 q2 q3 q4 q5 6 meas H H H H H H ZZ ( 0.563) ZZ ( 0.376) ZZ ( 0.376) ZZ ( 0.376) ZZ ( 0.376) ZZ ( 0.376) 0.698 RZ 0.886 RZ 0.747 RZ 0.037 RZ 0.935 RZ 0.037 RZ 1.36 RX 1.36 RX 1.36 RX 1.36 RX 1.36 RX 1.36 RX ZZ ( 1.17) ZZ ( 0.781) ZZ ( 0.781) ZZ ( 0.781) ZZ ( 0.781) ZZ ( 0.781) 1.45 RZ 1.84 RZ 1.55 RZ 0.0769 RZ 1.94 RZ 0.0769 RZ 0.907 RX 0.907 RX 0.907 RX 0.907 RX 0.907 R… view at source ↗
Figure 8
Figure 8. Figure 8: Standard QAOA circuit (Optimized) 26 [PITH_FULL_IMAGE:figures/full_fig_p026_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Our QAOA circuit (Initial) q0 q1 q2 q3 q4 q5 6 meas 0 1 2 3 4 5 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, . . .] | ZZ ( 4.26) ZZ ( 2.84) ZZ ( 2.84) ZZ ( 2.84) ZZ ( 2.84) ZZ ( 2.84) 5.28 RZ 6.7 RZ 5.65 RZ 0.28 RZ 7.07 RZ 0.28 RZ 2.33 RX 0 1 2.92 RXX 0 1 2.92 RXX 2.33 RX 0 1 2.92 RYY 0 1 2.92 RYY ZZ (0.684) ZZ (1.03) ZZ (0.684) ZZ (0.684) ZZ (0.684) 1.27 RZ ZZ (0.684) 1.7 RZ 0.0673 RZ 0.839 RX 1.61 RZ… view at source ↗
Figure 10
Figure 10. Figure 10: Our QAOA circuit (Optimized) 6. Conclusions This study investigates how QAOA can be made more effective for the vehicle routing problem by explicitly addressing the feasibility issue inherent in constrained combinatorial optimization. Under standard QAOA, the conventional uniform-superposition initialization distributes probability mass over the entire Hilbert space, while the standard Pauli-X mixer explo… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a constraint-aware QAOA framework for the Vehicle Routing Problem consisting of a lightweight initialization that encodes a selected subset of local one-hot constraints into the initial state and a hybrid XY-X mixer that preserves imposed structure while retaining exploratory flexibility. It reports empirical results from three simulation regimes (ideal statevector, finite-shot sampling, and noisy finite-shot sampling with a hardware-inspired error model) showing that the method yields lower average energies and higher feasible-solution ratios than standard QAOA, although the performance gap narrows under noise.

Significance. If the reported improvements hold under further scrutiny, the work provides a concrete technique for mitigating the severe feasibility bottleneck in QAOA for constrained combinatorial problems such as VRP. The direct multi-regime comparison to standard QAOA is a strength, as it supplies empirical evidence on how the proposed initialization and mixer affect both ideal and realistic execution conditions. The observation that the gap narrows under near-best laboratory noise levels also offers a useful data point for assessing near-term practicality.

major comments (2)
  1. [Abstract] Abstract: the claim that the method 'consistently achieves lower average energy and higher feasible-solution ratios' across all regimes is not accompanied by any mention of the specific VRP instance parameters (number of nodes, vehicles, or demand structure), the number of independent runs, or statistical measures such as standard deviations or confidence intervals on the reported energies and feasible ratios; these omissions are load-bearing because they prevent assessment of whether the observed improvements are robust or instance-dependent.
  2. [Evaluation section] Evaluation section: the suggestion that 'the practical advantage of the more structured mixer is likely to grow as quantum hardware improves' rests on a single optimistic noise model; because the central empirical claim concerns behavior under that specific model, additional results under at least one more pessimistic or varied noise model (or an explicit scaling study) are required before the extrapolation can be considered supported.
minor comments (1)
  1. [Methods] The hybrid XY-X mixer is described only at a high level; adding a short equation or circuit diagram in the methods section would clarify how the XY and X components are interleaved and how constraint preservation is enforced.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and constructive comments on our manuscript. We address each of the major comments in detail below and indicate the revisions we have made or will make to the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that the method 'consistently achieves lower average energy and higher feasible-solution ratios' across all regimes is not accompanied by any mention of the specific VRP instance parameters (number of nodes, vehicles, or demand structure), the number of independent runs, or statistical measures such as standard deviations or confidence intervals on the reported energies and feasible ratios; these omissions are load-bearing because they prevent assessment of whether the observed improvements are robust or instance-dependent.

    Authors: We agree that the abstract would benefit from additional context on the experimental setup to allow readers to better gauge the robustness of the results. The full manuscript provides these details in the Evaluation section, including the VRP instance sizes (number of nodes, vehicles, and demand structure), the number of independent runs performed, and statistical measures such as standard deviations. To improve the abstract, we will revise it to include a brief mention of the instance parameters used and the number of runs, while referring readers to the main text for full statistical details. This addresses the concern without compromising the abstract's conciseness. revision: yes

  2. Referee: [Evaluation section] Evaluation section: the suggestion that 'the practical advantage of the more structured mixer is likely to grow as quantum hardware improves' rests on a single optimistic noise model; because the central empirical claim concerns behavior under that specific model, additional results under at least one more pessimistic or varied noise model (or an explicit scaling study) are required before the extrapolation can be considered supported.

    Authors: We appreciate this point regarding the extrapolation. The noise model employed is explicitly described as hardware-inspired and based on near-best-reported laboratory qubit gate and readout fidelities, which we consider a reasonable optimistic baseline for assessing near-term potential. The observed narrowing of the gap under this model supports our tentative suggestion that advantages may increase with improved hardware. However, to strengthen the manuscript, we will revise the Evaluation section to provide a more detailed justification of the noise model choice, discuss its limitations, and explicitly note that the extrapolation is based on this single model. We will also consider adding a brief scaling analysis if feasible within the revision. This partial revision addresses the referee's concern by enhancing the supporting discussion. revision: partial

Circularity Check

0 steps flagged

No circularity; empirical benchmarking is independent of inputs

full rationale

The paper proposes a constraint-aware initialization and hybrid XY-X mixer for QAOA on VRP, then reports lower energies and higher feasible ratios via direct statevector, shot, and noisy simulations compared to standard QAOA. No derivation chain exists that reduces a claimed result to a fitted parameter, self-citation, or ansatz by construction. All performance claims rest on explicit, reproducible simulation protocols whose outputs are not presupposed by the method definitions. The observed gap narrowing under noise is reported as an empirical fact rather than derived, leaving the central claims externally falsifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the effectiveness of the new initialization and mixer design; no free parameters, new physical entities, or ad-hoc axioms beyond standard QAOA and VRP encoding assumptions are mentioned.

axioms (2)
  • domain assumption Standard quantum circuit model and QAOA ansatz apply to VRP encoding
    The paper builds directly on the QAOA framework for combinatorial optimization without re-deriving its foundations.
  • domain assumption VRP can be mapped to a Hamiltonian with one-hot constraints that admit partial local enforcement
    Implicit in the choice to encode a subset of local one-hot constraints at initialization.

pith-pipeline@v0.9.0 · 5599 in / 1503 out tokens · 108828 ms · 2026-05-10T17:38:41.673186+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 10 canonical work pages · 1 internal anchor

  1. [1]

    Quantum-enhancedoptimizationforlngshiprouting: Integrating digital twins with qaoa, in: 2025 IEEE International Conference on Communications Workshops (ICC Workshops), IEEE. pp. 769–774. Awasthi, A., Bär, F., Doetsch, J., Ehm, H., Erdmann, M., Hess, M., Klepsch, J., Limacher, P.A., Luckow, A., Niedermeier, C., et al.,

    2025

  2. [2]

    Quantum- assisted vehicle routing: Realizing qaoa-based approach on gate-based quantum computer,

    Quantum-assisted vehicle routing: Realizing qaoa-based approach on gate-based quantum computer. arXiv preprint arXiv:2505.01614 . Baker, J.S., Radha, S.K.,

    work page arXiv

  3. [3]

    arXiv preprint arXiv:2202.06782

    Wasserstein solution quality and the quantum approximate optimization algorithm: a portfolio optimization case study. arXiv preprint arXiv:2202.06782 . Barahona, F., Jünger, M., Reinelt, G.,

    work page arXiv

  4. [4]

    Grover mixers for qaoa: Shifting complexity from mixer design to state preparation, in: 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), IEEE. pp. 72–82. Blekos, K., Brand, D., Ceschini, A., Chou, C.H., Li, R.H., Pandya, K., Summer, A.,

    2020

  5. [5]

    arXiv preprint arXiv:2504.19934

    Warm-starting qaoa with xy mixers: A novel approach for quantum-enhanced vehicle routing optimization. arXiv preprint arXiv:2504.19934 . Chatterjee, A., Stevenson, P., De Franceschi, S., Morello, A., de Leon, N.P., Kuemmeth, F.,

    work page arXiv

  6. [6]

    A tutorial on quantum approximate optimization algorithm (qaoa): Fundamen- tals and applications, in: 2019 international conference on information and communication technology convergence (ICTC), IEEE. pp. 138–142. Clarke, G., Wright, J.W.,

    2019

  7. [7]

    Farhi, J

    A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv preprint arXiv:1412.6062 . Flood, M.M.,

    work page arXiv

  8. [8]

    arXiv preprint arXiv:1811.11538

    A tutorial on formulating and using qubo models. arXiv preprint arXiv:1811.11538 . Harikrishnakumar, R., Nannapaneni, S.,

    work page arXiv

  9. [9]

    Smart rebalancing for bike sharing systems using quan- tum approximate optimization algorithm, in: 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), IEEE. pp. 2257–2263. Harwood, S., Gambella, C., Trenev, D., Simonetto, A., Bernal, D., Greenberg, D.,

    2021

  10. [10]

    Quantum computing with Qiskit

    Quantum computing with qiskit. arXiv preprint arXiv:2405.08810 . Ke, R., Guo, Q.w., . Quantum optimization for public transit systems: A quantum hardware-aware analysis of higher-order formulations. Available at SSRN 6431107 . Li, Z., Liu, P., Zhao, P., Mi, Z., Xu, H., Liang, X., Su, T., Sun, W., Xue, G., Zhang, J.N., et al.,

    work page internal anchor Pith review arXiv

  11. [11]

    Marxer, et al

    Above 99.9% fidelity single-qubit gates, two-qubit gates, and readout in a single superconducting quantum device. arXiv preprint arXiv:2508.16437 . Massimiliano, Z., Zhuoming, D., Giorgi, G.L., Sun, X., Wandelt, S.,

    work page arXiv

  12. [12]

    Quest: Quantum-enhanced shared transportation, in: 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), IEEE. pp. 2149–

    2025

  13. [13]

    Quantum-assisted solution paths for the capacitated vehicle routing problem, in: 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), IEEE. pp. 648–658. Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.H., Zhou, X.Q., Love, P.J., Aspuru-Guzik, A., O’brien, J.L.,

    2023

  14. [14]

    arXiv preprint arXiv:2512.10813

    Quantum approaches to urban logistics: From core qaoa to clustered scalability. arXiv preprint arXiv:2512.10813 . Preskill, J.,

    work page arXiv

  15. [15]

    arXiv preprint arXiv:2501.11197

    Q-restore: quantum-drivenframeworkforresilientandequitable transportation network restoration. arXiv preprint arXiv:2501.11197 . Vikstål, P., Grönkvist, M., Svensson, M., Andersson, M., Johansson, G., Ferrini, G.,

    work page arXiv

  16. [16]

    arXiv preprint arXiv:2412.13849

    99.9%-fidelity in measuring a superconducting qubit. arXiv preprint arXiv:2412.13849 . Wang, D., Higgott, O., Brierley, S.,

    work page arXiv