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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Evaluating the Impact of Retaining Higher-Order Terms in Combinatorial Optimization Problems

Kazuki Ikeuchi, Yoshiki Matsuda, Shu Tanaka

Published Aug 30, 2025• 0 citations
Publisher

Abstract

Ising machines, including quantum annealing machines, are promising next-generation computers for combinatorial optimization problems. Due to hardware limitations, most Ising-type hardware can only solve functions expressed in linear or quadratic terms of binary variables. Therefore, problems with higher-order terms require order reduction, which increases the number of variables and constraints and may degrade solution quality. This study evaluates the effectiveness of directly solving such problems without order reduction by using the polynomial unconstrained binary optimization (PUBO) solver implemented in Toshiba's Simulated Quantum-inspired Bifurcation Machine+ (SQBM+). We compare its performance against a conventional quadratic unconstrained binary optimization (QUBO) solver on the same hardware platform. As benchmarks, we use a vehicle routing problem with distance balancing and the low autocorrelation binary sequence (LABS) problem, 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 the potential advantages of directly handling higher-order terms in practical optimization problems.

DOI
10.1109/qce65121.2025.10414

Related papers

Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Under Simulated Annealing

Kazuki Ikeuchi, Yoshiki Matsuda, Shu Tanaka

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.

arXiv:2510.24237•IEEE Access•Jan 1, 2026•1 citation

Boosting quantum annealing performance through direct polynomial unconstrained binary optimization

Sebastian Nagies, Kevin T. Geier, Javed Akram +3 more

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.

arXiv:2412.04398•Quantum Science and Technology•Apr 9, 2025•4 citations

New advances for quantum‐inspired optimization

Yu Du, Haibo Wang, Rick Hennig +3 more

Abstract Advances in quantum computing with applications in combinatorial optimization have evolved at an increasing rate in recent years. The quadratic unconstrained binary optimization (QUBO) model is at the center of these developments and has become recognized as an effective alternative method for representing a wide variety of combinatorial optimization problems. Additional momentum has resulted from the arrival of quantum computers and their ability to solve the Ising spin glass problem, another form of the QUBO model. This paper highlights advances in solving QUBO models and extensions to more general polynomial unconstrained binary optimization (PUBO) models as important alternatives to traditional approaches. Computational experience is provided that compares the performance of unique quantum‐inspired metaheuristic solvers—the Next Generation Quantum (NGQ) solver for QUBO models and the NGQ‐PUBO solver for PUBO models—with the performance of CPLEX and the Dwave quantum advantage solver. Extensive results, including experiments with a set of large set partitioning problems representing the largest QUBO models reported in the literature to date, along with maximum diversity and max cut problem sets, disclose that our solvers outperform both CPLEX and Dwave by a wide margin in terms of both computational time and solution quality.

International Transactions in Operational Research•Dec 28, 2023•17 citations

Compressed Quadratization of Higher Order Binary Optimization Problems

Avradip Mandal, Arnab Roy, Sarvagya Upadhyay +1 more

Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.

arXiv:2001.00658•DCC•Mar 1, 2020•33 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

Simulated Annealing for Quadratic and Higher-Order Unconstrained Integer Optimization

Kohei SUZUKI

Simulated annealing (SA) is a key algorithm for solving combinatorial optimization problems, which model numerous real-world systems. While SA is commonly used to solve quadratic unconstrained binary optimization (QUBO) problems, many practical problems are more naturally formulated using integer variables. We therefore study quadratic and higher-order unconstrained integer optimization (QUIO and HUIO) problems, which generalize QUBO by allowing integer-valued variables and higher-order interactions. Conventional approaches often convert these problems into QUBO formulations through binary encoding and the reduction of higher-order terms. Such conversions, however, greatly increase the number of variables and interactions, resulting in long computation times and, for large-scale problems, even making the conversion itself a dominant computational bottleneck. To overcome this limitation, we propose an efficient framework that directly applies SA to QUIO and HUIO problems without converting them into QUBO. Within this framework, we introduce an optimal-transition Metropolis method, designed to improve efficiency when the variable range is wide, and evaluate its performance alongside the conventional Metropolis and heat bath methods. Numerical experiments demonstrate that the proposed direct approach achieves higher efficiency and better solution quality than the conventional QUBO-based formulation and reveal the practical advantages of the optimal-transition Metropolis method. The algorithm developed in this study is available as part of the open-source library OpenJij, which provides a Python front end with a C++ backend.

arXiv:2511.17245•Nov 21, 2025•0 citations
Ising machines, including quantum annealing machines, are promising next-generation computers for combinatorial optimization problems. Due to hardware limitations, most Ising-type hardware can only solve functions expressed in linear or quadratic terms of binary variables. Therefore, problems with higher-order terms require order reduction, which increases the number of variables and constraints and may degrade solution quality. This study evaluates the effectiveness of directly solving such problems without order reduction by using the polynomial unconstrained binary optimization (PUBO) solver implemented in Toshiba's Simulated Quantum-inspired Bifurcation Machine+ (SQBM+). We compare its performance against a conventional quadratic unconstrained binary optimization (QUBO) solver on the same hardware platform. As benchmarks, we use a vehicle routing problem with distance balancing and the low autocorrelation binary sequence (LABS) problem, 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 the potential advantages of directly handling higher-order terms in practical optimization problems.
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.
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 Advances in quantum computing with applications in combinatorial optimization have evolved at an increasing rate in recent years. The quadratic unconstrained binary optimization (QUBO) model is at the center of these developments and has become recognized as an effective alternative method for representing a wide variety of combinatorial optimization problems. Additional momentum has resulted from the arrival of quantum computers and their ability to solve the Ising spin glass problem, another form of the QUBO model. This paper highlights advances in solving QUBO models and extensions to more general polynomial unconstrained binary optimization (PUBO) models as important alternatives to traditional approaches. Computational experience is provided that compares the performance of unique quantum‐inspired metaheuristic solvers—the Next Generation Quantum (NGQ) solver for QUBO models and the NGQ‐PUBO solver for PUBO models—with the performance of CPLEX and the Dwave quantum advantage solver. Extensive results, including experiments with a set of large set partitioning problems representing the largest QUBO models reported in the literature to date, along with maximum diversity and max cut problem sets, disclose that our solvers outperform both CPLEX and Dwave by a wide margin in terms of both computational time and solution quality.
Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.
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.
Simulated annealing (SA) is a key algorithm for solving combinatorial optimization problems, which model numerous real-world systems. While SA is commonly used to solve quadratic unconstrained binary optimization (QUBO) problems, many practical problems are more naturally formulated using integer variables. We therefore study quadratic and higher-order unconstrained integer optimization (QUIO and HUIO) problems, which generalize QUBO by allowing integer-valued variables and higher-order interactions. Conventional approaches often convert these problems into QUBO formulations through binary encoding and the reduction of higher-order terms. Such conversions, however, greatly increase the number of variables and interactions, resulting in long computation times and, for large-scale problems, even making the conversion itself a dominant computational bottleneck. To overcome this limitation, we propose an efficient framework that directly applies SA to QUIO and HUIO problems without converting them into QUBO. Within this framework, we introduce an optimal-transition Metropolis method, designed to improve efficiency when the variable range is wide, and evaluate its performance alongside the conventional Metropolis and heat bath methods. Numerical experiments demonstrate that the proposed direct approach achieves higher efficiency and better solution quality than the conventional QUBO-based formulation and reveal the practical advantages of the optimal-transition Metropolis method. The algorithm developed in this study is available as part of the open-source library OpenJij, which provides a Python front end with a C++ backend.