Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2406.08889 · IEEE International Conference on Quantum Software (QSW)

Polynomial Reduction Methods and their Impact on QAOA Circuits

Lukas Schmidbauer, Karen Wintersperger, Elisabeth Lobe, Wolfgang Mauerer

Published Jul 7, 2024• 12 citations
arXivHTMLPDF

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. Based on a practically relevant use-case and a graph-theoretic analysis, we evaluate how different transformation approaches influence widely used quantum performance metrics (circuit depth, gates count, gate distribution, qubit scaling), and also consider the classical computational efforts required to perform the transformations, as they influence possibilities for achieving future quantum advantage. Furthermore, we establish more general properties and invariants of the transformation methods. 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.

DOI
10.1109/qsw62656.2024.00018

Related papers

It’s Quick to be Square: Fast Quadratisation for Quantum Toolchains

Lukas Schmidbauer, Elisabeth Lobe, Ina Schaefer +1 more

Many of the envisioned use-cases for quantum computers involve optimisation processes. While there are many algorithmic primitives to perform the required calculations, all eventually lead to quantum gates operating on quantum bits, with an order as determined by the structure of the objective function and the properties of target hardware. When the structure of the problem representation is not aligned with structure and boundary conditions of the executing hardware, various overheads degrading the computation may arise, possibly negating any possible quantum advantage. Therefore, automatic transformations of problem representations play an important role in quantum computing when descriptions (semi-)targeted at humans must be cast into forms that can be “executed” on quantum computers. Mathematically equivalent formulations are known to result in substantially different non-functional properties depending on hardware, algorithm and detail properties of the problem. Given the current state of noisy intermediate-scale quantum (NISQ) hardware, these effects are considerably more pronounced than in classical computing. Likewise, efficiency of the transformation itself is relevant because possible quantum advantage may easily be eradicated by the overhead of transforming between representations. In this article, we consider a specific class of higher-level representations, that is, PUBOs, and devise novel automatic transformation mechanisms into widely used QUBOs that substantially improve efficiency and versatility over the state of the art. In addition, we conduct a comprehensive investigation of industry-relevant problem formulations and their conversion into a quantum-specific representation, identifying significant obstacles in scaling behaviour and demonstrating how these can be circumvented.

arXiv:2411.19934•ACM Transactions on Quantum Computing•Mar 24, 2026•1 citation

Quantum Hardware-Efficient Selection of Auxiliary Variables for QUBO Formulations

Damian Rovara, Lukas Burgholzer, Robert Wille

The Quantum Approximate Optimization Algorithm (QAOA) requires considered optimization problems to be translated into a compatible format. A popular transformation step in this pipeline involves the quadratization of higher-order binary optimization problems, translating them into Quadratic Unconstrained Binary Optimization (QUBO) formulations through the introduction of auxiliary variables. Conventional algorithms for the selection of auxiliary variables often aim to minimize the total number of required variables without taking the constraints of the underlying quantum computer-in particular, the connectivity of its qubits-into consideration. This quickly results in interaction graphs that are incompatible with the target device, resulting in a substantial compilation overhead even with highly optimized compilers. To address this issue, this work presents a novel approach for the selection of auxiliary variables tailored for architectures with limited connectivity. By specifically constructing an interaction graph with a regular structure and a limited maximal degree of vertices, we find a way to construct QAOA circuits that can be mapped efficiently to a variety of architectures. We show that, compared to circuits constructed from a QUBO formulation using conventional auxiliary selection methods, the proposed approach reduces the circuit depth by almost 40%. An implementation of all proposed methods is publicly available at https://github.com/munich-quantum-toolkit/problemsolver.

quant-pharXiv:2511.19613•Design, Automation, and Test in Europe•Nov 26, 2025•0 citations

Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA

Jonas Stein, Farbod Chamanian, Maximilian Zorn +4 more

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.

arXiv:2305.03390•Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•13 citations

AutoQubo

Alberto Moraglio, Serban Paul Georgescu, Przemysław Sadowski

This paper presents a general method to derive automatically a Quadratic Unconstrained Binary Optimisation (QUBO) formulation of, in principle, any combinatorial optimisation problem from its high-level description given in any programming language in a free format. Currently ad-hoc approaches to formulating a problem at a time as a QUBO are the norm. The proposed method goes beyond the state-of-the-art as it is general in its applicability. The method is data-driven and based on sampling, but the obtained QUBO is exact rather than only an approximation of the original problem for optimisation problems occurring in practice. The method is of particular interest in the context of Quantum Ising Machines - quantum computers specialised to optimisation tasks. It can be understood as a compiler that makes these machines usable without specific expertise by automating the translation of high-level description of combinatorial optimisation problems to a low-level format suitable for the quantum hardware.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•24 citations

