A Quantum Linear Equation Solver

joe writes "Aram Harrow and colleagues have just published on the arXiv a quantum algorithm for solving systems of linear equations (paper, PDF). Until now, the only quantum algorithms of practical consequence have been Shor's algorithm for prime factoring, and Feynman-inspired quantum simulation algorithms. All other algorithms either solve problems with no known practical applications, or produce only a polynomial speedup versus classical algorithms. Harrow et. al.'s algorithm provides an exponential speedup over the best-known classical algorithms. Since solving linear equations is such a common task in computational science and engineering, this algorithm makes many more important problems that currently use thousands of hours of CPU time on supercomputers amenable to significant quantum speedup. Now we just need a large-scale quantum computer. Hurry up, guys!"

Re:Seems bogus

[Anonymous Coward]

Maybe you should READ the damn thing and notice how that's addressed in the first half-page.

Re:not able to be used == not useful

[Andr T.]

Maybe it's just a story, but I've read something about Faraday that made me think about what you've written.

When the Prime Minister asked him about a new discovery, "What good is it?", Faraday replied, "What good is a newborn baby?"

Re:not able to be used == not useful

[norton_I]

You think that quantum computers are not able to justify grants or PhDs? What world are you living in?

until these quantum computers exist and are cheap enough to fill datacentres

Yeah, because classical computers were never useful to anyone (or anyone important) until datacenters existed.

No, to be really useful, quantum computing has to be as easy to afford and deploy as current computing technology.

And until then, developments that bring us closer are irrelevant? Applications that could give us more reason to develop the technology are pointless?

What exactly is your point here?

Re:not able to be used == not useful

[bmwm3nut]

I see your point, but think conversely: I make a quantum computer that's cheap enough to fill a data center but there's no algorithms out there? What use is it? We need the physicists our there making the quantum computers and we need the computer scientists out there developing the algorithms. One without the other is useless. Also think of this: Dijkstra's "Go To Statement Considered Harmful" was published in the late 60's, there weren't many cheap computers to fill data centers then. He was working on the theory of algorithms not worrying about how to actually implement it. The same thing here, there are people working on the theory of these algorithms, other people will worry about actually using it when the time come.

Re:not able to be used == not useful

[Ambitwistor]

I know quantum is the 'new toy' in computer science, but seriously, until these quantum computers exist and are cheap enough to fill datacentres with, no-one outside of academia is going to get any useful work from them.

Er, yes. If there aren't any quantum computers then quantum computers aren't useful. That's not the point of this work. The point of this work is primarily to present a new algorithm for which quantum computing shows exponential speedup, which is an interesting theoretical issue in computer science. If quantum computers ever become practical, then this algorithm will be too, but no one has claimed that this algorithm is useful today. (The submitter noted explicitly that it is not.)

Re:not able to be used == not useful

[physicsphairy]

I could just as well argue that there is nothing useful about developing quantum computers until we have programs we can run on them.

This is not tangential science. The is the real groundwork for the development of the new technology. Without this sort of work quantum computers will simply never exist.

So pointing out its lack of present utility is like pointing out that after laying the foundation for a house that you still have nothing to live in. That may be true, but in so far as the initial step is pre-requisite to your ultimate goal, it is erroneous to dismiss it as 'not useful.'

Re:n to log(n)

[popmaker]

Often, one does not need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., xMx for some matrix M . In this case, when A is sparse and well-conditioned, with largest dimension n, the best classical algorithms can ïnd x and estimate xMx in O(n) time. Here, we exhibit a quantum algorithm for solving linear sets of equations that runs in O(log n) time, an exponential improvement over the best classical algorithm.

This is a long quote, which is at top of the actual paper cited (I'd trim it down, but I'd need to brush op on my linear algebra to be sure not to ruin it).

According to them, the best algorithms are O(n) and their algorithm improves that to O(log n). It has nothing to do with P vs NP but it is an exponential improvement anyway (going from n to log n), as promised in the summary.

Re:Avinatan Hassidim and Seth Lloyd

[saburai]

I work in CFD, so this is all thrilling to me. I suspected it was only a matter of time before methods were discovered for applying quantum computation to large systems of linear equations, and I certainly hope your work stands up to peer review. Cheers!

Re:not able to be used == not useful

[nog_lorp]

Eh, in that case your post is irrelevant. It amounts to saying "Until we have x, people won't be able to use x, so it will only be of interest to people studying creating x". It goes without saying, and people on Slashdot are clearly interested in this.

Re:not able to be used == not useful

[MaskedSlacker]

He's my number 1 for being a genius AND a manwhore.