QCJC: Harrow 2009

It’s been a while since I’ve come back to the QCJC, but the start of a new year is as good of a time as any :) I was browsing through a few recent publications from the Pan group at USTC, and came across an interesting implementation. It uses a quantum algorithm to solve linear systems of equations, which I thought was phenomenal! While most of the algorithms that I’ve gone over so far are very limited in scope, the algorithm described in this paper seemed much more general and applicable to so many different contexts and uses.

Although most of this algorithm seems to go over my head, it’s useful to go over the key assumptions found in this paper:

  • The goal of this paper is to achieve an exponential speedup in solving eigenvalue problems, which are equivalent to solving linear systems of equations.
  • However, the way this speedup is achieved is by not actually solving these linear equations. In fact, the paper notes that in general, to write down the solution of N linear equations would require time that scales as N. The authors achieve the speedup by computing the expectation values of eigenvalue solutions rather than computing those actual solutions.
  • The authors compare their algorithm to a classical Monte Carlo sampling algorithm, but also show that no classical algorithm is able to match the same speed, even for algorithms that are only computing summary or expectation values as well.

The first step of this algorithm is to solve the problem Ax = b for x, the standard eigenvalue problem. First, the vector $b$ is assumed to be initiated, perhaps as a result of some other subroutine. Afterwards, this algorithm is rooted in earlier work that allows the creation of an operator e^{iAt}, where A is a Hermitian matrix representing the linear system of equations, through a process known as phase estimation. This operator is then applied to solve for the eigenvalues of b in order to find x.

However, the goal of this algorithm is to not directly find or output x. Instead, using the vector x, we can then find the expectation value of various quantities. Those values can be used to find different weights of the solution, or further moments of the solution vector.

Unfortunately, I don’t really follow the remainder of the mathematics of this paper… however, tomorrow I’m going to take a look at two implementations of this algorithm, and hope that those experimental papers will provide a little more insight as to how this is actually computed. It looks like the Wikipedia page for this algorithm is also directly based on this paper, so perhaps some additional research will help me understand that, at least :)

Happy New Year!

References: December 31, 2017: Harrow, A. et al. Quantum Algorithms for Linear Systems of Equations Phys. Rev. Lett. 103 210504 (2009)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s