Classical Approach to Instance 6 (Nv = 5, C = 5)
Quantum Approach to Instance 4 (Nv = 4, C = 3)
QAOA vs DQI Model Convergance
QAOA Convergance on Instance 4

Schrödinger's Husky - CVRP Solution Approach

Challenge: QuantumCT x RTRC x qBraid

Team: Parth Danve, Shai Verma, Pranay Kakkar, Pham Minh Toan Le, Manyata Pathania

Inspiration

We chose this project because the CVRP is a practical optimization problem with clear real-world value and a strong case for quantum experimentation. Routing appears in logistics, delivery, and field service, but exact optimization becomes expensive very quickly as the problem size grows. We wanted to build a solution that was more than a toy demo: a generalized hybrid pipeline that could solve the challenge instances, scale to larger instances, and let us compare multiple quantum and classical methods in the same framework.

We were especially interested in one practical question: where can quantum methods add value in a routing workflow, and how should they be combined with classical decomposition and post-processing to make the full system usable?

What it does

Our solution implements a hybrid quantum-classical approach to the Capacitated Vehicle Routing Problem (CVRP).

At a high level:

we take a full routing problem and break it into smaller capacity-feasible subproblems
each subproblem is converted into a QUBO / Ising formulation
we solve these using a mix of Gurobi, Genetic Algorithms, QAOA, DQI, and QITE
finally, we reconstruct the full set of routes and validate feasibility

The core idea is simple but powerful: instead of trying to solve everything at once, we isolate the hard combinatorial part and send that to quantum (or quantum-inspired) solvers.

How we built it

1. Problem formulation

We model CVRP as minimizing total travel distance:

$$ \min \sum_{k=1}^{K} \sum_{i=0}^{N} \sum_{j=0}^{N} d_{ij} \, x_{ijk} $$

subject to:

$$ \sum_{k=1}^{K} \sum_{i \ne j} x_{ijk} = 1 \quad \forall j \in V \setminus {0} $$

$$ \sum_{i} x_{ihk} - \sum_{j} x_{hjk} = 0 \quad \forall h \in V \setminus {0}, \ \forall k $$

$$ \sum_{j} x_{0jk} = 1, \quad \sum_{i} x_{i0k} = 1 \quad \forall k $$

$$ \sum_{i \in V \setminus {0}} q_i \sum_{j} x_{ijk} \le C \quad \forall k $$

These constraints enforce that each customer is visited exactly once, flow is conserved, each route starts and ends at the depot, and vehicle capacity is respected.

2. Decomposition (key idea)

Directly encoding CVRP into a quantum model quickly becomes too large.

So instead, we decompose the problem using capacity-aware clustering:

group nearby customers until capacity (C) is reached
refine cluster boundaries with local swaps
treat each cluster as a smaller routing problem

This reduces the quantum problem size from depending on total nodes (N) to depending on capacity (C).

3. QAOA (route ordering)

For each cluster, we convert routing into a QUBO:

$$ H = H_{\text{assignment}} + H_{\text{distance}} $$

and map it to an Ising Hamiltonian using:

$$ x_i = \frac{1 - Z_i}{2} $$

We then run QAOA to minimize the expected energy:

$$ \min_{\gamma,\beta} \langle \psi(\gamma,\beta) | H | \psi(\gamma,\beta) \rangle $$

We optimize parameters on simulators and then run the circuits on real hardware (IBM + qBraid).

4. DQI (subset selection)

Instead of solving ordering directly, DQI builds routes step-by-step:

pick a seed customer
choose a subset of nearby customers using a QUBO
use quantum-style interference to bias toward good subsets
solve ordering exactly using classical dynamic programming

This hybrid approach ended up being one of the strongest performers.

5. QITE (ground state evolution)

QITE takes a different approach by evolving the system toward the minimum:

$$ |\psi(\tau)\rangle \propto e^{-H\tau} |\psi(0)\rangle $$

This naturally pushes the system toward optimal solutions, but is limited by exponential memory when simulated classically.

6. Benchmarking

We compare all methods across multiple instances using:

total distance
feasibility
runtime
qubit count and gate depth

This lets us understand not just which method works, but why.

Challenges we ran into

