8 papers
Use case study: benchmarking quantum breadth-first search for maximum flow problems
Andreea-Iulia Lefterovici, Lara Lelakowski, Michael Perk
The maximum flow problem asks to find the largest possible flow from a source to a sink in a capacitated network. It arises frequently in scheduling, project selection, and as a co…
Drone Air Traffic Control: Tracking a Set of Moving Objects with Minimal Power
Chek-Manh Loi, Michael Perk, Malte Hoffmann +1
A common sensing problem is to use a set of stationary tracking locations to monitor a collection of moving devices: Given objects that need to be tracked, each following its o…
Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We consider a class of optimization problems that are fundamental to testing in modern configurable software systems, e.g., in automotive industries. In pairwise interaction sampli…
A quantum search method for quadratic and multidimensional knapsack problems
Sören Wilkening, Andreea-Iulia Lefterovici, Lennart Binkowski +5
Solving combinatorial optimization problems is a promising application area for quantum algorithms in real-world scenarios. In this work, we extend the "Quantum Tree Generator" (QT…
Beyond asymptotic scaling: Comparing functional quantum linear solvers
Andreea-Iulia Lefterovici, Michael Perk, Debora Ramacciotti +3
Solving systems of linear equations is a key subroutine in many quantum algorithms. In the last 15 years, many quantum linear solvers (QLS) have been developed, competing to achiev…
Exact Algorithms for Minimum Dilation Triangulation
Sándor P. Fekete, Phillip Keldenich, Michael Perk
We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable…