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:2010.08693 · PLoS ONE

Binary matrix factorization on special purpose hardware

Osman Asif Malik, Hayato Ushijima‐Mwesigwa, Arnab Roy, Avradip Mandal, Indradeep Ghosh

Published Dec 16, 2021• 6 citations
arXivHTMLPDF

Abstract

Many fundamental problems in data mining can be reduced to one or more NP-hard combinatorial optimization problems. Recent advances in novel technologies such as quantum and quantum-inspired hardware promise a substantial speedup for solving these problems compared to when using general purpose computers but often require the problem to be modeled in a special form, such as an Ising or quadratic unconstrained binary optimization (QUBO) model, in order to take advantage of these devices. In this work, we focus on the important binary matrix factorization (BMF) problem which has many applications in data mining. We propose two QUBO formulations for BMF. We show how clustering constraints can easily be incorporated into these formulations. The special purpose hardware we consider is limited in the number of variables it can handle which presents a challenge when factorizing large matrices. We propose a sampling based approach to overcome this challenge, allowing us to factorize large rectangular matrices. In addition to these methods, we also propose a simple baseline algorithm which outperforms our more sophisticated methods in a few situations. We run experiments on the Fujitsu Digital Annealer, a quantum-inspired complementary metal-oxide-semiconductor (CMOS) annealer, on both synthetic and real data, including gene expression data. These experiments show that our approach is able to produce more accurate BMFs than competing methods.

DOI
10.1371/journal.pone.0261250

Related papers

Ising-Based Consensus Clustering on Specialized Hardware

Eldan Cohen, Avradip Mandal, Hayato Ushijima‐Mwesigwa +1 more

The emergence of specialized optimization hardware such as CMOS annealers and adiabatic quantum computers carries the promise of solving hard combinatorial optimization problems more efficiently in hardware. Recent work has focused on formulating different combinatorial optimization problems as Ising models, the core mathematical abstraction used by a large number of these hardware platforms, and evaluating the performance of these models when solved on specialized hardware. An interesting area of application is data mining, where combinatorial optimization problems underlie many core tasks. In this work, we focus on consensus clustering (clustering aggregation), an important combinatorial problem that has received much attention over the last two decades. We present two Ising models for consensus clustering and evaluate them using the Fujitsu Digital Annealer, a quantum-inspired CMOS annealer. Our empirical evaluation shows that our approach outperforms existing techniques and is a promising direction for future research.

arXiv:2003.01887•Lecture notes in computer science•Jan 1, 2020•16 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

Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network

Yuta Shikuri

Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.

arXiv:2006.06926•Proceedings of the AAAI Conference on Artificial Intelligence•Apr 11, 2025•5 citations

Deriving Compact QUBO Models via Multilevel Constraint Transformation

Оксана Сергеевна Пичугина, Yingcong Tan, J. Christopher Beck

With the advances in customized hardware for quantum annealing and digital/CMOS Annealing, Quadratic Unconstrained Binary Optimization (QUBO) models have received growing attention in the optimization literature. Motivated by an existing general-purpose approach that derives QUBO models from binary linear programs (BLP), we propose a novel Multilevel Constraint Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary binary variables. We formulate sufficient conditions for the existence of a compact QUBO formulation (i.e., in the original BLP decision space) in terms of constraint levelness and demonstrate the flexibility and applicability of MLCTS on synthetic examples and several well-known combinatorial optimization problems, i.e., the Maximum 2-Satisfiability Problem, the Linear Ordering Problem, the Community Detection Problem, and the Maximum Independence Set Problem. For a proof-of-concept, we compare the performance of two QUBO models for the latter problem on both a general-purpose software-based solver and a hardware-based QUBO solver. The MLCTS-derived models demonstrate significantly better performance for both solvers, in particular, solving up to seven times more instances with the hardware-based approach.

arXiv:2404.03610•Apr 4, 2024•0 citations

Physics-Inspired Optimization in the QUBO Framework: Key Concepts and Approaches

Lien-Po Yu, Chin-Fu Nien

Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.

SPIN•Aug 30, 2023•1 citation

Unified Clustering and Outlier Detection on Specialized Hardware

