If the ground states of interacting QFTs are so complicated, how did Nature find them? My question was inspired by trying to understand the paper Quantum Algorithms for Quantum Field Theories, by Jordan, Lee, and Preskill.  The main result of that paper is that scattering experiments in one of the simplest-possible interacting quantum field theories, namely &varphi;4 theory, can be efficiently simulated using a quantum computer (not just perturbatively, but in general).
Intuitively, that result sounds "obvious": how could it possibly be false?  So what's surprising to me, and in need of explanation, is how much work goes into making it rigorous---and even more pointedly, the fact that JLP don't know how to generalize their algorithm to handle massless particles, let alone other aspects of the full Standard Model like chiral fermions.  To some extent, these difficulties probably just reflect the complexity of QFT itself: when you're designing an algorithm (classical or quantum) to simulate something, and proving its correctness, you're not allowed to handwave any issue as "standard" or "well-known" or "who cares if it's not quite rigorous"!  Indeed, for that very reason, I think understanding how one would go about simulating QFT on a quantum computer could provide an extremely interesting avenue to understanding QFT itself.
But there's one thing in particular that seems to cause JLP their main difficulty, and that's what leads to my question.  Even for a "simple" interacting QFT like &varphi;4, the ground state of a few well-separated particles in the vacuum is already complicated and (it seems) incompletely understood.  So even for the very first step of their algorithm---preparing the initial state---JLP need to take a roundabout route, first preparing the ground state of the noninteracting field theory, then adiabatically turning on the interaction, adjusting the speed as they go to prevent level crossings.  Here, they need some assumption that causes the spectral gap to remain reasonably large, since the inverse of the spectral gap determines how long the adiabatic process needs to run.  And this, I think, is why they can't handle massless particles: because then they wouldn't have the spectral gap.
(Note that, at the end of the algorithm, they also need to adiabatically turn off the interaction prior to measuring the state.  Another note: this adiabatic trick seems like it might have something to do with the LSZ reduction formula, but I might be mistaken about that.)
Here, though, I feel the need to interject with an extremely naive comment: surely Nature itself doesn't need to do anything nearly this clever or complicated to prepare the ground states of interacting QFTs!  It doesn't need to adiabatically turn on interactions, and it doesn't need to worry about level crossings.  To explain this, I can think of three possibilities, in rapidly-increasing order of implausibility:
(1) Maybe there's a much simpler way to simulate QFTs using a quantum computer, which doesn't require this whole rigamarole of adiabatically turning on interactions.  Indeed, maybe we already know such a way, and the issue is just that we can't prove it always works?  More specifically, it would be nice if the standard dynamics of the interacting QFT, applied to some easy-to-describe initial state, led (always or almost always) to the interacting ground state that we wanted, after a reasonable amount of time.
(2) Maybe the cooling that took place shortly after the Big Bang simulated the adiabatic process, helping to ease the universe into the "right" interacting-QFT ground state.
(3) Maybe the universe simply had to be "initialized," at the Big Bang, in a ground state that couldn't be prepared in polynomial time using a standard quantum computer (i.e., one that starts in the state |0...0&rangle;).  If so, then the computational complexity class we'd need to model the physical world would no longer be BQP (Bounded-Error Quantum Polynomial-Time), but a slightly larger class called BQP/qpoly (BQP with quantum advice states).
I'll be grateful if anyone has any insights about how to rule out one or more of these possibilities.
 A: As you note, this is really a question about cosmology. There is a lot to say, but in the interest of brevity I will just address a part of the question.
Quantum chromodynamics is a strongly-coupled theory with a very complex vacuum state. The universe is not in the QCD vacuum today, but is pretty darn close to it, since the 2.7K background temperature is way below the mass gap of QCD. 
At high temperature QCD is a lot simpler -- the quarks and gluons are weakly interacting (asymptotic freedom). The state of high temperature QCD is fairly simple (though not trivial); it's approximately an ideal gas of relativistic particles. 
As the universe expanded and cooled adiabatically it passed through a (first order) phase transition from the "easier" high-temp state to the "harder" low temp state. Just below the phase transition the state was still pretty hot, but as the universe continued to expand adiabatically the state approached the QCD vacuum.
Of course, this would not have worked if preparing the QCD vacuum were QMA hard; the universe would have gotten stuck is some long-lived metastable state. That apparently did not happen, so we have cosmological evidence that preparing the QCD vacuum is easy, even if JLP have not proved it (yet).
You can ask further questions about how the hot initial state was prepared, why it was so homogeneous and isotropic, etc. which would lead us into a discussion about how cosmic inflation started and ended, but that's enough for now.
