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:2203.15634 · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS)

Convex Non-negative Matrix Factorization Through Quantum Annealing

Ahmed Zaiou, Basarab Mateï, Younès Bennani, Mohamed HIBTI

Published Dec 1, 2021• 2 citations
arXivHTMLPDF

Abstract

In this paper we provide the quantum version of the Convex Non-negative Matrix Factorization algorithm (Convex-NMF) by using the D-wave quantum annealer. More precisely, we use D-wave 2000Q to find the low rank approximation of a fixed real-valued matrix$X$by the product of two non-negative matrices factors$W$and$G$such that the Frobenius norm of the difference$X$- XWG is minimized. In order to solve this optimization problem we proceed in two steps. In the first step we transform the global real optimization problem depending on$W, G$into two quadratic unconstrained binary optimization problems (QUBO) depending on$W$and$G$respectively. In the second step we use an alternative strategy between the two QUBO problems corresponding to$W$and$G$to find the global solution. The running of these two QUBO problems on D-wave 2000Q need to use an embedding to the chimera graph of D-wave 2000Q, this embedding is limited by the number of qubits of D-wave 2000Q. We perform a study on the maximum number of real data to be used by our approach on$\mathbf{D}$-wave 2000Q. The proposed study is based on the number of qubits used to represent each real variable. We also tested our approach on D-Wave 2000Q with several randomly generated data sets to prove that our approach is faster than the classical approach and also to prove that it gets the best results.

DOI
10.1109/hpcc-dss-smartcity-dependsys53884.2021.00191

Related papers

Low Rank Non-Negative Matrix Factorization with D-Wave 2000Q

Daniele Ottaviani, Alfonso Amendola

In this article we want to demonstrate the effectiveness of the new D-Wave quantum annealer, D-Wave 2000Q, in dealing with real world problems. In particular, it is shown how the quantum annealing process is able to find global optima even in the case of problems that do not directly involve binary variables. The problem addressed in this work is the following: taking a matrix V, find two matrices W and H such that the norm between V and the matrix product WH is as small as possible. The work is inspired by O'Malley's article [1], where the author proposed an algorithm to solve a problem very similar to ours, where however the matrix H was formed by only binary variables. In our case neither of the two matrices W or H is a binary matrix. In particular, the factorization foresees that the matrix W is composed of real numbers between 0 and 1 and that the sum of its rows is equal to 1. The QUBO problem associated with this type of factorization generates a potential composed of many local minima. We show that simple forward-annealing techniques are not sufficient to solve the problem. The new D-Wave 2000Q has introduced new solution refinement techniques, including reverse-annealing. Reverse-annealing allows to explore the configuration space starting from a point chosen by the user, for example a local minimum obtained with a precedent forward-annealing. In this article we propose an algorithm based on the reverse annealing technique (that we called adaptive reverse annealing) able to reach global minimum even in the case of QUBO problems where the classic forward annealing, or uncontrolled reverse annealing, can not reach satisfactory solutions.

arXiv:1808.08721•Aug 27, 2018•23 citations

Balanced K-means using Quantum annealing

Ahmed Zaiou, Younès Bennani, Basarab Mateï +1 more