Eldan Cohen, Hayato Ushijima‐Mwesigwa, Avradip Mandal +1 more

Clustering and outlier detection are often studied as separate problems. However, previous work has shown that a unified approach can lead to better performance. Unified clustering and outlier detection is a hard combinatorial problem that has received significant attention in recent years. The recent emergence of specialized optimization hardware capable of solving combinatorial problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) models has led to increased interest in harnessing these platforms in core data mining tasks. In this work, we present a novel QUBO formulation of the unified clustering and outlier detection problem and use the Fujitsu Digital Annealer, a specialized CMOS hardware, to solve it. Experiments on synthetic and real datasets demonstrate the effectiveness of our approach.

IEEE International Conference on Acoustics Speech and Signal Processing•May 13, 2021•2 citations
Many fundamental problems in data mining can be reduced to one or more NP-hard combinatorial optimization problems. Recent advances in novel technologies such as quantum and quantum-inspired hardware promise a substantial speedup for solving these problems compared to when using general purpose computers but often require the problem to be modeled in a special form, such as an Ising or quadratic unconstrained binary optimization (QUBO) model, in order to take advantage of these devices. In this work, we focus on the important binary matrix factorization (BMF) problem which has many applications in data mining. We propose two QUBO formulations for BMF. We show how clustering constraints can easily be incorporated into these formulations. The special purpose hardware we consider is limited in the number of variables it can handle which presents a challenge when factorizing large matrices. We propose a sampling based approach to overcome this challenge, allowing us to factorize large rectangular matrices. In addition to these methods, we also propose a simple baseline algorithm which outperforms our more sophisticated methods in a few situations. We run experiments on the Fujitsu Digital Annealer, a quantum-inspired complementary metal-oxide-semiconductor (CMOS) annealer, on both synthetic and real data, including gene expression data. These experiments show that our approach is able to produce more accurate BMFs than competing methods.
The emergence of specialized optimization hardware such as CMOS annealers and adiabatic quantum computers carries the promise of solving hard combinatorial optimization problems more efficiently in hardware. Recent work has focused on formulating different combinatorial optimization problems as Ising models, the core mathematical abstraction used by a large number of these hardware platforms, and evaluating the performance of these models when solved on specialized hardware. An interesting area of application is data mining, where combinatorial optimization problems underlie many core tasks. In this work, we focus on consensus clustering (clustering aggregation), an important combinatorial problem that has received much attention over the last two decades. We present two Ising models for consensus clustering and evaluate them using the Fujitsu Digital Annealer, a quantum-inspired CMOS annealer. Our empirical evaluation shows that our approach outperforms existing techniques and is a promising direction for future research.
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.
Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.
With the advances in customized hardware for quantum annealing and digital/CMOS Annealing, Quadratic Unconstrained Binary Optimization (QUBO) models have received growing attention in the optimization literature. Motivated by an existing general-purpose approach that derives QUBO models from binary linear programs (BLP), we propose a novel Multilevel Constraint Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary binary variables. We formulate sufficient conditions for the existence of a compact QUBO formulation (i.e., in the original BLP decision space) in terms of constraint levelness and demonstrate the flexibility and applicability of MLCTS on synthetic examples and several well-known combinatorial optimization problems, i.e., the Maximum 2-Satisfiability Problem, the Linear Ordering Problem, the Community Detection Problem, and the Maximum Independence Set Problem. For a proof-of-concept, we compare the performance of two QUBO models for the latter problem on both a general-purpose software-based solver and a hardware-based QUBO solver. The MLCTS-derived models demonstrate significantly better performance for both solvers, in particular, solving up to seven times more instances with the hardware-based approach.
Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.
Clustering and outlier detection are often studied as separate problems. However, previous work has shown that a unified approach can lead to better performance. Unified clustering and outlier detection is a hard combinatorial problem that has received significant attention in recent years. The recent emergence of specialized optimization hardware capable of solving combinatorial problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) models has led to increased interest in harnessing these platforms in core data mining tasks. In this work, we present a novel QUBO formulation of the unified clustering and outlier detection problem and use the Fujitsu Digital Annealer, a specialized CMOS hardware, to solve it. Experiments on synthetic and real datasets demonstrate the effectiveness of our approach.