In first head-to-head speed test with conventional computing, quantum computer wins

May 08, 2013 by Peter Rooney
The D-Wave Systems Fridge with Cryogenic Packaging

(Phys.org) —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 () 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."

The quantum computer system she was testing, produced by D-Wave just outside Vancouver, BC, has a thumbnail-sized chip that is stored in a dilution refrigerator within a shielded cabinet at near absolute zero, or .02 degrees Kelvin in order to perform its calculations. Whereas conventional computing is binary, 1s and 0s get mashed up in , and within that super-cooled (and non-observable) state of flux, a lightning-quick logic takes place, capable of thousands of times faster than conventional computing methods can, according to her findings.

"You think you're in Dr. Seuss land," McGeoch says. "It's such a whole different approach to computation that you have to wrap your head around this new way of doing things in order to decide how to evaluate it. It's like comparing apples and oranges, or apples and fish, and the difficulty was coming up with experiments and analyses that allowed you to say you'd compared things properly. It definitely was the oddest set of problems I've ever coped with."

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.

That's why she spent a month last fall at D-Wave, which has produced what it claims is the world's first commercially available quantum . Geordie Rose, D-Wave's founder and Chief Technical Officer, retained McGeoch as an outside consultant to help devise experiments that would test its machines against conventional computers and algorithms.

McGeoch will present her analysis at the peer-reviewed 2013 Association for Computing Machinery (ACM) International Conference on Computing Frontiers in Ischia, Italy, on May 15. Her 10-page-paper, titled "Experimental Evaluation of an Adiabiatic Quantum System for Combinatorial Optimization," was co-authored with Cong Wang, a graduate student at Simon Fraser University.

D-Wave Cryogenic Packaging—Fridge Payload

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

Briefly stated, the travelling 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 apromising scaling trajectory."

McGeoch, who has spent her academic career in computer science, doesn't take a stance on whether the D-Wave is a true quantum computer or not, a notionsome physicists take issue with.

D-Wave One Systems Being Tested in the Lab

"Whether or not it's a quantum computer, it's an interesting approach to solving these problems that is worth studying," she says.

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

Explore further: Physicists design quantum switches which can be activated by single photons

Related Stories

D-Wave sells first commercial quantum computer

Jun 01, 2011

(PhysOrg.com) -- Last week, Burnaby, British Columbia-based company D-Wave Systems, Inc., announced that it sold its first commercial quantum computer. Global security company Lockheed Martin, based in Bethesda, ...

Recommended for you

Could 'Jedi Putter' be the force golfers need?

Apr 18, 2014

Putting is arguably the most important skill in golf; in fact, it's been described as a game within a game. Now a team of Rice engineering students has devised a training putter that offers golfers audio, ...

User comments : 25

Adjust slider to filter visible comments by rank

Display comments: newest first

bertibus
1 / 5 (4) May 08, 2013
They've already sold two to Lockheed Martin, and I believe the price was $10myn a piece.
eachus
3 / 5 (2) May 09, 2013
What this seems to be saying transferred through non-mathematicians is that D-Wave qNP=P whether or not P=?NP is even decidable. What does that mean? That there are problems that you can hand to a D-Wave machine (with enough qbits), say solve, and you get an answer in a few minutes, instead of a few thousand years (or more) for a conventional computer.

For example, cracking keys for most public key (actually non-symmetric key) systems will be a function of how many qbits your quantum computer can handle. At 439 qbits SSL2 is still safe, and I can't imagine any crooks managing to buy a several thousand qbit version anytime soon. But it is comming. (Shorr's algorithm for factoring numbers takes about 6 qbits per bit of key length. That doesn't mean that better algorithms are not possible...)
Nawangsari
1 / 5 (2) May 09, 2013
Somebody at Lockheed will be winning the Lotteries very soon.
NeutronicallyRepulsive
3.7 / 5 (3) May 09, 2013
I would love to see this (quantum cpu) as an integrated chip on a motherboard. As was x87 floating point co-processor once. With its special instruction set for the specific tasks. That would be bliss.
Ryan1981
1 / 5 (1) May 09, 2013
What I wonder if at some point an algorithm will be found that can use the advantages of a quantum computer for all computations instead of a select set as is now the case.
antialias_physorg
4 / 5 (4) May 09, 2013
But does it have it really? The precision of 439-qubit is less than primitive forty years old eight-bit processor like the Intel 8008 from 1972.

It's qbit. Not bit.
While a qbit, like a classical bit, is classified by 2 states (e.g. polarization directions) a single qbit can be in a superposition of both - making it able to hold as much information as many (theoretically infinitely many) classical bits.
Jo01
1 / 5 (7) May 09, 2013
It's qbit. Not bit.
While a qbit, like a classical bit, is classified by 2 states (e.g. polarization directions) a single qbit can be in a superposition of both - making it able to hold as much information as many (theoretically infinitely many) classical bits.

