Quantum algorithm for linear systems of equations

The quantum algorithm for linear systems of equations, also called HHL algorithm, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm published in 2008 for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations. The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm, Grover's search algorithm, and the quantum fourier transform. Provided the linear system is sparse and has a low condition number , and that the user is interested in the result of a scalar measurement on the solution vector, instead of the values of the solution vector itself, then the algorithm has a runtime of , where is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in (or for positive semidefinite matrices). An implementation of the quantum algorithm for linear systems of equations was first demonstrated in 2013 by Cai et al., Barz et al. and Pan et al. in parallel. The demonstrations consisted of simple linear equations on specially designed quantum devices. The first demonstration of a general-purpose version of the algorithm appeared in 2018 in the work of Zhao et al. Due to the prevalence of linear systems in virtually all areas of science and engineering, the quantum algorithm for linear systems of equations has the potential for widespread applicability. The HHL algorithm tackles the following problem: given a Hermitian matrix and a unit vector , prepare the quantum state corresponding to the vector that solves the linear system . More precisely, the goal is to prepare a state whose amplitudes equal the elements of . This means, in particular, that the algorithm cannot be used to efficiently retrieve the vector itself. It does, however, allow to efficiently compute expectation values of the form for some observable .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (86)

Related people (21)

Related units (14)

Related concepts (2)

Related courses (4)

Related lectures (69)

COM-309: Introduction to quantum information processing

Information is processed in physical devices. In the quantum regime the concept of classical bit is replaced by the quantum bit. We introduce quantum principles, and then quantum communications, key d

PHYS-641: Quantum Computing

After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament

CS-308: Introduction to quantum computation

The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

Quantum Fourier transform

In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith.

Quantum algorithm

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer.

Shor's algorithm: factoring integers CS-308: Introduction to quantum computation

Covers the basics of Shor's algorithm for factoring integers and the steps involved in the quantum algorithm.

Deutsch and Josza Problem CS-308: Introduction to quantum computation

Covers the Deutsch and Josza problem in quantum computation, focusing on boolean functions and oracles.

Quantum Algorithms: Shor Algorithm CS-308: Introduction to quantum computation

Covers the analysis of measurements in the context of the Shor algorithm.

Quantum radio astronomy: Data encodings and quantum image processing

Jean-Paul Richard Kneib, Emma Elizabeth Tolley, Stefano Corda

We explore applications of quantum computing for radio interferometry and astronomy using recent developments in quantum image processing. We evaluate the suitability of different quantum image representations using a toy quantum computing image reconstruc ...

Elsevier2024

The complexity of quantum support vector machines

Gian Florin Gentinetta, Stefan Woerner

Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any known classical algorithm for certain data sets. The training of such models c ...

Wien2024

Scalable Quantum Algorithms for Noisy Quantum Computers

Julien Sebastian Gacon

Quantum computing not only holds the potential to solve long-standing problems in quantum physics, but also to offer speed-ups across a broad spectrum of other fields. Access to a computational space that incorporates quantum effects, such as superposition ...

EPFL2024