When Can Quantum Annealing Win?

H

HardOCP News

[H] News
Joined
Dec 31, 1969
Messages
0
The big brains at Google announced a breakthrough in the field of quantum computing yesterday. According to this blog post, the search giant thinks it has discovered a quantum algorithm that is one hundred million times faster than conventional processes. :eek:


We found that for problem instances involving nearly 1000 binary variables, quantum annealing significantly outperforms its classical counterpart, simulated annealing. It is more than 108 times faster than simulated annealing running on a single core. We also compared the quantum hardware to another algorithm called Quantum Monte Carlo. This is a method designed to emulate the behavior of quantum systems, but it runs on conventional processors. While the scaling with size between these two methods is comparable, they are again separated by a large factor sometimes as high as 108.
 
"The problems were designed to demonstrate that quantum annealing can offer runtime advantages for hard optimization problems characterized by rugged energy landscapes."

It's faster at doing what?
 
When are we going to stop talking about quantum computing and start seeing it in commercial products? This technology has been the promised land, right around the corner, revolution in computing, for the last 15+ years. Let's get it out of the lab and into production already please.
 
jardows said:
When are we going to stop talking about quantum computing and start seeing it in commercial products? This technology has been the promised land, right around the corner, revolution in computing, for the last 15+ years. Let's get it out of the lab and into production already please.
Click to expand...

DWAVE already has; that's the machine google is using. There's been questions whether DWAVES machine is actually a quantum machine or not, but googles results indicates it likely is.

Which is amazing, given no one else can get a single qbit stable, where DWAVE has a 64-qbit machine available that appears to work.
 
When Can Quantum Annealing Win?
Click to expand...

It's already WINNING like Sheen :D

jardows said:
When are we going to stop talking about quantum computing and start seeing it in commercial products? This technology has been the promised land, right around the corner, revolution in computing, for the last 15+ years. Let's get it out of the lab and into production already please.
Click to expand...

Because it won't help you in any general computing task. Sorry, the problem range that quantum computers are good at is very limited.

Also, according to this post on Ars by Statistical, even the worries about quantum computers breaking crypto are unfounded:

Well a couple things. First is that DWAVE is a quantum annealer. It is utterly useless for breaking crypto. General purpose quantum computers capable of implementing Shor's algorithm are at this point academic experiments. I think the best experiments were on the order of 5 qubits (i.e. can factor 5 bits numbers yes like "21"). Now DWAVE is pretty cool stuff and almost magic for the very limited set of problems it is optimized for but it isn't well suited for breaking crypto.

The second is most cryptography can't be broken by quantum computing. Shor's algorithm doesn't work against symmetric ciphers or hashing algorithms. Grover's algorithm can be used but the speedup is rather lackluster. You can achieve the same security by just doubling the key/hash length.

Also while most asymmetric encryption is highly vulnerable to Shor's algorithm running on a sufficiently sized general purpose QC (that don't exist yet) there are "post-quantum" algorithms which are not. They are not widely used today because they tend to have keys much larger and are significantly slower but they provide a quantum resistant option.
Click to expand...
 
For those wondering, these D-Wave "Quantum Processors" are so alien that to produce this algorithm that seems to show a more than significant enough speed up vs modified algorithms in regular processors, has taken the NASA- Google - D-Wave team a bit over 2 years studying how does the actual processor works in order to design it.

Kinda mind blowing.
 
This all sounds facinating, but can someone explain to me what Quantum Annealing is like I'm 5?

I am aware of the bare basics of quantum physics...schrodinger's cat, something exists in multiple states at once until observed, etc.
 
Revdarian said:
For those wondering, these D-Wave "Quantum Processors" are so alien that to produce this algorithm that seems to show a more than significant enough speed up vs modified algorithms in regular processors, has taken the NASA- Google - D-Wave team a bit over 2 years studying how does the actual processor works in order to design it.

Kinda mind blowing.
Click to expand...

Reverse engineering something to figure it out is like opening a treasure chest, especially if it is a technology you stumbled upon.
 
evilsofa said:
"The problems were designed to demonstrate that quantum annealing can offer runtime advantages for hard optimization problems characterized by rugged energy landscapes."

It's faster at doing what?
Click to expand...

CaptNumbNutz said:
This all sounds facinating, but can someone explain to me what Quantum Annealing is like I'm 5?

I am aware of the bare basics of quantum physics...schrodinger's cat, something exists in multiple states at once until observed, etc.
Click to expand...

Here's an explanation from D-Wave:

Quantum computing uses an entirely different approach than classical computing. A useful analogy is to think of a landscape with mountains and valleys.

Solving optimization problems can be thought of as trying to find the lowest point on this landscape. Every possible solution is mapped to coordinates on the landscape, and the altitude of the landscape is the “energy’” or “cost” of the solution at that point. The aim is to find the lowest point on the map and read the coordinates, as this gives the lowest energy, or optimal solution to the problem.

Classical computers running classical algorithms can only "walk over this landscape". Quantum computers can tunnel through the landscape making it faster to find the lowest point. The D-Wave processor considers all the possibilities simultaneously to determine the lowest energy required to form those relationships. The computer returns many very good answers in a short amount of time - 10,000 answers in one second. This gives the user not only the optimal solution or a single answer, but also other alternatives to choose from.

D-Wave systems use "quantum annealing" to solve problems. Quantum annealing “tunes” qubits from their superposition state to a classical state to return the set of answers scored to show the best solution...
Click to expand...
 
gamerk2 said:
Which is amazing, given no one else can get a single qbit stable, where DWAVE has a 64-qbit machine available that appears to work.
Click to expand...

And at the same time, appears NOT to work. Amirite?! :D

CaptNumbNutz said:
This all sounds facinating, but can someone explain to me what Quantum Annealing is like I'm 5?
Click to expand...

So it's like if...no, wait.
It's kind of like...no, that's not it.
Take, for example...nah, that's not gonna work.

To answer your question, no.
 
"We are optimistic that the significant runtime gains we have found will carry over to commercially relevant problems as they occur in tasks relevant to machine intelligence."

Oh dear.
 
LMT MFA said:
"We are optimistic that the significant runtime gains we have found will carry over to commercially relevant problems as they occur in tasks relevant to machine intelligence."

Oh dear.
Click to expand...
The class of problems they're using it for are useful for a particular type of discrete optimization. Commercially relevant problems include search, scheduling, routing and other very scary things. :p The problems are currently being solved less efficiently, but they're still being solved.
 
pxc said:
The class of problems they're using it for are useful for a particular type of discrete optimization. Commercially relevant problems include search, scheduling, routing and other very scary things. :p The problems are currently being solved less efficiently, but they're still being solved.
Click to expand...

I should have highlighted machine intelligence ;)
 
gamerk2 said:
DWAVE already has; that's the machine google is using. There's been questions whether DWAVES machine is actually a quantum machine or not, but googles results indicates it likely is.

Which is amazing, given no one else can get a single qbit stable, where DWAVE has a 64-qbit machine available that appears to work.
Click to expand...

Wow, this is really amazing technology.
I've never even heard of this before, thanks for sharing.
 
gamerk2 said:
DWAVE already has; that's the machine google is using. There's been questions whether DWAVES machine is actually a quantum machine or not, but googles results indicates it likely is.

Which is amazing, given no one else can get a single qbit stable, where DWAVE has a 64-qbit machine available that appears to work.
Click to expand...

DWave is using Quantum Annealing. The computers you are most likely thinking of are Quantum Gate Computers. Quantum Annealing is of limited usefulness and is restricted to a very specific set of optimization problems whereas quantum gate computing is much more general purpose.

Quantum annealing uses low-energy state qubits which are less prone to having troubles with decoherence.
 
damicatz said:
DWave is using Quantum Annealing. The computers you are most likely thinking of are Quantum Gate Computers. Quantum Annealing is of limited usefulness and is restricted to a very specific set of optimization problems whereas quantum gate computing is much more general purpose.

Quantum annealing uses low-energy state qubits which are less prone to having troubles with decoherence.
Click to expand...
Does that mean this could not be used in theory to crack passwords and password hashes?

I wonder what kind of impact quantum computing will have on the cyber security industry.
 
Tuxon86 said:
I, for one, welcome our new quantum annealing overlords :D
Click to expand...

Best first reply ever! :D

So...how does this topic have barely two pages of replies while the 'OMG Microsoft is stealing my cat pictures' thread have 4 pages already?

I read the Google blog post - which itself required some research on what the hell quantum annealing even is. It seems to me, as compared to where the "computer" (PC, laptop, Mac, cell phone, iPod, iPad, game console, etc, etc.) we all know and love is on it's own timeline, quantum computing is someplace before 1975 BUT as quantum makes progress it isn't going to take an actual 40 years to catch up because of the nature of quantum computing. There may be human constraints to the software - but some of that 40 years of progress on standard architecture can be applied directly to quantum with regard to software development methodologies. It's also possible the human constraints get sorted out in the process of advancing quantum. :eek:

IOW, take the current state of quantum and advance from where our current PCs were in 1975 to today - because that's apparently happening now. It won't be 40 years and might be a LOT less - if AI is possible and gets advancing like that...did I mention welcome to our new quantum computing overlords. I follow specific directions well, I'm easily entertained digitally and require minimal upkeep. :D
 
DarkStar02 said:
Does that mean this could not be used in theory to crack passwords and password hashes?

I wonder what kind of impact quantum computing will have on the cyber security industry.
Click to expand...

That is correct. The D-Wave cannot run Shor's algorithm. The D-Wave limited to a very specific set of problems. In addition, the fact that the quantum annealing requires the chip to be cooled to near absolute zero (using liquid helium) pretty much limits it to big institutions (i.e. you are unlikely to see a phone using a D-Wave chip).

True quantum computing would necessitate quantum cryptography
 
Not disputing that the D-Wave can't run Shor's (thanks for clarification on that in fact!) but stuff is happening...

https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml

"For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition."
(From August of 2015)
 
You must log in or register to reply here.
Back
Top