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:2111.00747 · International Conference on Information and Communication Technology Convergence (ICTC)

On the application of matrix congruence to QUBO formulations for systems of linear equations

Sun Woo Park, Hyunju Lee, Byung Chun Kim, Youngho Woo, Kyungtaek Jun

Published Oct 20, 2021• 1 citation
arXivHTMLPDF

Abstract

Recent studies on quantum computing algorithms focus on excavating features of quantum computers which have potential for contributing to computational model enhancements. Among various approaches, quantum annealing methods effectively parallelize quadratic unconstrained binary optimization (QUBO) formulations of systems of linear equations. In this paper, we simplify these formulations by exploiting congruence of real symmetric matrices to diagonal matrices. We further exhibit computational merits of the proposed QUBO models, which can outperform classical algorithms such as QR and SVD decomposition.

DOI
10.1109/ictc52510.2021.9620851

Related papers

On the application of Sylvester's law of inertia to QUBO formulations for systems of linear equations

Sun Woo Park, Kyungtaek Jun

Previous research on quantum annealing methods focused on effectively modeling systems of linear equations by utilizing quadratic unconstrained binary optimization (QUBO) formulations. These studies take part in enhancing quantum computing algorithms, which extract properties of quantum computers suitable for improving classical computational models. In this paper, we further develop the QUBO formulations of systems of linear equations by applying Sylvester's law of inertia, which explores matrix congruence of any real symmetric matrix to a diagonal matrix. We expect that the proposed algorithm can effectively implement higher dimensional systems of linear equations on a quantum computer. Further experimental verification of the proposed QUBO models as well as their comparisons to classical algorithms are also made.

arXiv:2111.10084•Nov 19, 2021•0 citations

Algorithmic QUBO formulations for k -SAT and hamiltonian cycles

Jonas Nüßlein, Thomas Gabor, Claudia Linnhoff–Popien +1 more

Quadratic Unconstrained Binary Optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO formulations for k-SAT and Hamiltonian Cycles that scale significantly better than existing approaches. For k-SAT we reduce the growth of the QUBO matrix from O(k) to O(log(k)). For Hamiltonian Cycles the matrix no longer grows quadratically in the number of nodes, as currently, but linearly in the number of edges and logarithmically in the number of nodes.

arXiv:2204.13539•Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•18 citations

Range dependent Hamiltonian algorithms for numerical QUBO formulation

Hyunju Lee, Kyungtaek Jun

With the advent and development of quantum computers, various quantum algorithms that can solve linear equations and eigenvalues faster than classical computers have been developed. In particular, a hybrid solver provided by D-Wave's Leap quantum cloud service can utilize up to two million variables. Using this technology, quadratic unconstrained binary optimization (QUBO) models have been proposed for linear systems, eigenvalue problems, RSA cryptosystems, and computed tomography (CT) image reconstructions. Generally, QUBO formulation is obtained through simple arithmetic operations, which offers great potential for future development with the progress of quantum computers. A common method here was to binarize the variables and match them to multiple qubits. To achieve the accuracy of 64 bits per variable, 64 logical qubits must be used. Finding the global minimum energy in quantum optimization becomes more difficult as more logical qubits are used; thus, a quantum parallel computing algorithm that can create and compute multiple QUBO models is introduced here. This new algorithm divides the entire domain each variable can have into multiple subranges to generate QUBO models. This paper demonstrates the superior performance of this new algorithm particularly when utilizing an algorithm for binary variables.

Scientific Reports•Mar 14, 2025•1 citation

A Tutorial on Formulating and Using QUBO Models

Fred Glover, Gary A. Kochenberger, Yu Du

The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.

arXiv:1811.11538•Nov 13, 2018•164 citations

Quantum solution for solving the Bin Packing problem

Samuel Deleplanque, Amélia Durbec, Amina El Yaagoubi

Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.

International Conference on Control, Decision and Information Technologies (CoDIT)•Jul 1, 2024•1 citation

QUBO formulations for a system of linear equations

Kyungtaek Jun

Abstract With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. For a given square matrix A∈R(n×n) and a vector b∈R(n), we will find unconstrained binary optimization (QUBO) models for a vector x∈R(n) that satisfies Ax=b. To formulate QUBO models for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate those QUBO models on the D-Wave system and discuss the results. For a simple system, We provide a python code to calculate the matrix characterizing the relationship between the variables and to print the test code that can be used directly in D-Wave system.

Results in Control and Optimization•Feb 5, 2024•20 citations
Recent studies on quantum computing algorithms focus on excavating features of quantum computers which have potential for contributing to computational model enhancements. Among various approaches, quantum annealing methods effectively parallelize quadratic unconstrained binary optimization (QUBO) formulations of systems of linear equations. In this paper, we simplify these formulations by exploiting congruence of real symmetric matrices to diagonal matrices. We further exhibit computational merits of the proposed QUBO models, which can outperform classical algorithms such as QR and SVD decomposition.
Previous research on quantum annealing methods focused on effectively modeling systems of linear equations by utilizing quadratic unconstrained binary optimization (QUBO) formulations. These studies take part in enhancing quantum computing algorithms, which extract properties of quantum computers suitable for improving classical computational models. In this paper, we further develop the QUBO formulations of systems of linear equations by applying Sylvester's law of inertia, which explores matrix congruence of any real symmetric matrix to a diagonal matrix. We expect that the proposed algorithm can effectively implement higher dimensional systems of linear equations on a quantum computer. Further experimental verification of the proposed QUBO models as well as their comparisons to classical algorithms are also made.
Quadratic Unconstrained Binary Optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO formulations for k-SAT and Hamiltonian Cycles that scale significantly better than existing approaches. For k-SAT we reduce the growth of the QUBO matrix from O(k) to O(log(k)). For Hamiltonian Cycles the matrix no longer grows quadratically in the number of nodes, as currently, but linearly in the number of edges and logarithmically in the number of nodes.
With the advent and development of quantum computers, various quantum algorithms that can solve linear equations and eigenvalues faster than classical computers have been developed. In particular, a hybrid solver provided by D-Wave's Leap quantum cloud service can utilize up to two million variables. Using this technology, quadratic unconstrained binary optimization (QUBO) models have been proposed for linear systems, eigenvalue problems, RSA cryptosystems, and computed tomography (CT) image reconstructions. Generally, QUBO formulation is obtained through simple arithmetic operations, which offers great potential for future development with the progress of quantum computers. A common method here was to binarize the variables and match them to multiple qubits. To achieve the accuracy of 64 bits per variable, 64 logical qubits must be used. Finding the global minimum energy in quantum optimization becomes more difficult as more logical qubits are used; thus, a quantum parallel computing algorithm that can create and compute multiple QUBO models is introduced here. This new algorithm divides the entire domain each variable can have into multiple subranges to generate QUBO models. This paper demonstrates the superior performance of this new algorithm particularly when utilizing an algorithm for binary variables.
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.
Abstract With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. For a given square matrix A∈R(n×n) and a vector b∈R(n), we will find unconstrained binary optimization (QUBO) models for a vector x∈R(n) that satisfies Ax=b. To formulate QUBO models for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate those QUBO models on the D-Wave system and discuss the results. For a simple system, We provide a python code to calculate the matrix characterizing the relationship between the variables and to print the test code that can be used directly in D-Wave system.