Polynomial Reduction Methods and their Impact on QAOA Circuits

Abstract

Abstraction layers are of paramount importance in software architecture, as they shield the higher-level formulation of payload computations from lower-level details. Since quantum computing (QC) introduces many such details that are often unaccustomed to computer scientists, an obvious desideratum is to devise appropriate abstraction layers for QC. For discrete optimisation, one such abstraction is to cast problems in quadratic unconstrained binary optimisation (QUBO) form, which is amenable to a variety of quantum approaches. However, different mathematically equivalent forms can lead to different behaviour on quantum hardware, ranging from ease of mapping onto qubits to performance scalability. In this work, we show how using higher-order problem formulations (that provide better expressivity in modelling optimisation tasks than plain QUBO formulations) and their automatic transformation into QUBO form can be used to leverage such differences to prioritise between different desired non-functional properties for quantum optimisation. Our quantitative study shows that the approach allows us to satisfy different trade-offs, and suggests various possibilities for the future construction of general-purpose abstractions and automatic generation of useful quantum circuits from high-level problem descriptions.

References in corpus (11)

• The theory of variational hybrid quantum-classical algorithms
• Adiabatic Quantum Computing
• Quantum computing with trapped ions
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Perspectives of quantum annealing: Methods and implementations
• Realization of the quantum Toffoli gate with trapped ions
• Prime factorization using quantum annealing and computational algebraic geometry
• Theory of robust multi-qubit non-adiabatic gates for trapped-ions
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Quantum Annealing-Based Software Components: An Experimental Case Study with SAT Solving
• Uncovering Instabilities in Variational-Quantum Deep Q-Networks

Cited by in corpus (5)

• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions
• Path Matters: Industrial Data Meet Quantum Optimization
• It's Quick to be Square: Fast Quadratisation for Quantum Toolchains