# A Quantum Linear Equation Solver

#### kdawson posted more than 5 years ago | from the traveling-salesman-gets-a-break dept.

171
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!"*

## Implications (0)

## Anonymous Coward | more than 5 years ago | (#26004263)

## Re:Implications (0)

## Anonymous Coward | more than 5 years ago | (#26004305)

## Re:Implications (5, Funny)

## Anonymous Coward | more than 5 years ago | (#26004917)

Does this mean they can solve P=NP?

Yes: N=1.

## Re:Implications (1)

## X0563511 (793323) | more than 5 years ago | (#26005089)

Or if P=0, in which case N can be any number.

## Re:Implications (5, Funny)

## lenester (625236) | more than 5 years ago | (#26005585)

## Re:Implications (0)

## Anonymous Coward | more than 5 years ago | (#26006787)

No, and neither does any other quantum algorithm because P=NP is a question about Turing machines and quantum computers are not equivalent to Turing machines.

## RE: Obama didn't make it (-1, Offtopic)

## lapinmalin (1400199) | more than 5 years ago | (#26004301)

## Thoughts? (-1, Offtopic)

## Anonymous Coward | more than 5 years ago | (#26004317)

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 becauseblack 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

junglebunnyinfant.And finally, Marshall Mathers came from there. Look at his goddamned

face. He looks like anasshole criminal. Can you blame him, though? Being surrounded byape-like drug dealerssince 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, crustylipsare wrapped around the monster cocks of the jig "elite".That

goddamnedmovie 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 aresmart. Well, guess what, you gynecomastia sufferer! It only presented moreevidencethat 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?

Youdoagree.## Re:Thoughts? (0, Offtopic)

## lancelotlink (958750) | more than 5 years ago | (#26004483)

## Re:Thoughts? (-1, Troll)

## Anonymous Coward | more than 5 years ago | (#26004617)

Theunfortunate darker sideof online anonymity.Dark skin is unfortunate, eh, you racist shit-sniffer?

## Re:Thoughts? (-1, Offtopic)

## ConceptJunkie (24823) | more than 5 years ago | (#26005083)

The unfortunate darker side of online anonymity.Meaning, on the internet, no one knows if you're a Secret Chimp?

## Re:Thoughts? (0)

## Anonymous Coward | more than 5 years ago | (#26004655)

Survival of the fittest... these jigaboos know it, and KNOW that they are inferior to us, and will die out eventually

lol, have you ever seen a child of a black and white couple? Is it white? No. Is it black? No.

If anything the entire human race will become less white and less black. Maybe some day we will all be blue and these stupid racial issues will finally be behind us. Maybe then, the human race as a whole, has left its stage of infancy.

## Re:Thoughts? (-1, Troll)

## Anonymous Coward | more than 5 years ago | (#26004857)

Yeah, and maybe then the URBAN BLACK MAN will stop robbing (and MURDERING) white people, and everyone else, for fucking

money. To buy what? Food? Yeah right. Drugs. Alcohol. Fucking DVDs.You think THAT behavior isn't infantile? Do you seriously not have a shiver of worry go through you when you are approaching one of those fucking thugs on the street? With their idiotic strut, their puffy North Face jackets, and the sullen look of a fucking ANIMAL on their faces? Let's be realistic here. I am guessing that you do not live in a major city, right? If you do, try to count the number of times you have seen one of these "people" smile. You probably won't need ANY hands to do it.

When black people stop being the number one criminal race, per capita, in the country, I will change my views. No question. Until then, I will treat THEM like they treat US.

TELL ME IF I AM WRONG. PLEASE! I DO NOT LIKE BEING HATEFUL, AND I DO NOT WANT TO BE HATEFUL ANYMORE, BUT THE EVIDENCE IS JUST OVERWHELMING. I CANNOT HELP IT.

## Re:Thoughts? (-1, Troll)

## Anonymous Coward | more than 5 years ago | (#26005249)

Moderated TROLL? Oh my, you people still don't get it, do you? You still believe that crap they spoonfed you in fifth grade social studies class, don't you? "Racism is bad! Look at the civil rights movement! Everyone is created equal! We are forced, by the government, to teach these lies because otherwise the powers that be will be voted out by the NAACP!" It is bullshit, and you need to revise your views based on evidence.

Racism is NOT evil. We are taught that it is the worst thing in the world, right? WHY IS IT SO BAD? It's viewed on par with RAPE! What the fuck? How did this START?

