# reperiendi

## Renormalization and Computation 1

Posted in Category theory, Math, Programming, Quantum by Mike Stay on 2009 October 7

Yuri Manin recently put two papers on the arxiv applying the methods of renormalization to computation and the Halting problem. Grigori Mints invited me to speak on Manin’s results at the weekly Stanford logic seminar because in his second paper, he expands on some of my work.

In these next few posts, I’m going to cover the idea of Feynman diagrams (mostly taken from the lecture notes for the spring 2004 session of John Baez’s Quantum Gravity seminar); next I’ll talk about renormalization (mostly taken from Andrew Blechman’s overview and B. Delamotte’s “hint”); third, I’ll look at the Hopf algebra approach to renormalization (mostly taken from this post by Urs Schreiber on the n-Category Café); and finally I’ll explain how Manin applies this to computation by exploiting the fact that Feynman diagrams and lambda calculus are both examples of symmetric monoidal closed categories (which John Baez and I tried to make easy to understand in our Rosetta stone paper), together with some results on the density of halting times from my paper “Most programs stop quickly or never halt” with Cris Calude. I doubt all of this will make it into the talk, but writing it up will make it clearer for me.

Renormalization is a technique for dealing with the divergent integrals that arise in quantum field theory. The quantum harmonic oscillator is quantum field theory in 0+1 dimensions—it describes what quantum field theory would be like if space consisted of a single point. It doesn’t need renormalization, but I’m going to talk about it first because it introduces the notion of a Feynman diagram.

“Harmonic oscillator” is a fancy name for a rock on a spring. The force exerted by a spring is proportional to how far you stretch it:

$\displaystyle F = kx.$

The potential energy stored in a stretched spring is the integral of that:

$\displaystyle V_0 = \frac{1}{2}kx^2 + C,$

and to make things work out nicely, we’re going to choose $C = -1/2.$ The total energy $H_0$ is the sum of the potential and the kinetic energy:

$\displaystyle H_0 = V_0 + T = \frac{1}{2}kx^2 + \frac{1}{2}mv^2 - \frac{1}{2}.$

By choosing units so that $k = m = 1,$ we get

$\displaystyle H_0 = \frac{x^2}{2} + \frac{p^2}{2} - \frac{1}{2},$

where $p$ is momentum.

Next we quantize, getting a quantum harmonic oscillator, or QHO. We set $p = -i \frac{\partial}{\partial x},$ taking units where $\hbar = 1.$ Now

$\begin{array}{rl}\displaystyle [x, p]x^n & \displaystyle = xp - px \\ & = (- x i \frac{\partial}{\partial x} + i \frac{\partial}{\partial x} x)x^n \\\ & \displaystyle = -i(nx^n - (n+1)x^n) \\ & \displaystyle = ix^n.\end{array}$

If we define a new observable $z = \frac{p + ix}{\sqrt{2}},$ then

$\begin{array}{rl} \displaystyle z z^* & \displaystyle = \frac{(p + ix)}{\sqrt{2}} \frac{(p - ix)}{\sqrt{2}} \\ & = \frac{1}{2}(p^2 + i(xp - px) + x^2) \\ & = \frac{1}{2}(p^2 -1 + x^2) \\ & = H_0.\end{array}$

We can think of $z^*$ as $\frac{d}{dz}$ and write the energy eigenvectors as polynomials in $z:$

$\displaystyle H_0 z^n = z \frac{d}{dz} z^n = n z^n.$

The creation operator $z$ adds a photon to the mix; there’s only one way to do that, so $z\cdot z^n = 1 z^{n+1}.$ The annihilation operator $\frac{d}{dz}$ destroys one of the photons; in the state $z^n$, there are $n$ photons to choose from, so $\frac{d}{dz} z^n = n z^{n-1}.$

Schrödinger’s equation says $i \frac{d}{dt} \psi = H_0 \psi,$ so

$\displaystyle \psi(t) = \sum_{n=0}^{\infty} e^{-itn} a_n z^n.$

This way of representing the state of a QHO is known as the “Fock basis”.

Now suppose that we don’t have the ideal system, that the quadratic potential $V_0 = \frac{1}{2}kx^2 - \frac{1}{2}$ is only a good local approximation to the real potential $V_0 + \lambda V$. Then we can write the total as $H = H_0 + \lambda V,$ where $V$ is a function of position and momentum, or equivalently of $z$ and $\frac{d}{dz},$ and $\lambda$ is small.

Now we solve Schrödinger’s equation perturbatively. We know that

$\displaystyle \psi(t) = e^{-itH} \psi(0),$

and we assume that

$\displaystyle e^{-itH}\psi(t) \approx e^{-itH_0} \psi(t)$

so that it makes sense to solve it perturbatively. Define

$\displaystyle \psi_1(t) = e^{itH_0} e^{-itH}\psi(t)$

and

$\displaystyle V_1(t) = e^{itH_0} \lambda V e^{-itH_0}.$

After a little work, we find that

$\displaystyle \frac{d}{dt}\psi_1(t) = -i V_1(t) \psi_1(t),$

and integrating, we get

$\displaystyle \psi_1(t) = -i\int_0^t V_1(t_0) \psi_1(t_0) dt_0 + \psi(0).$

We feed this equation back into itself recursively to get

$\begin{array}{rl}\displaystyle \psi_1(t) & \displaystyle = -i \int_0^t V_1(t_0) \left[-i\int_0^{t_0} V_1(t_1) \psi_1(t_1) dt_1 + \psi(0) \right] dt_0 + \psi(0) \\ & \displaystyle = \left[\psi(0)\right] + \left[\int_0^t i^{-1} V_1(t_0)\psi(0) dt_0\right] + \left[\int_0^t\int_0^{t_0} i^{-2} V_1(t_0)V_1(t_1) \psi_1(t_1) dt_1 dt_0\right] \\ & \displaystyle = \sum_{n=0}^{\infty} \int_{t \ge t_0 \ge \ldots \ge t_{n-1} \ge 0} i^{-n} V_1(t_0)\cdots V_1(t_{n-1}) \psi(0) dt_{n-1}\cdots dt_0 \\ & \displaystyle = \sum_{n=0}^{\infty} (-\lambda i)^n \int_{t \ge t_0 \ge \ldots \ge t_{n-1} \ge 0} e^{-i(t-t_0)H_0} V e^{-i(t_0-t_1)H_0} V \cdots V e^{-i(t_{n-1}-0)H_0} \psi(0) dt_{n-1}\cdots dt_0.\end{array}$

So here we have a sum of a bunch of terms; the $n$th term involves $n$ interactions with the potential interspersed with evolving freely between the interactions, and we integrate over all possible times at which those interactions could occur.

Here’s an example Feynman diagram for this simple system, representing the fourth term in the sum above:

The lines represent evolving under the free Hamiltonian $H_0$, while the dots are interactions with the potential $V$.

As an example, let’s consider $V = (z + \frac{d}{dz})$ and choose $\lambda = \frac{1}{\sqrt{2}}$ so that $\lambda V = p.$ When $V$ acts on a state $\psi = z^n,$ we get $V \psi = z^{n+1} + nz^{n-1}.$ So at each interaction, the system either gains a photon or changes phase and loses a photon.

A particle moving in a quadratic potential in $n$-dimensional space gives the tensor product of $n$ QHOs, which is QFT in a space where there are $n$ possible harmonics. Quantum electrodynamics (QED) amounts to considering infinitely many QHOs, one for each possible energy-momentum, which forms a continuum. The diagrams for QED start to look more familiar:

The vertices are interactions with the electromagnetic field. The straight lines are electrons and the wiggly ones are photons; between interactions, they propagate under the free Hamiltonian.