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

• URL: http://arxiv.org/abs/2604.22194v1
• Date: Fri, 24 Apr 2026 03:46:25 GMT
• Title: Qubit-Scalable CVRP via Lagrangian Knapsack Decomposition and Noise-Aware Quantum Execution
• Abstract summary: We present an end-to-end framework for scaling hybrid quantum CVRP optimization through OR decomposition, learning-augmented dual control, and adaptive hardware-aware execution.<n>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.
• Score: 3.652509571098291
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Noise-Aware Quantum Algorithm for Credit Valuation Adjustments on Real Quantum Hardware [0.0]
  Credit Valuation Adjustment (CVA) requires repeated risk-neutral expectation estimation.<n>We develop an end-to-end, noise-aware quantum workflow for CVA.
  arXiv  Detail & Related papers  (2026-07-14T17:41:11Z)
• WINDQuant: Weight-Informed Neural Decision-Making for Global Mixed-Precision LLM Quantization [40.655670203062805]
  WINDQuant is a reinforcement-learning-based allocation controller for ultra-low-bit LLM quantization.<n>It learns how to assign bit-widths and quantization treatments to fine-grained column chunks under a global storage budget.<n>Experiments on LLaMA models demonstrate that WINDQuant achieves competitive performance in ultra-low-bit settings.
  arXiv  Detail & Related papers  (2026-05-26T07:46:13Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Large-scale portfolio optimization on a trapped-ion quantum computer [32.24411362086563]
  We present an end-to-end pipeline for large-scale portfolio selection with cardinality constraints.<n>We experimentally demonstrate it on trapped-ion quantum processors using hardware-aware decomposition.
  arXiv  Detail & Related papers  (2026-02-27T12:36:14Z)
• An Adaptive Purification Controller for Quantum Networks: Dynamic Protocol Selection and Multipartite Distillation [10.706268477180858]
  We propose an Adaptive Purification Controller (APC) that automatically optimize the entanglement distillation sequence to maximize the goodput.<n>We show that our approach mitigates the "fidelity cliffs" inherent in static protocols and reduces resource wastage in high-noise regimes.<n>We extend the controller to heterogeneous scenarios, and evaluate it for both multipartite GHZ state generation and continuous-variable systems.
  arXiv  Detail & Related papers  (2026-01-26T10:56:37Z)
• Adaptive Fidelity Estimation for Quantum Programs with Graph-Guided Noise Awareness [30.900274564864223]
  QuFid is an adaptive and noise-aware framework that determines measurement budgets online.<n>We show that QuFid significantly reduces measurement cost compared to fixed-shot and learning-based baselines.
  arXiv  Detail & Related papers  (2026-01-21T07:04:05Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer [1.5119440099674915]
  Vehicle Problem Routing (VRP) is a fundamental optimization challenge with broad applications in logistics and transportation.<n>We present a quantum-assisted framework that integrates the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of VRP.<n>Our approach encodes flow conservation and subtour elimination directly into the cost Hamiltonian, preserving graph structure while avoiding ancillary qubits.
  arXiv  Detail & Related papers  (2025-05-02T22:31:01Z)
• A Fast and Adaptable Algorithm for Optimal Multi-Qubit Pathfinding in Quantum Circuit Compilation [0.0]
  This work focuses on multi-qubit pathfinding as a critical subroutine within the quantum circuit compilation mapping problem. We introduce an algorithm, modelled using binary integer linear programming, that navigates qubits on quantum hardware optimally with respect to circuit SWAP-gate depth. We have benchmarked the algorithm across a variety of quantum hardware layouts, assessing properties such as computational runtimes, solution SWAP depths, and accumulated SWAP-gate error rates.
  arXiv  Detail & Related papers  (2024-05-29T05:59:15Z)
• Compiler for Distributed Quantum Computing: a Reinforcement Learning Approach [6.347685922582191]
  We introduce a novel compiler that prioritizes reducing the expected execution time by jointly managing the generation and routing of EPR pairs. We present a real-time, adaptive approach to compiler design, accounting for the nature of entanglement generation and the operational demands of quantum circuits. Our contributions are twofold: (i) we model the optimal compiler for DQC using a Markov Decision Process (MDP) formulation, establishing the existence of an optimal algorithm, and (ii) we introduce a constrained Reinforcement Learning (RL) method to approximate this optimal compiler.
  arXiv  Detail & Related papers  (2024-04-25T23:03:20Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.