Margarita Veshchezerova (Mocqua) will defend her thesis on Friday, December 16 at 10 am in the room C005.

The title of her thesis is Quantum algorithms for energy management.

The domain of energy management involves many combinatorial optimization problems known to be computationally hard. The emergence of quantum computers suggests new approaches for these problems. For near-future machines particularly promising are variational quantum heuristics such as QAOA that can leverage the computational power of the imperfect quantum hardware.

We explore the potential of variational quantum algorithms for optimization problems issued from the field of “smart charging” of electrical vehicles. We consider two problems inspired by real-world usecases. In the first problem, modeled asMax-K-Cut, we search to schedule a set of prioritized charges on several stations while minimizing the weighted completion time. In the second problem, modeled as Maximum Independent Set, we aim to maximize the number of satisfied charge demands on a single station while respecting the conflicts between demands. For both problems we develop an experimental protocol specifying the encoding step and the parameter optimization routine. Our numerical experiments confirm the interest of quantum heuristics for these problems as well as the quality of our experimental protocol.

In order to extend the applicability of quantum heuristics we introduce a new hybrid approach that integrates quantum routines in the classical Branch \& Price algorithm for large integer linear programs. We test this approach on a smart charging problem that is modeled as graph coloring problem. Our computational results affirm the potential of the hybrid approach while revealing the considerable dependence of the performance gain on the particular instance of the problem.

Important components of variational algorithms can be represented as ZX-diagrams. We demonstrate how the rewriting rules of ZX-calculus can be used to derive the analytical formula for the mean energy of a general Ising model in a QAOA_1 state. Furthermore, we contribute to the theoretical exploration of variational algorithms by extending the ZX-calculus with addition and differentiation of ZX-diagrams. Our inductive procedure for the addition is fully diagrammatic. For the differentiation we suggest two approaches. The first approach is inductive, it leverages our procedure for addition to explicitly represent the product rules. The second approach is resumed in two formulas that are derived from the factored form of parameterized diagrams.

KeyWords: Combinatorial optimization, quantum computing, energy management, smart charging, ZX-calculus