Integrability, neural and quantum computational complexity

We study the relationship between the notion of computability and complexity in computer science,and the notion of integrability in mathematical physics as a basis for understanding the newly evolving discipline of quantum computing. Quantum computing consists in finding a suitable mapping function between an instance of a mathematical problem and the corresponding interference problem, using suitable potential functions. Feynman's path integral (FPI) formulation of quantum mechanics serves as a basis for studying the computational complexity of neural and quantum computing. Hence if FPI can be computed exactly, we can solve computational problems using quantum dynamical analogues. Unfortunately, FPI is exactly integrable (analytically or in closed form) only for a few problems (e.g., the harmonic oscillator) involving quadratic potentials; otherwise, FPI is only approximately computable or noncomputable. In spin glass (Ising models) computation and neural computng the partition function (PF) plays an important role. Since there is a one to one correspondence between the FPI and PF under the substitution of temperature to Euclidean time interval, it turns out that the the expressive power and complexity aspects quantum and neural computing techniques are mirrored by the exact and efficient integrability of FPI (PF). Our analysis will be useful in designing interiorpoint-like methods based on quantum dynamics.