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:2606.26206

Higher-Order vs. Quadratic Binary Optimization: Which Is Better for Probability Optimization with Tensor Sampling?

Hadi Salloum, Kirill Novoselov, Aleksandr Pochtarev, Yaroslav Kholodov

Published Jun 24, 2026• 0 citations
arXivHTMLPDF

Abstract

This article explores the comparative strengths of Higher-Order Unconstrained Binary Optimization (HUBO) and Quadratic Unconstrained Binary Optimization (QUBO) models in the context of probability optimization using tensor sampling techniques. HUBO can represent interactions beyond pairwise terms without introducing auxiliary variables, while QUBO benefits from a simpler algebraic structure and a wide range of established solvers. We combine a theoretical analysis of formulation expressiveness and reduction overhead with empirical experiments on synthetic polynomial objectives, RSA factorization, and Max-Cut instances. The results show that native HUBO formulations are often preferable when the original problem contains high-order interactions, because reducing such problems to QUBO increases the effective dimension seen by tensor samplers. At the same time, QUBO remains competitive for naturally quadratic problems. These findings provide practical guidance for selecting an optimization framework that balances model fidelity, dimension growth, and solver performance.

DOI
10.48550/arxiv.2606.26206

Related papers

Quantum optimization beyond QUBO for industrial logistics and scheduling

Juan F. R. Hernandez, Pavle Nikacevic, Enrique Solano +4 more

The increasing complexity of industrial scheduling and transport routing problems motivates the study of alternative optimization formulations and computational paradigms. In this work, we study how higher-order unconstrained binary optimization (HUBO) formulations of such problems map onto quantum optimization workflows in both noisy and fault-tolerant regimes. We consider three representative logistics and manufacturing use cases and formulate each as a HUBO problem. This captures process intricacies, such as highly correlated assembly-line scheduling rules, which are difficult to express faithfully with the standard quadratic (QUBO) form, while at the same time reducing the number of binary variables required in the quantum mapping, thus lowering qubit demand. We compare the HUBO formulations with corresponding QUBO encodings, highlighting a key trade-off: while HUBO reduces qubit requirements through compact binary encoding, it introduces higher-order interaction terms that increase circuit depth, limiting feasibility on current quantum hardware. The proposed formulations are validated using classical solvers across several problem instances and benchmark small routing problem instances using bias-field digitized counterdiabatic quantum optimization in classical simulation. We complement these results with a resource and scalability analysis, focusing on the capacitated vehicle routing problem as a representative large-scale industrial use case. Our analysis indicates that while HUBO formulations offer advantages in qubit scaling compared to QUBO encodings, their practical implementation is constrained by gate fidelity, coherence, and circuit depth, making hybrid quantum-classical workflows and early fault-tolerant quantum hardware the most plausible settings for their practical use.

quant-pharXiv:2605.30252•May 29, 2026•1 citation

Resource-Efficient Quantum Optimization via Higher-Order Encoding

Frederik Koch, Shahram Panahiyan, Rick Mukherjee +2 more

Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to a QUBO formulation in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, significantly reduces qubit requirements and decreases total CNOT gate counts by at least 89.6% for all tested instances. These results highlight HUBO as a practical alternative for quantum optimization on near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, extends beyond the examples presented in this work, and broadens access to resource-efficient quantum optimization.

quant-pharXiv:2511.17545•EPJ Quantum Technology•Nov 11, 2025•6 citations

Quantum Feature Selection with Higher-Order Binary Optimization on Trapped-Ion Hardware

Carlos Flores-Garrigós, Anton Simen, Qi Zhang +6 more

We present a quantum feature-selection framework based on a higher-order unconstrained binary optimization (HUBO) formulation that explicitly incorporates multivariate dependencies beyond standard quadratic encodings. In contrast to QUBO-based approaches, the proposed model includes one-, two-, and three-body interaction terms derived from mutual-information measures, enabling the objective function to capture feature relevance, pairwise redundancy, and higher-order statistical structure within a unified energy model. To suppress trivial all-selected solutions, we further include structured linear penalties that promote sparsity while preserving informative variables. The resulting HUBO instances are optimized with digitized counterdiabatic quantum optimization on IonQ Forte and compared against noiseless quantum simulation as well as two classical dimensionality-reduction baselines: SelectKBest based on mutual information and principal component analysis (PCA). We evaluate the proposed workflow on two benchmark classification datasets, namely the Gallstone dataset and the Spambase dataset, and analyze both predictive performance and selected-subset structure. The results show good qualitative agreement between hardware executions and noiseless simulations, supporting the feasibility of implementing higher-order feature-selection Hamiltonians on current trapped-ion processors. In addition, the quantum approach yields competitive classification performance while producing compact and informative feature subsets, highlighting the potential of higher-order quantum optimization for machine-learning preprocessing tasks.

