D-Wave uses quantum method to solve protein folding problem

Aug 21, 2012 by Lisa Zyga report
D-Wave One and CEO Geordie Rose. Image credit: D-Wave Systems, Inc.

(Phys.org) -- While there has been some skepticism as to whether the Canadian company D-Wave’s quantum computing system, the D-Wave One, truly involves quantum computing, the company is intent on proving that the system is both a quantum device as well as a useful one. In a new study, D-Wave CEO Geordie Rose and other D-Wave researchers have teamed up with Harvard quantum physicist Alán Aspuru-Guzik and post-doc Alejandro Perdomo-Ortiz to demonstrate that the D-Wave One system can solve the challenging task of finding the lowest-energy configuration of a folded protein.

The study, “Finding low-energy conformations of lattice models by quantum annealing,” is published in a recent issue of Nature’s Scientific Reports.

The computer used quantum annealing to find the lowest-energy protein configuration by solving for the configuration as an optimization problem, where the optimal state was the lowest-energy state. Proteins can be folded in a large number of ways because they’re made up of many chains of amino acids. Yet somehow, proteins almost always manage to fold themselves in the correct configuration (when they don’t fold correctly, they can cause misfolded-protein diseases such as Alzheimer's, Huntington's, and Parkinson's). Scientists think that proteins fold themselves correctly because the correct configuration is also the state of lowest energy, the state at which the protein becomes stable.

In quantum annealing, the system starts by randomly picking a starting state, and then selecting random neighbor states to see if they have lower energies than the starting state. If they do, the computer replaces the original state with the lower-energy state. The process is considered quantum because it involves quantum tunneling to explore the different states by traveling directly through certain barriers rather than climbing over them. In this way, quantum annealing differs from the classical version, called “simulated annealing,” which explores different states based on temperature. Previous research has shown that quantum annealing has advantages over simulated annealing in some situations.

In this study, the researchers showed that D-Wave One - which has the distinction of being the first commercial quantum annealer - can solve some simple problems by annealing all the way to the ground state. The problems here only contain a small number of amino acids, so they have only a relatively small number of possible configurations, and can still be solved on a classical computer. Also, the quantum technique has low odds of measuring the ground state, with only 13 out of 10,000 measurements yielding the desired solution. The researchers attribute this low percentage in part to the limitations of the machine itself, and in part to thermal noise that disrupted the computation. Nevertheless, the study provides the first quantum-mechanical implementation of protein models using a programmable quantum device.

“Harnessing quantum-mechanical effects to speed up the solving of classical optimization problems is at the heart of quantum annealing algorithms (QA),” the researchers wrote in their study. “There is theoretical and experimental evidence of the advantage of solving classical optimization problems using QA, over its classical analogue (simulated annealing). In QA, quantum mechanical tunneling allows for more efficient exploration of difficult potential energy landscapes such as that of classical spin-glass problems. In our implementation of lattice folding, quantum fluctuations (tunneling) occurs between states representing different model protein conformations or folds.”

The study also lends more support to the quantum nature of the D-Wave One, since the system behaved exactly as expected if quantum aspects were contributing. The researchers see even more to look forward to in the future.

“The approach employed here can be extended to treat other problems in biophysics and statistical mechanics, such as molecular recognition, protein design, and sequence alignment,” they wrote.

Explore further: Experiment makes Schrodinger's cat choose—things can be real, or certain, but not both

More information: Alejandro Perdomo-Ortiz. “Finding low-energy conformations of lattice protein models by quantum annealing.” Scientific Reports. DOI:10.1038/srep00571

Abstract
Lattice protein folding models are a cornerstone of computational biophysics. Although these models are a coarse grained representation, they provide useful insight into the energy landscape of natural proteins. Finding low-energy threedimensional structures is an intractable problem even in the simplest model, the Hydrophobic-Polar (HP) model. Description of protein-like properties are more accurately described by generalized models, such as the one proposed by Miyazawa and Jernigan (MJ), which explicitly take into account the unique interactions among all 20 amino acids. There is theoretical and experimental evidence of the advantage of solving classical optimization problems using quantum annealing over its classical analogue (simulated annealing). In this report, we present a benchmark implementation of quantum annealing for lattice protein folding problems (six different experiments up to 81 superconducting quantum bits). This first implementation of a biophysical problem paves the way towards studying optimization problems in biophysics and statistical mechanics using quantum devices.

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

A quantum leap in computing

Jan 04, 2012

When American physicist Richard Feynman in 1982 proposed creating a quantum computer that could solve complex problems, the idea was merely a theory scientists believed was far off in the future.

Breaking the limits of classical physics

Jun 07, 2012

(Phys.org) -- With simple arguments, researchers show that nature is complicated. Researchers from the Niels Bohr Institute have made a simple experiment that demonstrates that nature violates common sense ...

At Yale, quantum computing is a (qu)bit closer to reality

Feb 15, 2012

(PhysOrg.com) -- Physicists at Yale University have taken another significant step in the development of quantum computing, a new frontier in computing that promises exponentially faster information processing ...

Recommended for you

Putting the squeeze on quantum information

Sep 25, 2014

Canadian Institute for Advanced Research researchers have shown that information stored in quantum bits can be exponentially compressed without losing information. The achievement is an important proof of principle, and could ...

Are weak values quantum? Don't bet on it

Sep 24, 2014

(Phys.org) —New work asserts that a key technique used to probe quantum systems may not be so quantum after all, according to Perimeter postdoctoral researcher Joshua Combes and his colleague Christopher ...

User comments : 6

Adjust slider to filter visible comments by rank

Display comments: newest first

El_Nose
not rated yet Aug 21, 2012
if it works then it's big -- as I recall Cal tech has not given it a stamp of approval yet.
Deathclock
1 / 5 (2) Aug 21, 2012
The technological singularity is approaching... quantum computing will be the turning point.
Sonhouse
not rated yet Aug 21, 2012
What is the difference between this 'quantum' method and 'genetic programming'? Isn't that what they call making a small change and checking the results against some criteria, then re-iterate?
Tausch
1 / 5 (1) Aug 21, 2012
Lowest energy state vs. temperature 'states'.
Traveling salesman problem - the 'least' 'distance' solutions.

It is not about minimum distance.
Oh well.
An ideal 'temperature' 'state' for 'folds' of a feather...
sticking together.
Deathclock
1 / 5 (2) Aug 21, 2012
What is the difference between this 'quantum' method and 'genetic programming'? Isn't that what they call making a small change and checking the results against some criteria, then re-iterate?


Genetic or evolutionary algorithms solve optimization problems by simulating evolution via natural selection... this really has nothing at all to do with that other than that it is an optimization algorithm.

As was mentioned, look up the travelling salesman problem. There are a finite number of solutions and each can be checked in turn but this would take a remarkable amount of time... the hope of quantum computing is that each potential solution could be checked simultaneously... reducing a O(n!) problem to an O(1) problem.
MCPtz
not rated yet Aug 21, 2012
In my university experience, Genetic algorithms are approximations. They may settle on a good answer, but it isn't guaranteed to be optimal.

The article intended to find the optimal solution which means it has to solve at least an exponential if not a factorial run time problem on a typical serial cpu. (I'm not sure about the original problem)

On that note, it looks like they are running a genetic algorithm, because they only got 13 out of 10000 tries are correct. Not sure if they intend to get 100% correct or what.

I think it's really cool still. They are using Q-bits to solve things. I also noted they used as many Q-bits as they needed to solve the problem (81), rather than having a classical power of 2 as the number of Q-bits.