What could be the possible future applications for HHL algorithm?

Question

^{Note on the vocabulary: the word "hamiltonian" is used in this question to speak about hermitian matrices.}

---

The HHL algorithm seems to be an active subject of research in the field of quantum computing, mostly because it solve a very important problem which is finding the solution of a linear system of equations.

According to the original paper Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009) and some questions asked on this site

• Quantum phase estimation and HHL algorithm - knowledge on eigenvalues required?
• Quantum algorithm for linear systems of equations (HHL09): Step 2 - Preparation of the initial states $\vert \Psi_0 \rangle$ and $\vert b \rangle$

the HHL algorithm is limited to some specific cases. Here is a summary (that may be incomplete!) of the characteristics of the HHL algorithm:

---

HHL algorithm

The HHL algorithm solves a linear system of equation $$A \vert x \rangle = \vert b \rangle$$ with the following limitations:

Limitations on $A$:

• $A$ needs to be Hermitian (and only Hermitian matrix works, see this discussion in the chat).
• $A$'s eigenvalues needs to be in $[0,1)$ (see Quantum phase estimation and HHL algorithm - knowledge on eigenvalues required?)
• $e^{iAt}$ needs to be efficiently implementable. At the moment the only known matrices that satisfy this property are:
  • local hamiltonians (see Universal Quantum Simulators (Lloyd, 1996)).
  • $s$-sparse hamiltonians (see Adiabatic Quantum State Generation and Statistical Zero Knowledge (Aharonov & Ta-Shma, 2003)).

Limitations on $\vert b \rangle$:

• $\vert b \rangle$ should be efficiently preparable. This is the case for:
  1. Specific expressions of $\vert b \rangle$. For example the state $$\vert b \rangle = \bigotimes_{i=0}^{n} \left( \frac{\vert 0 \rangle + \vert 1 \rangle}{\sqrt{2}} \right)$$ is efficiently preparable.
  2. $\vert b \rangle$ representing the discretisation of an efficiently integrable probability distribution (see Creating superpositions that correspond to efficiently integrable probability distributions (Grover & Rudolph, 2002)).

Limitations on $\vert x \rangle$ (output):

• $\vert x \rangle$ cannot be recovered fully by measurement. The only information we can recover from $\vert x \rangle$ is a "general information" ("expectation value" is the term employed in the original HHL paper) such as $$\langle x\vert M\vert x \rangle$$

---

Question: Taking into account all of these limitations and imagining we are in 2050 (or maybe in 2025, who knows?) with fault-tolerant large-scale quantum chips (i.e. we are not limited by the hardware), what real-world problems could HHL algorithm solve (including problems where HHL is only used as a subroutine)?

I am aware of the paper Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target (Scherer, Valiron, Mau, Alexander, van den Berg & Chapuran, 2016) and of the corresponding implementation in the Quipper programming language and I am searching for other real-world examples where HHL would be applicable in practice. I do not require a published paper, not even an unpublished paper, I just want to have some examples of real-world use-cases.

---

EDIT:

Even if I am interested in every use-case, I would prefer some examples where HHL is directly used, i.e. not used as a subroutine of an other algorithm.

I am even more interested in examples of linear systems resulting of the discretisation of a differential operator that could be solved with HHL.

But let me emphasise one more time I'm interested by every use-case (subroutines or not) you know about.

Answer 1

A couple years ago it was shown in Quantum algorithms and the finite element method by Montanaro and Pallister that the HHL algorithm could be applied to the Finite Element Method (FEM) which is a "technique for efficiently finding numerical approximations to the solutions of boundary value problems (BVPs) for partial differential equations, based on discretizing the parameter space via a finite mesh".

They showed that within this context HHL could be used to achieve (perhaps at most) a polynomial speedup over the standard classical algorithm (the "conjugate gradient method").

With respect to real-world use-cases, they state that

"One example application is any dynamical problem involving $n$ bodies, which implies solving a PDE defined over a configuration space of dimension 2n. Also, there may be a significant advantage for problems in mathematical finance; for example, pricing multiasset options requires solving the Black-Scholes equation over a domain with dimension given by the number of assets"

This opens up a whole area of potential use-cases for HHL (assuming conditions on the sparsity of $A$ can be satisfied).

Answer 2

Rebentrost et al. recently used the HHL09 algorithm in their A Quantum Hopfield Neural Network (2018) paper, for optimization of the Hopfield network's energy function.

Basically, if the Lagrangian (which is used to optimize the network energy $E = -\frac{1}{2}x^{T}Wx + \theta^Tx$ given the constraint $Px - x^{\text{(inc)}} = 0$) is:

$$\mathcal{L} = -\frac{1}{2}x^{T}Wx + \theta^Tx - \lambda^T (Px - x^{\text{(inc)}}) + \frac{\gamma}{2}x^T x$$ then the optimization equations $\frac{\partial \mathcal{L}}{\partial x} = 0$ and $\frac{\partial \mathcal{L}}{\partial \lambda} = 0$ can be written in the form $A \mathbf{v} = \mathbf{w}$. Note that the $\gamma$ in the expression is the regularization parameter. We need to find $\mathbf{v}$ which extremizes network energy subject to the constraint $Px = x^{(\text{inc})}$ and thus, we need a matrix inversion technique. In the paper they've done exactly that and for the matrix inversion they utilized the HHL09 algorithm. See page 4 of the paper.

---

In short, I believe that once we have quantum computers with a sufficiently large number of qubits and decoherence time, the HHL algorithm is going to be one of the most useful subroutines for any quantum machine learning algorithm (since almost all machine learning and neural network algorithms involve some form of "gradient descent" or "optimization").