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

This paper demonstrates that using qudit (integer) encodings instead of conventional qubit (binary) encodings for variational quantum algorithms significantly reduces resource requirements and simulation runtime while achieving comparable or superior optimization performance on realistic electric vehicle fleet management problems.

The Gist

Imagine you are the manager of a small fleet of electric taxis. You have two big jobs to do every day:

1. Charge the cars: You need to decide when to plug them in (to charge) or let them give power back to the grid (discharge) to save money.
2. Assign trips: You need to decide which car takes which customer's trip.

This is a puzzle. If you assign the wrong car to a trip, or charge it at the wrong time, you might run out of battery or break the rules of the power grid. Solving this puzzle perfectly is very hard for computers, especially when you add the rules of quantum physics to the mix.

This paper is a report from researchers at Honda Research Institute and Leiden University who asked a simple question: "Does it matter how we translate this puzzle into the language of a quantum computer?"

They tested two different "languages" (encodings) to see which one helps the quantum computer solve the problem faster and better.

The Two Languages: "Qubits" vs. "Qudits"

To understand their experiment, imagine you are trying to describe a list of trips to a robot.

1. The Old Way: The "Qubit" Language (The Binary Switch)
Think of a light switch. It's either ON or OFF.

• In this method, the researchers used a separate light switch for every single possible pairing of a car and a trip.
• If you have 3 cars and 2 trips, you need 6 switches. If a switch is ON, it means "Car 1 takes Trip A." If it's OFF, it doesn't.
• The Problem: This creates a massive, messy room full of switches. The computer has to check millions of combinations, most of which are nonsense (like "Car 1 takes Trip A" AND "Car 2 takes Trip A" at the same time). The computer wastes time checking these impossible scenarios.

2. The New Way: The "Qudit" Language (The Multi-Position Dial)
Think of a dimmer switch or a dial that can point to many numbers, not just 0 or 1.

• In this method, instead of using many switches, they used one dial for each trip.
• If the dial points to "1," it means "Car 1 takes this trip." If it points to "2," it means "Car 2." If it points to "0," it means "No car takes this trip."
• The Benefit: This is much more direct. You don't need to check if two cars are fighting over the same trip; the dial physically can't point to two cars at once. It shrinks the "room" the computer has to search through.

The Experiment: A Race Against Time

The researchers ran a simulation of their quantum computer (a "state-vector simulation," which is like a perfect, noise-free practice run) to see how these two languages performed. They set up many random scenarios with different numbers of cars, trips, and time slots.

Here is what they found:

• The Search Space Shrank: The "Qudit" (dial) method reduced the size of the search space exponentially. Imagine trying to find a needle in a haystack. The Qubit method gave you a haystack the size of a mountain. The Qudit method gave you a haystack the size of a shoebox.
• Faster Results: Because the "shoebox" was so much smaller, the simulation ran much faster. The Qudit method took significantly less time to find a solution.
• Better Quality: Surprisingly, the Qudit method didn't just run faster; it found better or equal solutions. The solutions it found were closer to the perfect answer, and the results were more consistent (less "jittery" or random).
• The "Deep" Problem: They tried making the quantum computer "think" harder by adding more layers (depth) to the algorithm. Usually, thinking harder helps. But here, the Qubit method got confused and performed worse as it got deeper, likely because it had too many variables to juggle and the computer stopped optimizing too early. The Qudit method stayed steady and robust, even as the problem got more complex.

The Bottom Line

The paper concludes that for problems involving scheduling and assigning things (like electric cars to trips), using the Qudit (dial) approach is a much smarter choice than the traditional Qubit (switch) approach.

It's like packing for a trip:

• Qubit: You bring a suitcase full of individual socks, one by one, and try to fit them in a box. You waste space and time.
• Qudit: You bring a single, neatly folded bundle of socks. It fits perfectly, takes up less space, and you can grab it instantly.

The researchers suggest that for real-world scheduling problems with many options, using these "multi-valued" quantum dials (qudits) is a practical and efficient path forward, saving both time and computing power.

Technical Summary

Technical Summary: Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

Problem Statement
The paper addresses the constrained optimization problem of managing a fleet of electric vehicles (EVs). This involves two coupled decision processes: scheduling the bi-directional (or uni-directional) charging of $N_{EV}$ vehicles over a discrete time horizon $T$, and assigning these vehicles to $R$ customer trip requests. The objective is to minimize charging costs while satisfying strict operational constraints, including battery state-of-charge (SOC) limits, trip overlaps, grid power bounds, and the requirement that a vehicle cannot charge while serving a trip.

