<p>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!).</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-08T22:02:23.357Z
2011-08-09T14:05:50.253Z
2011-08-09T14:05:50.253Z
Joe Fitzsimons
<p>To complement what Joe wrote, and maybe explain this question a bit more (without answering it!):</p>

<p>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.</p>

<p>But the situation is different for the <i>(2+1)-dimensional</i> QFTs called <i>topological</i> quantum field theories (TQFTs).  For those, there <i>is</i> 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 <a href="http://arxiv.org/abs/quant-ph/0101025" rel="noreferrer">Freedman, Kitaev, Larsen, and Wang</a>, which showed that simulating TQFTs is indeed BQP-complete, as one would hope and expect (see <a href="http://arxiv.org/abs/quant-ph/0511096" rel="noreferrer">Aharonov, Jones, and Landau</a> for a more computer-scientist-friendly version).  This remains essentially the only rigorous result we have about the computational complexity of quantum field theory.</p>

<p>Now, the questioner is asking whether some <i>new</i> 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. :-)</p>

<p><b>Addendum (Oct. 12, 2013):</b> 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 <a href="http://arxiv.org/abs/1111.3633" rel="noreferrer">important paper</a> showing how to simulate "&phi;<sup>4</sup> 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."</p>

CC BY-SA 3.0
2011-08-08T22:34:49.190Z
This is probably a much better answer than mine.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-09T00:08:46.620Z
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.
dhillonv10
CC BY-SA 3.0
2011-08-08T22:32:21.143Z
2013-10-12T21:18:10.790Z
2013-10-12T21:18:10.790Z
Scott Aaronson
<p><strong>Context:</strong> Ed. Witten recently wrote a potentially revolutionary <a href="http://arxiv.org/abs/1009.6032">paper</a> 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)</p>

<p><strong>Speculation:</strong> 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: <a href="http://en.wikipedia.org/wiki/Quantum_algorithm#Computing_knot_invariants">Wikipedia</a> and <a href="http://arxiv.org/abs/quant-ph/0511096">this paper</a>) 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.</p>

<p><strong>Question:</strong> 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!</p>

<p>PS. Also thanks to Mitchell Porter who brought up that paper before. </p>

CC BY-SA 3.0
2011-08-08T21:04:19.897Z
This seems a little out of scope to me, but I'll defer to the quantum experts.
Suresh Venkat
CC BY-SA 3.0
2011-08-08T21:07:09.160Z
perhaps i should post a version of this question to physics stack exchange, that might help.
dhillonv10
CC BY-SA 3.0
2011-08-08T21:40:13.770Z
Could you translate your language to a more pure math/cs audience?
v s
CC BY-SA 3.0
2011-08-08T22:08:39.780Z
@Suresh: I'd think it's borderline for this site, but others might have different views.
Joe Fitzsimons
<quantum-computing>
Ed. Witten's new paper and the simulation of a quantum field theory
dhillonv10
# Ed. Witten's new paper and the simulation of a quantum field theory

(Asked by: username_0 on 2011-08-08)

**Context:** Ed. Witten recently wrote a potentially revolutionary [paper](http://arxiv.org/abs/1009.6032) 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](http://en.wikipedia.org/wiki/Quantum_algorithm#Computing_knot_invariants) and [this paper](http://arxiv.org/abs/quant-ph/0511096)) 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.

**Tags:** quantum-computing
> **Comments:**
> **username_1**: This seems a little out of scope to me, but I'll defer to the quantum experts.  
> **username_0**: perhaps i should post a version of this question to physics stack exchange, that might help.  
> **username_2**: Could you translate your language to a more pure math/cs audience?  
> **username_3**: @Suresh: I'd think it's borderline for this site, but others might have different views.  

---

## 2 answers

### Answer by username_4 on 2011-08-08. Score: 19 | Accepted answer

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](http://arxiv.org/abs/quant-ph/0101025), which showed that simulating TQFTs is indeed BQP-complete, as one would hope and expect (see [Aharonov, Jones, and Landau](http://arxiv.org/abs/quant-ph/0511096) 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](http://arxiv.org/abs/1111.3633) 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."

> **Comments:**
> **username_3**: This is probably a much better answer than mine.  
> **username_0**: 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.  

---

### Answer by username_3 on 2011-08-08. Score: 7

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.


---

