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
2
+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$
  • $\begingroup$ I didn't downvote, but the question asks for specific instances where the matrix and vector satisfy the restrictions of the HHL algorithm. For example you say "this opens up a whole area of potential use-cases for HHL" but what is a useful example where A and b satisfy the HHL conditions? $\endgroup$ – user1271772 Jul 19 '18 at 18:42
  • $\begingroup$ Where did it ask for a specific instance? As far as I can see they only asked for a real-world problem to solve, which I gave by the way of FEM and further an instance where FEM is applied, I.e Black-Sholes $\endgroup$ – SLesslyTall Jul 19 '18 at 18:48
  • $\begingroup$ "Question: Taking into account all of these limitations..." means you have to take into account that A and b cannot just be any matrix and any vector. Otherwise the question is too easy. "Black-Sholes differential equation" is one application, so is any other differential equation. See the two deleted answers to this question and the reasons they deleted those answers (if you're able to). $\endgroup$ – user1271772 Jul 19 '18 at 18:52
  • 1
    $\begingroup$ The whole point of the paper that I linked was that they ensured that both A and b used by FEM were sufficient to satisfy the HHL conditions to ensure a quantum speedup--not just any old system of simultaneous equations. The reason Black-Sholes is referenced is that it is is solvable using FEM as described by the paper. $\endgroup$ – SLesslyTall Jul 19 '18 at 18:57
  • 1
    $\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$

The Wikipedia page lists a few applications of the HHL algorithm.

Quantum computers are devices that harness quantum mechanics to perform computations in ways that classical computers cannot. For certain problems, quantum algorithms supply exponential speedups over their classical counterparts, the most famous example being Shor's factoring algorithm. Few such exponential speedups are known, and those that are (such as the use of quantum computers to simulate other quantum systems) have so far found limited use outside the domain of quantum mechanics. This algorithm provides an exponentially faster method of estimating features of the solution of a set of linear equations, which is a problem ubiquitous in science and engineering, both on its own and as a subroutine in more complex problems.

Electromagnetic scattering

Clader et al. provided a preconditioned version of the linear systems algorithm that provided two advances. First, they demonstrated how a preconditioner could be included within the quantum algorithm. This expands the class of problems that can achieve the promised exponential speedup since the scaling of HHL and the best classical algorithms are both polynomials in the condition number. The second advance was the demonstration of how to use HHL to solve for the radar cross-section of a complex shape. This was one of the first end-to-end examples of how to use HHL to solve a concrete problem exponentially faster than the best known classical algorithm. [9]

Linear differential equation solving

Dominic Berry proposed a new algorithm for solving linear time-dependent differential equations as an extension of the quantum algorithm for solving linear systems of equations. Berry provides an efficient algorithm for solving the full-time evolution under sparse linear differential equations on a quantum computer.[10]

Least-squares fitting

Wiebe et al. provide a new quantum algorithm to determine the quality of a least-squares fit in which a continuous function is used to approximate a set of discrete points by extending the quantum algorithm for linear systems of equations. As the amount of discrete points increases, the time required to produce a least-squares fit using even a quantum computer running a quantum state tomography algorithm becomes very large. Wiebe et al. find that in many cases, their algorithm can efficiently find a concise approximation of the data points, eliminating the need for the higher-complexity tomography algorithm.[11]

Machine learning and big data analysis

Machine learning is the study of systems that can identify trends in data. Tasks in machine learning frequently involve manipulating and classifying a large volume of data in high-dimensional vector spaces. The runtime of classical machine learning algorithms is limited by a polynomial dependence on both the volume of data and the dimensions of the space. Quantum computers are capable of manipulating high-dimensional vectors using tensor product spaces are thus the perfect platform for machine learning algorithms.[12]

The quantum algorithm for linear systems of equations has been applied to a support vector machine, which is an optimized linear or non-linear binary classifier. A support vector machine can be used for supervised machine learning, in which training set of already classified data is available, or unsupervised machine learning, in which all data given to the system is unclassified. Rebentrost et al. show that a quantum support vector machine can be used for big data classification and achieve an exponential speedup over classical computers.[13]


Rebentrost et al. also 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$
  • $\begingroup$ But the question asks for specific examples given the restrictions on A and b, so even though you can solve matrix-valued differential equations, the matrices are restricted, and the question is what specific applications are there that satisfy these restrictions? So what useful differential equation satisfies the mentioned restrictions? $\endgroup$ – user1271772 Jul 11 '18 at 12:20
  • $\begingroup$ Same goes for machine learning, what's a specific machine learning matrix and vector that satisfies the restrictions mentioned in the question? The quesiton is pointing out that HHL cannot be applied to all possible matrices and vectors, so are there any specific examples of problems that do satisfy these restrictions, that HHL can be applied to? $\endgroup$ – user1271772 Jul 11 '18 at 12:24
  • $\begingroup$ @user1271772 In the Hopfield network paper I linked, the matrix is necessarily Hermitian since $w_{ij}=w_{ji}$. Also, the restriction on spectral norm has been considered in that paper (for the weighing matrix $||W||<1$) As for state preparation, that is still a problem, yes. Arbitrary states cannot be prepared efficiently. It has been addressed in the first part of the paper: "This could in principle be achieved using the developing techniques of quantum random access memory (qRAM) [33] or efficient quantum state preparation, for which restricted, oracle based, results exist [34]" $\endgroup$ – Sanchayan Dutta Jul 11 '18 at 12:33
  • $\begingroup$ Also, see the related post: Is it possible to speed up the generation of the weighting matrix using a quantum algorithm? $\endgroup$ – Sanchayan Dutta Jul 11 '18 at 12:35
  • $\begingroup$ The Hopfield example was not my problem. You copied and pasted a bunch of examples from Wikipedia (such as differential equation solving), which anyone could have done including the asker, but the reason I didn't (and presumably the reason why the asker asked this question in the first place) is because the asker seems to want (for example) specific differential equations where the matrices and vectors satisfy the restrictions imposed by algorithms of the HHL family. $\endgroup$ – user1271772 Jul 11 '18 at 12:44

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.