A team of Harvard University researchers, led by Professor Alan Aspuru-Guzik, have used Dwave’s adiabatic quantum computer to solve a protein folding problem. The researchers ran instances of a lattice protein folding model, known as the Miyazawa-Jernigan model, on a D-Wave One quantum computer.

The research used 81 qubits and got the correct answer 13 times out of 10,000. However these kinds of problems usually have simple verification to determine the quality of the answer. So it cut down the search space from a huge number to 10,000. Dwave has been working on a 512 qubit chip for the last 10 months. The adiabatic chip does not have predetermined speed up amounts based on more qubits and depends upon what is being solved but in general the larger number of qubits will translate into better speed and larger problems that can be solved. I interviewed the CTO of Dwave Systems (Geordie Rose back in Dec, 2011). Usually the system is not yet faster than regular supercomputers (and often not faster than a desktop computer) for the 128 qubit chip but could be for some problems with the 512 qubit chip and should definitely be faster for many problems with an anticipated 2048 qubit chip. However, the Dwave system can run other kinds of algorithms and solutions which can do things that regular computers cannot. The system was used by Google to train image recognition systems to remove outliers in an automated way.

ABSTRACT – We present the first quantum-mechanical implementation of lattice protein models using a programmable quantum device. We were able to encode and to solve the global minima solution for a small tetrapeptide and hexapeptide chain under several experimental schemes involving 5 and 8 qubits for the four-amino-acid sequence (Hydrophobic-Polar model) and 5, 27, 28, and 81 qubits experiments for the six-amino-acid sequence under the Miyazawa-Jernigan model for general pairwise interactions. For the experiment with 8 qubits, we simulated the dynamics of the quantum device with a Redfield equation with no adjustable parameters, obtaining excellent agreement with experiment. Since the quantum annealing algorithm not only finds the ground state but also the low-lying excited states, it provides information about the relevant minimum energy compact structures of protein sequences and it is useful to evaluate designability and stability such as that found in natural protein sequences, where the global minimum of free energy is well separated in energy from other misfolded states. 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.

This was 81 qubit work. Dwave announced a 512 qubit chip was created late in 2011 and was being prepared for commercialization in 2012. The published research work generally lags the current work by 1-2 years. 512 qubits used for protein folding solutions would be a lot faster and should be able to solve far larger problems. Dwave should also be developing 2048 qubit chips in the next few years.

“The D-Wave computer found the ground-state conformation of six-amino acid lattice protein models. This is the first time a quantum device has been used to tackle optimization problems related to the natural sciences,” said Professor Alán Aspuru-Guzik from the Department of Chemistry and Chemical Biology at Harvard University.

Proteins contribute to virtually every process that occurs within a cell. The shape of a protein is closely related to its function. Understanding the shape of a protein helps researchers understand how it behaves, accelerating advances in many different areas of life sciences, including drug and vaccine design.

A cornerstone of computational biophysics, lattice protein folding models provide useful insight into the energy landscapes of real proteins. Understanding these landscapes, and how real proteins fold into the shapes that help give them their function, is an extremely difficult problem for today’s computers to solve.

Dr. Alejandro Perdomo-Ortiz, the lead author of the paper, stated that: “Knowing that we can use real quantum computers to solve hard problems in biology is an exciting and important result. The techniques developed in this report can also be used to tackle other biophysical problems such as molecular recognition, protein design, and sequence alignment.”

*Device architecture and qubit connectivity. The array of superconducting quantum bits is arranged in 4 × 4 unit cells that consist of 8 quantum bits each. Within a unit cell, each of the 4 qubits in the left-hand partition (LHP) connects to all 4 qubits in the right-hand partition (RHP), and vice versa. A qubit in the LHP (RHP) also connects to the corresponding qubit in the LHP (RHP) of the units cells above and below (to the left and right of) it. (a) Qubits are labeled from 0 to 127 and edges between qubits represent couplers with programmable coupling strengths. Grey qubits indicate the 115 usable qubits, while vacancies indicate qubits under calibration which were not used. The larger experiments (Experiments 1,2, and 4) were performed on this chip, while the three remaining smaller experiments were run on other chips with the same architecture. (b) Embedding and qubit connectivity for Experiment 4, coloring the 81 qubits used in the experiment. Nodes with the same color represent the same logical qubit from the original 19-qubit Ising-like Hamiltonian resulting from the energy function associated with Experiment 4 (see Supplementary material for details). This embedding aims to fulfill the arbitrary connectivity of the Ising expression and allows for the coupling of qubits that are not directly coupled in hardware.*

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.

