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:2609.19575

Vehicle-Routing Clustering by Sparse Quantum Relaxation

Farzan Moosavi, Bilal Farooq

quant-phSubmitted Sep 17, 2026• Announced Sep 18, 2026• 0 citations
arXivHTMLPDF

Abstract

This paper studies the cluster-assignment layer of a cluster-first-route-second decomposition for the capacitated pickup-and-delivery problem with time windows (CPDPTW), instead of a direct route-ordering quadratic unconstrained binary optimization (QUBO). Sample-based subspace diagonalization (SQD) degenerates to best-of-shots for any diagonal optimization Hamiltonian, so a useful transfer to routing requires non-diagonal relaxation. Quantum random access optimization (QRAO) provides this non-diagonality by encoding binary variables through non-commuting quantum random access code (QRAC) observables. CPDPTW-derived conflict graphs expose a routing-specific obstruction because dense objectives and penalty-encoded constraints destroy QRAO compression. We keep the Hamiltonian sparse by encoding only the sparsified objective and enforcing one-hot, capacity, and cluster time-budget feasibility by repair after rounding. We make no quantum-advantage claim. Under strong repair the classical pass alone reaches near-optimal cost at the tested sizes. The result is a regime map linking sparsification, achieved compression, linear-combination-of-unitaries (LCU) 1-norm, heavy-hex two-qubit depth, sampling drift, and final routing quality on Qiskit Aer, calibrated FakeTorino, and IBM Heron ibm_quebec. Across a 108-row ideal-calibrated-hardware evaluation grid spanning four to twelve pickup-delivery request pairs, the hardware slice has mean gap 0.0016 and mean device-vs-ideal total variation distance (TVD) 0.279; a decoder ablation at sizes six through twelve isolates the non-diagonal signal.

AI Summary

The paper asks whether sample-based subspace diagonalization (SQD) can support quantum-assisted clustering for capacitated pickup-and-delivery routing with time windows. For a diagonal cost Hamiltonian, SQD on sampled computational-basis states is exactly best-of-shots. It therefore uses quantum random access optimization (QRAO) to construct a non-diagonal relaxation of a cluster-assignment surrogate, leaving route sequencing classical. The pipeline sparsifies request-conflict graphs, encodes only the clustering objective, and enforces assignment, capacity, and cluster-time budgets through classical repair after rounding. Graph analysis shows why this matters: dense interactions prevent independent-set packing for QRAO, while quadratic constraint penalties restore cliques. Across tested instances, binary/HOBO compression changes from $1\times$ on dense graphs to $3\times$ after sparsification; full penalties maintain interaction density near $0.371$. Experiments use fixed shallow Krylov-state sampling, ideal simulation, calibrated noise simulation, and IBM Heron hardware. At eight requests, increasing the Krylov dimension from one to five lowers SQD energy from $-3.20\pm0.55$ to $-5.51\pm1.19$. A 108-record evaluation includes 36 hardware runs spanning four to twelve requests; hardware has mean reported gap $0.0016$ and mean device-versus-ideal total variation distance $0.279$, versus a finite-shot null floor of $0.114$. The principal limitation is that strong classical repair also brings classical baselines near optimality, masking any quantum contribution. Feasibility-only ablations show decoder-budget-dependent gains, but a matched randomized-rounding surrogate is deferred. The instances are small, routing constraints are partly represented by clustering proxies, and no quantum advantage is claimed.

Little sign of AI-generated textIncrementalSmall numerics onlyMissing comparison

Central claim may not hold: The abstract overgeneralizes the density-induced loss of QRAO compression: the reported objective-only one-hot encoding retains 3× compression, whereas the demonstrated collapse concerns binary/HOBO encodings. The advertised regime map includes heavy-hex two-qubit depth, but the paper supplies no numerical depth results or comparison across sparsification levels. Although the paper identifies true CPDPTW route cost as its final objective, it does not define the reported gap or its hardware reference optimum, leaving the claimed near-optimal routing quality unverified.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Journal reference
In the proceeding of IEEE Quantum Artificial Intelligence 2026

Related papers

Hardware-Aware Sparse QUBO Encoding for CVRPTW on Coherent Ising Machines: An LKH-Guided Variable-Compression Framework

