### Which is faster: conventional or quantum computer?

##### May 17, 2013

A computer science professor at Amherst College has conducted experiments to test the speed of a quantum computing system (from D-Wave) against conventional computing methods.

“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.

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.

D-Wave retained McGeoch as an outside consultant to help devise experiments that would test its machines against conventional computers and algorithms.

**Thousands of times faster for specific problems**

McGeoch says the calculations the D-Wave excels at involve a specific combinatorial optimization problem, comparable in difficulty to the more famous “traveling salesperson” problem that’s been a foundation of theoretical computing for decades.

Briefly stated, the traveling salesperson problem asks this question: given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the original city?

Questions like this apply to challenges such as shipping logistics, flight scheduling, search optimization, DNA analysis and encryption, and are extremely difficult to answer quickly. The D-Wave computer has the greatest potential in this area, McGeoch says.

“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 a promising scaling trajectory.”

Whether the D-Wave computer will ever have mass market appeal is also difficult for McGeoch to assess. While the 439-qubit model she tested does have incredible computing power, there is that near-zero Kelvin chip operating temperature requirement that would make home or office use a chilly proposition. At present, she thinks the power of the D-Wave approach is too narrowly focused to be of much use to the average personal computer user.

“The founder of IBM famously predicted that only about five of his company’s first computers would be sold because he just didn’t see the need for that much computing power,” McGeoch says. “Who needs to solve those big problems now? I’d say it’s probably going to be big companies like Google and government agencies.”

And, while conventional approaches to solving these problems will likely continue to improve incrementally, this fast quantum approach has the potential to expand to larger variety of problems than it does now, McGeoch says.

“Within a year or two I think these quantum computing methods will solve more and bigger problems significantly faster than the best conventional computing options out there,” she says.

At the same time, she cautions that her first set of experiments represents a snapshot moment of the state of quantum computing versus conventional computing.

“This by no means settles the question of how fast the quantum computer is,” she says. “That’s going to take a lot more testing and a variety of experiments. It may not be a question that ever gets answered because there’s always going to be progress in both quantum and conventional computing.”

### References:

- Catherine C. McGeoch, Cong Wang, Experimental Evaluation of an Adiabiatic Quantum System for Combinatorial Optimization, presented at the 2013 Association for Computing Machinery (ACM) International Conference on Computing Frontiers, Ischia, Italy, May 15, 2013

## Comments (5)

May 18, 2013by T

Non commutative mathematics is the key to the mathematical approach to quantum computing

May 17, 2013by Jim Mooney

Cripes, we are living in the future. Last time I was looking at quantum computing they were shoving a few quibits around and I figured “ten years at least.” But suddenly, there’s a commercial model available.

Now if we could only unshackle ourselves from this seventeenth century economic system. Science needs to take a look at that – and I don’t mean economists, since none of them agree. I tend to think economics follows a dynamic fractal distribution of energy centers, and you could make solid predictions based on that, instead of wishful thinking and mostly BS, depending on your political persuasion.

May 17, 2013by Beatriz Valdes

All that brilliantly shared data is what gives me hope that the expected progress against aging may cristalize sooner than pronosticated!

May 17, 2013by eldras

If quantum computers solve their error problem (error increases the faster they go) the will revolutionise calculation.

Some people think super-recursive algorithms are even faster.

May 17, 2013by Jabbah

Scott Aaronson would disagree:

“[The] USC paper that reported the quantum annealing behavior of the D-Wave One, also showed no speed advantage whatsoever for quantum annealing over classical simulated annealing. In more detail, Matthias Troyer’s group spent a few months carefully studying the D-Wave problem—after which, they were able to write optimized simulated annealing code that solves the D-Wave problem on a normal, off-the-shelf classical computer, about 15 times faster than the D-Wave machine itself solves the D-Wave problem!”

http://www.scottaaronson.com/blog/?p=1400

USC paper: http://arxiv.org/abs/1304.4595