7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This seems a little out of scope to me, but I'll defer to the quantum experts. $\endgroup$ – Suresh Venkat Aug 8 '11 at 21:04
  • $\begingroup$ perhaps i should post a version of this question to physics stack exchange, that might help. $\endgroup$ – dhillonv10 Aug 8 '11 at 21:07
  • 1
    $\begingroup$ Could you translate your language to a more pure math/cs audience? $\endgroup$ – v s Aug 8 '11 at 21:40
  • 1
    $\begingroup$ @Suresh: I'd think it's borderline for this site, but others might have different views. $\endgroup$ – Joe Fitzsimons Aug 8 '11 at 22:08
17
$\begingroup$

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 "φ4 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."

$\endgroup$
  • $\begingroup$ This is probably a much better answer than mine. $\endgroup$ – Joe Fitzsimons Aug 8 '11 at 22:34
  • $\begingroup$ thanks a lot for the clarification Scott. Yea if a particular TQFT and a known field theory are dual descriptions of each other, and a quantum computer can model on of them, then showing that the other can be modeled atleast theoretically seemed easy, but the problem is, as you mention, the QFT's aren't well defined, on top of that, doing that is a pretty hard problem. $\endgroup$ – dhillonv10 Aug 9 '11 at 0:08
7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I will try to answer my own question here, I found some new stuff :) John Preskill recently at Holographic Cosmology v2.0 gave a talk on some problems with this simulation and I just watched it again one more time. Joe mentioned some of the similar problems such as truncating the Hilbert space.

The way one might approach the simulation of a quantum field theory is through some indirect methods, one possible approach is as follows. This paper describes how it is possible to simulate a lattice gauge theory, a gauge theory is simply an invariant version of a field theory where the Lagrangian has some specific constrains. The paper I mentioned above gives a technique whereby one can generalize their implementation to other gauge theories under some constrains however, so generalizing their work to the gauge-gravity duality or its more specific case the AdS/CFT correspondence might be the way to go. In lattice gauge theory, the spacetime is Wick rotated into Euclidean space and discretized into a lattice, so once the work is done in the Euclidean space, oen can wick rotate back to AdS. Unfortunately, I don't nearly have the necessary required math or complexity theory knowledge to go deeper into it.

$\endgroup$
  • $\begingroup$ I also found this one paper that describes some on-going work on simulating the standard Yang-Mills theory (a QFT) here: arxiv.org/abs/1108.1503 $\endgroup$ – dhillonv10 Aug 9 '11 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.