Abstract Quantum optimization for routing must be evaluated against both feasibility and strategic incentives. We study a finite atomic congestion game in which four vehicles choose among three parallel roads with affine, increasing latencies. The experiment enumerates all 81 assignments in each of eight seeded synthetic instances, computes pure Nash equilibria and tests by linear programming whether any social-optimal correlated equilibrium exists. We compare a 12-qubit, depth-one one-hot penalty-QAOA statevector ansatz, a depth-one continuous-time quantumwalk (CTQW) ansatz represented directly on the 81 feasible profiles, and classical local search under the same maximum of 40 objective calls per start. Across 24 starts per method, local search reached the exact optimum in all starts. The mean relative gap was 23.22% (SD 11.21 percentage points) for QAOA’s expected cost conditioned on feasible outcomes and 8.34% (SD 3.42 points) for the feasible-profile CTQW expected cost. QAOA assigned an average 17.05% of its final ideal-state probability mass to feasible assignments; feasibility was 100% for CTQW by construction. An optimal correlated equilibrium existed in five of the eight games. These are descriptive results for a very small, noiseless statevector benchmark. The CTQW calculation uses classical dense diagonalization, the representations are not resource-matched, and no hardware advantage or quantum speedup is established.
We formulate capacitated vehicle routing as a colored permutation problem: each of the K vehicles selects a disjoint partial permutation, and the sum of these K submatrices forms a full n × n permutation matrix that assigns everycustomer to exactly one visit position. This representation requires no explicit load register (and hence no extra qubits) beyondthe routing variables. In contrast, prior quantum encodings introduce an explicit capacity/load representation with O(Q) or O(log Q) additional qubits for capacity Q [1, 2]. Our construction is designed to satisfy the kernel requirement of the Constraint-Enhanced QAOA (CE-QAOA) framework [3], making the resulting VRP instances compatible with its feasibility- and finite-shot guarantees [4, 5]. On the full benchmark suite of [6], our p = 1 CE–QAOA implementation recovers the certified optimum for every instance, without decomposition. All results are fully reproducible from the companion artifact archive in Ref. [7].
The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, making it a potential application for near-term quantum optimization. This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA, p = 2) against Google OR-Tools Guided Local Search on a seeded instance with three customers and two vehicles. The study examines the QUBO formulation, energy spectrum, optimization behavior, penalty weights, Hamiltonian scaling, and circuit depths. The experiments show that the tested QAOA configurations do not reliably concentrate probability on optimal solutions. The classical solver identifies the optimal solution for the selected instance. The study provides a reproducible baseline and discusses limitations and future research directions. The findings are limited to the tested instance, formulation, and optimization configurations.
Strategic decision-making among many agents under incomplete information is central to economics, security, and multi-agent artificial intelligence (AI). Computing equilibria in such settings is challenging because the joint type-action space grows exponentially with the number of players. In binary-type, binary-action Bayesian games with
n players, an explicit representation over type-action profiles requires
O(22n) entries, making direct linear-programming (LP) formulations increasingly costly as
n grows. We propose a hybrid quantum-classical framework for approximating Bayes correlated equilibrium (BCE) using a parameterized quantum circuit (PQC). The PQC represents the conditional distribution over joint actions using
O(nL) trainable parameters, where
L denotes the circuit depth; for the largest trained setting,
n=8 and
L=2, this corresponds to
48 trainable angles. Each player count is trained independently by maximizing expected social welfare with a penalty on positive aggregated BCE obedience violations. On a strategically coupled Bayesian congestion game with
n=2,4,6,8 players, feasible PQC solutions attain higher welfare than MCCFR and DCFR product-strategy baselines while satisfying
εmax≤10−3, where
εmax denotes the maximum positive aggregated BCE obedience violation. Across five independent runs per setting, all runs are feasible for
n=2,4,6, while four of five are feasible for
n=8. PQC welfare remains below the exact LP optimum, with the absolute gap increasing with
n, while classical state-vector simulation prevents PQC training beyond eight players. These results demonstrate the use of a compact PQC parameterization for approximate equilibrium computation and quantify its welfare, feasibility, and classical simulation scaling on the studied benchmark.
Siting a limited number of fast-charging hubs so that the greatest share of urban charging demand falls within reach is a discrete, NP-hard facility-location task that grows combinatorially with the number of candidate parcels. We recast this task for gate-model quantum hardware. Demand intensity and candidate parcels are extracted from a public Government of NCT of Delhi charging-station record of 2,270 georeferenced points, a demand-weighted maximumcoverage objective with a cardinality constraint is mapped to a Quadratic Unconstrained Binary Optimization (QUBO) model, and the QUBO is expressed as an Ising cost Hamiltonian solved by the Quantum Approximate Optimization Algorithm (QAOA). On a twelve-parcel instance selecting five hubs, exact enumeration places the optimum at 53.2% covered demand; QAOA recovers an approximation ratio that rises from 0.67 at depth p=1 to 0.93 at p=3, while a depth-four circuit regresses to 0.83 under a fixed optimizer budget, illustrating the trainability cost of added layers. At this NISQ-tractable size, greedy and simulated-annealing baselines both reach the exact optimum, so the quantum contribution is algorithmic rather than a wall-clock advantage; an explicit size sweep shows the classical search space and exact-solve effort growing as 2^N, which is where deeper quantum circuits are expected to matter. The study is reported transparently, including the negative parity results.
Transportation routing problems such as the Traveling Salesperson Problem (TSP) and the Vehicle Routing Problem (VRP) are characterized by strict feasibility requirements involving customer assignment and visit rules, route sequencing, and depot-return logic alongside cost minimization. Most quantum routing formulations adopt Quadratic Unconstrained Binary Optimization (QUBO) encodings, where feasibility is incorporated indirectly via penalty terms in the cost Hamiltonian. While convenient for standard implementations of the Quantum Approximate Optimization Algorithm (QAOA), QUBO encodings allow the quantum search dynamics to allocate substantial probability to infeasible route configurations. This study develops a transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator. We introduce a custom mixer that functions as a quantum analogue of feasibility-preserving routing neighborhoods, using column-wise swap moves, it restricts evolution to feasible configurations while enabling structured exploration of valid routes. We compare three constraint-handling architectures: penalty-based QUBO QAOA, penalty free QAOA+ with the feasibility-preserving mixer, and a Hybrid QAOA+ combining mixer based feasibility with and penalty guidance. Results on small TSP and VRP instances show that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes. These findings position constraint-aware quantum search as a methodological extension of transportation routing search approaches, where feasibility is enforced through admissible quantum transitions rather than post-hoc penalties.
This paper establishes the tractability of finding the optimal Nash equilibrium, as well as the optimal social solution, to a discrete congestion game using a gate-model quantum computer. The game is of the type originally posited by Rosenthal in the 1970's. To find the optimal Nash equilibrium, we formulate an optimization problem encoding based on potential functions and path selection constraints, and solve it using the Quantum Alternating Operator Ansatz. We compare this formulation to its predecessor, the Quantum Approximate Optimization Algorithm. We implement our solution on an idealized simulator of a gate-model quantum computer, and demonstrate tractability on a small two-player game. This work provides the basis for future endeavors to apply quantum approximate optimization to quantum machine learning problems, such as the efficient training of generative adversarial networks using potential functions.