Even though the quantum device follows a quantum annealing protocol, the odds of measuring the ground state are not necessarily high. For example, in the 81 qubit experiment, only 13 out of 10,000 measurements yielded the desired solution. We attribute these low-percentages to the analog nature of the device and to precision limitations in the real values of the local fields and couplings among the qubits in the experimental setup. When compared to other problem implementations, physical problems such as lattice folding lack the structure of the Ramsey number problem37. In the lattice folding problem implemented here, the parameters defining the problem instances are arbitrary and do not fall into certain integral distinct values as in the case of the Ramsey number experiment, making precision issues more pronounced in our implementation.

To gain insights into the dynamics and evolution of the quantum system, we numerically simulated the superconducting array with a Bloch-Redfield model of the 8-qubit experiment (see Supplementary material) which takes into account thermal fluctuations in the states due to the finite temperature (20mK) of the quantum device. For this 8-qubit experiment, the simulation predicted a ground state probability of 80.7 %, in excellent agreement with the experimentally observed value (80.3%). It is important to note that no adjustable parameters were used in our simulations to fit the data and all the parameters correspond to values measured directly from the quantum device.

The temperature of the device is comparable with the minimum gap of the eight-qubit Hamiltonian. Therefore, we expect stronger excitation/relaxation near the gap closing, τ ≈ 0.6, due to exchange of energy with the environment, when compared to the other regimes of the annealing schedule where the gap is much larger than kBT. In the absence of environment (a fully coherent process), our simulations indicate that that the success probability would be 100%, within numerical error. For the simulations at 20 mK, the probability in the ground state goes down to ~ 55%, but the same fluctuations make the system relax back to the ground state, yielding tan 80.27% success probability. This is due to the advantageous natural tendency of the system to approach a thermal equilibrium which favors the ground state after crossing the minimum energy gap. As previously discussed in similar numerical simulations of quantum annealing algorithms, strong coupling to the bath and non-Markovianity would require going beyond the Bloch-Redfield model, but the agreement between experimental and simulated results support the validity of the quantum mechanical model used to describe the device. Previously reported temperature dependence predictions for the tunneling rate on the same qubits22 and excellent agreement with the same level of theory used here reinforce the validity of our simulations for this 8-qubit instances.

*(a) Step-by-step construction of the binary representation of lattice protein. Two qubits per bond are needed and the bond directions are denoted as “00” (downwards), “01” (rightwards), “10” (leftwards), and “11” (upwards). The example shows one of the possible folds of an arbitrary six-amino-acid sequence. Any possible N-amino-acid fold can be represented by a string of variables with . (b)Time-dependence of the A(τ) and B(τ) functions, where τ = t/trun with trun = 148 µs, (c) time-dependent spectrum obtained through numerical diagonalization, and (d) Bloch-Redfield simulations showing the time-dependent population in the first eight instantaneous eigenstates of the experimentally implemented 8-qubit Hamiltonian (Eq. 3) with Hp from Eq. S18 in the Supplementary material. In panel (c), for each instantaneous eigenenergy curve we have subtracted the energy of the ground state, effectively plotting the gap of the seven-lowest-excited states with respect to the ground state (represented by the baseline at zero-energy). As a reference, we show the energy with the device temperature, which is comparable to the minimum gap between the ground and first excited state. In panel (d), populations are ordered in energy from top (ground state) to bottom. Although τ = t/trun runs from 0 to 1, we show the region where most of the population changes occur. As expected, this is in the proximity of the minimum gap between the ground and first excited state around τ ~ 0.4 [see panel(c)].*

26 pages of supplemental information

*If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks*