text: user732: It's supposed that quantum computers could help to find the native state of all human DNA proteins.
  Does anyone know how to formulate the protein folding problem into a decision problem solvable either by quantum annealers or universal quantum computers?
  It would also be interesting to know, how to model a decision problem for classical computers, like Folding@Home.
  
  user73: I would expect that without any further insights into protein folding, a quantum method would look fairly similar to existing methods, but might have a bit more capability of exploring multiple states at the same time (without multitasking).
  Here's the approach used by Rosetta, which is used in both the Rosetta@home distributed computing project, and the foldit distributed gaming project:
  
  Rosetta's strategy for finding low energy shapes looks like this:
  
  Start with a fully unfolded chain (like a metal chain with its ends pulled).
  Move a part of the chain to create a new shape.
  Calculate the energy of the new shape.
  Accept or reject the move depending on the change in energy.
  Repeat 2 through 4 until every part of the chain has been moved a lot of times.
  
  We call this a trajectory. The end result of a trajectory is a predicted structure.
  
  
  user191: Protein folding problem can be viewed as a minimization problem. One can use quantum annealing to perform the minimization. Running this on quantum computers would improve the performance since they can perform the tunneling directly.
  In fact, quantum annealing was used (blog post) for lattice protein folding on the the D-Wave quantum computer (128 qubits). But this was an extremely simplified model, with only 40 discrete states.
  
original_text: 732: <p>It's supposed that quantum computers could help to find the native state of all human DNA proteins.</p>
  
  <p>Does anyone know how to formulate the protein folding problem into a decision problem solvable either by <a href="https://en.wikipedia.org/wiki/Quantum_annealing" rel="nofollow noreferrer">quantum annealers</a> or <a href="https://en.wikipedia.org/wiki/Quantum_Turing_machine" rel="nofollow noreferrer">universal quantum computers</a>?</p>
  
  <p>It would also be interesting to know, how to model a decision problem for classical computers, like <a href="http://folding.stanford.edu/" rel="nofollow noreferrer">Folding@Home</a>.</p>
   73: <p>I would expect that without any further insights into protein folding, a quantum method would look fairly similar to existing methods, but might have a bit more capability of exploring multiple states at the same time (without multitasking).</p>
  <p>Here's the approach used by <a href="http://boinc.bakerlab.org/rosetta/rah_graphics.php" rel="nofollow noreferrer">Rosetta</a>, which is used in both the <a href="http://boinc.bakerlab.org/" rel="nofollow noreferrer">Rosetta@home</a> distributed computing project, and the <a href="http://fold.it/portal/" rel="nofollow noreferrer">foldit</a> distributed gaming project:</p>
  <blockquote>
  <p>Rosetta's strategy for finding low energy shapes looks like this:</p>
  <ol>
  <li>Start with a fully unfolded chain (like a metal chain with its ends pulled).</li>
  <li>Move a part of the chain to create a new shape.</li>
  <li>Calculate the energy of the new shape.</li>
  <li>Accept or reject the move depending on the change in energy.</li>
  <li>Repeat 2 through 4 until every part of the chain has been moved a lot of times.</li>
  </ol>
  <p>We call this a trajectory. The end result of a trajectory is a predicted structure.</p>
  </blockquote>
   191: <p>Protein folding problem can be viewed as a minimization problem. One can use <a href="https://en.wikipedia.org/wiki/Quantum_annealing" rel="noreferrer">quantum annealing</a> to perform the minimization. Running this on quantum computers would improve the performance since they can perform the tunneling directly.</p>
  
  <p>In fact, quantum annealing was <a href="https://dx.doi.org/10.1038/srep00571" rel="noreferrer">used</a> (<a href="http://blogs.nature.com/news/2012/08/d-wave-quantum-computer-solves-protein-folding-problem.html" rel="noreferrer">blog post</a>) for lattice protein folding on the the D-Wave quantum computer (128 qubits). But this was an extremely simplified model, with only 40 discrete states.</p>
  