New quantum algorithm can solve monster-size equations

[bananas]

http://www.scientificamerican.com/article.cfm?id=warp-speed-algebra

From the January 2010 Scientific American Magazine

Warp-Speed Algebra: New Algorithm Does Algebra in a Snap
New quantum algorithm can solve monster-size equations

By Davide Castelvecchi

<snip>

The latest quantum algorithm is generating excitement among physicists. It tackles linear equations: expressions such as 3x + 2y = 7 and typically written with unknowns on one side and constants on the other. Many high schoolers learn the trite mechanics of solving systems of such equations by eliminating one unknown at a time. Speed becomes crucial when systems contain billions of variables and billions of equations, which are not unusual in modern applications such as simulations of weather and other physical phenomena. Efficient algorithms can solve large, “N by N” systems (systems having N linear equations and N unknowns) by computer. Still, calculation time grows at least as fast as N does: if N gets 1,000 times larger, the problem will take at least 1,000 times longer to solve, often more.

The quantum algorithm now proposed by Aram W. Harrow of the University of Bristol in England and Avinatan Hassidim and Seth Lloyd of the Massachusetts Institute of Technology takes a clever shortcut. It can return the most relevant information about the solution without fully calculating the solution itself, thus trading off the amount of data it produces for speed. (For example, in the case of weather prediction it could return the average temperature over a town rather than the temperatures predicted city block by city block.)

<snip>

The gain in speed is enormous: the time required to produce the universal solution grows only with the number of digits in N. Thus, if N gets 1,000 times larger, the algorithm takes three times as long (because three digits are added to N), as opposed to 1,000 times as long. Even writing down the result for all the variables would involve 1,000 times more steps in the classical case. “It takes exponentially less time to solve the problem than to read the solution,” Lloyd says only half-jokingly.

<snip>

Some applications could be possible sooner, Lloyd says, if they exploit the intrinsically quantum nature of photons. He proposes, for example, that the algorithm could be embodied in a “superimaging device” that would remove optical distortions in a telescope. Each photon measured by the telescope would play the role of the constant terms of the equation, and the distortions would correspond to a linear system of equations. Finding the solutions would mean reversing the distortions, thus improving image quality.

[ChairmanAgnostic]

1. the maths continue to amaze. To think that the scientists of

the 1890s were convinced that the universe was solved. Then again, some bible experts contend that their book inerrantly contains all the knowledge in the universe.

[Xipe Totec]

2. Now we can finally create an infinite improbability Drive!

Infinite Improbability Drive

The Infinite Improbability Drive is a wonderful new method of crossing vast intersteller distances in a mere nothingth of a second without all that tedious mucking about in hyperspace.

It was discovered by a lucky chance, and then developed into a governable form of propulsion by the Galactic Government's research team on Damogran.

This, briefly, is the story of its discovery.

The principle of generating small amounts of finite improbability by simply hooking the logic circuits of a Bambleweeny 57 sub-meson Brain to an atomic vector plotter suspended in a strong Brownian Motion producer (say a nice hot cup of tea) were of course well understood - and such generators were often used to break the ice at parties by making all the molicules in the hostess's undergarments leap simultaneously one foot to the left, in accordance with the Theory of Indeterminacy.

Many respectable physicists said that they weren't going to stand for this - partly because it was a debasement of science, but mostly because they didn't get invited to those sort of parties.

Another thing they couldn't stand was the perpetual failure they encountered in trying to construct a machine which could generate the infinite improbability field needed to flip a spaceship across the mind-paralysing distances between the furthest stars, and in the end they grumpily announced that such a machine was virtually imposssible.

Then, one day, a student who had been left to sweep up the lab after a particulary unsuccessful party found himself reasoning this way:

If, he thought to himself, such amachine is a virtual impossibility, then it must logically be a finite improbability. So all I have to do in order to make one, is to work out exactly how improbable it is, feed that figure into the finite improbability generator, give it a fresh cup of really hot tea ... and turn it on!

He did this, and was rather startled to discover that he had managed to create the long sought after golden Infinite Improbability generater out of thin air.

It startled him even more when just after he was awarded the Galactic Institute's Prize for Extreme Cleverness he got lynced by a rampaging mob of respectable physicists who had finally realized that the one thing they really couldn't stand was a smartass.

http://www.earthstar.co.uk/drive.htm

[Birthmark]

6. I don't think that's very likely.

[Xipe Totec]

7. Yes, but how unlikely is it?

All we have to do in order to make one, is to work out exactly how unlikely it is, feed that figure into the finite improbability generator, give it a fresh cup of really hot tea ... and turn it on!

:P

[Birthmark]

8. I can't tell you right now.

Got a party to get to. ;)

[Xipe Totec]

9. I don't think that's very likely

:rofl:

[UndertheOcean]

3. I can't wait for the first Quantum Computer n/t

[ZombieHorde]

4. Recommended. nt

[Skink]

5. now bigger better subprime credit default swaps.