The dense case is an interesting open question. We'd really like to know more about that.
I don't know much about ray-tracing, but I thought it used 3x3 and 4x4 matrices, so for that our speedup wouldn't be particularly useful. More generally, measurement in quantum computers is likely to be painful, so we think the most dramatic quantum speedups will occur when the answer is a few bits, rather than megabytes, as occurs in ray tracing.
Chaotic systems we also probably can't do much with yet, but my friend Tobias Osborne is working on something that may be applicable.
As for fragility, this is addressed through fault-tolerant quantum computing techniques, just like for any other quantum algorithm. It's not easy, but it's in principle possible.
This is explained in the technical appendix. We assume that A has at most s non-zero entries per row, and that A is stored in a data structure that efficiently answers "return all non-zero entries in a row" queries. For example, an array of lists would work. Our run-time then has an O(s^2) dependence.
Basically we need to assume random-access memory. There has been some preliminary work on models for quantum RAM, some of which we cite in our paper. But as a sign that the model isn't too powerful, we know that classical computers with RAM are not exponentially faster than weaker models, like single-tape Turing machines or 1-D cellular automata.
Alternatively, there might be a short algorithm that generates the entries of A. In this case, we could simply use it as a subroutine without having to make any assumptions about the quantum computer's architecture.
What I'm wondering is whether similarly relaxing the requirements on the classical computation (so that you only require such an approximate solution in the same sense, not an exact solution) will reduce the classical computational complexity of the problem significantly.
We plan to soon update our arxiv post to explain that the matrix inversion problem (with the parameters we consider) is BQP-complete, meaning it is as hard as anything that quantum computers can solve in polynomial time. This is strong evidence that classical computers need exponentially more time to solve the problem in general. Of course, there may be special cases, some of practical interest, where good classical algorithms exist.
This is a great question. Here's how I like to think about it:
If A is a stochastic matrix and b is a probability distribution that we can sample from, then given a few assumptions, we can sample from Ab efficiently. This is more or less the idea behind so-called Monte Carlo simulations, which are a tremendously useful tool in classical computing.
However, we don't know how to get sampling access to A^{-1} b. Our algorithm gives us something like sampling access to A^{-1} b. Not exactly, because we're talking about quantum amplitudes, rather than probabilities. But more importantly, taking the inverse can make a sparse matrix dense, and (as we often see for problems admitting quantum speedups) sampling-based approaches to computing it fail because the samples have alternating signs.
are my coauthors, and the ordering of author names was alphabetical, and doesn't reflect our level of contributions (which were more or less equal).
So please cite this as "Harrow, Hassidim and Lloyd" and not "Harrow and coauthors."
That said, we're pleased about that attention.:)
In response to one question: the matrix inversion problem for the parameters we consider is (almost certainly) not NP-complete, but instead is BQP-complete, meaning that it is as difficult as any other problem that quantum computers can solve. We plan to update our arXiv paper shortly with an explanation of this point.
Slashdot Mirror
I don't know much about ray-tracing, but I thought it used 3x3 and 4x4 matrices, so for that our speedup wouldn't be particularly useful. More generally, measurement in quantum computers is likely to be painful, so we think the most dramatic quantum speedups will occur when the answer is a few bits, rather than megabytes, as occurs in ray tracing.
Chaotic systems we also probably can't do much with yet, but my friend Tobias Osborne is working on something that may be applicable.
As for fragility, this is addressed through fault-tolerant quantum computing techniques, just like for any other quantum algorithm. It's not easy, but it's in principle possible.
Dan and Mike: Hi! :)
Basically we need to assume random-access memory. There has been some preliminary work on models for quantum RAM, some of which we cite in our paper. But as a sign that the model isn't too powerful, we know that classical computers with RAM are not exponentially faster than weaker models, like single-tape Turing machines or 1-D cellular automata.
Alternatively, there might be a short algorithm that generates the entries of A. In this case, we could simply use it as a subroutine without having to make any assumptions about the quantum computer's architecture.
We plan to soon update our arxiv post to explain that the matrix inversion problem (with the parameters we consider) is BQP-complete, meaning it is as hard as anything that quantum computers can solve in polynomial time. This is strong evidence that classical computers need exponentially more time to solve the problem in general. Of course, there may be special cases, some of practical interest, where good classical algorithms exist.
This is a great question. Here's how I like to think about it: If A is a stochastic matrix and b is a probability distribution that we can sample from, then given a few assumptions, we can sample from Ab efficiently. This is more or less the idea behind so-called Monte Carlo simulations, which are a tremendously useful tool in classical computing. However, we don't know how to get sampling access to A^{-1} b. Our algorithm gives us something like sampling access to A^{-1} b. Not exactly, because we're talking about quantum amplitudes, rather than probabilities. But more importantly, taking the inverse can make a sparse matrix dense, and (as we often see for problems admitting quantum speedups) sampling-based approaches to computing it fail because the samples have alternating signs.
So please cite this as "Harrow, Hassidim and Lloyd" and not "Harrow and coauthors."
That said, we're pleased about that attention. :)
In response to one question: the matrix inversion problem for the parameters we consider is (almost certainly) not NP-complete, but instead is BQP-complete, meaning that it is as difficult as any other problem that quantum computers can solve. We plan to update our arXiv paper shortly with an explanation of this point.