Department of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
•    understand and discuss current problems in quantum informatics,
•    discuss new quantum computing technologies,
•    exchange ideas and research results,
•    integrate information across different research teams,
•    build a community around quantum informatics.
Venue:  via Internet, Webex

Tuesday, 5th of May, 2020, 9:30-11:00

Dawid Tomasiewicz, Department of Computer Science, AGH Krakow

Topic: Foundations for Workflow Application Scheduling on D-Wave System



Many scientific processes and applications can be represented in the standardized form of workflows [1]. One of the key challenges related to managing and executing workflows is scheduling. As an NP-hard problem with exponential complexity it imposes limitations on the size of practically solvable problems.

This talk will present a solution to the challenge of scheduling workflow applications with the help of the D-Wave quantum annealer, which includes transformation into a Quadratic Unconstrained Binary Optimization (QUBO) problem and discussion of experimental results, as well as possible applications of the solution [2]. Problem instances presented are small enough to fit into the annealer’s architecture. The talk will also discuss limitations of such an approach, the existing solutions (e.g. [3]) and point the possible future work.


[1] Deelman, E., Gannon, D., Shields, M., Taylor, I.: Workflows and e-science: An overview of workflow system features and capabilities. Future Generation Computer Systems 25 (5), 528–540 (2009)

[2] Tomasiewicz, D., Pawlik, M., Malawski, M., Rycerz, K.: Foundations for Workflow Application Scheduling on D-Wave System (2020) accepted for ICCS 2020

[3] Venturelli, D., M.D.J.J., Rojo, G.: Quantum Annealing Implementation of JobShop Scheduling. arXiv:1506.08479 (2015)



  • 4 years, 1 month ago