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!"
I'll wait until I can program in VB. Will it take long?
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
Maybe you should READ the damn thing and notice how that's addressed in the first half-page.
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?
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.
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.)
The summary cleverly omits that solving a linear equation is neither NP complete nor NP hard, the speed up is from O(n) to O(log n). I think you'd need a ginormous matrix for this to be useful depending on the constants and such (Of course it'd be crime for me to read paper instead of the abstract to actually find out the details). They already have the applications for quantum computing, it will be much more interesting when they actually figure out a way to build the damn things.
I'm sure it's still a significant result and there's a good chance they did something new that can be used in other applications.
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.
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.'
When things get complex, multiply by the complex conjugate.
Are arXiv articles peer-reviewed?
If not (as I suspect), that puts a serious question mark on them. On the other hadn, there are excellent non-peer reviewed scientific articles - and almost all the scientific articles produced in Europe before the 2nd WW were not peer-reviewed (back then that was an american practice, and a very good one I would add). However, nowadays peer review is a valuable and available resource that should be utilized.
THAT SAID again... some of the best, most innovative scientific articles are not being, nowadays, accepted for publication because the reviewers are one degree too dumb for the article. Eventually they do get published, but with an unnecessary 5-6 year delay.
Also, I have read in my life thousands of published peer-reviewed articles, and many of them contain incredible imbecillities where I have to question whether all the reviewers were high on hallucinogens. Very very high on hallucinogens.
"The agriculture ministry is not in charge of Gundam" - Japanese ministry official.
I think he liked to say things like those, because I just found a page quoting him just like I said.
Any life is made up of a single moment, the moment in which a man finds out, once and for all, who he is.
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)
In O(log n) time he can't read the entire article.
if we are solving a linear system, we need A to be square
No. You can "solve" an under-determined system (i.e., reduce it). You can also "solve" an over-determined system via a least-squares fit. Both are common problems in scientific computing.
The state you are in while your HEAD is detached... - wait, what?
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.
That depends. What is its tensile strength?
Oh come on, this deserves +P Funny.
They talk about dealing with sparse matrices but they would have to be O(log n) sparse to be useful for a single application of the algorithm. For example, a matrix with n=1000000 would have to have around 15 non-zero values and a trillion zero values.
Wrong. An upper bound in big O notation does not give any indication as to constant factors of the "real" bound (nor to other summands which are in o(log n)). In fact, your statement doesn't even make sense, because it is an asymptotical bound and hence can't be applied to a fixed size of the input size.
If you think quantum computing is about putting a physical system in a certain state and manipulating it, then you should also think classical computing is about setting a tape in a certain way and manipulating it.
When Turing first described a computer (a turing machine), it was essentially a mechanism where you put a tape in a certain state, manipulate it according to certain rules and in the end you get the tape in another state containing the "result" of your computation. What was so interesting about it it that it was theoretically possible to build a machine that would be able to do the manipulations automatically.
Quantum computation is analogous: get a certain vector in an n-dimensional Hilbert space, multiply it by these certain matrices in this specific order, and in the end you get a vector that corresponds to the "calculation" you did. This is absolutely only math, it has nothing to do with physics. What's exciting about this is that we expect to be able to build (real) machines that perform these operations way faster than any computer today can, because the specific operations with which be built our algorithm are exactly the things nature is capable of doing fast.
Of course, we only discovered this when we discovered quantum mechanics -- that's the relation to physics.
He's my number 1 for being a genius AND a manwhore.
This looks like a really interesting result, but having look a little at the paper it's not 100% clear to me what the quantum algorithm is being compared to. First a caveat, I study quantum physics but not CS, so my knowledge of algorithms and complexity theory is quite limited. Anyway, in solving problems on a good old classical computer, you can seek to solve a linear system exactly (up to the bounds of finite arithmetic) or you can seek to solve it approximately to within some error.
So the thing I'm wondering is what classical algorithm are they comparing their result to, and is this comparing apples to apples? They say
So it looks like the authors' algorithm gives an approximate solution to the linear system and they're comparing it to a classical algorithm that gives an exact solution to the problem. This seems like comparing apples to oranges. Perhaps someone who knows more about the features of the various classical algorithms can comment on whether it looks like the correct comparison to make and why.
I bring this up because I recall that given a matrix representing the density matrix of a bipartite quantum system, determining whether it represents an entangled or separable quantum state is in general NP-Hard, but IIRC there exist semi-definite programming techniques to get the answer probabilistically in polynomial time. The point is that in that case there's a big gain for accepting an answer that will be wrong every once in a while. I was just curious if settling for an approximate answer in solving linear systems changes the complexity of that problem drastically as well.
"You call it a new way of thinking; I call it regression to ignorance!" -- Operation Ivy
You're both wrong. They're equivalent.
From wikipedia:
"A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. "
This is not the greatest sig in the world, no. This is just a tribute.
The weak point to me is where they "map A to a quantum-mechanical operator". They completely ignore the timing of this step, which amounts to assuming assuming that multiplication by A takes time O(1). With that assumption I'm sure you can do linear algebra blazingly fast.