Comparison of algorithms and encoding schemes for workflow scheduling

The talk will be given by

Julia Plewa, AGH graduate & BNP Paribas

Joanna Sieńko, AGH graduate

Abstract

In this presentation, we will consider the trade-off between space efficiency and circuit complexity in the context of a specific optimization problem – workflow scheduling. We will compare three encoding schemes of varying density: one-hot, binary [2], and domain wall [1], and test their performance against two hybrid quantum-classical algorithms: QAOA and VQE. We will also discuss the various parameters of the algorithms and other state-of-the-art improvements, such as dedicated QAOA mixers. We will present the results of our experiments that were run using the Qiskit simulator [3]. Ultimately, we will prove that one-hot encoding is not always the best, and that using a denser encoding scheme, such as binary or domain wall, can allow for encoding larger problems and sometimes even for better results.

References

[1] Chancellor N.: Domain wall encoding of discrete variables for quantum annealing and QAOA. In: Quantum Science and Technology, vol. 4(4), p. 045004, 2019. URL http://dx.doi.org/10.1088/2058-9565/ab33c2.

[2] Glos A., Krawiec A., Zimborás Z.: Space-efficient binary optimization for variational computing. arXiv:quant-ph/[masked], 2020.

[3] Plewa J., Sienko J.: Hybrid algorithms for workflow scheduling problem in quantum devices based on gate model. Master’s thesis supervised by Katarzyna Rycerz, PhD, Institute of Computer Sciece, AGH University of Science and Technology, Krakow, September 2021. URL dice.cyfronet.pl/publications/source/MSc_theses/JPlewa_JSienko_msc.pdf.