Kvanttitietokoneen ja perinteisen tietokoneen nopeusvertailuja

A computer science professor at Amherst College who recently devised and conducted experiments to test the speed of a quantum computing system against conventional computing methods will soon be presenting a paper with her verdict: quantum computing is, “in some cases, really, really fast.”
“Ours is the first paper to my knowledge that compares the quantum approach to conventional methods using the same set of problems,” says Catherine McGeoch, the Beitzel Professor in Technology and Society (Computer Science) at Amherst. “I’m not claiming that this is the last word, but it’s a first word, a start in trying to sort out what it can do and can’t do.”

https://www.amherst.edu/aboutamherst/news/faculty/node/466477

http://dwave.wordpress.com/2013/05/08/first-ever-head-to-head-win-in-speed-for-a-quantum-computer/

Nyt on jo mahdollista tehdä ensimmäisiä karkeita arvioita kvanttitietokoneiden mahdollisista tehoista verrattuna perinteisiin tietokoneisiin. Kvanttitietokoneiden yleistyessä ja kvanttitietokone (D-Wave) teknologian kehittyessä tulee mahdolliseksi käyttää kvanttikiihdyttimiä tiettyjen raskaiden algoritmien ajamiseen.

McGeoch, author of A Guide to Experimental Algorithmics (Cambridge University Press, 2012), has 25 years of experience setting up experiments to test various facets of computing speed, and is one of the founders of “experimental algorithmics,” which she jokingly calls an “oddball niche” of computer science. Her specialty is, however, proving increasingly helpful in trying to evaluate different types of computing performance.

https://www.amherst.edu/aboutamherst/news/faculty/node/466477

“This type of computer is not intended for surfing the internet, but it does solve this narrow but important type of problem really, really fast,” McGeoch says. “There are degrees of what it can do. If you want it to solve the exact problem it’s built to solve, at the problem sizes I tested, it’s thousands of times faster than anything I’m aware of. If you want it to solve more general problems of that size, I would say it competes – it does as well as some of the best things I’ve looked at. At this point it’s merely above average but shows apromising scaling trajectory.”

https://www.amherst.edu/aboutamherst/news/faculty/node/466477

Erityisesti D-Wave on erittäin tehokas ratkaisemaan ns. traveling salesman problem (TSP).
http://en.wikipedia.org/wiki/Travelling_salesman_problem

http://mathworld.wolfram.com/TravelingSalesmanProblem.html

http://www.stanford.edu/~saberi/tsp.pdf

TSP:n voi ratkaista tehokkaasti jos tuloksen ei tarvitse olla kaikista paras mahdollinen. Jos tarvitsee todella parhaan ratkaisun, niin TSP on laskennallisesti rankka.
http://www.technologyreview.com/view/512821/shrinking-blob-computes-traveling-salesman-solutions/