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.10084

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

Sun Woo Park, Kyungtaek Jun

Published Nov 19, 2021• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2111.10084

Related papers

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

Sun Woo Park, Hyunju Lee, Byung Chun Kim +2 more

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.

arXiv:2111.00747•International Conference on Information and Communication Technology Convergence (ICTC)•Oct 20, 2021•1 citation

QUBO formulations for a system of linear equations

Kyungtaek Jun

With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in modern science and engineering. The Harrow Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. The algorithm was difficult to apply to general linear equations because it required various conditions for the matrix. In this paper, we introduce a new algorithm that can be applied to all linear systems. For a given general square matrix A∈Rn×n and a vector b→∈Rn, we will find quadratic unconstrained binary optimization (QUBO) models for a vector x→∈Rn that satisfies Ax→=b→. To formulate QUBO models for solving linear systems, we made use of a linear least-square problem with binary representation of the solution. We validated those QUBO models on the D-Wave system and discussed 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 the D-Wave system.

Results in Control and Optimization•Feb 5, 2024•25 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•29 citations

QUBO formulations for numerical quantum computing

Kyungtaek Jun

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 science and engineering. The Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. For a given n by n matrix A and a vector b, we will find unconstrained binary optimization (QUBO) models for a vector x 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 the D-Wave system.

arXiv:2106.10819•Jun 21, 2021•9 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

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•504 citations
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.
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.
With the advent of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in modern science and engineering. The Harrow Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. The algorithm was difficult to apply to general linear equations because it required various conditions for the matrix. In this paper, we introduce a new algorithm that can be applied to all linear systems. For a given general square matrix A∈Rn×n and a vector b→∈Rn, we will find quadratic unconstrained binary optimization (QUBO) models for a vector x→∈Rn that satisfies Ax→=b→. To formulate QUBO models for solving linear systems, we made use of a linear least-square problem with binary representation of the solution. We validated those QUBO models on the D-Wave system and discussed 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 the D-Wave system.
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 of quantum computers, many quantum computing algorithms are being developed. Solving linear systems is one of the most fundamental problems in almost all science and engineering. The Harrow-Hassidim-Lloyd algorithm, a monumental quantum algorithm for solving linear systems on gate model quantum computers, was invented and several advanced variations have been developed. For a given n by n matrix A and a vector b, we will find unconstrained binary optimization (QUBO) models for a vector x 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 the D-Wave system.
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.
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.