Slashdot Mirror
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!"
Maybe you should READ the damn thing and notice how that's addressed in the first half-page.
Is this algorithm in Haskell or somethin'?
I'll wait until I can program in VB. Will it take long?
It may or may not.
"Just a fox, a whisper."
When the Prime Minister asked him about a new discovery, "What good is it?", Faraday replied, "What good is a newborn baby?"
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
You think that quantum computers are not able to justify grants or PhDs? What world are you living in?
Yeah, because classical computers were never useful to anyone (or anyone important) until datacenters existed.
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?
It's not a 'new toy' for computer science. Computer science has pretty much nothing to do with it. Mostly, it's a toy, or rather, academic persuit for theoretical physicists.
No, it's of real interest to theoretical computer science. Quantum computing defines a new class of algorithmic complexity: there are, for instance, sub-exponential quantum algorithms for problems which have only exponential-time classical solutions. There is a whole subindustry of algorithmic complexity theory devoted to exploring the differences between algorithms that can be executed on quantum computers and those which are executed on classical computers. Scott Aaronson's lecture notes are a good introduction to this subject.
Quantum computing is nondeterministic and probability-based: when you put in a certain input, you have a finite probability of getting the right answer out, it could just as easily be anything else. So in other words, coming from VB, you'll be at a major advantage.
Dislike the Electoral College? Lobby your state to join the National Popular Vote Interstate Compact.
Finally a cool article on /. This is extremely cool! There are a lot of problems in the real world that have extremely large sparse matrices that need to be inverted. Fluid dynamics and solutions to Maxwells equations come to mind. But I am sure there are other applications in relativity and plasma physics. Estimating a solution to a linear dynamic system of say 2^128 degrees of freedom in only 128 cycles would change a lot of things.
And... Yes, we are working very hard on building the computers.
Does this mean they can solve P=NP?
Yes: N=1.
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.
To rephrase the other response, log vs. polynomial is the same as polynomial vs. exponential. Moving from polynomial time to logarithmic time is an exponential speedup (just as is moving from exponential time to polynomial time is).
O(n^3) vs. O(log n)
->
O(exp(n^3)) vs. O(n)
Are arXiv articles peer-reviewed?
No, they aren't.
My first program:
Hell Segmentation fault
In O(log n) time he can't read the entire article.
Oh come on, this deserves +P Funny.
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.