A Comparison of Quadratic and Higher-Order Representations for QAOA

Kristina Bell, Adam Lowe, Emily Coles, Nathanael Ridgway, Gillian Marshall · 2025

Read A Comparison of Quadratic and Higher-Order Representations for QAOA by Kristina Bell, Adam Lowe, Emily Coles, Nathanael Ridgway, Gillian Marshall (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20127.txt.

Introduction

Kristina Bell and four co-authors wrote this 2025 arXiv paper on quantum computing. They study the Quantum Approximate Optimisation Algorithm, a method for solving hard routing and planning problems. Most work encodes problems in quadratic form, which can demand many qubits as problems grow. The paper directly compares that encoding with a higher-order one on the same routing case.

The higher-order form gave better solution quality in their tests. It also scaled better in the number of qubits needed. Its cost was a larger number of two-qubit gates, which are slow and error-prone. A factoring trick then cut the gate depth of the higher-order version sharply. The team confirmed that gain on real IBM quantum hardware. The study gives practical guidance on when the richer encoding is worth its price.

Catalog record

CREATORKristina Bell, Adam Lowe, Emily Coles, Nathanael Ridgway, Gillian Marshall
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-20127

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Comparison of Quadratic and Higher-Order Representations for QAOA Kristina Bell, Adam Lowe, Emily Coles, Nathanael Ridgway, Gillian Marshall Abstract In this work we consider a routing problem and compare quadratic and higher-order representations using the Quantum Approximate Optimisation Algorithm (QAOA). The majority of works investigating QAOA use quadratic Hamiltonians to represent the considered problems, which can lead to poor scaling in qubit requirements. We address the gap of direct comparisons between quadratic and higher-order forms through an investigation into two distinct formulations of the same use case. We find that the higher-order form yields better solution quality and scales better in terms of numbers of qubits, but requires more two-qubit gates. We additionally consider a factoring method to reduce the gate depth of the higher-order version, which achieves a significant reduction in the number of two-qubit gates when run on real IBM hardware. 1 Introduction A key field in which quantum computing is theorised to have advantages over classical computing, is in combinatorial optimisation. This class of problems is often NP-hard or even NP-complete, making it intractable on classical computers for large problem sizes. Furthermore, many industry problems fall into this category, including routing [ 1 , 2 , 3 ] , scheduling [ 4 ] , and packing type problems [ 5 ] , giving it broad applicability. A popular way of representing combinatorial optimisation problems for quantum computers is as a Quadratic Unconstrained Binary Optimisation (QUBO) model [ 6 ] , which is equivalent to the quadratic Ising model [ 7 ] . QUBOs are compatible with both quantum annealing and the gate-based quantum computing paradigm, making them highly versatile [ 8 , 9 ] . The QUBO model can be extended to a Higher-Order Unconstrained Binary Optimisation (HUBO) model 1 1 1 HUBOs are sometimes called HOBOs or PUBOs in the literature. [ 10 ] , which, while being fully compatible with the standard gate-based algorithms, has been studied much less than QUBOs. One category of combinatorial optimisation problems that is particularly interesting is routing problems. There are a variety of different types of routing problem that have been considered as QUBOs, such as the Vehicle Routing Problem with Time Windows (VRPTW) [ 1 ] , the ride pooling problem (RPP) [ 2 ] , and the Travelling Salesperson Problem (TSP) [ 3 ] . They present an interesting application since not only do we need to consider the graph structure of the problem, but additionally there is often a timing element that adds an extra dimension to consider. This can lead to very poor scaling in the number of qubits required to encode the problem, motivating the use of HUBOs for a representation with better scaling. There has been some exploration of HUBOs for routing problems, mainly for TSP [ 11 , 12 ] , which this work builds on. In this work, we compare a QUBO and HUBO representation for a routing problem, inspired by a real problem, involving traversing a graph collecting assets, with an overall goal of reaching an end point within a set time limit. We call this problem the Asset Retrieval Problem (ARP). We consider the qubit scaling of both formulations, as well as the gate depth and two-qubit gate count of the naive gate implementation, through experimentation on IBM hardware. We run the two approaches on several small example problems to understand the solution quality and thus analyse which approach is more appropriate for this problem, under current hardware constraints. Within gate-based quantum computing, the most common algorithm for solving QUBOs is the Quantum Approximate Optimisation Algorithm (QAOA) [ 10 ] . QAOA is a hybrid quantum-classical algorithm that is feasible for running on near-term quantum devices and shows promise for demonstrating quantum advantage in the future [ 13 ] . It works by constructing a quantum ansatz that alternates cost and mixer Hamiltonians to form an approximation of the problem. A classical optimiser is then used to update the parameters of the cost and mixer Hamiltonians to reach the minimum energy state, which is then the problem solution (where problems are minimisations by convention). There has been much research aimed at understanding QAOA and increasing its utility [ 14 ] , prompting the development of variants such as Recursive QAOA (R-QAOA) [ 15 ] that runs QAOA recursively, fixing a subset of parameters at a time, and Warm-Start QAOA [ 16 ] that involves solving a relaxed problem and using that solution as the initial starting state of QAOA. Additionally, newer algorithms have started to emerge that adapt the QAOA model to mitigate some of its limitations. For example, the Quantum Alternating Operator Ansatz (QAOA+ for this paper, although often just QAOA) [ 17 ] uses the same principle of the QAOA ansatz construction, but allows for more customisable mixers. This means, for example, that a constraint can be encoded directly into the mixer, theoretically restricting the search space to the feasible subspace of that constraint. Unlike quantum annealing [ 18 ] , QAOA, and its variants, are not limited to quadratic-only problems and are able to support higher-order terms. Despite this, there has been limited research directly comparing QUBO and HUBO inputs to QAOA. There has been some work done on constructing HUBOs for specific problems [ 11 , 12 , 19 , 20 , 21 , 22 ] , but this is often done in isolation, or with restrictions. For purely HUBO exploration, there have been investigations aimed at understanding how QAOA [ 23 ] and QAOA+ [ 24 ] behave, particularly in relation to quantum annealing [ 23 , 25 ] , but a direct comparison with QUBOs is often not attempted. In cases where both a QUBO and HUBO is constructed, this is often done through either converting the QUBO to a HUBO via converting one-hot encoding of variables to binary encoding [ 19 , 26 ] , or by mapping the HUBO to a QUBO via quadratization [ 22 , 27 , 28 , 29 ] . This leads to situations where one encoding has better scaling, both in terms of qubit count and circuit depth, and where the other resulting encoding may not be in its most efficient form. Consequently, there is still limited understanding of how QUBO and HUBO formulations compare when neither is a more obvious choice. Since a HUBO can support higher-order terms, it has the potential to be able to represent problems more compactly, as can be seen in [ 11 , 20 , 22 ] . However, in general, this can come at the cost of requiring more two-qubit gates, since higher-order terms involve more inter-connected qubits, and thus multi-controlled gates that need to be decomposed into two-qubit gates to fit onto current quantum computers. This restriction to at most two-qubit gates may change in the future, with research suggesting ways of implementing higher order gates in various paradigms [ 30 , 31 , 32 ] . However, in the current Near-Term Intermediate Scale (NISQ) era, minimising the number of two-qubit gates remains highly important, since they are a significant contributor of noise to the system, and can thus be an influential source of errors. Thus, the

Read the complete text