The biggest challenge was that the mathematically natural CVRP formulation is not the same as a hardware-realistic quantum formulation. A direct end-to-end QUBO encoding of the full problem becomes impractical very quickly because route assignment, capacity inequalities, and subtour handling all increase the variable count, penalty complexity, and ultimately the logical qubit count.

Other technical challenges included:

designing a decomposition method that preserved feasibility while still producing subproblems with useful structure
tuning QUBO penalty weights so assignment constraints dominated invalid states without overwhelming the metric objective
decoding raw solver outputs into valid one-hot route assignments
handling the limits of QITE statevector simulation on larger instances
managing simulator-versus-hardware tradeoffs, including transpilation overhead, noise, queue latency, and circuit depth
making comparisons across exact, heuristic, variational, and quantum-inspired methods fair on the same benchmark suite

A major practical issue was that full variational optimization on current public hardware access modes is still difficult. In particular, iterative QAOA optimization is naturally suited to session-style execution, while many hardware access paths are better suited to final sampling of already-optimized circuits than to hundreds of optimizer-in-the-loop calls.

Accomplishments that we're proud of

We are proud that we built a generalized benchmarking pipeline, not a single hardcoded solver.

Some concrete things we are proud of:

implementing five distinct approaches in one project: Gurobi, GA, QAOA, DQI, and QITE
constructing a decomposition architecture that reduces the largest quantum subproblem from a function of total customer count (N) to a function of vehicle capacity (C)
solving six benchmark instances, including custom larger-scale instances beyond the smallest organizer-provided cases
producing route files, convergence traces, visualizations, and resource metrics in a reproducible structure
validating QAOA both on simulators and on live hardware backends
demonstrating that different methods dominate in different computational regimes rather than forcing a one-solver narrative

From a technical perspective, one of the strongest results is that the project does not merely compare algorithms on paper: it ties each method to a concrete formulation, concrete backend, concrete scaling regime, and measurable approximation behavior.

What we learned

Building this project gave us hands-on exposure to several quantum and quantum-inspired optimization methods, including QAOA, QITE, and DQI, and helped us understand how differently they behave in practice. One of our biggest lessons was that performance depends on much more than the solver itself; formulation, encoding, decomposition, and decoding all have a major impact on the final result.

We also learned that a pure QUBO formulation is not enough for the full CVRP. While equality constraints naturally fit into QUBO penalties, capacity constraints are more challenging to encode efficiently, as they quickly increase the problem size and circuit complexity. That pushed us toward a hybrid classical-quantum approach rather than trying to solve the entire problem directly on a quantum backend.

Another key lesson was that the classical decomposition stage matters just as much as the quantum algorithm. After comparing multiple clustering strategies, we found that capacity-aware agglomerative clustering produced the most stable and useful subproblems for downstream solvers.

What's next for Schrödinger's Husky

The next step is to evolve Schrödinger’s Husky from a hackathon prototype into a more realistic quantum-classical routing system.

Our technical priorities would be:

extending the CVRP model to include more real-world constraints, such as time windows, heterogeneous vehicle capacities, weighted and volumetric demand, pickup-and-delivery dependencies, driver shift limits, and vehicle-specific routing restrictions
improving the decomposition layer so clustering is guided not only by capacity and distance, but also by downstream solver cost, route balance, and operational feasibility
developing more compact QUBO / Hamiltonian encodings that reduce qubit requirements and circuit depth for larger subproblems
running larger experiments on lower-noise quantum hardware and comparing backend performance under realistic noise-aware evaluation, including transpilation cost, fidelity loss, and sampling stability
incorporating more advanced error-mitigation and hardware-aware compilation strategies to improve the quality of live quantum runs
expanding benchmarking so each solver is evaluated not just on objective value, but also on feasibility rate, resource usage, approximation gap, runtime, and scalability
packaging the pipeline into a reproducible end-to-end framework that can automatically ingest instances, select an appropriate solver, generate routes, and export operational metrics

From a production standpoint, the goal would be a routing engine that can handle operational constraints found in real logistics systems while dynamically choosing between exact, heuristic, quantum-inspired, and quantum methods based on problem size and hardware availability. That would make the system more practical, more scalable, and much closer to something that could be deployed in an actual decision-support environment.