Take the 2-minute tour ×

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 ϕ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 ϕ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⟩). 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.

share|improve this question
Doesn't spontaneous symmetry-breaking mean that the universe has lots of different (but equivalent) ground states? –  Peter Shor Jan 2 '13 at 22:24
Thanks---yes, I suppose! So then I simply revise the question to, "how does Nature find A ground state?" –  Scott Aaronson Jan 2 '13 at 22:26
An even trickier question is: "how did Nature find the same ground state throughout the observable universe?" And we're not quite in a ground state—there's that 3°K cosmic microwave background radiation. –  Peter Shor Jan 2 '13 at 22:36
Essentially by quantum computing...trying every possibility at once. It is a little more clear in the language of path integrals. –  dmckee Jan 2 '13 at 23:16
dmckee: So, if that's correct, can you get rid of the "adiabatically turn on the interaction" step in computer simulations of QFT, or can't you? –  Scott Aaronson Jan 2 '13 at 23:23

1 Answer 1

up vote 15 down vote accepted

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.

share|improve this answer
Thanks, John -- that's extremely helpful! I'm delighted and awestruck that my option (2), which I considered rather fanciful (but not logically excluded), seems not so far from the truth. So, what you need to do in the "adiabatic" step of JLP could be explained, only slightly tongue-in-cheek, as recreating something like the conditions of the early universe! (Of course, this still doesn't explain why you need to adiabatically turn off the interactions before measuring, but maybe that's a separate issue.) –  Scott Aaronson Jan 3 '13 at 1:04
One quick thing: your answer focuses on QCD. Is the story substantially different if we want to prepare other interacting ground states, say for the electroweak or Higgs fields? –  Scott Aaronson Jan 3 '13 at 1:09
BTW, I suppose we'd better HOPE that the early universe found the correct QCD ground state! I'd never quite put together that, if the known universe gets destroyed via tunneling to a lower-energy vacuum state, the Earth incinerated by a bubble expanding outward at the speed of light, then we ought to blame the failure of the quantum adiabatic algorithm to efficiently find global optima to NP- and QMA-hard optimization problems. :-) –  Scott Aaronson Jan 3 '13 at 1:28
@ScottAaronson There was an electroweak phase transition as well, when the universe cooled enough that the Higgs gained a nonzero vacuum expectation value. The transition is 2nd order in the standard model with the now measured Higgs mass, but some supersymmetric models can give a first order phase transition. I'm definitely not an expert on JLP, but my intuition is that these technical, thermodynamic details won't change the basic picture. Take my word with a big grain of salt though. :) –  Michael Brown Jan 3 '13 at 2:30
The main algorithm we have for find the ground state of an interacting QFT is Euclidean lattice field theory. Simulations indicate that ground state of QCD is complex, but not hard to find (in the sense that simple Metropolis algorithms converge quickly, even if initialized with very poor guesses of the ground state). –  Thomas Jan 3 '13 at 14:16

Your Answer


