© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

IEEE/ACM International Workshop on Quantum Software Engineering (Q-SE)

Generating Presence-Absence Matrices by Quantum Annealing

Philippe Codognet

Published May 1, 2023• 2 citations

Abstract

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.

DOI: 10.1109/q-se59154.2023.00008

Related papers

Generation of Fixed Margin Binary Matrices Using Quantum Annealing

Alexandre Bergerault, Daniel Fortunato, Rui Abreu

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

Encoding the At-Most-One Constraint for QUBO and Quantum Annealing: Experiments with the N-Queens problem

Philippe Codognet

We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•9 citations

Quantum and Digital Annealing for the Quadratic Assignment Problem

Philippe Codognet, Daniel Díaz, Salvador Pinto Abreu

The Quadratic Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware solvers based on quantum or quantum-inspired annealing (D-Wave, Fujitsu Digital Annealing Unit and Fixstars Amplify Annealing Engine). We present performance result for these implementations and compare them with well established metaheuristic solvers on classical hardware, such as Robust Tabu Search and External Optimization.

IEEE International Conference on Quantum Software (QSW)•Jul 1, 2022•12 citations

Constraint Solving by Quantum Annealing

Philippe Codognet

We present experiments in solving combinatorial optimization and constraint satisfaction problems by means of Quantum Annealing. We describe how to model classic constraint problems such as N-queens and Magic Square as well as hard combinatorial problems such as the Costas Array Problem or the Quadratic Assignment Problem in terms of QUBO (Quadratic Unconstrained Binary Optimization). QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of the ”quantum-inspired” but classical devices such as Fujitsu’s Digital Annealing Unit or Hitachi’s CMOS Annealing Machine. We present preliminary results for solving these combinatorial optimization and constraint satisfaction problems by implementation on the D-Wave quantum computer.

International Conference on Parallel Processing Workshops (ICPPW)•Aug 9, 2021•8 citations

Benchmarking Quantum Computing for Combinatorial Optimization

Nathan Kittichaikoonkij, Nutthapat Pongtanyavichai, Poopha Suwananek +2 more

Quantum computers can be much faster than any classical computers in solving a certain class of problems. One of the interesting problems is the combinatorial optimization problem, which is a challenge for classical computer systems. We encode these problems into the Quadratic Unconstrained Binary Optimization (QUBO) format and then solve them with quantum solvers. In this study, we compare the performance of D-Wave’s quantum annealing system with classical solvers, namely, Gurobi and Fixstars. We demonstrate the current capabilities of the D-Wave system.

International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON)•May 20, 2025•0 citations

A Constraint Programming Approach for QUBO Solving and Quantum Annealing

Philippe Codognet

Quantum Annealing is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). Quantum computers such as the D-Wave systems are indeed implementing those ideas in hardware, as well as "quantum-inspired" devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. All those systems use the same modeling language: Quadratic Unconstrained Binary Optimization (QUBO). However, QUBO is a low-level language and for modeling combinatorial problems such as constraint satisfaction and constrained optimization problems, we need to introduce higher-level abstractions in order to define complex constraints.

International Conference on Art, Science, and Engineering of Programming (<Programming>)•Mar 11, 2024•2 citations

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.

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.

We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.

The Quadratic Assignment Problem is a a classical constrained optimization problem used to model many real-life applications. We present experiments in solving the Quadratic Assignment Problem by means of Quantum Annealing and Quantum-inspired Annealing. We describe how to model this classical combinatorial problem in terms of QUBO (Quadratic Unconstrained Binary optimization) for implementing it on hardware solvers based on quantum or quantum-inspired annealing (D-Wave, Fujitsu Digital Annealing Unit and Fixstars Amplify Annealing Engine). We present performance result for these implementations and compare them with well established metaheuristic solvers on classical hardware, such as Robust Tabu Search and External Optimization.

We present experiments in solving combinatorial optimization and constraint satisfaction problems by means of Quantum Annealing. We describe how to model classic constraint problems such as N-queens and Magic Square as well as hard combinatorial problems such as the Costas Array Problem or the Quadratic Assignment Problem in terms of QUBO (Quadratic Unconstrained Binary Optimization). QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of the ”quantum-inspired” but classical devices such as Fujitsu’s Digital Annealing Unit or Hitachi’s CMOS Annealing Machine. We present preliminary results for solving these combinatorial optimization and constraint satisfaction problems by implementation on the D-Wave quantum computer.

Quantum computers can be much faster than any classical computers in solving a certain class of problems. One of the interesting problems is the combinatorial optimization problem, which is a challenge for classical computer systems. We encode these problems into the Quadratic Unconstrained Binary Optimization (QUBO) format and then solve them with quantum solvers. In this study, we compare the performance of D-Wave’s quantum annealing system with classical solvers, namely, Gurobi and Fixstars. We demonstrate the current capabilities of the D-Wave system.

Quantum Annealing is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). Quantum computers such as the D-Wave systems are indeed implementing those ideas in hardware, as well as "quantum-inspired" devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. All those systems use the same modeling language: Quadratic Unconstrained Binary Optimization (QUBO). However, QUBO is a low-level language and for modeling combinatorial problems such as constraint satisfaction and constrained optimization problems, we need to introduce higher-level abstractions in order to define complex constraints.