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)

Generation of Fixed Margin Binary Matrices Using Quantum Annealing

Alexandre Bergerault, Daniel Fortunato, Rui Abreu

Published Sep 15, 2024• 0 citations
Publisher

Abstract

Fixed margin binary matrices are used across various scientific fields. However, generating such matrices remains a complicated computational task using classical algorithms since the best algorithm performs in exponential time. In this paper, we model this problem using a Quadratic Unconstrained Binary Optimization (QUBO). Furthermore, we use D-Wave's Quantum Annealing computer and their simulator to generate these matrices. Results obtained through the simulator attest to the capacity of our solution to effectively generate fixed margin binary matrices up to size$9\times 9$(constraint based on qubits availability). Results obtained from the quantum computer significantly suffer from noise compared to the simulator-based ones; however, we still get exact results with less effectiveness. Our solution and results are publicly available at https://github.com/Niten-luxld-wave-qubo-solver.

DOI
10.1109/qce60285.2024.10277

Related papers

Generating Presence-Absence Matrices by Quantum Annealing

Philippe Codognet

We consider the problem of generating binary matrices with fixed sums for their rows and columns coefficients, i.e. with fixed margins. Such presence-absence (0/1) matrices are widely used in ecological research, for instance to represent the presence or absence of particular species in a particular habitat. Generating random matrices with fixed sums for their rows and their columns is an important issue in order to compare some given matrix presenting field data versus randomly generated matrices with similar characteristics (same sums on rows and columns) in order to test some hypothesis, i.e. when performing null model statistical analysis. We propose to model this problem in QUBO (Quadratic Unconstrained Binary Optimization) in order to solve it by quantum annealing. QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of “quantum-inspired” annealing solvers based on dedicated classical hardware. We present some experimental results achieved on the D-Wave Advantage quantum computer and on the Fixstars Amplify Annealing Engine.

IEEE/ACM International Workshop on Quantum Software Engineering (Q-SE)•May 1, 2023•2 citations

Solving linear systems by quadratic unconstrained binary optimization on D-Wave quantum annealing device

Kyungtaek Jun, Rebecca Conley, Yecheng Huang +2 more

Many quantum computing algorithms are being developed with the advent of quantum computers. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. HHL algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. However, HHL-based algorithms have a lot of limitations in spite of their importance. We address solving linear systems on a D-Wave quantum annealing device. To formulate a quadratic unconstrained binary optimization (QUBO) model for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate this QUBO model on the D-Wave system and discuss the results.

•Apr 9, 2021•6 citations

Convex Non-negative Matrix Factorization Through Quantum Annealing

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

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.

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)•Dec 1, 2021•2 citations

On good encodings for quantum annealer and digital optimization solvers

Alberto Ceselli, Marco Premoli

Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.

Scientific Reports•Apr 6, 2023•10 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

Solving the Traveling Salesman Problem on the D-Wave Quantum Computer

Siddharth Jain

The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.

Frontiers in Physics•Nov 12, 2021•50 citations
Fixed margin binary matrices are used across various scientific fields. However, generating such matrices remains a complicated computational task using classical algorithms since the best algorithm performs in exponential time. In this paper, we model this problem using a Quadratic Unconstrained Binary Optimization (QUBO). Furthermore, we use D-Wave's Quantum Annealing computer and their simulator to generate these matrices. Results obtained through the simulator attest to the capacity of our solution to effectively generate fixed margin binary matrices up to size9×99\times 99×9(constraint based on qubits availability). Results obtained from the quantum computer significantly suffer from noise compared to the simulator-based ones; however, we still get exact results with less effectiveness. Our solution and results are publicly available at https://github.com/Niten-luxld-wave-qubo-solver.
We consider the problem of generating binary matrices with fixed sums for their rows and columns coefficients, i.e. with fixed margins. Such presence-absence (0/1) matrices are widely used in ecological research, for instance to represent the presence or absence of particular species in a particular habitat. Generating random matrices with fixed sums for their rows and their columns is an important issue in order to compare some given matrix presenting field data versus randomly generated matrices with similar characteristics (same sums on rows and columns) in order to test some hypothesis, i.e. when performing null model statistical analysis. We propose to model this problem in QUBO (Quadratic Unconstrained Binary Optimization) in order to solve it by quantum annealing. QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of “quantum-inspired” annealing solvers based on dedicated classical hardware. We present some experimental results achieved on the D-Wave Advantage quantum computer and on the Fixstars Amplify Annealing Engine.
Many quantum computing algorithms are being developed with the advent of quantum computers. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. HHL algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. However, HHL-based algorithms have a lot of limitations in spite of their importance. We address solving linear systems on a D-Wave quantum annealing device. To formulate a quadratic unconstrained binary optimization (QUBO) model for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate this QUBO model on the D-Wave system and discuss the results.
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.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.
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.
The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.