Zhitao Wu, Zonglin Yang, Jie Zhou +2 more

Capacitated vehicle routing with time windows (CVRPTW) is a natural target for coherent Ising machines (CIMs), but a direct multi-vehicle arc encoding scales as O(mN2) and exceeds the variable budget of current CIM-compatible systems. We argue the bottleneck is encoding density, not expressiveness, and present LSQ, a hardware-aware sparse Quadratic Unconstrained Binary Optimization (QUBO) framework that decouples CVRPTW into a compact customer-to-route assignment QUBO and a classical intra-route ordering step under a soft no-wait service convention. LKH candidate edges compress the per-route edge space from O(N2) to O(KN), and a per-route dynamic-penalty subroutine encodes time-window sensitivities as binary variables in a round-wise outer loop. On a six-vehicle, 51-node reference instance curated from long-term operational data, LSQ shrinks the maximum single-submission QUBO from 15,300 arc variables to 342 logicalQUBOvariables (∼45× compression), cuts travel time by 22.9% (74 vs. 96), and cuts route duration by 11.2% (174 vs. 196) against an OR-Tools soft-window baseline at the same fleet size. OR-Tools retains an advantage on raw time-window penalty (1600 vs. 3540) and runtime; under the scalar operational cost ∑kT(πk)+∑iℓi(τi), OR-Tools is therefore the better single-objective solver, and the comparison is a multi-objective trade-off rather than a scalar dominance claim. Ablations confirm that the LKH prior recovers Held–Karp on a 15-customer TSP at 53 vs. 120 variables and that the dynamic-penalty encoding reduces compressed time-window loss by 15.25% at constant travel. All hardware claims refer to QUBO sizing on a Kaiwu/CIM-compatible backend, not physical CIM execution.

Algorithms•Jun 29, 2026•0 citations

Hybrid Classical-Quantum Optimization for CVRPTW: A Systems Framework with Provable Feasibility and Empirical Hardware Limits

Syamasundar Gopasana, Swatantra Singh, Rohan Joydhar +1 more

Solving large-scale Capacitated Vehicle Routing Problems with Time Windows (CVRPTW) remains challenging because strict operational constraints and scale limit both exact and heuristic methods. We present a hybrid classical-quantum architecture combining Mixed Integer Linear Programming (MILP) with vehicle-level Quadratic Unconstrained Binary Optimization (QUBO), solved using Toshiba SQBM+ and QAOA on Rigetti Ankaa-3 and IQM Emerald quantum processors. The decomposition avoids the variable growth and constraint-enforcement difficulties of monolithic CVRPTW QUBO formulations. We evaluate the framework on five realistic benchmarks derived from London traffic and location data, spanning 10--70 customers, using a validation pipeline enforcing feasibility and monotone improvement over classical baselines. SQBM+ achieves verified fleet-distance reductions of 2.80% (7,927 m) for the 25-customer instance and 0.22% (1,186 m) for the 55-customer instance. QAOA experiments establish a current hardware boundary for reliable constraint satisfaction at subproblems of up to 4 customers (16 qubits). Diagnostic results identify assignment-level time-window tightness, rather than local route optimization, as the dominant scalability bottleneck. The results demonstrate a practical near-term role for hybrid classical-quantum optimization while establishing empirical limits for current quantum hardware.

arXiv:2611.15343•Nov 11, 2026•0 citations

RL-Guided Quantum-ALNS for Constrained VRP

Farzan Moosavi, Bilal Farooq

This study develops a hybrid quantum-classical framework for constrained vehicle routing problems, focusing on the pickup-and-delivery problem with time windows. Instead of casting the full routing problem as a stand-alone quantum optimization task, we embed shallow quantum samplers inside the repair phase of an Adaptive Large Neighbourhood Search (ALNS) heuristic. A Deep Q-Network controller decides whether each reduced repair subproblem should be handled by a classical repair heuristic or by a quantum sampler, using features that describe the local repair structure and predicted hardware reliability. IBM Heron experiments are used to calibrate an empirical noise-aware model for local quantum repair circuits. Across the tested instances, quantum repair is admissible in only about 16% of reduced repair states and is not superior on average. However, under selected matched repair budgets, quantum-enabled repair reduces the final gap relative to standard ALNS in 29 of 36 tested settings. These results suggest that near-term quantum sampling is most useful as a selective local repair mechanism rather than as a replacement for classical routing heuristics.

