Solving workflow scheduling problems with QUBO modeling


Intro

Terra Quantum pioneers a range of quantum technologies with the mission of leading the quantum revolution from meaningful solutions today to a more prosperous future tomorrow. The development of quantum technologies will disrupt many industries, creating new opportunities and at the same time, new risks. Currently, there is considerable concern about the nefarious use of quantum technologies for illegal hacking. It is expected that in the near future, quantum computers will develop to such a point that they pose a significant threat to our current information security protocols, allowing hackers access to sensitive information globally by brute-forcing security problems previously uncrackable by classical computers. While companies in the financial and healthcare spaces are especially concerned with protecting confidential and sensitive information, all industries are aware of the financial losses and reputational damages that result from data breaches and should be proactive in addressing this threat. This business white paper discusses the nature of the coming threat and details our comprehensive offerings and solutions for secure communication in the quantum age. These include Terra Quantum’s novel Quantum Key Distribution (QKD) protocol, Quantum Random Number Generators (QRNGs) and Post-Quantum Library.


Abstract

In this paper we investigate the workflow scheduling problem, a known NP-hard class of scheduling problems. We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms. We develop a novel QUBO to represent our scheduling problem and show how the QUBO complexity depends on the input problem. We derive and present a decomposition method for this specific application to mitigate this complexity and demonstrate the effectiveness of the approach..

Keywords: terra quantum; QUBO


About the Author

Terra Quantum is committed to building quantum technology for a better future, breaking down the barriers between science and industry, and laying the foundations of a real quantum tech ecosystem and value chain.

Terra Quantum value the intrinsic connection between our planet and quantum technologies, putting sustainability at the core of our business and culture.

Standing at the very beginning of this revolution Terra Quantum feels the excitement – and responsibility – for the applications and tools they are developing.