Predict and Conquer: Navigating Algorithm Trade-Offs with Quantum Design Automation

Abstract

Combining quantum computers with classical compute power has become a standard means for developing algorithms and heuristics that are, eventually, supposed to beat any purely classical alternatives. While in-principle advantages for solution quality or runtime are expected for increasingly many approaches, substantial challenges remain: Non-functional properties like runtime or solution quality of many suggested approaches are not yet fully understood, and need to be explored empirically. This, in turn, makes it unclear which approach is best suited for a given problem. Accurately predicting behaviour and properties of quantum-classical algorithms opens possibilities for software abstraction layers, which in turn can automate decisionmaking for algorithm selection and parametrisation. While such techniques find frequent use in classical high-performance computing, they are still mostly absent from quantum software toolchains. In this paper, we present a methodology (accompanied by a reproducible reference implementation) to perform algorithm selection based on desirable non-functional requirements. This greatly simplifies decision-making processes for end users. Based on meta-information annotations at the source code level, our framework traces key characteristics of quantum-classical heuristics and algorithms, and uses this information to predict the most suitable approach and its parameters for given computational challenges and their non-functional requirements. As combinatorial optimisation is a very extensively studied aspect of quantumclassical systems, we perform a comprehensive case study based on numerical simulations of algorithmic approaches to implement and validate our ideas. We develop statistical models to quantify the influence of various factors on non-functional properties, and establish predictions for optimal algorithmic choices without manual user effort. We argue that our methodology generalises to problem classes beyond combinatorial optimisation, such as Hamiltonian optimisation, and lays a foundation for integrated software layers for quantum design automation.