Quantum Queb'Hackers

CVRP Solution - Instance 1 - Routes optimized with VQE
CVRP Solution - Instance 2 - Routes optimized with VQE
CVRP Solution - Instance 3 - Routes optimized with VQE
CVRP Solution - Instance 4 - Routes optimized with VQE

Inspiration

The Capacitated Vehicle Routing Problem (CVRP) is the lifeblood of modern logistics. From global supply chains to last-mile delivery, even a marginal $0.5\%$ optimization can translate to millions of dollars in annual savings and significant reductions in carbon emissions.

However, CVRP is an NP-hard problem. As the number of customers $N$ grows, the solution space explodes exponentially, rendering classical exact solvers powerless. We saw this as the perfect arena to demonstrate the potential of quantum computing. Our inspiration wasn't just to write a quantum algorithm, but to build a practical, NISQ-aware bridge between classical logistics and near-term quantum hardware. We wanted to prove that by intelligently combining classical geometry with quantum combinatorial search, we could tackle complex instances today.

What it does

Quantum Courier is a hybrid quantum-classical solver for the CVRP. It decomposes the massive global routing problem into a series of smaller, hardware-tractable Traveling Salesman Problems (TSPs).

Our solver operates in two phases:

Classical Partitioning: A novel "Rotation-Optimized Sweep" algorithm clusters customers based on vehicle capacity and minimal angular spread.
Quantum Routing: Each cluster's optimal route is solved using one of our two quantum backends: SamplingVQE (optimized for high-fidelity simulation) or QAOA (our path-to-real-hardware implementation).

How we built it

We built the project using Python, Qiskit, and the qBraid platform. The architecture relies on a "Cluster-First, Route-Second" paradigm:

Rotation-Optimized Sweep: Standard sweep heuristics use a fixed starting angle, which often creates overlapping or suboptimal vehicle sectors. We implemented an exhaustive $O(n)$ search across all possible starting angles to find the partition that explicitly minimizes the total angular spread:

$$\min \sum_{k=1}^{K} \left( \theta_{max}^{(k)} - \theta_{min}^{(k)} \right) \pmod{2\pi}$$

This guarantees geometrically compact clusters, resulting in near-planar distance matrices that quantum algorithms can solve much more efficiently at shallow circuit depths.

Dual Quantum Backends: We formulated each cluster as a Quadratic Unconstrained Binary Optimization (QUBO) problem.
- For our primary submission results, we utilized SamplingVQE with a hardware-efficient RealAmplitudes ansatz and the SPSA optimizer. This provided fast, reliable convergence on the qBraid AerSimulator.
- Simultaneously, we built a QAOA backend with the COBYLA optimizer. While slower on simulators, QAOA's fixed alternating operator structure maps natively to the entangling gates of real QPU hardware.

Challenges we ran into

The biggest challenge was qubit scaling and the limitations of the NISQ (Noisy Intermediate-Scale Quantum) era.

Solving CVRP directly on a quantum computer requires $O(N^2)$ qubits for the QUBO encoding. For our 12-customer instance (Instance 4), a direct approach would require well over 144 qubits—far beyond current uncorrected capabilities.

We overcame this by strictly bounding our cluster sizes to $n \le 4$. This mathematical guarantee ensures that no single quantum circuit ever requires more than $n^2 = 16$ qubits.

Additionally, managing the Depth vs. Noise tradeoff in our QAOA implementation was complex. Increasing the QAOA layers ($p$) improves the theoretical approximation ratio but deepens the circuit, making it highly vulnerable to decoherence on real hardware. We designed the architecture to keep depth manageable while relying on our optimized classical clustering to "feed" the quantum circuit an easier landscape.

Accomplishments that we're proud of

Surpassing the Heuristic Bound: On Instance 4, the provided heuristic reference distance was $61.85$. Our hybrid solver found a better global configuration, achieving a total distance of $59.66$ (an Approximation Ratio of $0.96$).
100% Accuracy on smaller sets: We consistently hit the absolute optimal bounds ($1.00$ ratio) on Instances 1 and 2.
A Truly Hardware-Ready Design: We are incredibly proud of our dual-backend architecture. We didn't just build a simulator script; by bounding our qubit requirements to $\le 16$ and maintaining a separate QAOA pipeline, our code is ready to run on physical superconducting or trapped-ion QPUs with a single line change.

What we learned

We learned that quantum advantage in optimization isn't just about the quantum circuit—it's about the classical-quantum handoff. By improving our classical clustering algorithm (the rotation optimization), we empirically observed faster convergence and better approximation ratios in our VQE optimizer. We learned how to formulate TSPs into Ising Hamiltonians, how to tune variational parameters like reps in our ansatz, and the practical differences between VQE's flexibility and QAOA's theoretical grounding.

What's next for Quantum Courier

Real Hardware Execution: Swapping out our StatevectorSampler for a qBraid QPU backend to test the QAOA implementation against real hardware noise profiles.
Dynamic VQE: Implementing dynamic circuit depth that automatically scales based on the specific condition number of the cluster's distance matrix.
Time Windows (VRPTW): Expanding our QUBO formulation to include penalty terms for strict delivery time windows, adding a critical layer of real-world applicability.