Racism is healthy. Fear of the "outsider" is

why human beings survived.Argh. But of course, your little sensibilities will be offended. Good fucking fuck. Open your eyes.

I DON'T HATE ALL BLACK PEOPLE! JUST THE FUCKING URBAN THUGS!

## Re:Thoughts? (1)

## MikeDirnt69 (1105185) | more than 5 years ago | (#26006105)

## Re:Thoughts? (0)

## Anonymous Coward | more than 5 years ago | (#26006401)

Not really, everybody hates the mongrel bastards.

## Hm (2, Funny)

## Andr T. (1006215) | more than 5 years ago | (#26004367)

I'll wait until I can program in VB. Will it take long?

## Re:Hm (5, Funny)

## FrozenFOXX (1048276) | more than 5 years ago | (#26004449)

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.

## Re:Hm (2, Funny)

## Anonymous Coward | more than 5 years ago | (#26004897)

Also, it may AND may not.

## Humor via moderation... (0, Redundant)

## Hurricane78 (562437) | more than 5 years ago | (#26006407)

...FOR THE WIN! :D

No, I will not explain this! :P

## Re:Hm (3, Funny)

## Anonymous Coward | more than 5 years ago | (#26004473)

Following the protocol of quantum physicists to be un-understandable by anyone but the top people in their field and 13-year-olds with too much time who watch NOVA and read Popular Science, they wrote it in Perl

## Re:Hm (1)

## Arthur Grumbine (1086397) | more than 5 years ago | (#26006935)

Following the protocol of quantum physicists to be

un-understandable..."Derstandable"!?

That word is

incomprehensibleto me. I amunable to understandit, is what I'm trying to get at...y'know:baffling, beyond comprehension, clear as mud, cryptic, Delphic, enigmatic, fathomless, Greek, impenetrable, incognizable, inconceivable, inscrutable, mysterious, mystifying, obscure, opaque, perplexing, puzzling, sibylline, unclear, unfathomable, ungraspable, unimaginable, unintelligible, unknowable.## Re:Hm (5, Funny)

## AdmiralXyz (1378985) | more than 5 years ago | (#26004697)

## Seems bogus (0)

## Anonymous Coward | more than 5 years ago | (#26004377)

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?

## Re:Seems bogus (4, Insightful)

## Anonymous Coward | more than 5 years ago | (#26004431)

## Re:Seems bogus (4, Funny)

## Bitch-Face Jones (588723) | more than 5 years ago | (#26005241)

## Re:Seems bogus (1)

## mesterha (110796) | more than 5 years ago | (#26005277)

It's not completely addressed or at least all the implications are not spelled out. 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. I don't know if that's practical.

It still might be useful if one needs to perform the operation repeatedly say for an iterative algorithm. As long as one only loaded the O(n) data once. However, I doubt that is likely for quantum computers since one probably needs to reset the quantum state. However, perhaps the algorithm can be adapted to solve iterative problems.

## Re:Seems bogus (3, Informative)

## adrianwn (1262452) | more than 5 years ago | (#26005675)

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 [wikipedia.org] 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.

## Re:Seems bogus (1)

## mesterha (110796) | more than 5 years ago | (#26005909)

It's an example, to give a feel for the order of magnitude. If the particular constant was very large, one would have to increase n to show the same effect, but the idea would hold. In addition, it has nothing to do with my argument. You can mentally delete that sentence if it bothers you. It has no impact on my point.

## not able to be used == not useful (-1, Troll)

## thermian (1267986) | more than 5 years ago | (#26004441)

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.

## Re:not able to be used == not useful (4, Insightful)

## Andr T. (1006215) | more than 5 years ago | (#26004487)

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 (1, Troll)

## thermian (1267986) | more than 5 years ago | (#26004727)

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?"

Wrong, actually it was in reference to his new electric motor, and the proper quote is 'When asked by the kind what use it was, Faraday replied, 'One day sir, you may tax it'.

Note also at that point the electric motor existed, quantum computers do not, not in any useful sense.

## Re:not able to be used == not useful (3, Informative)

## Andr T. (1006215) | more than 5 years ago | (#26004771)

## Re:not able to be used == not useful (1)

## shoor (33382) | more than 5 years ago | (#26005287)

