Applications of HHL's algorithm for solving linear equations

Question

In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a problems which would classically use the solutions of the linear equations?

Answer 1

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state in Harrow, Hassidim, Lloyd's algorithm does not immediately give you the classical solution $x$ of the system but a quantum states that encodes $x$ in its amplitudes; it is hard to extract the "explicit information" $x$ from that state.

However there are indeed interesting applications of the HHL linear systems algorithm as a subroutine to solve other problems, using the output of the quantum algorithm in "more quantum" ways.

• The HHL algorithm can be readily applied to compute expectation values $\langle x| M | x \rangle$ of a poly-size Hermitian operator $M$.

• Dominic Berry gave a generalized version of hte HHL algorithm to solve linear systems of the differential equations. The HHL algorithm is used as a subroutine there. (Berry's algorithm uses HHL's as a subroutine.) The final solution of Berry's algorithm is also encoded in the amplitudes of a quantum state.

• Wiebe, Braun, Lloyd gave an algorithm based on HHL's that can be used to find the optimal least-square fit to some discrete data. Although the output of that algorithm is again encoded in some quantum amplitudes, the authors also gave a quantum algorithm to asses the quality of an optimal least-square fit in a quantum computer, and there the output is classical. For certain types of fit functions, their quantum algorithm outperforms classical ones.

• Recently, HHL's algorithm has been employed in Lloyd-Mohseni-Rebentrost's quantum algorithm for machine learning.

Note that, in all of these algorithms, quantum manipulations of the output state of the HHL's algorithm are performed, instead of classical ones. This is similar to the case of the quantum Fourier transform (QFT), which can be computed exponentially faster in a quantum computer as a quantum gate than the classical discrete Fourier transform. We cannot use this fact in quantum algorithms to Fourier-transform classical functions faster. However, the QFT has remarkable applications in Shor's factoring algorithm and quantum phase estimation.