Ed. Witten's new paper and the simulation of a quantum field theory

Question

Context: Ed. Witten recently wrote a potentially revolutionary paper where he showed that under certain conditions, a Chern-Simons path integral in three dimensions is equivalent to an N = 4 path integral in four dimensions (this is the standard d=4, N=4 super Yang Mills theory)

Speculation: Witten had shown that the Chern-Simons topological quantum field theory can be solved in terms of Jones polynomials. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial. (source: Wikipedia and this paper) Now I haven't completed reading Witten's paper and I wouldn't understand much of it anyways. But the idea is that if a quantum computer can simulate a path integral (or a Chern-Simons TQF) and since now Witten has shown in both of them to be dual descriptions in some sense, a quantum computer, atleast theoritically might be able to simulate a QFT. Also by the extension of that, Maldacena proposed that the specific field theory that Witten is using to be dual to type-II B string theory in AdS/CFT so then it may also be possible (only theoritically) to simulate a string theory.

Question: What are the technical constrains that a quantum or classical computer faces while simulating a QFT? Also my speculations only partially complete, could experts suggest a better description? Thanks!

PS. Also thanks to Mitchell Porter who brought up that paper before.

Answer 1

To complement what Joe wrote, and maybe explain this question a bit more (without answering it!):

The computational complexity of simulating "realistic" quantum field theories has been considered an open problem for a long time. One of the main problems, as I understand it, is that (3+1)-dimensional QFTs aren't sufficiently well-defined mathematically for it to be clear what model of computation should correspond to them.

But the situation is different for the (2+1)-dimensional QFTs called topological quantum field theories (TQFTs). For those, there is a rigorous mathematical description based on the Jones polynomial, due to Witten from the 1980s. It's that description that led to the deep and celebrated result of Freedman, Kitaev, Larsen, and Wang, which showed that simulating TQFTs is indeed BQP-complete, as one would hope and expect (see Aharonov, Jones, and Landau for a more computer-scientist-friendly version). This remains essentially the only rigorous result we have about the computational complexity of quantum field theory.

Now, the questioner is asking whether some new work by Witten could give a handle on the computational complexity of (3+1)-dimensional QFTs. I don't know the answer to that, but it seems obvious that whatever it is, it would involve a significant research effort, and probably not fit within the margins of CS Theory StackExchange. :-)

Addendum (Oct. 12, 2013): I just saw this answer again, and I thought I should add a note that, shortly after I posted it, Jordan, Lee, and Preskill released an important paper showing how to simulate "φ⁴ theory" (a simple interacting quantum field theory) in quantum polynomial time, in any number of spacetime dimensions. This doesn't directly address the OP's question, but it does render obsolete my comment about Freedman-Kitaev-Larsen-Wang remaining "essentially the only rigorous result we have about the computational complexity of quantum field theory."

Answer 2

You are correct that quantum computers can efficiently approximate the Jones polynomial. Simulating quantum fields is a bit weird, since you are generally considering an infinite dimensional system, and wish to simulate it with a finite dimensional system. Under reasonable energy assumptions you can usually truncate the Hilbert space, and consider only a finite dimensional subspace of the full infinite dimensional system which none the less contains most of the amplitude. The dynamics of the system can then generally be simulated efficiently on a quantum computer (assuming the matrix elements for transitions are reasonably well behaved, as they are in nature). You could certainly make up a Lagrangian for which the dynamics would not be efficiently simulable, even on a quantum computer, but there is nothing special about this. There are unnatural Hamiltonians which are not efficiently simulable, even without resorting to field theory. So the short answer is that you should be able to efficiently simulate the dynamics of well behaved quantum field theories (stringy or otherwise!).

Now, what I have said so far is about simulating the dynamics of the system. Finding ground states is much harder, and is not something a quantum computer can do efficiently, even for relatively simple Hamiltonians for finite systems. Indeed, ground state problems, even for local Hamiltonians for finite systems have been shown to be QMA-complete (this is essentially the quantum analogue of NP). So while quantum computers help with certain kinds of simulations, they do not allow you to efficiently find ground states (and hence vacua, etc.) except in some special cases.