I read an autobiography of Benjamin Franklin which said that when Franklin was in France either negotiating the Treaty of Paris (that's the one where England actually recognized the USA as a separate country, ending the Revolutionary War), or maybe he was still just getting the French to back us, he was observing one of the first balloon flights of the Montgolfier bros, and someone wondered aloud what good was it, and his reply was "What good is a newborn baby?"

BTW, I don't have "heroes", but if I did, Franklin would be my nr 1.

## Re:not able to be used == not useful (2, Insightful)

## MaskedSlacker (911878) | more than 5 years ago | (#26006653)

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

## Re:not able to be used == not useful (3, Funny)

## Steneub (1070216) | more than 5 years ago | (#26005555)

## Re:not able to be used == not useful (4, Insightful)

## norton_I (64015) | more than 5 years ago | (#26004515)

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?

## Re:not able to be used == not useful (1)

## thermian (1267986) | more than 5 years ago | (#26004831)

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

One where I read peoples comments properly before replying to them. I did not say that at all.

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

We use datacentres *now* we didn't use them before. These days people in the real, working world need access to computing power in ways that we didn't before. I am talking practicality. The kinds of applications that get companies investors.

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?

Irrelevant is not the same as useless. It is, 'a lack of relevance', look it up. Academia will continue to explore the issue, but until we see deployments of quantum computers in large enough numbers to start basing the computer 'economy' on them they lack real world relevance.

## Re:not able to be used == not useful (0)

## Anonymous Coward | more than 5 years ago | (#26004983)

I think you're just grumpy that you're wrong. Wrong about each of the responses that you've made to people replying to yours. Stop while you're at least a little ahead.

Practical use, eh...I guess prime numbers aren't all too practical, with their many uses in crypto. Just a single example from the summary - maybe you should read the summary properly before replying to it.

## Re:not able to be used == not useful (2, Insightful)

## nog_lorp (896553) | more than 5 years ago | (#26005551)

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 (1)

## MoellerPlesset2 (1419023) | more than 5 years ago | (#26004531)

You will not be seeing Quantum Computers taking over general-purpose computing tasks anytime soon. Personally, I'm very skeptical to whether we will

eversee such a thing happen. Because it will almost certainlyneverbe easy and affordable to deploy; because I very much doubt you could ever get the necessary long decoherence times required for a quantum computer of any size to work, in an easily achievable environment. (by which I mean something approaching room temperatures, for instance).IOW, a computer that's a fancy elaboration on an NMR machine will never be a easy nor affordable.

## Re:not able to be used == not useful (4, Interesting)

## Ambitwistor (1041236) | more than 5 years ago | (#26004649)

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 [scottaaronson.com] are a good introduction to this subject.

## Re:not able to be used == not useful (1)

## DeadDecoy (877617) | more than 5 years ago | (#26005079)

## Re:not able to be used == not useful (1)

## MoellerPlesset2 (1419023) | more than 5 years ago | (#26005167)

That implies putting the results of a physical measurement on equal footing with 'classical' methods, i.e. what can be done using pure math. If you do that, I think you're turning Computer Science from having been a branch of Mathematics into some completely different animal.

Algorithms are math. They can be proven mathematically, etc. These 'quantum algorithms' are something different - even if they're derived mathematially (which is how physics works nowadays), they're essentially a statement of: Put this physical system in a certain state letting certain properties of the system represent your input. Manipulate it a certain way, and the 'algorithm' shows us that you can achieve a resulting state which - probabilistically - provides a measurable value representing the result of the 'calculation' you wanted to perform. It is not mathematically proven or provable (beyond the proof that the most probable state is the desired result).

Which makes the methods essentially

heuristics, not algorithms. And while that's perfectly good and useful for doing calculations and getting results, it is not a new kind of math, or any kind of math.## Re:not able to be used == not useful (1)

## Mr. McGibby (41471) | more than 5 years ago | (#26005293)

So you're basically saying that probabilistic computation isn't math? That doesn't make any sense. Just because we have computers that are extremely reliable doesn't mean that probabilistic methods are unimportant. Quantum computers are showing us that they are.

Richard Feynman would disagree. Please read his work on the Manhattan project.

## Re:not able to be used == not useful (3, Informative)

## FrangoAssado (561740) | more than 5 years ago | (#26005767)

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.

## Re:not able to be used == not useful (1)

## canajin56 (660655) | more than 5 years ago | (#26006393)

First, go read the paper and then say that it doesn't contain "any kind of math."

Second, explain how shooting electrons through doped silicon crystal gates, and then measuring the voltage across the end terminals isn't a physical measurement being put on equal footing with "pure math." I think that it is, so deterministic algorithms aren't algorithms either by your definition.

Third, you're wrong. Lets take a 65536 bit long encryption key, the product of two very large primes. Lets factor them! The best known deterministic algorithm is going to take longer than the universe will last. But I bet it takes well under a second to check an answer for correctness! Let's say you have a quantum "algorithm" Q. You are correct, you can't prove Q(key) will produce the correct factorization. But you can CHECK it in only a second. So, run Q(key) until your check passes. There, that's an algorithm by your definition. You just used math to prove that if you run your quantum + classical hybrid computer on that input, it will always output the correct result.

Fourth, an algorithm isn't a mathematical statement, stop redefining words just so you can get all riled up with righteous indignation. An algorithm is near universally defined as "a finite sequence of computational instructions, usually towards the end of computing a certain value or accomplishing a certain task." It's useless if you can't mathematically prove something about the answer. Deterministic algorithms you can always prove the answer is right (hopefully?). With randomized algorithms, you can mathematically prove that the answer is right too (in most cases) but not how long it takes. Conversely, you can usually also prove that it takes a finite amount of time, but then you can only prove a bound on it's probability of success, rather than being 100%. You're saying that it's "pure math" to prove (using math) that a sequence of instructions computes a correct answer in 1 year deterministically, but it's not pure math to prove (using math) that a sequence of instructions computes a correct answer in 1 year with probability of 1 - 1e-900. I submit that while the two are different proofs, for all intents and purposes, the two algorithms are equivalent, since you cannot have a computer that runs with 0 probability of errors, deterministic or not.

## Re:not able to be used == not useful (2, Insightful)

## bmwm3nut (556681) | more than 5 years ago | (#26004537)

## Re:not able to be used == not useful (2, Insightful)

## Ambitwistor (1041236) | more than 5 years ago | (#26004549)

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

theoreticalissue 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 (0)

## Anonymous Coward | more than 5 years ago | (#26004639)

And when/if the quantum computers become ready, you want to have to wait 20 years for the basic research necessary to make them usable? All research like this is useful, even if it leads nowhere right now.

I'm reminded of a nice little story I was told in my first year number theory course:

There was a mathematician who was extremely proud that his particular branch of mathematics was so obscure that it had absolutely no practical use and was purely theoretical. This branch formed the basis of modern encryption that is used constantly in everyday life now.

Anyone know the name of this mathematician, or am I completely getting this story wrong?

## Re:not able to be used == not useful (2, Insightful)

## physicsphairy (720718) | more than 5 years ago | (#26004667)

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-requisiteto yourultimate goal, it is erroneous to dismiss it as 'not useful.'## Quantum Computing needs a language (1)

## linzeal (197905) | more than 5 years ago | (#26004941)

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.

## Re:not able to be used == not useful (0)

## Anonymous Coward | more than 5 years ago | (#26005093)

It seems you didn't think quite through.

Quantum computing would be a waste of time if you couldn't do anything with it.

And as the article stated, before this algorithm, there wasn't much practical things that could be done, it's possible the practical use is very limited.

You are saying people should focus on developing the hardware first because those algorithms are useless now. After developing the hardware, how dumb would you feel if you discovered there is not much practical use for that?

## Re:not able to be used == not useful (1)

## Chris Burke (6130) | more than 5 years ago | (#26005821)

Did you know that the foundations of computer science were laid down before the existence of the first electrical computer?

Did you know that, when electrical computers came into existence, having this science all laid out already was actually pretty useful? Kept people from standing around going "Okay now what do we do?" for several years.

In short, your view of utility is short-sighted and lacks vision.

## Except... (0)

## Anonymous Coward | more than 5 years ago | (#26004447)

It can only solve the problems exponentially faster if no-one is looking.

## Re:Except... (0)

## Anonymous Coward | more than 5 years ago | (#26004523)

..ruinin' your xperiment.

## Polynomial Speedup (0)

## Anonymous Coward | more than 5 years ago | (#26004529)

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.

## Re:Polynomial Speedup (0)

## Anonymous Coward | more than 5 years ago | (#26004779)

## Re:Polynomial Speedup (4, Informative)

## blueg3 (192743) | more than 5 years ago | (#26005115)

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)

