Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

Authors: Linus Ekström, Hao Wang, Sebastian Schmitt · arXiv: 2605.10255 · submitted 12 May 2026 · score 8/10 (HIGH)

Abstract

Variational quantum algorithms have attracted attention for their potential to solve combinatorial optimization problems. We study how the choice of encoding affects the resource requirements and optimization behavior of a variational quantum optimization algorithm. In order to quantify these effects, realistically inspired constrained electric vehicle (EV) fleet management problems were considered. These problems couple determining the optimal EV battery charging schedule with assigning EVs to trips requested by customers. We compare a conventional binary (qubit) trip encoding with an integer (qudit) encoding that represents assignments more directly. Both encodings guarantee the same feasible solution set, while the qudit encoding exponentially reduces the required Hilbert-space dimension. We solve many random instances of highly constrained uni- and bi-directional charging problems using qudit-based quantum approximate optimization algorithm (QAOA) and thoroughly evaluate the performance results. We find that the qudit encoding of customer trips achieves similar or better optimization performance at much reduced resource requirements and shorter simulation runtime. These results highlight qudit-native encodings as a practical route for integer and multi-valued scheduling problems in variational quantum optimization.

Executive summary

Ekström, Wang and Schmitt run QAOA on an EV-fleet charging+trip-assignment problem under two encodings: a conventional one-qubit-per-(EV,trip) binary encoding and an integer one-qudit-per-trip encoding whose value names the assigned EV (or 0 if unserved). Both encodings cover the same feasible set, but the qudit encoding shrinks Hilbert-space dimension exponentially in the number of trips R and EVs N_EV. Across bi-directional (d=3, N_EV=3, T=2, R=2) and uni-directional (d=2, N_EV=2, T=3, R=2..4) instances, the qudit encoding matches or slightly beats the qubit one on success probability and mean energy gap, with substantially lower variance and dramatically faster simulation runtime. The result is the most direct empirical cousin to Y2's quasi-binary encoding argument in the published literature so far — same thesis (compact integer-aware encoding beats native binary on constrained QAOA), different problem class (EV fleet vs. portfolio optimization), and a published qudit mixer recipe Yuan can reuse.

Main contribution

The paper isolates encoding choice as a single experimental variable. In both formulations the charging variables l_n,t are qudit (d-ary) integers, mixed via a Bottarelli/Deller-style angular-momentum mixer H_X=β_1,lΣ_i L_i^x + β_2,lΣ_i (L_i^z)². Only the trip-assignment variable changes: r_n,i∈{0,1} (qubit, one per EV-trip pair) versus q_i∈{0,...,N_EV} (qudit, one per trip; q_i=0 means unserved). The integer encoding removes the one-EV-per-trip constraint automatically, since equal q_i values are forbidden only across overlapping trips. Hilbert dimension scaling is dim(H_int)/dim(H_bin) = 2^{−RN_EV+R log₂(N_EV+1)}, i.e. exponentially smaller in R for any N_EV≥2.

Key algorithms / experimental protocol

Problem family (§II): N_EV EVs across T discrete time-steps, R trip requests with overlap constraints, SOC bounds E_n⁰→E_n^min, grid power bounds P^min..P^max, charging cost c_tl_n,t, unserved-trip penalty λ.
Cost Hamiltonian (Eq. 13): H_C = C({l→L^z, r→R^z, q→Q^z}) + α Σ E_e + α Σ F_f, with equality/inequality penalties enforced via |·| and Heaviside Θ.
QAOA ansatz (Eq. 14): U(γ,β) = ∏_l=1..L e^-iH_X(β_l) e^-iγ_lH_C, equal-superposition initial state.
Mixer (Eq. 15): the L^x mixer plus a (L^z)² "squeeze" term — qudit-native, gives two mixing parameters per layer (3L total parameters vs. 2L for the pure-qubit case).
Optimizer: SciPy Powell, 200 iterations, M=256 shots per cost evaluation.
Benchmarks: 10 random instances per problem class; (a) bi-directional d=3, N_EV=3, T=2, R=2 (Hilbert dims 46656 qubit vs 11664 qudit); (b) uni-directional d=2, N_EV=2, T=3, R∈{2,3,4} (dims {1024,4096,16384} vs {576,1728,5184}).
Metrics: mean energy gap ΔE_mean, min energy gap ΔE_min, feasible-sample fraction f, success probability r over N_runs=10 runs.

