Abstract Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.
Abstract Quantum annealing aims at solving optimization problems of practical relevance using quantum-computing hardware. Problems of interest are typically formulated in terms of quadratic unconstrained binary optimization (QUBO) Hamiltonians. However, many optimization problems are much more naturally formulated in terms of polynomial unconstrained binary optimization (PUBO) functions of higher order. As we show with various problem examples, leveraging the PUBO formulation can bring considerable savings in terms of required number of qubits. Moreover, in numerical benchmarks for the paradigmatic 3-SAT problem, we find scenarios where the scaling of the minimum energy gap during the optimization sweep differs significantly, suggesting the possibility of an exponentially faster annealing time when using the PUBO as compared to the QUBO formulation. This advantage persists even when considering the overhead caused by the higher-order interactions necessary for PUBO cost Hamiltonians. As an interesting side effect, the analysis on minimum energy gaps of different 3-SAT instance generators reveals different degrees of hardness, which will be of interest also for classical benchmark calculations. Our findings show a promising path to improving the resource efficiency and sweeping speed of quantum annealing protocols on both analog and digital platforms, which are important prerequisites when aiming at solving larger optimization problems with relevance to industry.
Ising machines, including quantum annealing machines, are promising next-generation computers for combinatorial optimization problems. However, due to hardware limitations, most Ising-type hardware can only solve objective functions expressed in linear or quadratic terms of binary variables. Therefore, problems with higher-order terms require an order-reduction process, which increases the number of variables and constraints and may degrade solution quality. In this study, we evaluate the effectiveness of directly solving such problems without order reduction by using a high-performance simulated annealing-based optimization solver capable of handling polynomial unconstrained binary optimization (PUBO) formulations. We compare its performance against a conventional quadratic unconstrained binary optimization (QUBO) solver on the same hardware platform. As benchmarks, we use the low autocorrelation binary sequence (LABS) problem and the vehicle routing problem with distance balancing, both of which naturally include higher-order interactions. Results show that the PUBO solver consistently achieves superior solution quality and stability compared to its QUBO counterpart, while maintaining comparable computational time and requiring no order-reduction compilation indicating potential advantages of directly handling higher-order terms in practical optimization problems.
Quantum computing provides powerful algorithmic tools that have been shown to outperform established classical solvers in specific optimization tasks. A core step in solving optimization problems with known quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) is the problem formulation. While quantum optimization has historically centered around Quadratic Unconstrained Optimization (QUBO) problems, recent studies show, that many combinatorial problems such as the TSP can be solved more efficiently in their native Polynomial Unconstrained Optimization (PUBO) forms. As many optimization problems in practice also contain continuous variables, our contribution investigates the performance of the QAOA in solving continuous optimization problems when using PUBO and QUBO formulations. Our extensive evaluation on suitable benchmark functions, shows that PUBO formulations generally yield better results, while requiring less qubits. As the multi-qubit interactions needed for the PUBO variant have to be decomposed using the hardware gates available, i.e., currently single- and two-qubit gates, the circuit depth of the PUBO approach outscales its QUBO alternative roughly linearly in the order of the objective function. However, incorporating the planned addition of native multi-qubit gates such as the global Mølmer-Sørenson gate, our experiments indicate that PUBO outperforms QUBO for higher order continuous optimization problems in general.
Quantum annealing is a metaheuristic method aimed at finding the global minimum of a pseudo-Boolean quadratic function. To solve a problem by a quantum annealer, it must be restated as a QUBO (quadratic unconstrained binary optimization) problem, the standard format acceptable to an annealer. However, there are many natural problems that turn out be of cubic or higher order, yet promising solutions can be obtained for many instances using quantum annealers, after converting to the QUBO format, using order reduction criteria. Accordingly, quadratization becomes a crucial preprocessing step in order to make use of present-day quantum annealing hardware that relies on coupling technology, which can only process interactions of at most degree two. A critical challenge is that quadratization methods often require many additional variables, degrading the performance of the annealers. A number of algorithmic and heuristic quadratization techniques have been proposed and used for annealing in the literature, affecting the performance of the annealers differently. We examine a number of such quadratization techniques, focusing on their efficiency, compactness, and applicability. We analyze the approaches motivated by diverse goals and highlight the transition from foundational approaches to more recent compact approaches. An evaluation of the current usage of different quadratization methods in the literature is carried out at the end of the survey. Further, we comment on the limitations on usage and show possible opportunities to enhance the performance of annealers.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
Quantum Approximate Optimization Algorithm (QAOA) is one of the most short-term promising quantum-classical algorithm to solve unconstrained combinatorial optimization problems. It alternates between the execution of a parametrized quantum circuit and a classical optimization. There are numerous levers for enhancing QAOA performances, such as the choice of quantum circuit meta-parameters or the choice of the classical optimizer. In this paper, we stress on the importance of the input problem formulation by illustrating it with the resolution of an industrial railway timetabling problem. Specifically, we present a generic method to reformulate any polynomial problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem, with a specific formulation imposing penalty terms to take binary values when the constraints are linear. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. We then conduct a numerical comparison between the PUBO with binary penalty terms and the QUBO formulations proposed on a railway timetabling problem solved with QAOA. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.