Citation: Freedman, Michael H. "P/NP, and the quantum field computer." Proceedings of the National Academy of Sciences 95.1 (1998): 98-101.
Web: https://www.pnas.org/doi/10.1073/pnas.95.1.98
Tags: Foundational, Physical, TQFT, Universal-scheme
This paper gives the foundations for a quantum field theory (QFT) based computer, which Michael Freedman calls "quantum field computation". This work seems to be really "back-to-the-roots", in the sense of Feynman's original quantum computing work:
> Feynman, Richard P. "Simulating physics with computers." Int. j. Theor. phys 21.6/7 (2018).
The idea is that if there's something in physics which is hard to simulate with computers, then just letting that thing happen naturally and recording the result gives you a good computer. In Freedman's view, QFTs are just that: something in physics which is hard to simulate with computers. Moreover, good QFTs are especially nice because their outputs can be "easily" measured as expectation values, and the resulting difficulty is "easy" to quantify as an NP-complete problem. Namely, Witten proved that certain SU(2) field theories can be used to compute the values of the Jones polynomial evaluated at roots of unity:
> Witten, Edward. "Quantum field theory and the Jones polynomial." Communications in Mathematical Physics 121.3 (1989): 351-399.
These values are known to be NP-hard (in fact, #P-complete) to compute:
> Jaeger, François, Dirk L. Vertigan, and Dominic JA Welsh. "On the computational complexity of the Jones and Tutte polynomials." Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 108. No. 1. Cambridge University Press, 1990.
The paper is very short (3 pages of body), mostly spent giving some specifics about computational complexity and quantum field theory. There is also a good amount of philosophical discussion, which I find to be the most enjoyable parts of the paper. I particularly like one "toy model" Freedman proposes. He considers two closed loops in R^3 (wires). Sending an alternating electric current through the first wire, Maxwell's equations say a current will be induced in the second wire. The strength of this current is proportional to the linking number between the two wires. Measuring currents is very easy, and so in this way one can physically compute the linking number (a knot invariant!) of the wires. Of course, linking numbers are obviously easy to compute with a standard computer - this is a toy model to demonstrate the general principle of field theories inducing computation. Quoting the text, "One is tempted to assign the weakness of this computation to the fact that electromagnetism is an abelian theory".
Freedman observes that for the theory to be computationally interesting there should be particles present, contributing beyond-quadratic terms to the relevant Lagrangian. He makes the off-hand remark that the two most promising theories are Franz Wilczek's early work on anyons:
> Wilczek, Frank. Fractional statistics and anyon superconductivity. Vol. 5. World scientific, 1990.
as well as our favorite:
> Kitaev, A. Yu. "Fault-tolerant quantum computation by anyons." Annals of physics 303.1 (2003): 2-30.
Of course, time would go on to show that anyons were indeed a good candidate for realizing Freedman's ideas.
Freedman talks a bit about this time in a Simmons foundation interview. He tells a story about how Witten's discovery of the physical interpretation of the Jones polynomial was done overnight by a suggestion by Atiyah. "The big message for me from this was that quantum field theory was this enormously powerful machine which, in the hands of an expert, could elucidate mathematical problems where the expert in quantum field theory only had a cursory knowledge of the field he was revolutionizing". He then went on to say “I was immediately fascinated with the idea that you should try to build a computer that was based on whatever physics Witten was talking about, and then it would be able to solve these marvelously complicated problems”.