P/NP, and the quantum field computer

Abstract

The central problem in computer science is the conjecture that two complexity classes,P(polynomial time) and NP(nondeterministic polynomial time—roughly those decision problems for which a proposed solution can be checked in polynomial time), are distinct in the standard Turing model of computation:P≠NP. As a generality, we propose that each physical theory supports computational models whose power is limited by the physical theory. It is well known that classical physics supports a multitude of implementation of the Turing machine. Non-Abelian topological quantum field theories exhibit the mathematical features necessary to support a model capable of solving all ⧣P problems, a computationally intractable class, in polynomial time. Specifically, Witten [Witten, E. (1989)Commun. Math. Phys.121, 351–391] has identified expectation values in a certain SU(2)-field theory with values of the Jones polynomial [Jones, V. (1985)Bull. Am. Math. Soc.12, 103–111] that are ⧣P-hard [Jaeger, F., Vertigen, D. & Welsh, D. (1990)Math. Proc. Comb. Philos. Soc.108, 35–53]. This suggests that some physical system whose effective Lagrangian contains a non-Abelian topological term might be manipulated to serve as an analog computer capable of solving NP or even ⧣P-hard problems in polynomial time. Defining such a system and addressing the accuracy issues inherent in preparation and measurement is a major unsolved problem.