No, a qbit can hold the same information as a bit if you read it out. It has the information of two bits if its in superposition.

J.
Higgsbengaliboson
1 / 5 (5) May 09, 2013
D-wave machine will have the fastest technique to solve computation algorithm.A quantum processor will have the best technique here:the travelling salesperson problem is more like a problem in Discrete Mathematics where we have to choose the shortest possible path in the graph...here same phenomenology is being used in computing technique.
antialias_physorg
5 / 5 (3) May 09, 2013
But you can use it to perform information storage and/or processing that is much more than one bit

It has the information of two bits if its in superposition.

https://en.wikipe...._qubits

Careful. 'bit' is a unit of information logarithm base two of the number of possible states. qbit is not.
A 439 qbit memory can be in a superposition that would require 2^439 regular bits to represent (double that since they're complex states). Reading it out will get you only 439 bits. But here you already see that it's apples and oranges, because the storage/reading (as with regular memory registers) is not the main point of qbits
The point is that through this vast number of stored potential bits, choosing the right algorithm for reading out, you can get the answer in one go

Example: if all the combinations and permutations in a travelling salesman problem would need 2^439 bit to express you could solve the problem in one step using 439 qbits.
Jo01
1 / 5 (7) May 09, 2013

A 439 qbit memory can be in a superposition that would require 2^439 regular bits to represent (double that since they're complex states).


So, as I said: 1 qbit has the information of 2^1 bits and not as you stated in your previous comment: "...making it able to hold as much information as many (theoretically infinitely many) classical bits" which is clearly wrong.
So be careful yourself and acknowledge your wrong.

J.
Foolish1
1 / 5 (1) May 09, 2013
The problem with the 439-qubit claim is by itself conveys no useful information about the capabilities of this "quantum" computer.

D-wave is cheating the search space of a single operation is not 2^439 or anything remotly resembling it. The state of the art today is around 8 entangled qbits if your really really lucky. There is no reason to believe we will ever be able to scale up the **exponents** without having to pay an impractical cost.

I have no doubt quantum computers are and will continue to be useful in the future but the quantum hype of exponential scaling (e.g. code breaking, classically impossible to solve NP problems..etc) smacks of magic to which we are not entitled.
ValeriaT
1 / 5 (6) May 09, 2013
As I already explained here many times, the computer speed is defined with speed of processing information and it cannot beat the Heissenberg uncertainty principle. The quantum computers are potentially faster than the classical ones, but very approximate due their low number of qubits.
The state of the art today is around 8 entangled qbits if your really really lucky
D-wave systems are classical heavily overclocked/overcooled computers rather than the true quantum ones. In particular the questions remain due to the lack of conclusive experimental proof of quantum entanglement inside D-Wave devices
Pressure2
1 / 5 (6) May 09, 2013
D-wave systems are classical heavily overclocked/overcooled computers rather than the true quantum ones. In particular the questions remain due to the lack of conclusive experimental proof of quantum entanglement inside D-Wave devices
That pretty much sums it up ValeriaT.

I'll take it a step further, true quantum computers will never exist because superposition and quantum entanglement exist only in theory and have never been proven.
gwrede
1.8 / 5 (5) May 10, 2013
I couldn't help but giggle at
1s and 0s get mashed up in quantum computing, and within that super-cooled (and non-observable) state of flux, a lightning-quick logic takes place, capable of solving problems thousands of times faster than conventional computing methods can
This sounds just like some scifi movie poster from the Fifties.

(YouTube "Earth vs. the Flying Saucers" trailer, in honor of sfx icon Ray Harryhausen, 92, who just died.)

antialias_physorg
5 / 5 (3) May 10, 2013
So, as I said: 1 qbit has the information of 2^1 bits

No. this is wrong.
You can READ OUT 1 bit. But you can store/manipulate a lot of bits worth of information in onwe qbit at a time.
Thinking of a qbit as a mere memory cell is wrong. It's apples and oranges. The superpositon of states let's you do stuff with it that would require a lot of calssical bits of storage (and algorithmic processing capability)

If you'd argue that a 1 bit computer has the same cpabilities as a 1qbit computer just because you can read one bit out then that would be as wrong as you can get.
Jo01
1 / 5 (6) May 11, 2013
So, as I said: 1 qbit has the information of 2^1 bits

No. this is wrong.
You can READ OUT 1 bit. But you can store/manipulate a lot of bits worth of information in onwe qbit at a time.
Thinking of a qbit as a mere memory cell is wrong. It's apples and oranges. The superpositon of states let's you do stuff with it that would require a lot of calssical bits of storage (and algorithmic processing capability)

If you'd argue that a 1 bit computer has the same cpabilities as a 1qbit computer just because you can read one bit out then that would be as wrong as you can get.


You contradict your own statements. I never stated the last remark you made and I never compared a qbit to a memory cell.
So I wonder, do you agree with the following statement from a scientific paper:
"If there is a system of m-qubits, the system can contain information of 2^m states"

If so, then you must agree with "If there is a system of 1-qubits, the system can contain in- formation of 2^1 states"
Jo01
1 / 5 (6) May 11, 2013
2^1 is 2, so you must agree with "If there is a system of 1-qubits, the system can contain in- formation of 2 states". One state can be represented with a (one) bit so two states can be represented with 2 bits, hence you must agree with: "If there is a system of 1-qubits, the system can contain information of 2 bits".
So "1 qbit has the information of 2 bits".
QED.

J.
antialias_physorg
5 / 5 (3) May 11, 2013
"If there is a system of 1-qubits, the system can contain in- formation of 2 states".

No. A system of 1 qbit can READ OUT information that contains 1 bit. But the system can CONTAIN much more information.
qbit cells are not mere memory cells. You're comparing apples and oranges here.

You're comitting what we programmers call classical GIGO in your QED.
(GIGO: garbage in - garbage out. Which means: wrong assumptions lead to faulty conclusions).
Jo01
1 / 5 (7) May 12, 2013
"If there is a system of 1-qubits, the system can contain in- formation of 2 states".

No. A system of 1 qbit can READ OUT information that contains 1 bit. But the system can CONTAIN much more information.
qbit cells are not mere memory cells. You're comparing apples and oranges here.

You're comitting what we programmers call classical GIGO in your QED.
(GIGO: garbage in - garbage out. Which means: wrong assumptions lead to faulty conclusions).


Ha ha, I am a programmer (and amateur scientist) myself.
I might point out to my 'defense' that the starting axiom is from a scientific paper (and generally accepted for as far as I can see) and not from myself. So this means you reject a common scientific viewpoint. No laws (except logic in this case) against that.
The point is that 'information' relates to the information the (quantum) system handles and not the state of (quantum) system itself. In other words: we aren't simulating the quantum system itself and the (cont)
Jo01
1 / 5 (7) May 12, 2013
... quantum state is 'orthogonal' to the information the system handles. I don't care in what exact state the qbit is, if it is 0 or 1 or entangled, I only look at the maximum number of (bits of information) to represent it. And if all m qbits are entangled that maximum is 2^m.

J.
megmaltese
1.7 / 5 (6) May 12, 2013
"Really, really fast" is not a measure I can compare in any way to anything...
baudrunner
1 / 5 (6) May 12, 2013
D-wave systems are classical heavily overclocked/overcooled computers rather than the true quantum ones.
That's just so wrong. There's nothing "classical" about D-Wave's system. It's a true quantum computer in every meaning of the word. It's only drawback is that it is designed for one particular type of problem, which, incidentally, has many applications. Don't disparage the technology developed outside of America just because it isn't American, ValeriaT. You are being very transparent here.
megmaltese
1 / 5 (5) May 12, 2013
Why they didn't just give a TIME FRAME value about this test?
Traditional CPU needed 6 hours, QBIT CPU solved in 5 minutes?

Why?
ValeriaT
1 / 5 (5) May 19, 2013
just because it isn't American, ValeriaT. You are being very transparent here.
Nope, my theory is, that the computational power i.e. the product of speed and precision of calculations is limited with uncertainty principle in the same way for both classical, both quantum computers - which therefore cannot provide any substantial gain in processing speed. 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! Of course, if you wanted even more classical speedup than that, then you could simply add more processors to your classical computer, for only a tiny fraction of the ~$10 million that a D-Wave One would set you back. I absolutely don't care about country of origin of D-Wave - after all, I'm not from USA anyway.
antialias_physorg
5 / 5 (1) May 19, 2013
And if all m qbits are entangled that maximum is 2^m.

No. Read the wikipedia link. The maximum information contained (and processed) is much more. You're still thinking classical bit cells.
qbit cells are not memory cells in the classical sense.

More news stories

NASA's space station Robonaut finally getting legs

Robonaut, the first out-of-this-world humanoid, is finally getting its space legs. For three years, Robonaut has had to manage from the waist up. This new pair of legs means the experimental robot—now stuck ...

Ex-Apple chief plans mobile phone for India

Former Apple chief executive John Sculley, whose marketing skills helped bring the personal computer to desktops worldwide, says he plans to launch a mobile phone in India to exploit its still largely untapped ...

Filipino tests negative for Middle East virus

A Filipino nurse who tested positive for the Middle East virus has been found free of infection in a subsequent examination after he returned home, Philippine health officials said Saturday.

Egypt archaeologists find ancient writer's tomb

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...