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. The Harrow-Hassidim-Lloyd algorithm is an algorithm that can solve linear equations in a gate model quantum computer. Still, it is constrained by the use of quantum RAM and the size limit of the matrix according to the total number of qubits in the quantum computer. Recently, Jun and Lee developed a QUBO model for solving linear systems and eigenvalue problems in the quantum computer. However, even though their model uses 2048 qubits, the number of qubits for variables that can be used for the problem is only 64. To solve this problem, we introduce an algorithm that can be used by dividing the size of the entire domain according to the number of qubits. We also form a QUBO model related to each subregion.
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. The Harrow-Hassidim-Lloyd algorithm is an algorithm that can solve linear equations in a gate model quantum computer. Still, it is constrained by the use of quantum RAM and the size limit of the matrix according to the total number of qubits in the quantum computer. Recently, Jun and Lee developed a QUBO model for solving linear systems and eigenvalue problems in the quantum computer. However, even though their model uses 2048 qubits, the number of qubits for variables that can be used for the problem is only 64. To solve this problem, we introduce an algorithm that can be used by dividing the size of the entire domain according to the number of qubits. We also form a QUBO model related to each subregion.
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.
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.
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.
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.
Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics.
The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.