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

Results in Control and Optimization

QUBO formulations for a system of linear equations

Kyungtaek Jun

Published Feb 5, 2024• 25 citations
Publisher

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

DOI
10.1016/j.rico.2024.100380

Related papers

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

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.

arXiv:2202.07692•Scientific Reports•Mar 14, 2025•7 citations

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 Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits

Hyunju Lee, Kyungtaek Jun

In the era of quantum computing, the emergence of quantum computers and subsequent advancements have led to the development of various quantum algorithms capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. Notably, the hybrid solver provided by the D-wave system can leverage up to two million variables. By exploiting this technology, quantum optimization models based on quadratic unconstrained binary optimization (QUBO) have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The formulation of QUBO typically involves straightforward arithmetic operations, presenting significant potential for future advancements as quantum computers continue to evolve. A prevalent approach in these developments is the binarization of variables and their mapping to multiple qubits. These methods increase the required number of qubits as the range and precision of each variable increase. Determining the optimal value of a QUBO model becomes more challenging as the number of qubits increases. Furthermore, the accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. Problems arise because the qubits yielding the optimal value for the QUBO model may not necessarily correspond to the solution of a given problem. To address these issues, we propose a new iterative algorithm. The novel algorithm sequentially progresses from the highest to the lowest exponent in binarizing each number, whereby each number is calculated using two variables, and the accuracy can be computed up to a maximum of 16 decimal places.

arXiv:2411.16138•Nov 25, 2024•2 citations

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
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.
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.
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.
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.
In the era of quantum computing, the emergence of quantum computers and subsequent advancements have led to the development of various quantum algorithms capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. Notably, the hybrid solver provided by the D-wave system can leverage up to two million variables. By exploiting this technology, quantum optimization models based on quadratic unconstrained binary optimization (QUBO) have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The formulation of QUBO typically involves straightforward arithmetic operations, presenting significant potential for future advancements as quantum computers continue to evolve. A prevalent approach in these developments is the binarization of variables and their mapping to multiple qubits. These methods increase the required number of qubits as the range and precision of each variable increase. Determining the optimal value of a QUBO model becomes more challenging as the number of qubits increases. Furthermore, the accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. Problems arise because the qubits yielding the optimal value for the QUBO model may not necessarily correspond to the solution of a given problem. To address these issues, we propose a new iterative algorithm. The novel algorithm sequentially progresses from the highest to the lowest exponent in binarizing each number, whereby each number is calculated using two variables, and the accuracy can be computed up to a maximum of 16 decimal places.
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.