Optimized QUBO formulation methods for quantum computing

Dario De Santis, Salvatore Tirone, Stefano Marmi +1 more

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.

arXiv:2406.07681•Quantum Science and Technology•Jan 21, 2026•7 citations

Circuit Design Problems in Binary Polynomial Quantum Optimization

Dylan Laplace Mermoud, Dimitri Watel, Sourour Elloumi +1 more

Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree $d$ incur in circuit depth overheads, due to the lack of $d$-qubit gates, for $d\geq 3$, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the \textsf{NP}-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime.

quant-pharXiv:2610.13283•Oct 12, 2026•0 citations
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. Based on a practically relevant use-case and a graph-theoretic analysis, we evaluate how different transformation approaches influence widely used quantum performance metrics (circuit depth, gates count, gate distribution, qubit scaling), and also consider the classical computational efforts required to perform the transformations, as they influence possibilities for achieving future quantum advantage. Furthermore, we establish more general properties and invariants of the transformation methods. 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.
Many of the envisioned use-cases for quantum computers involve optimisation processes. While there are many algorithmic primitives to perform the required calculations, all eventually lead to quantum gates operating on quantum bits, with an order as determined by the structure of the objective function and the properties of target hardware. When the structure of the problem representation is not aligned with structure and boundary conditions of the executing hardware, various overheads degrading the computation may arise, possibly negating any possible quantum advantage. Therefore, automatic transformations of problem representations play an important role in quantum computing when descriptions (semi-)targeted at humans must be cast into forms that can be “executed” on quantum computers. Mathematically equivalent formulations are known to result in substantially different non-functional properties depending on hardware, algorithm and detail properties of the problem. Given the current state of noisy intermediate-scale quantum (NISQ) hardware, these effects are considerably more pronounced than in classical computing. Likewise, efficiency of the transformation itself is relevant because possible quantum advantage may easily be eradicated by the overhead of transforming between representations. In this article, we consider a specific class of higher-level representations, that is, PUBOs, and devise novel automatic transformation mechanisms into widely used QUBOs that substantially improve efficiency and versatility over the state of the art. In addition, we conduct a comprehensive investigation of industry-relevant problem formulations and their conversion into a quantum-specific representation, identifying significant obstacles in scaling behaviour and demonstrating how these can be circumvented.
The Quantum Approximate Optimization Algorithm (QAOA) requires considered optimization problems to be translated into a compatible format. A popular transformation step in this pipeline involves the quadratization of higher-order binary optimization problems, translating them into Quadratic Unconstrained Binary Optimization (QUBO) formulations through the introduction of auxiliary variables. Conventional algorithms for the selection of auxiliary variables often aim to minimize the total number of required variables without taking the constraints of the underlying quantum computer-in particular, the connectivity of its qubits-into consideration. This quickly results in interaction graphs that are incompatible with the target device, resulting in a substantial compilation overhead even with highly optimized compilers. To address this issue, this work presents a novel approach for the selection of auxiliary variables tailored for architectures with limited connectivity. By specifically constructing an interaction graph with a regular structure and a limited maximal degree of vertices, we find a way to construct QAOA circuits that can be mapped efficiently to a variety of architectures. We show that, compared to circuits constructed from a QUBO formulation using conventional auxiliary selection methods, the proposed approach reduces the circuit depth by almost 40%. An implementation of all proposed methods is publicly available at https://github.com/munich-quantum-toolkit/problemsolver.
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.
This paper presents a general method to derive automatically a Quadratic Unconstrained Binary Optimisation (QUBO) formulation of, in principle, any combinatorial optimisation problem from its high-level description given in any programming language in a free format. Currently ad-hoc approaches to formulating a problem at a time as a QUBO are the norm. The proposed method goes beyond the state-of-the-art as it is general in its applicability. The method is data-driven and based on sampling, but the obtained QUBO is exact rather than only an approximation of the original problem for optimisation problems occurring in practice. The method is of particular interest in the context of Quantum Ising Machines - quantum computers specialised to optimisation tasks. It can be understood as a compiler that makes these machines usable without specific expertise by automating the translation of high-level description of combinatorial optimisation problems to a low-level format suitable for the quantum hardware.
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.
Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree ddd incur in circuit depth overheads, due to the lack of ddd-qubit gates, for d≥3d\geq 3d≥3, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the \textsf{NP}-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime.