Requirements for Early Quantum Advantage and Quantum Utility in the Capacitated Vehicle Routing Problem

• URL: http://arxiv.org/abs/2509.11469v1
• Date: Sun, 14 Sep 2025 23:23:00 GMT
• Title: Requirements for Early Quantum Advantage and Quantum Utility in the Capacitated Vehicle Routing Problem
• Abstract summary: We introduce a transparent, encoding-agnostic framework for determining when the Capacitated Vehicle Problem (CVRP) can achieve early quantum advantage.<n>Our analysis shows this is unlikely on noisy intermediate scale quantum (NISQ) hardware even in best case scenarios.<n>In addition to identifying candidate instances for early quantum advantage in CVRP, the framework provides a unifying go/no-go metric.
• Score: 0.2578242050187029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a transparent, encoding-agnostic framework for determining when the Capacitated Vehicle Routing Problem (CVRP) can achieve early quantum advantage. Our analysis shows this is unlikely on noisy intermediate scale quantum (NISQ) hardware even in best case scenarios that use the most qubit-efficient direct encodings. Closed-form resource counts, combined with recent device benchmarks, yield three decisive go/no-go figures of merit: the quantum feasibility point and the qubit- and gate-feasibility lines, which place any CVRP instance on a single decision diagram. Contrasting a direct QUBO mapping with a space-efficient higher-order (HOBO) encoding reveals a large gap. Applied to early-advantage benchmarks such as Golden-5, our diagram shows that HOBO circuits require only 7,685 qubits, whereas comparable QUBO encodings still exceed 200,000 qubits. In addition to identifying candidate instances for early quantum advantage in CVRP, the framework provides a unifying go/no-go metric that ingests any CVRP encoding together with any hardware profile and highlights when quantum devices could challenge classical heuristics. Quantum advantage in CVRP would likely require innovative problem decomposition techniques.

Related papers

• AQER: a scalable and efficient data loader for digital quantum computers [62.40228216126285]
  We develop AQER, a scalable AQL method that constructs the loading circuit by systematically reducing entanglement in target states.<n>We conduct systematic experiments to evaluate the effectiveness of AQER, using synthetic datasets, classical image and language datasets, and a quantum many-body state datasets with up to 50 qubits.
  arXiv  Detail & Related papers  (2026-02-02T14:39:42Z)
• Domain-Aware Quantum Circuit for QML [0.7999703756441755]
  We present a Domain-Aware Quantum Circuit (DAQC) that leverages image priors to guide locality-preserving encoding and entanglement.<n>The design employs interleaved encode--train cycles, where entanglement is applied among qubits hosting neighboring pixels, aligned to device connectivity.<n>We evaluate DAQC on MNIST, FashionMentangle, and PneumoniaMNIST datasets.
  arXiv  Detail & Related papers  (2025-12-19T17:02:58Z)
• Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem [0.11242503819703255]
  Quantum Classical Branch-and-Price (QCBP) is a hybrid quantum-classical algorithm for the Vertex Coloring problem on neutral-atom Quantum Processing Units (QPUs)
  arXiv  Detail & Related papers  (2025-08-26T10:03:56Z)
• A Qubit-Efficient Hybrid Quantum Encoding Mechanism for Quantum Machine Learning [11.861417859173859]
  Quantum Principal Geodesic Analysis (qPGA) is a non-invertible method for dimensionality reduction and qubit-efficient encoding.<n>We show that qPGA preserves local structure more effectively than both quantum and hybrid autoencoders.<n>In downstream QML classification tasks, qPGA can achieve over 99% accuracy and F1-score on MNIST and Fashion-MNIST, outperforming quantum-dependent baselines.
  arXiv  Detail & Related papers  (2025-06-24T03:09:16Z)
• Partial Blind Quantum Computation: A Framework for Selective Circuit Protection [0.5755004576310334]
  Universal Blind Quantum Computation protocols enable clients with limited quantum resources to delegate computations while concealing both inputs and circuit details.<n>Applying UBQC uniformly to an entire quantum circuit incurs additional quantum resources and computational overhead.<n>We propose a selective application of UBQC that targets only the critical components of quantum circuits.
  arXiv  Detail & Related papers  (2025-03-13T03:31:12Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Delegated variational quantum algorithms based on quantum homomorphic encryption [69.50567607858659]
  Variational quantum algorithms (VQAs) are one of the most promising candidates for achieving quantum advantages on quantum devices. The private data of clients may be leaked to quantum servers in such a quantum cloud model. A novel quantum homomorphic encryption (QHE) scheme is constructed for quantum servers to calculate encrypted data.
  arXiv  Detail & Related papers  (2023-01-25T07:00:13Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• An Optimized Quantum Implementation of ISD on Scalable Quantum Resources [2.274915755738124]
  We show that Prange's ISD algorithm can be implemented rather efficiently on a quantum computer. We leverage the idea of classical co-processors to design hybrid classical-quantum trade-offs.
  arXiv  Detail & Related papers  (2021-12-12T06:01:10Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

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.