Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Iterative Improvement Method for HHL algorithm for Solving Linear System of Equations
88
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We propose an iterative improvement method for the Harrow-Hassidim-Lloyd (HHL) algorithm to solve a linear system of equations. This is a quantum-classical hybrid algorithm. The accuracy is essential to solve the linear system of equations. However, the accuracy of the HHL algorithm is limited by the number of quantum bits used to express the eigenvalues of the matrix. Our iterative method improves the accuracy of the HHL solutions, and gives higher accuracy which surpasses the accuracy limited by the number of quantum bits. In practical HHL algorithm, a huge number of measurements is required to obtain good accuracy, even if we provide a sufficient number of quantum bits for the eigenvalue expression, since the solution is statistically processed from the measurements. Our improved iterative method can reduce the number of measurements. Moreover, the sign information for each eigenstate of the solution is lost once the measurement is made, although the sign is significant. Therefore, the naive iterative method of the HHL algorithm may slow down, especially, when the solution includes wrong signs. In this paper, we propose and evaluate an improved iterative method for the HHL algorithm that is robust against the sign information loss, in terms of the number of iterations and the computational accuracy.
rate research
Read More
Quantum computers have the potential of solving certain problems exponentially faster than classical computers. Recently, Harrow, Hassidim and Lloyd proposed a quantum algorithm for solving linear systems of equations: given an $Ntimes{N}$ matrix $A$ and a vector $vec b$, find the vector $vec x$ that satisfies $Avec x = vec b$. It has been shown that using the algorithm one could obtain the solution encoded in a quantum state $|x$ using $O(log{N})$ quantum operations, while classical algorithms require at least O(N) steps. If one is not interested in the solution $vec{x}$ itself but certain statistical feature of the solution ${x}|M|x$ ($M$ is some quantum mechanical operator), the quantum algorithm will be able to achieve exponential speedup over the best classical algorithm as $N$ grows. Here we report a proof-of-concept experimental demonstration of the quantum algorithm using a 4-qubit nuclear magnetic resonance (NMR) quantum information processor. For all the three sets of experiments with different choices of $vec b$, we obtain the solutions with over 96% fidelity. This experiment is a first implementation of the algorithm. Because solving linear systems is a common problem in nearly all fields of science and engineering, we will also discuss the implication of our results on the potential of using quantum computers for solving practical linear systems.
We present and experimentally realize a quantum algorithm for efficiently solving the following problem: given an $Ntimes N$ matrix $mathcal{M}$, an $N$-dimensional vector $textbf{emph{b}}$, and an initial vector $textbf{emph{x}}(0)$, obtain a target vector $textbf{emph{x}}(t)$ as a function of time $t$ according to the constraint $dtextbf{emph{x}}(t)/dt=mathcal{M}textbf{emph{x}}(t)+textbf{emph{b}}$. We show that our algorithm exhibits an exponential speedup over its classical counterpart in certain circumstances. In addition, we demonstrate our quantum algorithm for a $4times4$ linear differential equation using a 4-qubit nuclear magnetic resonance quantum information processor. Our algorithm provides a key technique for solving many important problems which rely on the solutions to linear differential equations.
This paper introduces and analyzes a preconditioned modified of the Hermitian and skew-Hermitian splitting (PMHSS). The large sparse continuous Sylvester equations are solved by PMHSS iterative algorithm based on nonHermitian, complex, positive definite/semidefinite, and symmetric matrices. We prove that the PMHSS is converged under suitable conditions. In addition, we propose an accelerated PMHSS method consisting of two preconditioned matrices and two iteration parameters {alpha}, b{eta}. Theoretical analysis showed that the convergence speed of the accelerated PMHSS is faster compared to the PMHSS. Also, the robustness and efficiency of the proposed two iterative algorithms were demonstrated in numerical experiments.
We present a novel application of the HHL (Harrow-Hassidim-Lloyd) algorithm -- a quantum algorithm solving systems of linear equations -- in solving an open problem about quantum random walks, namely computing hitting (or absorption) probabilities of a general (not only Hadamard) one-dimensional quantum random walks with two absorbing boundaries. This is achieved by a simple observation that the problem of computing hitting probabilities of quantum random walks can be reduced to inverting a matrix. Then a quantum algorithm with the HHL algorithm as a subroutine is developed for solving the problem, which is faster than the known classical algorithms by numerical experiments.
Recently, it is shown that quantum computers can be used for obtaining certain information about the solution of a linear system Ax=b exponentially faster than what is possible with classical computation. Here we first review some key aspects of the algorithm from the standpoint of finding its efficient quantum circuit implementation using only elementary quantum operations, which is important for determining the potential usefulness of the algorithm in practical settings. Then we present a small-scale quantum circuit that solves a 2x2 linear system. The quantum circuit uses only 4 qubits, implying a tempting possibility for experimental realization. Furthermore, the circuit is numerically simulated and its performance under different circuit parameter settings is demonstrated.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
