The study, “Finding low-energy conformations of lattice protein 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 protein folding 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:**
D-Wave researchers demonstrate progress in quantum computing

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

## El_Nose

## Deathclock

## Deathclock

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

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.