quant-pharXiv:2604.26834•Apr 30, 2026•2 citations

Black-Box Optimization of QUBO-Based Machine Learning Models Using Tensor Train Sampling

Hadi Salloum, Osama Orabi, Salman Ahmdi +4 more

The Probabilistic Optimizer with TEnsor Sampling (PROTES) is a gradient-free optimization method for multidimensional arrays and discretized multivariate functions based on the tensor train (TT) format. This novel tensor-network methodology demonstrates significant promise for complex Quadratic Unconstrained Binary Optimization (QUBO) problems. We establish the first application of PROTES to machine learning model training via QUBO formulations and provide the inaugural comparative analysis against D-Wave quantum annealing. Our results reveal a critical performance dichotomy: For smallscale, structurally complex QUBO instances, PROTES achieves superior solution accuracy with enhanced computational stability compared to quantum annealing, while maintaining competitive efficiency. Conversely, Quantum Annealing retains scalability advantages for larger problem dimensions. These findings delineate precise operational domains for tensor-network versus quantum optimization paradigms, establishing PROTES as the preferred solver for compact, high-complexity QUBO problems. This research provides fundamental insights for strategic solver selection and advances the engineering of hybrid quantumclassical optimization frameworks.

•Jul 19, 2025•0 citations

HUBO & QUBO and Prime Factorization

Samer Rahmeh, Adam Neumann

This document details the methodology and steps taken to convert Higher Order Unconstrained Binary Optimization (HUBO) models into Quadratic Unconstrained Binary Optimization (QUBO) models. The focus is primarily on prime factorization problems; a critical and computationally intensive task relevant in various domains including cryptography, optimization, and number theory. The conversion from Higher-Order Binary Optimization (HUBO) to Quadratic Unconstrained Binary Optimization (QUBO) models is crucial for harnessing the capabilities of advanced computing methodologies, particularly quantum computing and DYNEX neuromorphic computing. Quantum computing offers potential exponential speedups for specific problems through its intrinsic parallelism capabilities. Conversely, DYNEX neuromorphic computing enhances efficiency and accelerates the resolution of intricate, pattern-oriented tasks by simulating memristors in GPUs, employing a highly decentralized approach, via Blockchain technology. This transformation enables the exploitation of these cutting-edge computing paradigms to address complex optimization challenges effectively. Through detailed explanations, mathematical formulations, and algorithmic strategies, this document aims to provide a comprehensive guide to understanding and implementing the conversion process from HUBO to QUBO. It underscores the importance of such transformations in making prime factorization computationally feasible on both existing classical computers and emerging computing technologies.

International Journal of Bioinformatics and Intelligent Computing•Feb 20, 2024•0 citations

VeloxQ: A Fast and Efficient QUBO Solver

Jakub Pawłowski, Jan Tuziemski, Paweł Tarasiuk +5 more

We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to $10^{8}$ sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.

arXiv:2501.19221•Jan 31, 2025•16 citations
This article explores the comparative strengths of Higher-Order Unconstrained Binary Optimization (HUBO) and Quadratic Unconstrained Binary Optimization (QUBO) models in the context of probability optimization using tensor sampling techniques. HUBO can represent interactions beyond pairwise terms without introducing auxiliary variables, while QUBO benefits from a simpler algebraic structure and a wide range of established solvers. We combine a theoretical analysis of formulation expressiveness and reduction overhead with empirical experiments on synthetic polynomial objectives, RSA factorization, and Max-Cut instances. The results show that native HUBO formulations are often preferable when the original problem contains high-order interactions, because reducing such problems to QUBO increases the effective dimension seen by tensor samplers. At the same time, QUBO remains competitive for naturally quadratic problems. These findings provide practical guidance for selecting an optimization framework that balances model fidelity, dimension growth, and solver performance.
The increasing complexity of industrial scheduling and transport routing problems motivates the study of alternative optimization formulations and computational paradigms. In this work, we study how higher-order unconstrained binary optimization (HUBO) formulations of such problems map onto quantum optimization workflows in both noisy and fault-tolerant regimes. We consider three representative logistics and manufacturing use cases and formulate each as a HUBO problem. This captures process intricacies, such as highly correlated assembly-line scheduling rules, which are difficult to express faithfully with the standard quadratic (QUBO) form, while at the same time reducing the number of binary variables required in the quantum mapping, thus lowering qubit demand. We compare the HUBO formulations with corresponding QUBO encodings, highlighting a key trade-off: while HUBO reduces qubit requirements through compact binary encoding, it introduces higher-order interaction terms that increase circuit depth, limiting feasibility on current quantum hardware. The proposed formulations are validated using classical solvers across several problem instances and benchmark small routing problem instances using bias-field digitized counterdiabatic quantum optimization in classical simulation. We complement these results with a resource and scalability analysis, focusing on the capacitated vehicle routing problem as a representative large-scale industrial use case. Our analysis indicates that while HUBO formulations offer advantages in qubit scaling compared to QUBO encodings, their practical implementation is constrained by gate fidelity, coherence, and circuit depth, making hybrid quantum-classical workflows and early fault-tolerant quantum hardware the most plausible settings for their practical use.
Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to a QUBO formulation in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, significantly reduces qubit requirements and decreases total CNOT gate counts by at least 89.6% for all tested instances. These results highlight HUBO as a practical alternative for quantum optimization on near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, extends beyond the examples presented in this work, and broadens access to resource-efficient quantum optimization.
We present a quantum feature-selection framework based on a higher-order unconstrained binary optimization (HUBO) formulation that explicitly incorporates multivariate dependencies beyond standard quadratic encodings. In contrast to QUBO-based approaches, the proposed model includes one-, two-, and three-body interaction terms derived from mutual-information measures, enabling the objective function to capture feature relevance, pairwise redundancy, and higher-order statistical structure within a unified energy model. To suppress trivial all-selected solutions, we further include structured linear penalties that promote sparsity while preserving informative variables. The resulting HUBO instances are optimized with digitized counterdiabatic quantum optimization on IonQ Forte and compared against noiseless quantum simulation as well as two classical dimensionality-reduction baselines: SelectKBest based on mutual information and principal component analysis (PCA). We evaluate the proposed workflow on two benchmark classification datasets, namely the Gallstone dataset and the Spambase dataset, and analyze both predictive performance and selected-subset structure. The results show good qualitative agreement between hardware executions and noiseless simulations, supporting the feasibility of implementing higher-order feature-selection Hamiltonians on current trapped-ion processors. In addition, the quantum approach yields competitive classification performance while producing compact and informative feature subsets, highlighting the potential of higher-order quantum optimization for machine-learning preprocessing tasks.
The Probabilistic Optimizer with TEnsor Sampling (PROTES) is a gradient-free optimization method for multidimensional arrays and discretized multivariate functions based on the tensor train (TT) format. This novel tensor-network methodology demonstrates significant promise for complex Quadratic Unconstrained Binary Optimization (QUBO) problems. We establish the first application of PROTES to machine learning model training via QUBO formulations and provide the inaugural comparative analysis against D-Wave quantum annealing. Our results reveal a critical performance dichotomy: For smallscale, structurally complex QUBO instances, PROTES achieves superior solution accuracy with enhanced computational stability compared to quantum annealing, while maintaining competitive efficiency. Conversely, Quantum Annealing retains scalability advantages for larger problem dimensions. These findings delineate precise operational domains for tensor-network versus quantum optimization paradigms, establishing PROTES as the preferred solver for compact, high-complexity QUBO problems. This research provides fundamental insights for strategic solver selection and advances the engineering of hybrid quantumclassical optimization frameworks.
This document details the methodology and steps taken to convert Higher Order Unconstrained Binary Optimization (HUBO) models into Quadratic Unconstrained Binary Optimization (QUBO) models. The focus is primarily on prime factorization problems; a critical and computationally intensive task relevant in various domains including cryptography, optimization, and number theory. The conversion from Higher-Order Binary Optimization (HUBO) to Quadratic Unconstrained Binary Optimization (QUBO) models is crucial for harnessing the capabilities of advanced computing methodologies, particularly quantum computing and DYNEX neuromorphic computing. Quantum computing offers potential exponential speedups for specific problems through its intrinsic parallelism capabilities. Conversely, DYNEX neuromorphic computing enhances efficiency and accelerates the resolution of intricate, pattern-oriented tasks by simulating memristors in GPUs, employing a highly decentralized approach, via Blockchain technology. This transformation enables the exploitation of these cutting-edge computing paradigms to address complex optimization challenges effectively. Through detailed explanations, mathematical formulations, and algorithmic strategies, this document aims to provide a comprehensive guide to understanding and implementing the conversion process from HUBO to QUBO. It underscores the importance of such transformations in making prime factorization computationally feasible on both existing classical computers and emerging computing technologies.
We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to 10810^{8}108 sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.