Source-linked AI summary
A hybrid quantum-classical neural network for learning to route
Marcus Rolf Peter Ritt, Alexsandro Santos da Rosa Júnior, Marcos Vinicius Reballo, Cesar Augusto do Amaral, Fernando Augusto Caletti de Barros
TL;DR
The paper asks whether small QNNs can replace parameter-heavy modules in attention-based neural routing while preserving solution quality. It evaluates encoder feed-forward replacement for CVRP and finds a 56.6% parameter reduction with quality close to the classical neural baseline, while classical heuristics remain highly competitive. The study therefore presents QNN replacement as a hybrid compression strategy rather than evidence of quantum advantage or solver dominance.
Problem
The paper asks whether small QNN modules can replace parameter-heavy components of competitive classical neural routing models while retaining most solution quality.
Method
The authors replace encoder feed-forward blocks in an attention-based CVRP model with a narrow QNN bottleneck and compare its routing performance with classical neural and classical heuristic methods.
Results
56.6% fewer parameters preserved most of the classical attention model’s solution quality, with FF-QNN objective values never more than about 2% worse across tested sizes and decoding modes.
Takeaways & Limitations
Encoder feed-forward replacement is a viable hybrid-module compression strategy for neural combinatorial optimization, while classical heuristics remain strong practical baselines.
Takeaways & Limitations
The study does not establish that the QNN bottleneck is superior to size-matched classical bottlenecks.
Abstract
from arXiv · showhide
This work studies hybrid quantum-classical neural networks for learning routing heuristics. Specifically, this paper asks whether small quantum neural networks can replace parameter-heavy modules inside a competitive attention-based routing model while maintaining solution quality. For the capacitated vehicle routing problem, encoder feed-forward replacement emerges as the most promising design: it reduces the number of model parameters by 56.6% while keeping the hybrid model close to the classical neural baseline at small and medium instance sizes, although the gap grows for larger instances. This work also compares to classical routing algorithms, which remain highly competitive and often superior on the fixed Euclidean test sets. Our results therefore do not indicate quantum advantage or solver dominance, but identify encoder feed-forward replacement as a viable hybrid-module compression strategy for neural combinatorial optimization.
I. INTRODUCTION
The paper examines whether small quantum neural-network modules can replace parameter-heavy components of classical routing models for the CVRP. It motivates this narrower hybrid approach because current quantum hardware and simulators cannot support entire neural routing architectures.
- Current neural approaches learn routing solutions from sampled instances, but their parameter counts are too large for complete replacement by near-term quantum neural networks.
- The paper studies whether hybrid quantum-classical models can retain solution quality while using fewer parameters in the strongly NP-hard CVRP.The CVRP minimizes total vehicle travel distance while serving all customers under homogeneous vehicle capacities.
- Classical CVRP methods include exact branch-and-cut formulations, constructive heuristics, local-search heuristics, and metaheuristics.The arc-based formulation uses flow, depot-capacity, capacity-cut, and integrality constraints; capacity-cut constraints are exponential in number.
- Small QNN modules are evaluated as replacements for parameter-heavy subcomponents of competitive classical neural routing models.The focus is narrower than replacing entire neural architectures because current devices and simulators limit circuit width and depth.
- The paper reports a hybrid quantum-classical CVRP solver, experimental robustness validation, and competitive performance with more than 50% fewer parameters.
II. A HYBRID QUANTUM-CLASSICAL NEURAL NETWORK
The proposed hybrid model builds on an attention-based encoder-decoder routing architecture and replaces encoder feed-forward layers with a narrow QNN bottleneck. The bottleneck projects representations to a small qubit space, applies variational quantum processing, and projects outputs back to the hidden dimension.
- The classical routing model uses an encoder with node embeddings, repeated multi-head attention and feed-forward layers, plus a decoder that constructs routes iteratively.The decoder combines graph and route-position context, masks infeasible successors, and selects nodes greedily or by sampling.
- For L = 3, more than half of the model parameters lie in feed-forward layers outside the critical decoder path.The decoder remains computationally intensive because its one-to-all attention is repeated until a complete routing is produced.
- The hybrid design replaces encoder feed-forward blocks with a QNN after projecting the hidden representation from dimension d_h to q qubits.RX encoding and a brickwall variational ansatz with trainable rotations and CNOT gates are followed by measurement and up-projection to d_h.
- The architecture imposes q ≪ d_h as a strong bottleneck to reduce parameter count, with its impact evaluated experimentally.
A. Problem Instances
The experiments use randomly generated two-dimensional Euclidean CVRP instances with four customer-count settings. Demands and vehicle capacities vary with instance size.
- Training uses randomly generated Euclidean CVRP instances with n ∈ {10, 20, 50, 100} customers.Node coordinates are sampled uniformly from the unit square [0, 1]^2.
- Customer demands are random integers from {1, 2, . . . , 9}.
B. Models and Training Setup
The study trains classical and hybrid routing models with REINFORCE, evaluates greedy and sampling-based decoding, and uses a compact four-qubit FF-QNN configuration that reduces model parameters by 56.6%.
- REINFORCE training uses a greedy rollout baseline and Adam optimization with a learning rate of 10^-4.
- The QNN components are simulated and trained via backpropagation using q = 4 qubits and Lq = 2 layers.
- The hybrid FF-QNN model contains 1,156 classical and 24 quantum parameters.
- 56.6% fewer total parameters results from replacing the encoder feed-forward blocks, a reduction of 391,596 parameters with L = 3 encoder layers.
- Models are evaluated with greedy decoding and stochastic sampling, reporting the best solution among 1,280 samples for sampling.
C. Baseline Algorithms
The experiments compare the neural approaches with five classical heuristic solvers spanning savings, randomized constructive, commercial-library, and specialized routing methods.
- Five classical solvers provide comparison baselines: CW, RCW, GOT, LKH3, and RSW.
IV. EXPERIMENTAL RESULTS
The hybrid FF-QNN remains close to the classical attention model while reducing parameters, but learned methods do not dominate classical heuristics and become relatively less competitive as instance size grows.
- All reported solutions are feasible, with decoder masking enforcing feasibility for neural models and no invalid routes observed.
- Five independent FF-QNN training runs show stable behavior with low variability across runs.
- The reported table metrics include mean objective value, average relative deviation from the best per-instance value, and total evaluation time.
- The average relative deviation compares each method's objective with the best value achieved for that instance across methods.
- Expected route-length estimates indicate that observed CVRP objective values lie within a plausible range, though the estimates are not strict upper bounds.
- LKH3 gives the best solution quality from n = 20 onward, while gaps increase with n and learned methods remain broadly comparable to constructive baselines.
- FF-QNN objective values are never more than about 2% worse than AM across instance sizes and decoding modes, and are slightly better at n = 10 with sampling.
- 56.6% parameter reduction preserves most AM solution quality through the four-qubit bottleneck replacement.
V. RELATED WORK
The work builds on neural combinatorial optimization and routing architectures, while highlighting that more encoder-heavy graph models may be harder to integrate with quantum components.
- Learning-based combinatorial optimization includes constructive and end-to-end approaches, with this work focusing on specialized architectures trained using reinforcement learning.
- Routing research spans sequence-to-sequence and pointer-network methods, reinforcement-learning approaches for CVRP, and attention-based models.
- Residual edge-graph attention networks shift more computation into the encoder, increasing computational cost and making hybrid quantum-classical integration less clear.
VI. CONCLUSION
The paper introduces a hybrid quantum-classical alternative that replaces encoder feed-forward blocks with a narrow QNN, reducing parameters by more than 50% while preserving solution quality close to the classical neural model. Classical heuristics remain strong, with LKH3 producing the best solutions at higher computational cost and CW and RCW offering efficient baselines; the study does not establish superiority over compact classical bottlenecks.
- Hybrid architecture: 56.6% fewer parameters are achieved by replacing the encoder feed-forward blocks with a narrow QNN module.The paper characterizes this compact QNN as an alternative to attention-based routing approaches.
- Hybrid architecture: The hybrid model attains solution quality close to that of the classical neural network despite the parameter reduction.
- Classical comparisons: LKH3 consistently produces the best solutions among the classical heuristics, but requires higher computational cost.
- Classical comparisons: CW and RCW provide strong and efficient baselines for Euclidean instances.
- Limitations: The study does not establish that the QNN bottleneck is superior to all size-matched classical bottlenecks.The authors identify systematic comparisons with compact classical compression modules as future work.