## n to log(n) (3, Informative)

## rcallan (1256716) | more than 5 years ago | (#26004571)

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.

## Re:n to log(n) (2, Insightful)

## popmaker (570147) | more than 5 years ago | (#26004813)

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:n to log(n) (1)

## kvezach (1199717) | more than 5 years ago | (#26004993)

## Re:n to log(n) (1)

## Darby (84953) | more than 5 years ago | (#26006623)

As for expansion, well, let's just hope there's a similar speedup to be found in linear programming :)Simplex method forever, Baby!

## Re:n to log(n) (1)

## hotdiggitydawg (881316) | more than 5 years ago | (#26005133)

A Slashdot summary that is still technically correct, despite the usual omission of key facts?

I think your discovery is perhaps even more notable than the algorithm!

## Re:n to log(n) (0)

## Anonymous Coward | more than 5 years ago | (#26006549)

This _is_ important. You say that you'll need ginormous matrices for this to be useful... but ginormous matrices are _always_ wanting to be inverted. Pretty much all applied mathematics problems end up being reduced to a problem of linear algebra. An exponential speed-up on this problem would be a great advance for our civilization. Of course, we need real quantum computers for it to be at all useful.

## Political Consequences thereof... (1)

## KudyardRipling (1063612) | more than 5 years ago | (#26004577)