The core challenge investigated is how the choice of encoding for the trip-assignment variables affects the resource requirements and optimization behavior of Variational Quantum Algorithms (VQAs), specifically the Quantum Approximate Optimization Algorithm (QAOA). The authors compare two distinct representations:

1. Binary (Qubit) Encoding: Uses one binary variable ($r_{n,i} \in \{0,1\}$) for every EV-trip pair. This requires explicit constraints to ensure each trip is served by at most one EV and that overlapping trips are not assigned to the same vehicle.
2. Integer (Qudit) Encoding: Uses one integer variable ($q_i \in \{0, \dots, N_{EV}\}$) per trip, where the value directly specifies the assigned EV (or an unserved state). This encoding inherently satisfies the "one EV per trip" constraint, removing the need for explicit binary constraints on assignment.

Methodology
The authors formulate the problem using QAOA. Both encodings utilize qudit variables for the charging power levels ($l_{n,t}$), but differ in the computational basis for trip assignments.

• Hamiltonian Construction: The classical cost functions and constraints are promoted to diagonal operators in the computational basis. Constraints (e.g., SOC limits, no charging during trips) are enforced via non-linear penalty terms added to the cost Hamiltonian.
• Simulation: The study employs exact state-vector simulations to benchmark the algorithms. To mimic realistic hardware limitations, the expectation values of the cost function are estimated using a finite number of measurement shots ($M=256$) rather than exact calculation.
• Optimization: A classical optimizer (Powell method) minimizes the cost function by varying the QAOA parameters ($\gamma, \beta$). The study runs 10 random instances for each problem class, with 10 optimization runs per instance, using a fixed budget of 200 internal optimizer iterations.
• Test Cases: Two problem classes are analyzed:
  • Bi-directional charging: 3 EVs, 2 time steps, 2 trips, 3 charging levels ($d=3$).
  • Uni-directional charging: 2 EVs, 3 time steps, varying trips ($R=2,3,4$), 2 charging levels ($d=2$).

Key Contributions and Results
The paper provides a comparative analysis of the two encodings across several metrics:

1. Hilbert Space Reduction: The integer (qudit) encoding exponentially reduces the dimension of the Hilbert space compared to the binary (qubit) encoding. The ratio of configurations is given by $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$. For the tested instances, this results in a search space reduction from tens of thousands to a few thousand states.
2. Optimization Performance:
   • Mean Energy Gap: The qudit encoding consistently achieves a mean energy gap comparable to or slightly better than the qubit encoding.
   • Variance: The qudit results exhibit significantly lower variance in energy gaps across different runs.
   • Success Probability: The fraction of runs finding the global optimum and the fraction of feasible states sampled are generally higher or more stable for the qudit encoding.
3. Runtime and Convergence:
   • Simulation Runtime: Due to the smaller Hilbert space, the qudit encoding requires substantially shorter simulation runtimes (linear in circuit depth but with a much smaller coefficient).
   • Layer Depth Behavior: As the QAOA depth ($L$) increases, the performance of the qubit encoding degrades more significantly than the qudit encoding. The authors attribute this to the increased number of variational parameters making the optimization landscape harder to navigate within a fixed iteration budget. The qudit encoding is more robust to premature termination of the classical optimizer.
4. Cost Landscape: The cost landscapes for the qubit encoding show a larger energy scale and higher oscillation frequencies due to the larger fraction of infeasible states (which incur high penalty costs) compared to the qudit encoding.

Significance and Claims
The paper claims that qudit-native encodings offer a practical route for solving integer and multi-valued scheduling problems in variational quantum optimization. The primary significance lies in demonstrating that representing discrete multi-valued variables directly via qudits, rather than expanding them into binary qubits, yields:

• Exponential resource savings in the Hilbert space dimension.
• Reduced computational overhead in classical simulations (serving as a proxy for representational complexity).
• Improved robustness in the optimization process, particularly in highly constrained regimes where feasible solutions are sparse.

The authors note that while the study uses state-vector simulations, the compact representation suggests potential benefits for hardware implementations by reducing the overhead of constraint handling and logical variable mapping. They conclude that for constrained scheduling problems, the qudit encoding is a superior choice that maintains or improves optimization performance while drastically reducing resource requirements. The paper modestly suggests that future work should test these trends on larger instances and on actual quantum hardware to verify if the advantages persist beyond simulation.