Formulating optimization problems for quantum computing

13/02/2023

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.

When trying to solve an optimization problem, the first step is to encode the cost function f in a Hamiltonian H and then finding the ground state of H, which corresponds to the solution of the optimization problem. Current standard approaches to formulating optimization problems on quantum computers include methods based on QUBO (Quadratic Unconstrained Binary Optimization) and one-hot encoding, which have substantial limitations depending on the type of optimization problem and type of hardware used. 

In the pre-print “Encoding-Independent Optimization Problem Formulation for Quantum Computing”, a group of physicists within ParityQC presents a novel method of formulating optimization problems for quantum computing, a method that is encoding- and hardware-independent. In the paper, the authors (Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler, Wolfgang Lechner) outline a comprehensive library of optimization problems and their various derived spin encodings. Common building blocks are identified, paving the way towards a fully automatic construction of Hamiltonians for arbitrary discrete optimization problems. The result is a spin formulation that is not limited to the QUBO paradigm. Non-binary interaction terms and hard constraints can be coped with by using the ParityQC Architecture, a paradigm for solving quantum optimization problems that does not rely on the QUBO formulation and allows a wide number of options for formulating Hamiltonians. 

The library of problems presented is intended to facilitate the Hamiltonian formulation beyond QUBO and one-hot encoding. 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 possible constraints of the problem are also identified and presented separately from the cost function, making it easy to explore the dynamic implementation of the constraints.

Among the problems presented there are the well-known clustering problem and the traveling salesperson problem. Below is the example of what a decision tree for formulation of the traveling salesperson would look like. The entire process is presented in four different blocks (Define problem, Encode variables, Replace variables and Final Hamiltonian) and the decisions taken are highlighted in green.

Overall, 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. This is a a feature rather than a burden, as it leaves room to improve the performance of quantum algorithms by making different choices. In addition, the identification of common, reoccurring building blocks allows users to develop a construction kit for the formulation of optimization problems. This paves the way to an automated preprocessing algorithm picking the best choices among the construction kit, to facilitate the search for optimally-performing quantum algorithms.  

Finding the optimal spin Hamiltonian for a given hardware platform for a quantum computer is in itself an important problem, as they are very likely to differ. It is important to have a procedure capable of tailoring a problem to any given platform, and the hardware agnostic approach presented here is a first key step towards this direction. 

Read the pre-print on arXiv.