Variational Algorithms for Workflow Scheduling Problem in Gate-Based Quantum Devices

Authors

  • Julia Plewa AGH University of Science and Technology, 30-059 Krakow, Poland
  • Joanna Sieńko AGH University of Science and Technology, 30-059 Krakow, Poland
  • Katarzyna Rycerz AGH University of Science and Technology, 30-059 Krakow, Poland

DOI:

https://doi.org/10.31577/cai_2021_4_897

Keywords:

Hybrid quantum-classical algorithms, QAOA, VQE, optimization, workflow scheduling, one-hot encoding, binary encoding, domain wall encoding

Abstract

In this paper we consider the combinatorial optimization problem known as workflow scheduling. We compare three encoding schemes of varying density: one-hot, binary, and domain wall, and test their performance against two well-known hybrid quantum-classical algorithms: Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE). In an attempt to obtain the best results possible, we investigate various parameters of the algorithms and test out other state-of-the-art improvements, such as dedicated QAOA mixers. Ultimately, we prove that, despite its popularity, one-hot encoding is not always the best, and using a denser encoding scheme, such as binary or domain wall, can allow for solving larger instances of workflow scheduling. Additionally, combining the above-mentioned encodings with dedicated QAOA mixers reduces the number of infeasible solutions, leading to better results.

Downloads

Download data is not yet available.

Downloads

Published

2021-12-14

How to Cite

Plewa, J., Sieńko, J., & Rycerz, K. (2021). Variational Algorithms for Workflow Scheduling Problem in Gate-Based Quantum Devices. COMPUTING AND INFORMATICS, 40(4), 897–929. https://doi.org/10.31577/cai_2021_4_897

Issue

Section

Special Section Articles