Hybrid Combinatorial Optimization using Noisy Intermediate-Scale Quantum (NISQ) computers
Master’s Thesis, Research Project
Abstract
Quantum computers, as they are available today, are so-called Noisy Intermediate-Scale Quantum machines (which includes quantum annealers). When it comes to well-known hard to solve combinatorial optimization problems from computer science in particular, such computers are unfit for problem instances of relevant size due to memory and noise constraints.
We work on a classical-quantum process, where we combine algorithms for classical and quantum computers that are efficient in their respective domain. That way we can solve the NP-hard problem kernel on a quantum machine, while pre- and postprocessing, problem partitioning and scheduling is performed classically.
References
- M. A. Nielsen, I. L. Chuang: Quantum Computation and Quantum Information
- F. Leymann, J. Barzen: The Bitter Truth About Quantum Algorithms in the NISQ Era
Requirements
- Basics: Python, Git
- Very strong foundations in linear algebra
- Very strong foundations in algorithms and theoretical computer science
- Basic understanding of how quantum computers operate (see References)