Detailed walkthrough

The setup (§II–III) is a clean ablation: the only thing changing between treatments is how trip assignment is represented. In the binary encoding, the algorithm must learn — through penalty terms — that two r_n,i=1 entries for the same trip i (different EVs n) is forbidden; the integer encoding makes that constraint physically impossible because q_i takes a single value per trip. Concretely, the equality penalty E₁=Σ|R^z_n,iL^z_n,t| present in the qubit case is replaced by Σ|δ_{q_i,n}L^z_n,t| in the qudit case — the latter is sparser and triggers only on the single n that q_i selects.

§IV.A's bi-directional results (Fig. 4) are the headline plot. Across QAOA depths L=1..10 the qudit encoding produces lower ΔE_mean with substantially tighter inter-instance variance, and a higher success probability. Most strikingly, the qubit encoding's performance degrades with circuit depth, while the qudit encoding stays flat. The authors trace this to the 200-iteration Powell cap (Fig. 6): for the qubit Hilbert space (46656-dim), 200 iterations isn't enough — both encodings converge to similar limits when run for 1000 iterations, but at the 200 cap the qubit case is still mid-descent. So the "encoding advantage" here is partly an interaction with a fixed compute budget — exactly the realistic regime Y3 worried about for QAOA-DGMVP under shot/iteration limits.

§IV.B's uni-directional sweep over R=2,3,4 (Fig. 8 for R=3) tightens the case: the qudit encoding has more variational parameters per layer (3L vs 2L, since (L^z)² is non-trivial only for qudits with d>2), so it is structurally disadvantaged in a budgeted optimization. It still wins on success probability across all R, suggesting the dimension reduction outweighs the parameter-count penalty. As R grows the problem becomes more constrained — feasible-state fractions drop from ~20% to ~0.1% (Fig. 1) — and the qudit encoding's advantage grows accordingly: shrinking the Hilbert space matters more when feasibility is rare.

The cost-landscape visualization (Figs. 2–3) is qualitative but informative. Both landscapes are oscillatory and shot-noisy at M=256, but the qubit landscape sits at roughly 3× higher energy scale because its infeasible-configuration mass — penalized heavily — is exponentially larger. This bears directly on QAOA's signal-to-noise ratio: when most of the wavefunction sits in penalty-dominated regions, the cost gradient is dominated by infeasibility rather than by the actual objective, and Powell wastes iterations climbing out of the penalty plateau.

The runtime plot (Fig. 7) shows the qudit advantage in raw classical-simulation time, ~order-of-magnitude faster. The authors caveat that this doesn't directly translate to hardware gate counts — that would require explicit circuit compilation under realistic constraints (cited Bottarelli 2024 for constraint handling) — but it does serve as a representational-complexity proxy. The §V conclusion explicitly flags that scaling and hardware-realistic implementations are the natural next step.