Has anyone spoken on its applications vis-a-vis cryptography and cryptanalysis?

## Re:Political Consequences thereof... (1)

## professorguy (1108737) | more than 5 years ago | (#26005003)

## Could this break RSA/public key crypto? (0)

## gillbates (106458) | more than 5 years ago | (#26004589)

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.

## Re:Could this break RSA/public key crypto? (1)

## Andr T. (1006215) | more than 5 years ago | (#26004687)

## Re:Could this break RSA/public key crypto? (1)

## kmac06 (608921) | more than 5 years ago | (#26004721)

## Re:Could this break RSA/public key crypto? (1)

## Darby (84953) | more than 5 years ago | (#26006657)

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.Factoring primes is the easiest freaking thing in the world.

Give me a prime, any prime. Ok, its factors are it and 1.

Perhaps someone more versed in mathematics can shed some light on this.HTH HAND.

## Practical Application?! (1)

## 31415926535897 (702314) | more than 5 years ago | (#26004641)

Yes, because all quantum algorithms are hugely practical these days...

## Re:Practical Application?! (1)

## blueg3 (192743) | more than 5 years ago | (#26004855)

You have your word semantics wrong. Shor's algorithm has enormous practical application. However, as there are no computers to run it, it's impractical to actually put it to use.

## arXiv articles - question (2, Informative)

## blind biker (1066130) | more than 5 years ago | (#26004745)

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.

## Re:arXiv articles - question (1)

## MozeeToby (1163751) | more than 5 years ago | (#26004933)

I thought it had been nearly proven that peer review for highly specialized complez subjects was pretty much worthless, since most reviewers will not understand the subject matter and also won't be willing to admit that they don't understand it. Didn't some students at MIT create a giberish generating program that was able to produce papers that pass peer review?

The basic problem is, for truly ground breaking research, there often isn't a ready supply of peers to do the review. There are plenty of subjects in science where litterally a dozen or less people in the world qualified to do the review. And in all likelyhood, 4 of them collaborated on the research in question and another 6 were consulted at some point during the research.

## Re:arXiv articles - question (1)

## Chocky2 (99588) | more than 5 years ago | (#26005305)

Didn't some students at MIT create a giberish generating program that was able to produce papers that pass peer review?

I doubt it, unless they were sociologists :)

Peer review may not be able to reliably tell for certain if something is correct, but it's often a good mechanism for spotting things that are wrong.

You don't need ten years post-doc work in QCD to spot an error in addition, though if you're trying to extend the number of colours in a gauge theory you probably do :)

## Re:arXiv articles - question (1)

## Saysys (976276) | more than 5 years ago | (#26005315)

No. Speaking as a scientist involved in esoteric areas: That program was a farce, it was accepted for "review" [naturalnews.com] at a scientific conference, a much lower standard. When it comes to a conference someone who is simply interested in the title might allow the paper in.

As for important research: If you are publishing in a good journal, something that has more citations than articles published, then you will have someone who knows enough about the subject to give it a reasonable review.

## Re:arXiv articles - question (1)

## blind biker (1066130) | more than 5 years ago | (#26005673)

Didn't some students at MIT create a giberish generating program that was able to produce papers that pass peer review?

I don't know. But sure as heck would like to - any more info on this so I can look it up?

