13
$\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$
  • $\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$ – Sanchayan Dutta Jul 11 '18 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$ – Nelimee Jul 11 '18 at 15:29
3
+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$
  • 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$ – Nelimee Jul 20 '18 at 12:09
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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