Using fermion-based analog computers to solve NP-hard problems in polynomial time If the fermion sign problem is an NP-hard problem as it seems to be proved by this work, is it possible to take an NP-hard problem, convert it into an equivalent fermionic state evolution problem, prepare the system physically, let it evolve, average over many experiments, and expect the result to converge to the solution of the original problem in a reasonable time? (i.e: less than exponential time)
 A: Scott Aarson gives examples of problems that might look like enabling such a reduction procedure, but fail in the paper 'NP-complete Problems and Physical Reality'.

Can NP-complete problems be solved efficiently in the physical universe? I survey proposals
  including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic
  algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation,
  analog computing, (...)

On classical approaches:

(...) There are other proposed methods for solving NP-complete problems that involve relaxation to
  a minimum-energy state, such as spin glasses and protein folding . All of these methods are subject
  to the same pitfalls of local optima and potentially long relaxation times.

On quantum computing:

(...) In other words,
  there is no “brute-force” quantum algorithm to solve NP-complete problems in polynomial time,
  just as there is no brute-force classical algorithm.

http://www.scottaaronson.com/papers/npcomplete.pdf
