@article{KruegerMauerer, author = {Kr{\"u}ger, Tom and Mauerer, Wolfgang}, title = {Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation}, series = {Quantum}, volume = {9}, journal = {Quantum}, publisher = {Verein zur F{\"o}rderung des Open Access Publizierens in den Quantenwissenschaften}, doi = {10.22331/q-2025-11-06-1903}, pages = {32}, abstract = {The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.}, language = {de} } @unpublished{KruegerMauerer, author = {Kr{\"u}ger, Tom and Mauerer, Wolfgang}, title = {Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation}, pages = {20}, abstract = {The Quantum Approximate Optimisation Algorithm (qaoa) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While qaoa targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the qaoa optimisation landscape from solution space structures, we derive a new algorithmic variant: Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth qaoa for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in qaoa. By ensuring generality, we link existing empirical observations on qaoa parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.}, language = {en} } @inproceedings{GreiweKruegerMauerer, author = {Greiwe, Felix and Kr{\"u}ger, Tom and Mauerer, Wolfgang}, title = {Effects of Imperfections on Quantum Algorithms}, series = {2023 IEEE International Conference on Quantum Software (QSW), Chicago, IL, USA, 02-08 July 2023}, booktitle = {2023 IEEE International Conference on Quantum Software (QSW), Chicago, IL, USA, 02-08 July 2023}, publisher = {IEEE}, doi = {10.1109/QSW59989.2023.00014}, pages = {31 -- 42}, abstract = {Quantum computers promise considerable speedups over classical approaches, which has raised interest from many disciplines. Since any currently available implementations suffer from noise and imperfections, achieving concrete speedups for meaningful problem sizes remains a major challenge. Yet, imperfections and noise may remain present in quantum computing for a long while. Such limitations play no role in classical software computing, and software engineers are typically not well accustomed to considering such imperfections, albeit they substantially influence core properties of software and systems. In this paper, we show how to model imperfections with an approach tailored to (quantum) software engineers. We intuitively illustrate, using numerical simulations, how imperfections influence core properties of quantum algorithms on NISQ systems, and show possible options for tailoring future NISQ machines to improve system performance in a co-design approach. Our results are obtained from a software framework that we provide in form of an easy-to-use reproduction package. It does not require computer scientists to acquire deep physical knowledge on noise, yet provide tangible and intuitively accessible means of interpreting the influence of noise on common software quality and performance indicators.}, language = {en} } @inproceedings{KruegerMauerer, author = {Kr{\"u}ger, Tom and Mauerer, Wolfgang}, title = {Quantum Annealing-Based Software Components}, series = {Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops (ICSE'20): Seoul Republic of Korea 27.06.2020 - 19.07.2020}, booktitle = {Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops (ICSE'20): Seoul Republic of Korea 27.06.2020 - 19.07.2020}, publisher = {Association for Computing Machinery}, address = {New York, NY}, isbn = {9781450379632}, doi = {10.1145/3387940.3391472}, pages = {445 -- 450}, abstract = {Quantum computers have the potential of solving problems more efficiently than classical computers. While first commercial prototypes have become available, the performance of such machines in practical application is still subject to exploration. Quantum computers will not entirely replace classical machines, but serve as accelerators for specific problems. This necessitates integrating quantum computational primitives into existing applications. In this paper, we perform a case study on how to augment existing software with quantum computational primitives for the Boolean satisfiability problem (SAT) implemented using a quantum annealer (QA). We discuss relevant quality measures for quantum components, and show that mathematically equivalent, but structurally different ways of transforming SAT to a QA can lead to substantial differences regarding these qualities. We argue that engineers need to be aware that (and which) details, although they may be less relevant in traditional software engineering, require considerable attention in quantum computing.}, language = {en} }