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!"
Does this mean they can solve P=NP?
code quantum: what the fuck??
Detroit just needs to be burned to the ground.
First of all, it is an almost ALL BLACK city. Think that's a good idea? Look at fucking Africa. These people are still primitive, and have not evolved like us white peeps. Crime is HUGE in Detroit because black people are lazy and do not want to work for their money. End of story. Oh, and they are intellectually inferior. Think I'm wrong? The only smart jiglets are those who have some white blood in 'em.
Second of all, the automotive industry in this country is laughable bullshit. The cars are junk. Look at the interior of a Ford. It looks like an infant could destroy their dashboards with a few feeble kicks.
A junglebunny infant.
And finally, Marshall Mathers came from there. Look at his goddamned face. He looks like an asshole criminal. Can you blame him, though? Being surrounded by ape-like drug dealers since inception would do that to any of us.
Now I know I will be flamed for "being racist". But it is the fucking elephant in the room, people. Black people, as a whole, are degenerate. "Wih wih wih, you are ignorant, for shame for shame, blah blah blah!" Fuck that. Survival of the fittest... these jigaboos know it, and KNOW that they are inferior to us, and will die out eventually, and that is why they kill us. They are nothing but animals.
Why do you think Barack Obama wants to outlaw firearms? Because he knows that then, instead of law-abiding WHITE people being able to defend themselves, only the CRIMAL BLACKS (100% of the entire black population) will have them, and thus will be able to rob and murder us with ease. Why haven't the major news outlets picked up on this? Oh that's right, because their hairy, crusty lips are wrapped around the monster cocks of the jig "elite".
That goddamned movie with Denzel "Fatlips" Washington, about the "black criminal overlord", was nothing but a ploy made by the Tim Robbinses of the world to try to get INTELLIGENT WHITE PEOPLE to think that black people are smart. Well, guess what, you gynecomastia sufferer! It only presented more evidence that BLACK PEOPLE ARE ALL, DEEP DOWN, CRIMINALS.
There are many of you who would never admit that you agree with what I have written. But, do you know what? You do agree.
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.
Uh, in O(log n) time their algorithm can't even read all the input. Maybe they meant to compare parallel quantum vs parallel classical?
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.
I define useful work as gaining a Ph.D or justifying grants. Besides, fast linear equation solvers are only good if you can actually get what you need to run them.
No, to be really useful, quantum computing has to be as easy to afford and deploy as current computing technology.
As it happens I'm currently grappling with trying to create an ODE solver that works superQuickFast using normal computers. Unless someone buys be a quantum computer I think I'll be working this way for a fair while yet.
A learning experience is one of those things that say, 'You know that thing you just did? Don't do that.' - D. Adams
It can only solve the problems exponentially faster if no-one is looking.
This is amazing research, and if it works it will be more powerful than the FFT, and maybe even quicksort.
However, the article make a mistake in calling this an exponential improvement. Even the slowest solving algorithm (QR) is O(n^3). This promises O(log(n)). This is only a polynomial speedup.
That being said, this still kicks ass, and I hope it works.
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.
Has anyone spoken on its applications vis-a-vis cryptography and cryptanalysis?
Submission as evidence constitutes plaintiff and/or prosecutorial misconduct.
I can't help but wonder how (if?) this is going to affect public key cryptography. RSA security is dependent on the difficulty of factoring large primes, and this seems like it would reduce the time required to solve the problem considerably.
Perhaps someone more versed in mathematics can shed some light on this.
The society for a thought-free internet welcomes you.
Yes, because all quantum algorithms are hugely practical these days...
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.
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.
Do you realize, that until they begin solving these problems in academia that there will be no industry-ready solution? I mean this is a whole new advent of computing really with three-dimensional processors coming online at around the same time we may see the same sort of increase in computational power that they did with the first electric computers.
This are some workable challenges that lay ahead in the next few years.
1. Not only will a lot of algorithm design need to be hacked out but I think Quantum Computing needs its own language to really shine and that can be worked on now.
2. A lot of work can be made possible with a clever and cheap single or dual qubit hardware solution that is yet to be designed. Please make the connection USB. The boys and girls down in applied physics may be able to help you. Like Morlocks they usually are underground and desire a eloi/hippy for snackerfice.
3. The ability to run an exponentially greater amount of calculations is going to lead to revolutionary engineering breakthroughs across the board. Lattice work in concrete is particularly linear, curvilinear or hodge-podge; now imagine lattice inside a concrete pylon like a fractal tree, it could be made to withstand force vectors that would turn a standard pylon to dust, sure we have the computing power to do a pylon like that now but not all the components of a 1000 story building.
An Education is the Font of All Liberty
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.
In this case, when A is sparse and well-conditioned, with largest dimension n, the best classical algorithms can find x and estimate x^\dag M x in O(n) time
First of all, "with largest dimension n" means nothing because if we are solving a linear system, we need A to be square. Then, the complexity of the best classical algorithms does not depend only on the size "n" of the matrix but also on the number "nnz" of non-zero entries.
My first program:
Hell Segmentation fault
...FOR THE WIN! :D
No, I will not explain this! :P
Any sufficiently advanced intelligence is indistinguishable from stupidity.
I don't have a clue what a quantum linear equation is or why I'd need to solve it, let alone know how to.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
What kind of side effects will a progress bar have since you can't know what its doing if you know where it is?
If someone is passing you on the right, you are an asshole for driving in the wrong lane.
Quantum of Solvethis.
A cool algorithm that should be possible on a quantum computer is "perfect" data compression. IOW, "what is the smallest turing machine + input string that outputs the following string in less than 1 billion steps?"
Such an algorithm would need a quantum computer to run, but the decompression could happen on a classical computer.
Anyone aware if such an algorithm exists? The summary would seem to indicate not.
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
Would weather simulation be an applicable problem?
Because if they could use this to predict tomorrow's weather even 5% more accurately that'd be nice.
Here is a long list of problems that have superpolynomial i.e. more than polynomial speedup compared to classical computation. Even though the author doesn't think so many do have practical applications.
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.
Where is the on-line version of the 'Quantum Linear Equation Solver' built with hookers and blackjack?
Sig this!
Like all real mathematicians, I solve my quantum linear equations by hand.
Couldn't this break certain encryption schemes? Or am I confused here?
Maybe I was thinking of discreet logarithms or something else instead.
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.
Could someone mod the parent up +1 whatever [insightful, informative, funny - really, a "tragicomic" mod point would be most appropriate here].
Back in the day, Goro Shimura used to say that something like 50% of all published mathematics is simply rank nonsense, but these days, I'd say that the proportion is closer to 99%.
I think reviewers should be held accountable in some way.
Quis custodiet ipsos custodes?
The truth of the matter is that the problem is inherently intractable.
If you have good people writing papers, then you will get good papers.
If you have lousy people writing papers, then you will get lousy papers.
What people need to realize [and what almost all people in the grant-writing racket lack the strength of character to admit] is that most published "research" is simply false.
And if to "false" you were to add "trivially tautological or essentially meaningless" then you would have classified almost all of published "research" nowadays.
But the grant-writing racket is very powerful politically, and the milk from the teat of that sow tastes oh so good...