Quantum approximate optimization algorithm for qudit systems

A frequent starting point of quantum computation platforms is the two-state quantum system, i.e., the qubit. However, in the context of integer optimization problems, relevant to scheduling optimization and operations research, it is often more resource-efficient to employ quantum systems with more than two basis states, so-called qudits. Here, we discuss the quantum approximate optimization algorithm (QAOA) for qudit systems. We illustrate how the QAOA can be used to formulate a variety of integer optimization problems such as graph coloring problems or electric vehicle charging optimization. In addition, we comment on the implementation of constraints and describe three methods to include these in a quantum circuit of a QAOA by penalty contributions to the cost Hamiltonian, conditional gates using ancilla qubits, and a dynamical decoupling strategy. Finally, as a showcase of qudit-based QAOA, we present numerical results for a charging optimization problem mapped onto a maximum-$k$-graph-coloring problem. Our work illustrates the flexibility of qudit systems to solve integer optimization problems.

Figure 1

QAOA for qudits. General structure of the QAOA, consisting of preparation of the initial state $|{\psi }_0\rangle$, which is the equal superposition of all basis states; application of the alternating QAOA circuit [consisting of phase separation gate $U_C\left(\mathit{\gamma }\right)$ and mixing gate $U_M\left(\mathit{\beta }\right)$]; and measurement together with subsequent classical optimization of the variational parameters with respect to the expectation value of the cost Hamiltonian.

Figure 2

QAOA with conditional gates for constraints: In order to enforce constraints, one performs a conditional gate $U_g$ and measures the ancilla qubit $|0\rangle$. If the measurement returns the value 0, the constraint is fulfilled, and we do not change the cost function. If the measurement yields the value 1, then the constraint is violated, and we forward the measurement result to the cost function, use the Hamiltonian $H_{\tilde{C}}$, and penalize the violation of the constraint.

Figure 3

Schematic representation of the simplified EV charging problem. $N$ cars need to be assigned to $k$ charging stations, where each car needs to be placed at a charging station for a given time period. Here, we consider $N=5$ cars and $k=3$ charging stations. No two cars with overlapping charging periods can be assigned to the same charging station, which can be formulated as a conflict graph where cars with overlapping time slots are connected by an edge. If we denote each charging station by a different color, the charging station assignment can be formulated as a coloring problem of the conflict graph. Furthermore, we assume that each charging station incurs different costs, which are dimensionless numbers.

Figure 4

Probability distributions of the optimized state and optimal solution graphs. Probability distribution of representative final QAOA states for a $N=6$ graph without coloring cost [(a) and (c)] and with coloring cost $(c_{-1},c_0,c_1)=(0,1,2)$ [(b) and (d)]. (a) and (b) depict results for shallow circuits with depth $p=1$, while (c) and (d) show results for depth $p=5$. The red dashed lines indicate the 12 (1) optimal solutions without (with) coloring cost. The insets in (c) and (d) show the energy spectra of the respective Hamiltonian in arbitrary units. (e) Candidate solutions for the simplified charging problem, where the colors red, green, and blue have cost $c_{-1}, c_0$, and $c_1$, respectively. Without coloring cost, all shown graphs are optimal solutions, and the additional eight optimal solutions can be generated by pairwise color exchange. With coloring cost $(c_{-1},c_0,c_1)=(0,1,2)$, only the leftmost graph of (e) is optimal.

Figure 5

Optimality gap and cost function landscape. Optimality gap of the final QAOA states for a graph with $N=6$ (a) without coloring cost, i.e., $(c_{-1},c_0,c_1)=(0,0,0)$, and (b) with coloring cost $(c_{-1},c_0,c_1)=(0,1,2)$, as a function of the circuit depth $p$ and for the two optimizers L-BFGS (orange) and CMA-ES (blue). The plots show the best result for each of the 50 (300) CMA-ES (L-BFGS) runs. (c) and (d) show the cost function landscape for circuit depth $p=1$ in a certain parameter region of the search space for the same $N=6$ graph without (c) and with (d) coloring cost.

Figure 6

Optimization progress. Optimality gap values of 50 CMA-ES optimization runs as a function of the internal optimization generation number for an $N=6$ graph without coloring cost and with a circuit depth of $p=1$ (a) and $p=5$ (b). Each color represents one individual optimization run with different initial values for the search parameters $\mathit{\gamma }$ and $\mathit{\beta }$.

Figure 7

Distribution of optimal solutions over several QAOA runs. Number of optimal solutions found in one QAOA optimization run for simplified charging problem instances on graphs with $N=5$ [(a) and (b)], $N=6$ [(c) and (d)], and $N=8$ [(e) and (f)] without [(a), (c), and (d)] and with [(b), (d), and (f)] charging cost. The colored bars show the number of found optimal solutions in each run, where a larger width implies a larger number of found solutions. Lines show the mean number of found solutions aggregated over all 50 and $300–600$ different optimization runs using CMA-ES and L-BFGS, respectively.

Figure 8

Job-shop scheduling. Table representation of a job schedule. The horizontal line denotes the discretized time, whereas the vertical axis denotes the machine. Filling the box corresponds to using the machine with the job $j_{n,k}$.