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 that are eventually supposed to beat any purely classical alternatives. While in-principle advantages for solution quality or runtime are expected for many approaches, substantial challenges remain: Non-functional properties like runtime or solution quality of many approaches are not fully understood, and need to be explored empirically. This makes it unclear which approach is best suited for a given problem. Accurately predicting behaviour of quantum-classical algorithms opens possibilities for software abstraction layers, which can automate decision-making for algorithm selection and parametrisation. While such techniques find frequent use in classical high-performance computing, they are still mostly absent from quantum toolchains. We present a methodology to perform algorithm selection based on desirable non-functional requirements. This simplifies decision-making processes for users. Based on annotations at the source code level, our framework traces key characteristics of quantum-classical 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 quantum-classical 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 effort. We argue that our methodology generalises to problems beyond combinatorial optimisation, such as Hamiltonian simulation, and lays a foundation for integrated software layers for quantum design automation.

To be published at QCE25

References in corpus (30)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Simulation
• Ising formulations of many NP problems
• A Quantum Engineer's Guide to Superconducting Qubits
• Adiabatic Quantum Computing
• Hamiltonian Simulation by Qubitization
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• $XY$-mixers: analytical and numerical results for QAOA
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Modelling and Simulating the Noisy Behaviour of Near-term Quantum Computers
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• A quantum-classical cloud platform optimized for variational hybrid algorithms
• Digital-Analog Quantum Simulations with Superconducting Circuits
• A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Characterizing local noise in QAOA circuits
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Quantum Annealing-Based Software Components: An Experimental Case Study with SAT Solving
• Quantum Computing Techniques for Multi-Knapsack Problems
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Analogue Quantum Simulation: A New Instrument for Scientific Understanding
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Approximating under the Influence of Quantum Noise and Compute Power
• Make Some Noise! Measuring Noise Model Quality in Real-World Quantum Software
• Greedy MAXCUT Algorithms and their Information Content