The paper does not test against vanilla QAOA-with-XY-mixer, hard-constraint mixers (Hadfield-style), or CVaR-QAOA — all of which Y2 used or contributed to. The omission is acceptable for an isolated encoding study, but it leaves open the question of whether the qudit encoding still wins when combined with stronger constraint-preserving mixers, and conversely whether quasi-binary encoding (Y2's intermediate point between binary and qudit) would land somewhere in between.

Figures

Figure 1. Statistics of all the benchmark problem instances as a function of the number of trips for the two encodings — left panel from the paper's Fig. 1: relative number of feasible solutions. The problems considered are highly constrained with feasible fractions of ~0.1%–20%, decreasing with R.

Figure 2. Cost function landscape for an L=1 layer QAOA as function of variational parameters β and γ for a bi-directional benchmark instance, qubit trip encoding (with β₂=0). Multi-modal with overall energy scale ~3× the qudit case due to higher infeasible mass.

Figure 3. Same instance and slice as Figure 2 but for the qudit trip encoding. Multi-modal with lower energy scale; the M=256-shot noise is visible.

Figure 4. Mean energy gap ΔE_mean averaged over 10 instances vs. QAOA depth L for the bi-directional (d=3, N_EV=3, T=2, R=2) problem. Qudit encoding produces slightly better results with lower variance and is robust to L; qubit encoding degrades with L under the 200-iteration Powell cap.

Figure 5. Success probability r vs. circuit depth L for the bi-directional problem (10 instances, 10 runs each). Qudit encoding consistently above qubit; both show that increasing L doesn't help under the iteration cap.

Figure 6. Powell optimization progress (mean energy gap vs. iteration) at fixed L=3, with 1000 iterations. Both encodings converge to similar low-energy values eventually, but the qudit encoding reaches them substantially faster — explaining why the 200-iteration cap penalizes the qubit encoding disproportionately.

Figure 7. Mean simulation runtime (minutes) for one Powell optimization run with 200 iterations and M=256 shots vs. depth L, bi-directional d=3 problem. Linear in L, with qudit ~order-of-magnitude faster owing to the smaller state vector.

Figure 8. Success probability r vs. L for the uni-directional (d=2, N_EV=2, T=3) problem at R=3 trip reservations. Even with the qudit encoding's higher parameter count (3L vs. 2L), it still beats the pure-qubit case across depths.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography. The only Yuan listed is Xiao Yuan (different author) in the Cerezo et al. 2021 VQA review.

Overlap with Y1–Y6

Y2 (quasi-binary encoding, CVaR-QAOA, hard mixers, portfolio): the strongest alignment. Y2's quasi-binary encoding occupies ~2log₂(U-L+1) qubits per variable — an intermediate point between this paper's pure binary (N_EV qubits per trip) and qudit (one qudit per trip). The motivating thesis is identical: native, integer-aware encodings of constrained combinatorial variables outperform binary expansions, because they shrink the infeasible mass that QAOA otherwise has to learn to avoid via penalties. This paper extends the same idea to scheduling under SOC and grid constraints, on different hardware primitives (high-dimensional qudits) than Y2 used. A direct head-to-head — quasi-binary vs. qudit on the same EV problem, or vs. binary on a portfolio instance — would be a clean Y2 extension.
Y3 (QAOA-DGMVP portfolio, layerwise optimization, shot-noise scaling): shared concern with realistic constrained-optimization regimes and the fact that, under fixed shot/iteration budgets, the encoding (and the resulting circuit/optimizer complexity) determines whether the algorithm converges in time. Y3 found dual annealing + layerwise to be most robust; this paper uses Powell with a fixed iteration cap. The cap-induced degradation observed here is the same phenomenon Y3 worried about for QAOA-portfolio under thermal noise.
Y4 (Grover + ADMM for cardinality-constrained binary opt): tangential. Cardinality constraints are conceptually related to the one-EV-per-trip constraint (which the qudit encoding absorbs structurally), but the methods diverge — this paper sticks with variational QAOA rather than amplitude-amplification.
Y1, Y5, Y6: minimal overlap.

Recommended action for Yuan

Cite in any future Y2-extension paper. This is the cleanest 2026 statement of the encoding-matters thesis on a constrained scheduling problem; Y2's portfolio quasi-binary work and this paper's EV-fleet qudit work are sister contributions and should reference each other in the next iteration.
Run quasi-binary on the EV problem. Since both encodings here are sub-optimal in different ways — binary has too many qubits and infeasibility; qudit needs a (L^z)² mixer term that doubles the parameter count per layer — Y2's quasi-binary encoding (log₂(N_EV+1) qubits per trip) is the obvious intermediate to test. This would be a low-cost extension benchmark that strengthens Y2's positioning.
Consider co-authoring a follow-up with the Honda/Leiden team. They have engineering-relevant constrained problems, the Bottarelli-Deller qudit mixer toolkit, and the (L^z)² "squeeze" recipe that would slot directly into a Y2-style hard-mixer framework. The paper's §V explicitly calls for broader benchmarks against "industrially relevant constrained optimization problems with sparse feasibility" — a portfolio testbed would fit.