quant-pharXiv:2607.07550•Jul 9, 2026•2 citations

Qubit-Scalable CVRP via Lagrangian Knapsack Decomposition and Noise-Aware Quantum Execution

Monit Sharma, Hoong Chuin Lau

Hybrid quantum optimization for vehicle routing faces a practical bottleneck: direct QUBO encodings of CVRP quickly exceed near-term qubit and gate budgets, while quantum evaluations are expensive, noise-limited, and sensitive to backend and circuit configuration. We address this gap with an end-to-end decomposition pipeline that converts CVRP into bounded-width quantum subproblems and treats quantum execution as a decision problem within the optimization loop. Starting from a Fisher--Jaikumar assignment linearization, we apply Lagrangian relaxation to dualize customer-assignment couplers, yielding independent per-vehicle knapsack subproblems that admit QUBO/Ising evaluation. To replace brittle subgradient tuning, we learn a multiplier-update controller using expert-guided pretraining followed by reinforcement-learning fine-tuning, with rewards based on execution-realized progress and route reconstruction. We also introduce a constrained contextual bandit as a hardware-aware execution layer that selects backend and circuit configuration with feasibility screening, enabling adaptation across heterogeneous noisy resources and parallel multi-QPU scheduling. Computational results on multiple CVRPLIB families show that the decomposition yields stable bounded-width subproblems across instance sizes, learned multiplier updates improve end-to-end routing quality relative to classical subgradient control under matched budgets, and hardware-mode configuration reduces median optimality gaps relative to static execution choices in our test set. We do not claim quantum advantage. Instead, the contribution is a practical end-to-end framework for scaling hybrid quantum CVRP optimization through OR decomposition, learning-augmented dual control, and adaptive hardware-aware execution.

quant-pharXiv:2604.22194•Apr 27, 2026•2 citations

QUBO Formulation of the Pickup and Delivery Problem with Time Windows for Quantum Annealing

Cosmin Ștefan Curuliuc, Florin Leon

This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).

Applied Sciences•Feb 8, 2026•1 citation

Complexity Amplification from Compression in Quantum Random Access Optimization

Stuart Hadfield

Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP $\cap$ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.