In this paper, we propose a new quantum version of the Balanced K-means algorithm in the D-wave quantum annealer. D-wave 2000Q quantum computer has been used by many papers in the last few years to solve optimization problems and for finding the global minimum of the balanced K-means optimization problem. However, in this paper, we modify the quadratic unconstrained binary optimization (QUBO) formulation of the Balanced K-means that has been proposed in a recent paper. Our modification is trained on different data sets: Iris, Wine and Breast Cancer. Also, we performed a comparative analysis between the two approaches (our approach and the paper's approach) to find the one that assigns the largest number of data to clusters and we also use the Davies-Bouldi metric to prove that our method gives the best clustering.

IEEE Symposium Series on Computational Intelligence (SSCI)•Dec 5, 2021•8 citations

Quantum Annealing versus Digital Computing

Michael Jünger, Elisabeth Lobe, Petra Mutzel +4 more

Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.

arXiv:1904.11965•ACM Journal of Experimental Algorithmics•Jul 9, 2021•48 citations

Simple Constraint Embedding for Quantum Annealers

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.

IEEE International Conference on Rebooting Computing (ICRC)•Nov 1, 2018•9 citations

Approximate Block Diagonalization of Symmetric Matrices Using Quantum Annealing

Koushi Teramoto, Masaki Kugaya, Shuhei Kudo +2 more

We consider the problem of transforming a given symmetric matrix into a nearly block diagonal form by permutation of its rows and columns. Such a transformation is useful as preconditioning to accelerate the convergence of an eigenvalue solver, but the problem of finding an optimal permutation that maximizes the Frobenius norms of the diagonal blocks is NP-complete. We formulate this problem as QUBO (Quadratic Unconstrained Binary Optimization) and solve it using D-Wave Advantage quantum annealing machine. Experimental results on small problems show that the true minimum can be obtained with high probability. We also discuss how to improve the mapping of the problem onto the physical qubit network to increase the size of the problems that can be solved.

International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia)•Jan 18, 2024•1 citation

Non-Negative Matrix Factorization Using Non-Von Neumann Computers

Ajinkya Borle, Charles Nicholas, Uchenna Chukwu +2 more

Non-negative matrix factorization (NMF) is a matrix decomposition problem with applications in unsupervised learning. The general form of this problem (along with many of its variants) is NP-hard in nature. In our work, we explore how this problem could be solved with an energy-based optimization method suitable for certain machines with non-von Neumann architectures. We used the Dirac-3, a device based on the entropy computing paradigm and made by Quantum Computing Inc., to evaluate our approach. Our formulations consist of (i) a quadratic unconstrained binary optimization model (QUBO, suitable for Ising machines) and a quartic formulation that allows for real-valued and integer variables (suitable for machines like the Dirac-3). Although current devices cannot solve large NMF problems, the results of our preliminary experiments are promising enough to warrant further research. For non-negative real matrices, we observed that a fusion approach of first using Dirac-3 and then feeding its results as the initial factor matrices to Scikit-learn's NMF procedure outperforms Scikit-learn's NMF procedure on its own, with default parameters in terms of the error in the reconstructed matrices. For our experiments on non-negative integer matrices, we compared the Dirac-3 device to Google's CP-SAT solver (inside the Or-Tools package) and found that for serial processing, Dirac-3 outperforms CP-SAT in a majority of the cases. We believe that future work in this area might be able to identify domains and variants of the problem where entropy computing (and other non-von Neumann architectures) could offer a clear advantage.