## Re:arXiv articles - question (4, Funny)

## fph il quozientatore (971015) | more than 5 years ago | (#26005135)

Are arXiv articles peer-reviewed?

No, they aren't [arxiv.org].

## Re:arXiv articles - question (0)

## Anonymous Coward | more than 5 years ago | (#26005363)

heh...most of those were not a paper attempting to prove the riemann hypothesis, and those that were had tons of reviews pointing out mistakes. At least one was withdrawn by the author once the mistake was pointed out.

Sounds like a more thorough peer-review than most other journals. I think arxiv is the future.

## Re:arXiv articles - question (1)

## Chocky2 (99588) | more than 5 years ago | (#26005223)

arXiv holds preprints, so no -- they've not been peer-reviewed.

However it has moderation and endorsement systems which (in theory) spot any Archimedes Plutonium wannabes.

## Re:arXiv articles - question (0)

## Anonymous Coward | more than 5 years ago | (#26005297)

Wow, you've read thousands of published peer-review articles, but you don't know whether or not arxiv articles are peer-reviewed?

Colour me skeptical.

## Re:arXiv articles - question (1)

## blind biker (1066130) | more than 5 years ago | (#26005731)

Wow, you've read thousands of published peer-review articles, but you don't know whether or not arxiv articles are peer-reviewed?

Colour me skeptical.

I have never read a single arXiv article. I've seen a few titles and abstracts, though.

## Re:arXiv articles - question (1)

## LeadSongDog (1120683) | more than 5 years ago | (#26006301)

## Re:arXiv articles - question (1)

## XchristX (839963) | more than 5 years ago | (#26005939)

Peer-review isn't always what it's cracked up to be. Read about the Bogdanov controversy that erupted in my uni some years back that exposes some serious flaws in the peer-review process.

http://en.wikipedia.org/wiki/Bogdanov_Affair [wikipedia.org]

## Looks like a big deal to me. (4, Informative)

## jonniesmokes (323978) | more than 5 years ago | (#26004825)

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 [uibk.ac.at] are working very hard on building the computers.

## Avinatan Hassidim and Seth Lloyd (5, Informative)

## aram.harrow (1424757) | more than 5 years ago | (#26004981)

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.

## Re:Avinatan Hassidim and Seth Lloyd (2, Insightful)

## saburai (515221) | more than 5 years ago | (#26005219)

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:Avinatan Hassidim and Seth Lloyd (2)

## wolfemi1 (765089) | more than 5 years ago | (#26005697)

It's Mike Wolfe, congratulations on making Slashdot, if this is your first time. What a happy surprise seeing your name there!

-Mike

## Re:Avinatan Hassidim and Seth Lloyd (1)

## JohnFluxx (413620) | more than 5 years ago | (#26005719)

It's awesome that you posted here :)

A quick question if I may..

Could raytracing be done efficently on quantum computers?

## Re:Avinatan Hassidim and Seth Lloyd (1)

## LeadSongDog (1120683) | more than 5 years ago | (#26006413)

## Re:Avinatan Hassidim and Seth Lloyd (1)

## joe_frisch (1366229) | more than 5 years ago | (#26006621)

## Bzzzt, wrong! (1, Informative)

## fph il quozientatore (971015) | more than 5 years ago | (#26005177)

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.

## Re:Bzzzt, wrong! (3, Interesting)

## pablomme (1270790) | more than 5 years ago | (#26005423)

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.

## A quantum linear equation (1)

## Hognoxious (631665) | more than 5 years ago | (#26006437)

## Progress Bar? (1)

## Fujisawa Sensei (207127) | more than 5 years ago | (#26006629)

What kind of side effects will a progress bar have since you can't know what its doing if you know where it is?

## Quantum of Solvethis (0)

## Anonymous Coward | more than 5 years ago | (#26006655)

## Other algorithms (1)

## Teppy (105859) | more than 5 years ago | (#26006711)

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.

## Comparing Apples to Apples (3, Interesting)

## internic (453511) | more than 5 years ago | (#26006875)

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.

## Re:Comparing Apples to Apples (1)

## BZ (40346) | more than 5 years ago | (#26007031)

Of course any quantum computing algorithm (including Shor's) has the same issue.

In practice, once the probability of the answer being incorrect is smaller than some threshold (e.g. the probability of the classical computer giving a wrong answer due to cosmic rays) it really doesn't matter that you're using a probabilistic algorithm.