New paper on Frontiers – Flexible formulation of optimization problems
Innsbruck, 14th September 2023 – A group of physicists from ParityQC have compiled a collection of encoding- and hardware-independent methods for formulating optimization problems for quantum computers. In a paper recently published in the journal Frontiers in Quantum Science and Technology, they present an extensive library of optimization problems formulated using this generalized approach, and their various derived spin encodings. This highly valuable resource will be used in the context of ParityQC’s current and future collaborations focused on solving optimization problems.
Optimization problems are omnipresent in many fields of industry, from healthcare to finance, manufacturing to logistics, as well as in academic sectors. Many of these are so-called NP-hard problems: they are difficult to solve and not scalable on classical computers, but could have an enormous impact on our society, so there has been a growing interest in using quantum computing to solve them. The key step in this is to formulate the optimization problem in a language that quantum computers can understand, which is very challenging. Current standard approaches have substantial limitations depending on the type of optimization problem and type of hardware used. In the paper “Encoding-Independent Optimization Problem Formulation for Quantum Computing”, a group of physicists from ParityQC have now presented a framework for formulating optimization problems for quantum computers, that is both encoding- and hardware-independent. The paper has been published in the journal Frontiers in Quantum Science and Technology.
In the paper, the authors (Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler, Wolfgang Lechner) present the general method and outline a comprehensive library of optimization problems with their various derived spin encodings. The physicists identified a set of common building blocks for the formulation of optimization problems, leading to a fully automatic construction of Hamiltonians for arbitrary discrete optimization problems. This new method is both encoding-independent and hardware-independent, which represents an important contribution to this field, as current standard approaches have limitations depending on the type of optimization problem and type of hardware used. The method also allows a freedom in the problem formulation, which is a key step for tailoring optimal spin Hamiltonians for different hardware platforms.
The more general method and corresponding library of problems simplify the Hamiltonian formulation beyond the usual techniques of QUBO and one-hot encoding. With this new method, non-binary interaction terms and hard constraints can be handled using the ParityQC Architecture, which does not rely on the QUBO formulation and allows a wide number of options for formulating Hamiltonians. In the paper, common problems in the literature are revisited and reformulated using encoding-independent formulations, meaning that they can be encoded trivially using any spin encoding. The authors also identify and separate from the cost function the possible constraints of the problem, making it easy to explore their dynamic implementation.
The paper presents important findings that have the potential to improve and streamline the formulation of optimization problems for quantum computing. Firstly, it shows that obtaining the spin Hamiltonian for an optimization problem involves several choices, meaning that one can improve the performance of a quantum algorithm by making the best choice. Secondly, it shows that it is possible to build an efficient construction kit of common, reoccurring building blocks for formulating optimization problems, paving the way to an automated preprocessing algorithms picking the best choices in the construction kit. And finally, the authors show the importance of having a procedure for tailoring a problem to any given hardware platform, the hardware-agnostic approach presented being a first key step towards this direction.
Publication:
Encoding-Independent Optimization Problem Formulation for Quantum Computing. Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler, Wolfgang Lechner. Frontiers in Quantum Science and Technology (2023)