quant-pharXiv:2512.00675•Dec 2, 2025•0 citations
In this paper we provide the quantum version of the Convex Non-negative Matrix Factorization algorithm (Convex-NMF) by using the D-wave quantum annealer. More precisely, we use D-wave 2000Q to find the low rank approximation of a fixed real-valued matrixXXXby the product of two non-negative matrices factorsWWWandGGGsuch that the Frobenius norm of the differenceXXX- XWG is minimized. In order to solve this optimization problem we proceed in two steps. In the first step we transform the global real optimization problem depending onW,GW, GW,Ginto two quadratic unconstrained binary optimization problems (QUBO) depending onWWWandGGGrespectively. In the second step we use an alternative strategy between the two QUBO problems corresponding toWWWandGGGto find the global solution. The running of these two QUBO problems on D-wave 2000Q need to use an embedding to the chimera graph of D-wave 2000Q, this embedding is limited by the number of qubits of D-wave 2000Q. We perform a study on the maximum number of real data to be used by our approach onD\mathbf{D}D-wave 2000Q. The proposed study is based on the number of qubits used to represent each real variable. We also tested our approach on D-Wave 2000Q with several randomly generated data sets to prove that our approach is faster than the classical approach and also to prove that it gets the best results.
In this article we want to demonstrate the effectiveness of the new D-Wave quantum annealer, D-Wave 2000Q, in dealing with real world problems. In particular, it is shown how the quantum annealing process is able to find global optima even in the case of problems that do not directly involve binary variables. The problem addressed in this work is the following: taking a matrix V, find two matrices W and H such that the norm between V and the matrix product WH is as small as possible. The work is inspired by O'Malley's article [1], where the author proposed an algorithm to solve a problem very similar to ours, where however the matrix H was formed by only binary variables. In our case neither of the two matrices W or H is a binary matrix. In particular, the factorization foresees that the matrix W is composed of real numbers between 0 and 1 and that the sum of its rows is equal to 1. The QUBO problem associated with this type of factorization generates a potential composed of many local minima. We show that simple forward-annealing techniques are not sufficient to solve the problem. The new D-Wave 2000Q has introduced new solution refinement techniques, including reverse-annealing. Reverse-annealing allows to explore the configuration space starting from a point chosen by the user, for example a local minimum obtained with a precedent forward-annealing. In this article we propose an algorithm based on the reverse annealing technique (that we called adaptive reverse annealing) able to reach global minimum even in the case of QUBO problems where the classic forward annealing, or uncontrolled reverse annealing, can not reach satisfactory solutions.
In this paper, we propose a new quantum version of the Balanced K-means algorithm in the D-wave quantum annealer. D-wave 2000Q quantum computer has been used by many papers in the last few years to solve optimization problems and for finding the global minimum of the balanced K-means optimization problem. However, in this paper, we modify the quadratic unconstrained binary optimization (QUBO) formulation of the Balanced K-means that has been proposed in a recent paper. Our modification is trained on different data sets: Iris, Wine and Breast Cancer. Also, we performed a comparative analysis between the two approaches (our approach and the paper's approach) to find the one that assigns the largest number of data to clusters and we also use the Davies-Bouldi metric to prove that our method gives the best clustering.
Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.
Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.
We consider the problem of transforming a given symmetric matrix into a nearly block diagonal form by permutation of its rows and columns. Such a transformation is useful as preconditioning to accelerate the convergence of an eigenvalue solver, but the problem of finding an optimal permutation that maximizes the Frobenius norms of the diagonal blocks is NP-complete. We formulate this problem as QUBO (Quadratic Unconstrained Binary Optimization) and solve it using D-Wave Advantage quantum annealing machine. Experimental results on small problems show that the true minimum can be obtained with high probability. We also discuss how to improve the mapping of the problem onto the physical qubit network to increase the size of the problems that can be solved.
Non-negative matrix factorization (NMF) is a matrix decomposition problem with applications in unsupervised learning. The general form of this problem (along with many of its variants) is NP-hard in nature. In our work, we explore how this problem could be solved with an energy-based optimization method suitable for certain machines with non-von Neumann architectures. We used the Dirac-3, a device based on the entropy computing paradigm and made by Quantum Computing Inc., to evaluate our approach. Our formulations consist of (i) a quadratic unconstrained binary optimization model (QUBO, suitable for Ising machines) and a quartic formulation that allows for real-valued and integer variables (suitable for machines like the Dirac-3). Although current devices cannot solve large NMF problems, the results of our preliminary experiments are promising enough to warrant further research. For non-negative real matrices, we observed that a fusion approach of first using Dirac-3 and then feeding its results as the initial factor matrices to Scikit-learn's NMF procedure outperforms Scikit-learn's NMF procedure on its own, with default parameters in terms of the error in the reconstructed matrices. For our experiments on non-negative integer matrices, we compared the Dirac-3 device to Google's CP-SAT solver (inside the Or-Tools package) and found that for serial processing, Dirac-3 outperforms CP-SAT in a majority of the cases. We believe that future work in this area might be able to identify domains and variants of the problem where entropy computing (and other non-von Neumann architectures) could offer a clear advantage.