quant-pharXiv:2609.07090•Sep 8, 2026•2 citations
This paper studies the cluster-assignment layer of a cluster-first-route-second decomposition for the capacitated pickup-and-delivery problem with time windows (CPDPTW), instead of a direct route-ordering quadratic unconstrained binary optimization (QUBO). Sample-based subspace diagonalization (SQD) degenerates to best-of-shots for any diagonal optimization Hamiltonian, so a useful transfer to routing requires non-diagonal relaxation. Quantum random access optimization (QRAO) provides this non-diagonality by encoding binary variables through non-commuting quantum random access code (QRAC) observables. CPDPTW-derived conflict graphs expose a routing-specific obstruction because dense objectives and penalty-encoded constraints destroy QRAO compression. We keep the Hamiltonian sparse by encoding only the sparsified objective and enforcing one-hot, capacity, and cluster time-budget feasibility by repair after rounding. We make no quantum-advantage claim. Under strong repair the classical pass alone reaches near-optimal cost at the tested sizes. The result is a regime map linking sparsification, achieved compression, linear-combination-of-unitaries (LCU) 1-norm, heavy-hex two-qubit depth, sampling drift, and final routing quality on Qiskit Aer, calibrated FakeTorino, and IBM Heron ibm_quebec. Across a 108-row ideal-calibrated-hardware evaluation grid spanning four to twelve pickup-delivery request pairs, the hardware slice has mean gap 0.0016 and mean device-vs-ideal total variation distance (TVD) 0.279; a decoder ablation at sizes six through twelve isolates the non-diagonal signal.
The paper asks whether sample-based subspace diagonalization (SQD) can support quantum-assisted clustering for capacitated pickup-and-delivery routing with time windows. For a diagonal cost Hamiltonian, SQD on sampled computational-basis states is exactly best-of-shots. It therefore uses quantum random access optimization (QRAO) to construct a non-diagonal relaxation of a cluster-assignment surrogate, leaving route sequencing classical.
The pipeline sparsifies request-conflict graphs, encodes only the clustering objective, and enforces assignment, capacity, and cluster-time budgets through classical repair after rounding. Graph analysis shows why this matters: dense interactions prevent independent-set packing for QRAO, while quadratic constraint penalties restore cliques. Across tested instances, binary/HOBO compression changes from 1×1\times1× on dense graphs to 3×3\times3× after sparsification; full penalties maintain interaction density near 0.3710.3710.371.
Experiments use fixed shallow Krylov-state sampling, ideal simulation, calibrated noise simulation, and IBM Heron hardware. At eight requests, increasing the Krylov dimension from one to five lowers SQD energy from −3.20±0.55-3.20\pm0.55−3.20±0.55 to −5.51±1.19-5.51\pm1.19−5.51±1.19. A 108-record evaluation includes 36 hardware runs spanning four to twelve requests; hardware has mean reported gap 0.00160.00160.0016 and mean device-versus-ideal total variation distance 0.2790.2790.279, versus a finite-shot null floor of 0.1140.1140.114.
The principal limitation is that strong classical repair also brings classical baselines near optimality, masking any quantum contribution. Feasibility-only ablations show decoder-budget-dependent gains, but a matched randomized-rounding surrogate is deferred. The instances are small, routing constraints are partly represented by clustering proxies, and no quantum advantage is claimed.
Capacitated vehicle routing with time windows (CVRPTW) is a natural target for coherent Ising machines (CIMs), but a direct multi-vehicle arc encoding scales as O(mN2) and exceeds the variable budget of current CIM-compatible systems. We argue the bottleneck is encoding density, not expressiveness, and present LSQ, a hardware-aware sparse Quadratic Unconstrained Binary Optimization (QUBO) framework that decouples CVRPTW into a compact customer-to-route assignment QUBO and a classical intra-route ordering step under a soft no-wait service convention. LKH candidate edges compress the per-route edge space from O(N2) to O(KN), and a per-route dynamic-penalty subroutine encodes time-window sensitivities as binary variables in a round-wise outer loop. On a six-vehicle, 51-node reference instance curated from long-term operational data, LSQ shrinks the maximum single-submission QUBO from 15,300 arc variables to 342 logicalQUBOvariables (∼45× compression), cuts travel time by 22.9% (74 vs. 96), and cuts route duration by 11.2% (174 vs. 196) against an OR-Tools soft-window baseline at the same fleet size. OR-Tools retains an advantage on raw time-window penalty (1600 vs. 3540) and runtime; under the scalar operational cost ∑kT(πk)+∑iℓi(τi), OR-Tools is therefore the better single-objective solver, and the comparison is a multi-objective trade-off rather than a scalar dominance claim. Ablations confirm that the LKH prior recovers Held–Karp on a 15-customer TSP at 53 vs. 120 variables and that the dynamic-penalty encoding reduces compressed time-window loss by 15.25% at constant travel. All hardware claims refer to QUBO sizing on a Kaiwu/CIM-compatible backend, not physical CIM execution.
Solving large-scale Capacitated Vehicle Routing Problems with Time Windows (CVRPTW) remains challenging because strict operational constraints and scale limit both exact and heuristic methods. We present a hybrid classical-quantum architecture combining Mixed Integer Linear Programming (MILP) with vehicle-level Quadratic Unconstrained Binary Optimization (QUBO), solved using Toshiba SQBM+ and QAOA on Rigetti Ankaa-3 and IQM Emerald quantum processors. The decomposition avoids the variable growth and constraint-enforcement difficulties of monolithic CVRPTW QUBO formulations. We evaluate the framework on five realistic benchmarks derived from London traffic and location data, spanning 10--70 customers, using a validation pipeline enforcing feasibility and monotone improvement over classical baselines. SQBM+ achieves verified fleet-distance reductions of 2.80% (7,927 m) for the 25-customer instance and 0.22% (1,186 m) for the 55-customer instance. QAOA experiments establish a current hardware boundary for reliable constraint satisfaction at subproblems of up to 4 customers (16 qubits). Diagnostic results identify assignment-level time-window tightness, rather than local route optimization, as the dominant scalability bottleneck. The results demonstrate a practical near-term role for hybrid classical-quantum optimization while establishing empirical limits for current quantum hardware.
This study develops a hybrid quantum-classical framework for constrained vehicle routing problems, focusing on the pickup-and-delivery problem with time windows. Instead of casting the full routing problem as a stand-alone quantum optimization task, we embed shallow quantum samplers inside the repair phase of an Adaptive Large Neighbourhood Search (ALNS) heuristic. A Deep Q-Network controller decides whether each reduced repair subproblem should be handled by a classical repair heuristic or by a quantum sampler, using features that describe the local repair structure and predicted hardware reliability. IBM Heron experiments are used to calibrate an empirical noise-aware model for local quantum repair circuits. Across the tested instances, quantum repair is admissible in only about 16% of reduced repair states and is not superior on average. However, under selected matched repair budgets, quantum-enabled repair reduces the final gap relative to standard ALNS in 29 of 36 tested settings. These results suggest that near-term quantum sampling is most useful as a selective local repair mechanism rather than as a replacement for classical routing heuristics.
Hybrid quantum optimization for vehicle routing faces a practical bottleneck: direct QUBO encodings of CVRP quickly exceed near-term qubit and gate budgets, while quantum evaluations are expensive, noise-limited, and sensitive to backend and circuit configuration. We address this gap with an end-to-end decomposition pipeline that converts CVRP into bounded-width quantum subproblems and treats quantum execution as a decision problem within the optimization loop. Starting from a Fisher--Jaikumar assignment linearization, we apply Lagrangian relaxation to dualize customer-assignment couplers, yielding independent per-vehicle knapsack subproblems that admit QUBO/Ising evaluation. To replace brittle subgradient tuning, we learn a multiplier-update controller using expert-guided pretraining followed by reinforcement-learning fine-tuning, with rewards based on execution-realized progress and route reconstruction. We also introduce a constrained contextual bandit as a hardware-aware execution layer that selects backend and circuit configuration with feasibility screening, enabling adaptation across heterogeneous noisy resources and parallel multi-QPU scheduling. Computational results on multiple CVRPLIB families show that the decomposition yields stable bounded-width subproblems across instance sizes, learned multiplier updates improve end-to-end routing quality relative to classical subgradient control under matched budgets, and hardware-mode configuration reduces median optimality gaps relative to static execution choices in our test set. We do not claim quantum advantage. Instead, the contribution is a practical end-to-end framework for scaling hybrid quantum CVRP optimization through OR decomposition, learning-augmented dual control, and adaptive hardware-aware execution.
This paper addresses the Pickup and Delivery Problem with Time Windows (PDPTW), an NP-hard combinatorial optimization problem with major practical relevance in logistics and transportation. The study focuses on a quadratic unconstrained binary optimization (QUBO) formulation for quantum annealing and benchmarks it against two classical optimization paradigms. A modular Python framework is developed that encodes PDPTW in three ways: a mixed-integer linear programming (MILP) model that serves as an exact reference, a genetic algorithm (GA) metaheuristic, and a QUBO model that is compatible with quantum annealers. The framework supports test scenarios with increasing structural complexity, with both feasible and intentionally infeasible instances. An additional contribution is the conceptual design and preliminary analysis of an automatic-penalty weight-tuning scheme for the QUBO model. Experimental results show that the proposed QUBO formulation can produce high-quality solutions for simpler PDPTW instances, but its performance strongly depends on the careful calibration of penalty weights. MILP provides optimal baselines on small instances but becomes intractable as problem size grows. The GA scales to the largest scenario and finds feasible solutions of reasonable quality, but they are not necessarily optimal. The evaluation also includes a large number of problem instances and runs on IBM Quantum hardware using the Quantum Approximate Optimization Algorithm (QAOA).
Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli XXX, YYY, and ZZZ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP ∩\cap∩ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.