30
$\begingroup$

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

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$:

Limitations on $\vert b \rangle$:

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.

$\endgroup$
2
  • $\begingroup$ You mention that you want some examples where HHL is "directly used". I am not very clear on what you mean by that. I do know some algorithms (which can potentially have practical uses) in which HHL is one of the primary steps, but surely not the only step. Would something like recognizing genetic sequences using HHL as one of the primary steps (subject to all the constraints you mentioned), be a suitable answer? The other primary steps mainly involve Hamiltonian simulation and state preparation. $\endgroup$ Jul 11, 2018 at 15:25
  • $\begingroup$ I would prefer some examples where HHL is directly used. It means that the problem can be directly formulated as a linear system of equation to solve. This is the case when solving differential equations: we discretise the equation and solve the discretised problem which is most of the time a sparse linear system. But other examples are welcomed. $\endgroup$ Jul 11, 2018 at 15:29

3 Answers 3

10
+50
$\begingroup$

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).

$\endgroup$
4
  • 2
    $\begingroup$ I don't have the time to read the article right now, but from the abstract it seems that the paper is interesting. I read quickly the section III and could not find any references to the eigenvalues of $M$ but the other points are either trivial ($M$ is hermitian), covered in other articles (hamiltonian simulation of $s$-sparse matrix with $s=3$) or covered in the article (state preparation). I did not know about this article, and the application is of particular interest for me (finite-elements is closely linked with PDEs). You have my upvote (and probably the bounty) :) $\endgroup$ Jul 20, 2018 at 12:09
  • $\begingroup$ Hey Nelimee, if you found the answer useful and feel that it answered your question, please feel free to select it as the accepted answer. Thanks! :) $\endgroup$ Mar 19, 2020 at 5:46
  • 1
    $\begingroup$ Hi! Your answer is the best one yet, but I was expecting a list more than one specific application. Since the time I asked this question I advanced quite a bit in my research (and moved on a different subject), so I will try to provide a synthetic answer of all the applications I found, including yours, when I will find the time! Nevertheless, I was not aware of the application you gave me at the time being, so thanks again! $\endgroup$ Mar 29, 2020 at 12:20
  • $\begingroup$ Cool! I would be very interested in that list! :) $\endgroup$ Mar 29, 2020 at 15:17
5
$\begingroup$

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").

$\endgroup$
2
  • $\begingroup$ But don't they need to obtain the full vector $\mathbf{v}$ in A Quantum Hopfield Neural Network (2018) to be able to extremize the network energy (see also comments in section VIII)? The HHL algorithm does not give this in polynomial time (only a function of the obtained state). $\endgroup$
    – wondering
    Jul 29, 2023 at 11:33
  • $\begingroup$ In a recent work A quantum algorithm for track reconstruction... they seem to have the same problem: "The measurement of all the amplitudes of the final state, at this point, would require at least 𝑁 repetitions of the algorithm, voiding the exponential advantage. One can employ quantum post-processing techniques on the final state and measure the expectation value of an observable ⟨𝑆|O|𝑆⟩. The identification of such an observable is currently out of the scope of this work, and state-vector analyses have been performed using a quantum simulator." $\endgroup$
    – wondering
    Aug 13, 2023 at 11:30
1
$\begingroup$

There has been a recent work on end-to-end use of HHL based (i.e., Quantum Linear system problem aka, QLSA) solvers.

This is in the context of gradient-based (say, stochastic GD) training for certain classical neural networks.

Source: Liu, J., Liu, M., Liu, JP. et al. Towards provably efficient quantum algorithms for large-scale machine-learning models. Nat Commun 15, 434 (2024)

Now, I will briefly mention how they avoid three caveats mentioned in the question by @Adrien Suau.

Their key hypothesis is that Sparse neural networks can be resourceful in some important Machine learning tasks. (Note: Sparse implies that most of the weights in the network are zero.)

Now they proved that training such (sparse) network is equivalent to solve linear system problem.

  1. In this context $|b\rangle$ would be initial weight vector. If the network is sparse, then there exists an efficient way to upload the vector/state.

  2. The matrix A will also be the sparse matrix. I am not going into much detail. But the key idea is the linearisation of the non-linear system (i.e., solving the optimisation problem via Gradient descent) will give you such sparse matrix A.

  3. The algorithm will give you the solution weight as a quantum state $|x\rangle$. This could be downloaded efficiently as it will also be sparse. You plug the downloaded vector back into the classical network.

Few comments:

Indeed, there are subtle caveats to it. Like, the early phase training is more amenable to this approach. I am leaving these details to be further explored by the reader.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.