text:
# Geometric Phases and Topological Quantum Computation 22footnote 2Based on the set of lectures delivered in October 2002 at the International Centre for Theoretical Physics in Trieste.

## 1
Introduction

This review is on the nature of geometric phases in quantum mechanics and their use in quantum computation. I will introduce the notion of a geometric phase in a general way which is neither traditional nor historical. This will, I believe, help us appreciate the importance of this notion and also its generality - it is a phenomenon that has been discovered and exploited to explain a number of effects in many different areas of physics (see the collection of papers in ). One of the potential applications of this phase which is of interest to us is in quantum computation (the standard text is ). By using geometric phases to implement any elementary quantum gate we can therefore perform any quantum computation. The main reason why we would want to use geometrical phases for quantum computation is that frequently geometrical evolutions are easier to control and may also be more resistant to random noise coming from the environment. We will see, in Section $`4`$, how any quantum computation can be implemented by using purely geometric (topological) phases. This review is nether complete nor detailed \- I have tried to emphasize points and connections that are usually neglected in literature, and to arrive at a potentially very important modern application in quantum computing. I have left a number of exercises and problems for the readers to address on their own. My intention is for the reader to acquire the basic flavor of the field which will then provide a good basis for a more independent study and work.

The review is organized as follows: In section $`2`$, I will review the notion of the geometric phase for the gauge invariant perspective. This section will also present a method of measuring geometric phases and discuss the classical analogue of the geometric phase. Various links with differential geometry will be emphasized. In section $`3`$, I review some basic notions in quantum computation and present some simple algorithms. This is a necessary background to be able to show why geometrical phases can be used to implement any quantum computation. Section $`4`$ then presents the most general way of implementing geometric quantum evolution, via the so called non-Abelian geometric phases. An example is given of a system that can support such an implementation. Section $`5`$, finally, summarizes the review and offers an outlook on the field.

## 2 Geometric Phases

Quantum states are represented as vectors in a complex vector space (with a few other properties we need not worry about here). However, these vectors are only defined up to a unit modulus complex number, or a phase in other words. So, the two states $`|\xi `$ and $`e^{i\mu }|\xi `$ are indistinguishable as far as quantum mechanics is concerned - no set of measurements can discriminate them. It is interesting that although this statement looks fairly innocent at first sight, it can lead to some very profound conclusions. The route we will take here and that turns out to be very fruitful is to think of this extra phase in a geometric way as well - where we represent the phase as a unit length vector in the complex plane diagram.

Although we think of the amplitudes between two quantum states as fundamental entities in quantum theory, it is only the corresponding probabilities that we can ever observe experimentally. Therefore, given two states $`|\psi _i`$ and $`|\psi _f`$, we can only measure the mod square of their overlap, $`|\psi _i|\psi _f|^2`$. What happens then if we wish to know the relative phase between these two states? Can we define their relative phase in spite of the fact that the absolute phase has no observable consequences? One idea to do so may be to look at the amplitude between the two states in the polar decomposition:

$$\psi _i|\psi _f=re^{i\theta _{if}}$$
(1)
and define the phase $`\theta _{if}`$ as the relative phase between the two states. The main problem with this definition is that the states $`e^{i\alpha }|\psi _i`$ and $`e^{i\beta }|\psi _f`$ which differ from the original states by an overall arbitrary phase will have a different relative phases by the amount of $`\mathrm{\Delta }\theta =\alpha \beta `$. This is not very satisfactory as there are infinitely many choices for $`\mathrm{\Delta }\theta `$ and they all look equally appropriate. We formally say that this definition of phase is gauge dependent (meaning “phase dependent”) - a feature that is considered negative as all observable quantities should be independent of the choice of the gauge. How about defining a path connecting the two states, $`|\psi (s)`$, such that when $`s=0`$ we have $`|\psi _i`$ and when $`s=1`$ we have $`|\psi _f`$ (see Fig 1)? Then we can transport the states $`|\psi (s)`$ from the position $`i`$ to the position $`f`$ and see how different the final phase is to that of $`|\psi _f`$ through interference. And if the states $`|\psi _f`$ and $`|\psi _i`$ transported to $`|\psi _f`$ interfere constructively, then they are in phase and if they interfere destructively, they are out of phase; the degree of interference can therefore define the phase difference (I will be as vague as possible about what kind of interference this is - I will be much more precise later on in subsection $`2,5`$). But which path do we choose and how do we know that the transport itself doesn’t introduce any additional “twists and turns” in the phases so that we are actually comparing some different phases to the original ones? This, in fact, is a well known problem in (differential) geometry (see  for an excellent introduction). Let’s state the problem in an abstract setting first (those of you familiar with general relativity will know immediately what I am taking about) and then specialize to quantum geometric phases.

### 2.1 Parallel Transport

Suppose we have a curved manifold (as in Fig. 2) and we have a vector at a point $`A`$ and another at a point $`B`$. What is the angle between the two vectors (since phases in quantum mechanics can be thought of as vectors, this question is the same as our original question of relative phase between two quantum states). So, how do we measure the angle when the two vectors are at different positions? Well, we can transport one of them to the other one and then, when they are next to each other, the angle is easily measured (in the usual way as the “angular distance” between the vectors). But, again, we don’t want the transport itself to introduce any additional angles - we’d like it to be as “straight” as possible. The straightest possible path is known as a geodesic and the corresponding evolution along this path is known as the parallel transport (the usefulness of this concept in physics cannot be overemphasized - see ). To define a parallel transport, let’s look at the infinitesimal evolution, from $`|\psi (s)`$ to $`|\psi (s+ds)`$. If we don’t want there to be any twists and turns in the phase, even infinitesimally, then the two states should be in phase. So, we require that

$$\text{Arg}\{\psi (s)|\psi (s+ds)\}=0$$
(2)
This is the same as asking that $`\psi (s)|\psi (s+ds)`$ is purely real, i.e.

$$\text{Im}\{\psi (s)|\psi (s+ds)\}=\text{Im}\{\psi (s)|d|\psi (s)\}=0$$
(3)
up to second order. But $`\psi (s)|d|\psi (s)`$ is purely imaginary anyway (prove it by differentiating $`\psi (s)|\psi (s)=1`$ by $`ds`$), and hence the parallel transport condition becomes:

$$\psi (s)|d|\psi (s)=0$$
(4)
If the evolution satisfies this equation, then the phase is said to be parallely transported, which is what we mentioned was required in order to be able to define a relative phase between two states (also see  for an accessible treatment of the phase parallel transport) . This definition of parallel transport is, however, not automatically gauge invariant. By this we mean that if instead of the state $`|\psi (s)`$, we use the state $`|\stackrel{~}{\psi }(s)=e^{i\alpha (s)}|\psi (s)`$, then the parallel transport condition changes by the amount

$$\stackrel{~}{\psi }(s)|d|\stackrel{~}{\psi }(s)=\psi (s)|d|\psi (s)+i\frac{d\alpha }{ds}ds$$
(5)
as can easily be checked. In order to obtain something that is gauge invariant we can integrate the expression $`\psi |d|\psi `$ over a closed loop, giving us the expression for the geometric phase, and then exponentiate the result (the integral of $`\frac{d\alpha }{ds}`$ over a closed loop is $`2\pi `$, whose exponential is equal to unity). So, the geometric phase resulting from the parallel transport is

$$\gamma =_i^f\psi (s)|\frac{d}{ds}|\psi (s)𝑑s$$
(6)
and its exponential (over a closed loop) is gauge independent, but not path independent 333Path dependence cannot easily be eliminated, although this is the key idea behind constructing “topological” as opposed to “geometric” phases. Incidentally, note that we are requiring that the phase difference between every two infinitesimal points is zero. So, how come, if every infinitesimal difference is zero, that on a finite stretch a non-zero phase builds up? The answer is that the underlying space is curved and it is the curvature that is reflected in the phase difference; in fact, the curvature is equal the phase difference (up to a constant factor). When a quantity vanishes infinitesimally, but its integral over a finite region doesn’t, then this quantity is called non-integrable. Therefore, it can be succinctly said that geometric phases are a manifestation of non-integrable phase factors in quantum mechanics. Let’s look at a spin half system to illustrate this point.

### 2.2 The Bloch Sphere

Two level systems are ubiquitous in nature and can be used to store and manipulate any form of information (in quantum computing they are known as quantum bits or qubits). Two level systems are very conveniently represented on a sphere, such that all pure states lie on the surface of this sphere and all the mixed states are inside. There is a one-to-one correspondence between the points on and inside the sphere and quantum states of a two level system (Fig 3). This is because we need at most three parameters to specify every two level state, as can be seen from the general density matrix for the systems:

$$\rho =\frac{1}{4}(I+\underset{i}{}s_i\sigma _i)$$
(7)
where $`\sigma _i`$ are the Pauli spin matrices and $`s_i=\text{tr}\sigma _i\rho `$ are the $`x,y,z`$ coordinates on the sphere. If a state is pure than $`s_x^2+s_y^2+s_z^2=1`$ which, as we said, is a point on the surface of the sphere (a pure state in other words).

Suppose that we now evolve from the state $`|0`$ to the state $`|+=|0+|1`$, then to $`|x=|0+i|1`$ and finally back to the state $`|0`$. On the Bloch sphere we are going from the North Pole to the Equator, then we move on the Equator by an angle of $`\pi /2`$ and finally we move back to the North Pole). What is the corresponding geometric phase? To see this we start with a tangential vector initially at the North Pole pointing in some direction (there are infinitely many directions corresponding to infinitely many arbitrary phases to start with). If we now parallely transport this vector along the described path, then we end up with a vector pointing in a different direction to the original one (even though, infinitesimally, the phase vector has always stayed parallel to itself!). The angle between the initial and the final vector is $`\pi /2`$, which is exactly equal to the area covered by the state vector during the transport, or the corresponding solid angle of the transport (the two are just different ways of phrasing the same thing and can be seen to be equivalent using Stokes’ theorem). Therefore, the two orthogonal states $`|0`$ and $`|1`$ evolve in the following way:

$`|0`$ $``$ $`e^{i\mathrm{\Omega }/2}|0`$ (8)
$`|1`$ $``$ $`e^{i\mathrm{\Omega }/2}|1`$ (9)
where $`\mathrm{\Omega }`$ is the solid angle (the factor of half is there because the orthogonal states are $`\pi `$ away from each other in the Bloch representation). This is important as it shows that orthogonal states pick up opposite phases of equal magnitude. The phase can be computed from the formula in eq. (6), but we note that it can also be written in a “discrete” way as

$$\mathrm{arg}\{0|++|xx|0\}$$
(10)
This beautiful formula - originally due to Pancharatnam  \- will be the basis of our general formulation of the geometric phase for pure states. From it we will be able to find that the space of quantum two level systems is curved. Are there, for that matter, any quantum states whose space is not curved (i.e. is flat) and how do we determine the curvature in general? If you want to measure a curvature at a point, then make a small loop around that point and compare the initial phase of your state to the phase after completing this loop. Suppose that the evolution is $`|\psi (s_i)|\psi (s_i+\delta s)|\psi (s_i+\delta s+\mathrm{\Delta }s)|\psi (s_i)`$. Then, the final phase difference is (according to Pancharatnam)

$`\delta \theta `$ $`=`$ $`\mathrm{arg}\{\psi (s_i)|\psi (s_i+\delta s)\psi (s_i+\delta s)|\psi (s_i+\delta s+\delta s^{})\psi (s_i+\delta s+\delta s^{})|\psi (s_i)\}`$ (11)
$`=`$ $`\mathrm{arg}\{1+i({\displaystyle \frac{\delta }{\delta s}}\psi (s_i)|{\displaystyle \frac{\delta }{\delta s^{}}}|\psi (s_i){\displaystyle \frac{\delta }{\delta s^{}}}\psi (s_i)|{\displaystyle \frac{\delta }{\delta s}}|\psi (s_i))\}`$
$`=`$ $`{\displaystyle \frac{\delta }{\delta s}}\psi (s_i)|{\displaystyle \frac{\delta }{\delta s^{}}}|\psi (s_i){\displaystyle \frac{\delta }{\delta s^{}}}\psi (s_i)|{\displaystyle \frac{\delta }{\delta s}}|\psi (s_i)`$ (12)
The definition of curvature, $`K`$, is $`\delta \theta =K\delta A`$, where $`A`$ is the area enclosed (this definition of curvature is due to Gauss). You can convince yourselves that for spin half particles $`\delta \theta =\delta A`$, which means that the curvature is $`1`$ (it is really $`1/r^2`$ as for any sphere, but the Bloch sphere has a unit radius). For optical coherent states, on the other hand, $`\delta \theta =0`$ (if we vary the phase and the amplitude of the state only), indicating that they line on a flat surface (which you can prove as an exercise, but see  for more details on the Riemannian structure of quantum states).

This formalism is very powerful and important in the modern formulation of physical theories (the so called gauge theories - see  for more details). But before we admire the beauty and cleverness of all this any further, let’s ask ourselves a very basic question: how do we actually (physically) implement the parallel transport given above?

### 2.3 Adiabatic implementation of parallel transport

Here we present one such implementation due to Berry , who actually discovered the quantum geometric phase in $`1984`$ in this way. A wavefunction of a system is a function of a set of parameters (which generally depend on time) and the time itself, $`|\mathrm{\Psi }(s(t),t)`$. Suppose that the Hamiltonian is a function of $`s`$ only $`H=H(s(t))`$. Suppose, in addition, that these parameters change very slowly so that the system, which starts in a eigenstate of the initial Hamiltonian, stays an eigenstate of the instantaneous Hamiltonian, i.e.

$$H(s(t))|\mathrm{\Psi }_n(s(t),t)=E_n(s(t))|\mathrm{\Psi }_n(s(t),t)$$

(this is what is known as the adiabatic approximation in quantum physics- the other extreme is the sudden approximation where the Hamiltonian changes instantaneously). The Schrödinger equation for this system is

$$i\frac{d}{dt}|\mathrm{\Psi }_n(s(t),t)=H(s(t))|\mathrm{\Psi }_n(s(t),t)$$

(where we assume throughout that $`\mathrm{}=1`$). We would like to show that the adiabatic evolution naturally implements the parallel transport of the phase of the quantum state. Note that apart from the adiabaticity assumption our analysis is completely general. Multiplying the Schrödinger equation by $`\mathrm{\Psi }_n|`$, and taking the eigenvalue equation into account we obtain:

$$i\mathrm{\Psi }_n|\frac{d}{dt}|\mathrm{\Psi }_n=E_n$$

Now, every state gains a dynamical phase (as well as a geometric one) as it evolves. We’d like to get rid of the dynamical component of the phase and not take it into account when we are measuring the geometric contribution. To do so we define a new wavefunction by taking into account the dynamical phase

$$|\mathrm{\Phi }_n(s(t),t):=\mathrm{exp}\{iE_n(s(t))\}|\mathrm{\Psi }_n(s(t),t)$$

which satisfies the following equation:

$$\mathrm{\Phi }(s(t),t)|\frac{d}{dt}|\mathrm{\Phi }(s(t),t)=0$$

And this is the same as the parallel transport condition. So, the geometric part of the quantum phase is parallely transported when the state evolves under the Schrödinger equation in the adiabatic approximation. So can we derive a closed formula for the geometric phase? The answer is yes, and the solution to this equation is given by:

$$|\mathrm{\Phi }(s(t),t)=e^{i\gamma (t)}|\mathrm{\Phi }(s(t))$$

where

$$\frac{d}{dt}\gamma (t)=i\mathrm{\Phi }(s(t))|\frac{d}{ds}|\mathrm{\Phi }(s(t))\frac{ds}{dt}$$

We notice that the right hand side involves the 1-form $`\beta `$ describing the (symplectic) manifold of the projective Hilbert space 444Differential forms are just things that exist under the integral sign, however, in mathematics they can be given a life of their own. We will not need this formalization in the rest of this review, but they feature very strongly in modern theoretical physics, which is why I mention them here. \- see Simon’s original differential geometric interpretation . Therefore,

$$\frac{d}{ds}\gamma =\beta $$

where $`\beta =i\mathrm{\Phi }(s(t))|\frac{d}{ds}|\mathrm{\Phi }(s(t))`$. Integrating over a closed circuit $`S`$ we solve for the Berry phase

$$\gamma =_S\beta $$

Invoking Stokes’ theorem this becomes

$$\alpha =_S\sigma $$

where $`S`$ is the area enclosed by the circuit $`S`$ and $`\sigma `$ is the 2-form on the symplectic manifold of the projective Hilbert space. This phase is called the Berry phase (the Berry and geometric phase are terms that I will use interchangeably, although this is by no means the standard convention in the literature).

In summary, the quantum phase arising in a general evolution of a quantum system consists of two parts: the dynamical part given by the formula

$$\delta =E(t)𝑑t$$

and the geometric part, given by

$$\gamma =\mathrm{\Psi }(s)|\frac{d}{ds}|\mathrm{\Psi }(s)\frac{ds}{dt}𝑑t$$

The total phase is then the sum of the two contributions, $`\varphi =\delta +\gamma `$.

We can encapsulate this whole subsection by saying that

The Schrödinger equation in the adiabatic limit implements the parallel transport of the phase of the evolving state.

In order to become more acquainted with the notion of geometric phases, we look at the classical analogue of this phenomenon.

### 2.4 Classical geometric phase

In this subsection we will talk about astronauts, cats and the Foucault pendulum in this section, all of which are classical objects. What do all these have in common? They all have the geometric phase at the root of their basic behaviour! Suppose an astronaut is in free space and initially facing away from his space ship. He wants to turn around by $`180`$ degrees to return to the ship, but there is nothing around him to push against or hold onto in order to turn around. His task may at first sight look impossible to achieve: his angular momentum is initially zero and in order to turn he seems to need to generate some angular momentum. But there are no forces externally, so this looks indeed impossible! However, anyone who has been observing cats knows that this reasoning is false. Cats face the same problem everyday and they manage to solve it. If a cat falls from a certain height and was initially upside down, she is still going to (almost always) land on her feet (hence the allegorical expression: “cats always land on their feet”). So, how do cats manage to apparently “violate the conservation of angular momentum”? Well, they don’t violate angular momentum conservation: they don’t use dynamics to turn, they use topology! Fig. 4 shows how the astronaut does something similar to the cat to turn around. Note that his hand movement is the same as the spin half evolution on the Bloch sphere - hence the angle by which he turns can be calculated in the same way.

Interestingly enough, the Foucault pendulum can be explained in the same geometric way . Imagine that a pendulum is suspended at some latitude $`\theta `$, and that we observe its swinging motion as the Earth spins around its own axis. It is well known that the pendulum will after one rotation of the Earth swing in a plane at an angle to the original plane of motion. To see this, let us obtain an equation of motion of the pendulum. The Lagrangian for this problem is given by

$$L=\frac{1}{2}m(\frac{dx}{dt}^2+\frac{dy}{dt}^2)\frac{1}{2}m\omega ^2(x^2+y^2)m\mathrm{\Omega }\mathrm{cos}\theta (x\frac{dy}{dt}y\frac{dx}{dt})$$
(13)
where $`\mathrm{\Omega }`$ is the Earth’s frequency of rotation ($`2\pi `$ per day), $`m`$ is the mass of the pendulum and $`\omega `$ its natural frequency of swinging. The corresponding Euler-Lagrange equations of motion are easy to obtain (exercise!) and their solution written in the coordinate $`z=x+iy`$ is (in the adiabatic limit):

$$z(t)x_0e^{i\mathrm{\Omega }\mathrm{cos}\theta t}e^{i\omega t}$$
(14)
This form of the solution is convenient as it allows us to see two phases in the motion of the pendulum: the dynamical phase $`\omega t`$ which is the same as the quantum dynamical phase seen before and the geometric phase $`\mathrm{\Omega }\mathrm{cos}\theta t`$. Note that after one day revolution of the earth, the geometric phase is $`2\pi (1\mathrm{cos}\theta )`$ which is the same as the spin half geometrical phase. This is because our planet is a very good, albeit somewhat imperfect, physical representation of the Bloch sphere!

### 2.5 Experimental realization: The Pancharatnam connection

I now summarize the theory so far: we would like to compare phases of a quantum state at two different points. To do so we have to chose a path connecting the two points, and evolve one of the points along the path until it coincides with the other one. Then we interfere them to infer the phase. But how does this interference work?

Consider a conventional Mach-Zehnder interferometer in which the beam-pair spans a two dimensional Hilbert space $`\stackrel{~}{}=\{|\stackrel{~}{0},|\stackrel{~}{1}\}`$ . The state vectors $`|\stackrel{~}{0}`$ and $`|\stackrel{~}{1}`$ can be taken as (orthogonal) wave packets that move in two given directions defined by the geometry of the interferometer. In this basis, we may represent mirrors, beam-splitters and relative $`U(1)`$ phase shifts by the unitary operators

$`\stackrel{~}{U}_M`$ $`=`$ $`\left(\begin{array}{cc}\hfill 0& \hfill 1\\ \hfill 1& \hfill 0\end{array}\right),\stackrel{~}{U}_B={\displaystyle \frac{1}{\sqrt{2}}}\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right),`$ (19)
$`\stackrel{~}{U}(1)`$ $`=`$ $`\left(\begin{array}{cc}e^{i\chi }& \hfill 0\\ 0& \hfill 1\end{array}\right),`$ (22)
respectively. An input pure state $`\stackrel{~}{\rho }_{in}=|\stackrel{~}{0}\stackrel{~}{0}|`$ of the interferometer transforms into the output state

$`\stackrel{~}{\rho }_{out}`$ $`=`$ $`\stackrel{~}{U}_B\stackrel{~}{U}_M\stackrel{~}{U}(1)\stackrel{~}{U}_B\stackrel{~}{\rho }_{in}\stackrel{~}{U}_B^{}\stackrel{~}{U}^{}(1)\stackrel{~}{U}_M^{}\stackrel{~}{U}_B^{}`$ (25)
$`=`$ $`{\displaystyle \frac{1}{2}}\left(\begin{array}{cc}1+\mathrm{cos}\chi & i\mathrm{sin}\chi \\ i\mathrm{sin}\chi & 1\mathrm{cos}\chi \end{array}\right)`$
that yields the intensity along $`|\stackrel{~}{0}`$ as $`I1+\mathrm{cos}\chi `$. Thus the relative $`U(1)`$ phase $`\chi `$ could be observed in the output signal of the interferometer.

Now assume that the particles carry additional internal degrees of freedom, e.g., spin (it is this degree of freedom that will be parallely transported). This internal spin space $`_i𝒞^N`$ is spanned by the vectors $`|k`$, $`k=1,2,\mathrm{}N`$. The density operator could be made to change inside the interferometer

$$\rho _0U_i\rho _0U_i^{}$$
(26)
with $`U_i`$ a unitary transformation acting only on the internal degrees of freedom (we will see later on that this transformation need not be unitary, but could be a more general completely positive map). Mirrors and beam-splitters are assumed to leave the internal state unchanged so that we may replace $`\stackrel{~}{U}_M`$ and $`\stackrel{~}{U}_B`$ by $`𝐔_M=\stackrel{~}{U}_M1_i`$ and $`𝐔_B=\stackrel{~}{U}_B1_i`$, respectively, $`1_i`$ being the internal unit operator. Furthermore, we introduce the unitary transformation

$$𝐔=\left(\begin{array}{cc}\hfill 0& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right)U_i+\left(\begin{array}{cc}e^{i\chi }& \hfill 0\\ 0& \hfill 0\end{array}\right)1_i.$$
(27)
The operators $`𝐔_M`$, $`𝐔_B`$, and $`𝐔`$ act on the full Hilbert space $`\stackrel{~}{}_i`$. $`𝐔`$ corresponds to the application of $`U_i`$ along the $`|\stackrel{~}{1}`$ path and the $`U(1)`$ phase $`\chi `$ similarly along $`|\stackrel{~}{0}`$. We shall use $`𝐔`$ to generalize the notion of phase to unitarily evolving mixed states.

Let an incoming state given by the density matrix $`\varrho _{in}=\stackrel{~}{\rho }_{in}\rho _0=|\stackrel{~}{0}\stackrel{~}{0}|\rho _0`$ be split coherently by a beam-splitter and re-combine at a second beam-splitter after being reflected by two mirrors. Suppose that $`𝐔`$ is applied between the first beam-splitter and the mirror pair. The incoming state transforms into the output state

$$\varrho _{out}=𝐔_B𝐔_M\mathrm{𝐔𝐔}_B\varrho _{in}𝐔_B^{}𝐔^{}𝐔_M^{}𝐔_B^{}.$$
(28)
Inserting Eqs. (22) and (27) into Eq. (28) yields

$`\varrho _{out}`$ $`=`$ $`{\displaystyle \frac{1}{4}}[\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right)U_i\rho _0U_i^{}+\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right)\rho _0`$ (39)
$`+e^{i\chi }\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right)\rho _0U_i^{}`$
$`+e^{i\chi }\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right)U_i\rho _0].`$
The output intensity along $`|\stackrel{~}{0}`$ is

$`I`$ $``$ $`Tr\left(U_i\rho _0U_i^{}+\rho _0+e^{i\chi }U_i\rho _0+e^{i\chi }\rho _0U_i^{}\right)`$ (40)
$``$ $`1+|Tr\left(U_i\rho _0\right)|\mathrm{cos}\left[\chi \mathrm{arg}Tr\left(U_i\rho _0\right)\right],`$
where we have used $`Tr(\rho _0U_i^{})=\left[Tr\left(U_i\rho _0\right)\right]^{}`$.

The important observation from Eq. (40) is that the interference oscillations produced by the variable $`U(1)`$ phase $`\chi `$ is shifted by $`\varphi =\mathrm{arg}Tr\left(U_i\rho _0\right)`$ for any internal input state $`\rho _0`$, be it mixed or pure. This phase difference reduces for pure states $`\rho _0=|\psi _0\psi _0|`$ to the Pancharatnam phase difference between $`U_i|\psi _0`$ and $`|\psi _0`$. Moreover the visibility of the interference pattern is $`\nu =|Tr\left(U_i\rho _0\right)|0`$, which reduces to the expected $`\nu =|\psi _0|U_i|\psi _0|`$ for pure states.

It is clear from this experiment what it means to have a parallel transport of phase, i.e. no phase introduced during an infinitesimal evolution. We require that

$$\mathrm{arg}Tr\left(U(t,t+dt)\rho _0\right)=0$$
(41)
which is the same as the parallel transport condition presented before in eq. (4). Suppose for that matter that we have no dynamics and only projective transformations (the transformation $`U`$ is in this case no longer unitary, but the same above analysis still holds). Then $`U=|\psi _n\psi _{n1}|\mathrm{}|\psi _2\psi _1|`$ so that the formula for the phase now becomes

$$\gamma =arg\{\psi _1|\psi _2\psi _2|\psi _3\mathrm{}\psi _n|\psi _1\}$$
(42)
which is known as the Pancharatnam phase. Now, this is the most general form of the phase for pure state, which leaves the motion between the states completely arbitrary: it could be adiabatic, and cyclic, but it could also be non-unitary and open. There are many advantages of expressing the phase in this way:

* it is aesthetically pleasing!
* it is manifestly gauge invariant since whenever we have the ket $`|\psi _j`$ in the expansion, we also have its bra present, $`\psi _j|`$, meaning that all the extra phases of individual states cancel. Thus, states only appear as projectors which is the key to achieving independence of phase. As a slight digression, those of you who know a bit about the lattice gauge theory (see  for an excellent succinct introduction) will immediately notice the similarity with Wilson’s loop construction. In order to obtain the action leading to the geometric phase we have to sum up the infinitesimal loops, $`W_P`$, over all points $`P`$. Each loop is defined as

$$W_P=\psi (x_P)|\psi (x_P+dx)\mathrm{}\psi (x_P+dx+\delta x)|\psi (x_P)$$
(43)
After a simple manipulation and using the Baker-Hausdorff formula

$$\mathrm{exp}(\lambda A)\mathrm{exp}(\lambda B)=\mathrm{exp}(\lambda (A+B)+\lambda ^2/2[A,B]+O(\lambda ^3),$$

it can be shown that

$$W_P=e^{iF_{\mu \nu }dx_\mu \delta x_\nu }$$
(44)
where the fictitious geometric field strength is

$$F_{\mu \nu }=_\mu A_\nu _\nu A_\mu i[A_{mu},A_{nu}]$$
(45)
and the geometric potential (also called connection in the lectures) is

$$A_\nu =\psi (x)|_\nu |\psi (x)$$
(46)
To obtain the Wilson loop over a finite range we just need to add up all the infinitesimal loops such that $`W=_PW_P`$. Pushing the analogy with gauge theories we can think of a fictitious topological charge $`Q^T`$ defined via Gauss’ law:

$$\frac{1}{A}B_{\mu \nu }𝑑A=Q^T$$
(47)
Also, a covariant derivative of a field $`\mathrm{\Phi }`$ is given by

$$\mathrm{\Phi }_{;\alpha }=_\alpha \mathrm{\Phi }+iA_\alpha \mathrm{\Phi }$$
(48)
and the field satisfies the following well known identity

$$F_{\mu \nu ;\rho }+F_{\nu \rho ;\mu }+F_{\nu \rho ;\mu }=0$$
(49)
* the formulation is very general. Any most general quantum evolution (the so called Completely positive, trace preserving map) going through the states above will lead to the same phase. There are many issues in this generalization that are still unclear, but I will not make any comments on this as it would obscure the exposition (see Sjöqvist et al.  for details).
* offers us a way of generalizing the phase to mixed states (as averaging over the corresponding pure states).

So, the geometric phase is independent of dynamics and gauge-free, however, it does depend on the underlying geometry of the evolution. To what extent can we eliminate the sensitivity to geometry?

### 2.6 Topology: The Aharonov-Bohm effect

The Aharonov-Bohm effect  can be revisited and explained in terms of the geometrical phase notion. Whereas the curvature in the above examples was in some sense fictitious (i.e. not generated by a “real” field, but by the intrinsic curvature in the geometry of quantum states), the Aharanov-Bohm effect is a manifestation of the electro-magnetic field. From this perspective we can even say that

electro-magnetism is the gauge invariant manifestation of a non-integrable quantum phase factor.

In other words, this means that the electromegnetic field (more precisely the potential) can be derived by postulating that the Schrödinger equation is invariant under local phase change of the wavefunction.

The Aharonov-Bohm set-up is the best example that explores the effect of the electro-magnetic field on phase through a beam of electrons in a double connected region where the field strength is zero as in Fig. 6. The phase gained by the beam is

$$\mathrm{exp}\{\frac{ie\mathrm{\Phi }}{\mathrm{}c}\}$$
(50)
where $`\mathrm{\Phi }`$ is the flux of the field. This phase has been experimentally observed. We see that the phase is path dependent (which is another way of saying that it is non-integrable). Even though it is path dependent, if we make one round trip about the flux, then we always gain the same amount of phase no matter what the path is. This a nice topological feature of the Aharonov-Bohm phase; the phase is then dependent on the number of times the flux has been encircled (the so called winding number in topology). It is this topological feature that we would like to have when we implement quantum computation (this idea was first presented in a seminal paper by Kitaev ). However, we would like the topology to be of a non-abelian (i.e. non-commutative) character as we explain later on in the review.

## 3 Quantum Computation

So far we have explored connections between physics and geometry through the concept of the geometric phase which we saw is manifested both in quantum and classical mechanics. Now we plunge into another equally exciting and cross-disciplinary area: quantum information processing (see  for details).

All information is ultimately encoded in the most elementary quantum systems, so called quantum bits. A *qubit* is a quantum system in which the Boolean states $`0`$ and $`1`$ are represented by a prescribed pair of normalised and mutually orthogonal quantum states labeled as $`\{|0,|1\}`$. Unlike a simple Boolean variable, a qubit, typically a microscopic system such as an atom, a nuclear spin, or a polarised photon, can exist in an arbitrary superposition $`\alpha |0+\beta |1`$, making it more powerful as a computational resource.

In quantum computation, we set some *register* of qubits to an “input” state, evolve the qubits unitarily using simple building-block operations and then take the final state as “output”. More formally, a *quantum logic gate* is a device which performs a fixed unitary operation on selected qubits in a fixed period of time and a *quantum network* is a device consisting of quantum logic gates whose computational steps are synchronised in time. The outputs of some of the gates are connected by wires to the inputs of others. Also we define the *size* of the network to be the number of gates it contains.

### 3.1 Quantum logic gates and universality

The most common quantum gate is the Hadamard gate, a single qubit gate $`H`$ performing the unitary transformation known as the Hadamard transform. It is defined as

$$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)\text{ }\text{ }\text{}\text{ }$$
(51)
The matrix is written in the computational basis $`\{|0,|1\}`$ and the diagram on the right provides a schematic representation of the gate $`H`$ acting on a qubit in state $`|x`$, with $`x=0,1`$.

The addition of another single qubit gate, the phase shift gate $`\varphi `$, defined as $`|\mathrm{\hspace{0.17em}0}|\mathrm{\hspace{0.17em}0}`$ and $`|\mathrm{\hspace{0.17em}1}e^{i\varphi }|\mathrm{\hspace{0.17em}1}`$, or, in matrix notation,

$$\varphi =\left(\begin{array}{cc}1& 0\\ 0& e^{i\varphi }\end{array}\right)\text{ }\text{ }\text{}\text{ }$$
(52)
is actually sufficient to construct the following network (of size four), which generates the most general pure state of a single qubit (up to a global phase),

$$\text{ }\text{}\text{ }\mathrm{cos}\theta |0+e^{i\varphi }\mathrm{sin}\theta |1.$$
(53)
Consequently, the Hadamard and phase gates are sufficient to construct *any* unitary operation on a single qubit. We have used both the above gates in our discussion of the Pancharatnam phase in the Mach-Zehnder interferometer.

Thus the Hadamard gates and the phase gates can be used to transform the input state $`|0|0\mathrm{}|0`$ of $`n`$ qubits into any state of the type $`|\mathrm{\Psi }_1`$ $`|\mathrm{\Psi }_2\mathrm{}`$ $`|\mathrm{\Psi }_n,`$ where $`|\mathrm{\Psi }_i`$ is an arbitrary superposition of $`|0`$ and $`|1.`$ These are rather special $`n`$-qubit states, called the product states or the separable states. In general, a register of $`n`$ qubits can be prepared in states which are not separable, known as entangled states.

However, in order to entangle two (or more qubits) it is necessary to have access to two-qubit gates. One such gate is the controlled phase shift gate $`B(\varphi )`$ defined as

$$B(\varphi )=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& e^{i\varphi }\end{array}\right)\text{ }\text{ }\text{}\}e^{ixy\varphi }|x|y.$$
(54)
The matrix is written in the computational basis $`\{|00,|01,|10,`$ $`|11\}`$ and the diagram on the right shows the structure of the gate. Note: we know how to implement the single qubit phase gate geometrically, but not the other two gates aforementioned. Which gates are important to be able to implement in order to perform any quantum computation?

An important result in the theory of quantum computation states that the Hadamard gate, and all $`B(\varphi )`$ controlled phase gates form an universal set of gates: if the Hadamard gate as well as all $`B(\varphi )`$ gates are available then any $`n`$-qubit unitary operation can be simulated exactly with less than $`C4^nn`$ such gates, for some constant $`C`$ . Consequently, being able to implement 1- and 2- qubit phase gates is of crucial importance in quantum computation. In the remaining part of the lectures we describe a new method for implementing the controlled phase gates based explicitly on geometric phases rather than dynamic ones. Thus if we show that the universal set can be implemented geometrically, then any computation can be implemented geometrically (see  for an NMR geometric implementation of the controlled phase gate).

### 3.2 Lightning review of quantum algorithms

Deutsch’s problem  is the simplest possible example which illustrates the advantages of quantum computation . The problem is the following. Suppose that we are given a binary function of a binary variable $`f:\{0,1\}\{0,1\}`$. Thus, $`f(0)`$ can either be $`0`$ or $`1`$, and $`f(1)`$ likewise can either be $`0`$ or $`1`$, giving altogether four possibilities. However, suppose that we are not interested in the particular values of the function at $`0`$ and $`1`$, but we need to know whether the function is: 1) constant, i.e. $`f(0)=f(1)`$, or 2) varying, i.e. $`f(0)f(1)`$. Now Deutsch poses the following task: by computing $`f`$ only once determine whether it is constant or varying. This kind of problem is generally referred to as a promise algorithm, because one property out of a certain number of properties is initially promised to hold, and our task is to determine computationally which one holds.

First of all, classically finding out in one step whether a function is constant or varying is clearly impossible. We need to compute $`f(0)`$ and then compute $`f(1)`$ in order to compare them. There is no way out of this double evaluation. Quantum mechanically, however, there is a simple method to achieve this task by computing $`f`$ only once! We need to implement the following unitary transformation

$`|xe^{i\pi f(x)}|x`$
where $`x=0,1`$. Now we can see where the power of quantum computers is fully realised: each of the components in the superposition of $`|0+|1`$ undergoes the same above evolution “simultaneously”, leading to the powerful “quantum parallelism”. This feature is true for quantum computation in general. Let us look at the two possibilities now:

1. if $`f`$ is constant, then the final state is

$`|\mathrm{\Psi }_{\text{out}}=\pm (|0+|1).`$
and
2. if, on the other hand, $`f`$ is varying, then, the final state is

$`|\mathrm{\Psi }_{\text{out}}=\pm (|0|1).`$

Note that the output qubit emerges in two different orthogonal states, depending on the type of $`f`$. These two states can be distinguished with $`100`$ percent efficiency. This is easy to see if we first perform a Hadamard transformation on this qubit, leading to the state $`|0`$ if the function is constant, and to the state $`|1`$ if the function is varying. Now a single projective measurement in $`0,1`$ basis determines the type of the function. Therefore, unlike their classical counterparts, quantum computers can solve Deutsch’s problem.

It should be emphasised that this quantum computation, although extremely simple, contains all the main features of successful quantum algorithms: it can be shown that all quantum computations are just more complicated variations of Deutsch’s problem. In particular, Shor’s algorithm for factorisation of numbers is just a scaled up version of Deutsch as it is based on period finding. Note, finally, that the main operation in Deutsch’s algorithm was the introduction of a phase conditional on the state of the qubit. This phase can, of course, be introduced in a purely geometrical way, by a spin-half encircling an area of the size of $`2\pi `$.

## 4 Topological implementation of quantum gates

Speaking somewhat loosely, we would now like to construct a universal set of quantum gates, which we know is impossible if we only have the (abelian) geometric phases (because we cannot implement a Hadamard transform with them). However, in addition to achieving the universality, we’d like to be able to achieve a certain degree of resistance to errors, but without performing any error correction. How far can this idea be pushed?

### 4.1 Non-abelian formalism

The best way of explaining the non-abelian phases is to look at how they arise during quantum evolution. The term “non-abelian” refers to the fact that two different phases don’t commute. Note that the ordinary (Berry) phases we discussed so far are abelian, i.e.

$$e^{i\gamma _1}e^{i\gamma _2}=e^{i\gamma _2}e^{i\gamma _1}$$

This inequality, however, would not be satisfied if we had non-abelian phases. This therefore implies that the non-abelian phases would not be represented by ordinary numbers, but by matrices. We now show that this scenario arises during the Schrödinger evolution in the adiabatic setting when our system is degenerate. Suppose that we have

$`H(t)|\psi _1(t)`$ $`=`$ $`E(t)|\psi _1(t)`$ (55)
$`H(t)|\psi _1(t)`$ $`=`$ $`E(t)|\psi _1(t)`$ (56)
and $`\psi _1(t)|\psi _2(t)=0`$. From the Schrödinger equation we can conclude:

$`i\psi _1|{\displaystyle \frac{d}{dt}}|\psi `$ $`=`$ $`E\psi _1|\psi `$ (57)
$`i\psi _2|{\displaystyle \frac{d}{dt}}|\psi `$ $`=`$ $`E\psi _2|\psi `$ (58)
We recast this pair of equations by writing $`|\psi =a_1(t)|\psi _1+a_2(t)|\psi _2`$, and subtracting the dynamical phases by putting $`E(t)=0`$ (for all time $`t`$) we obtain

$`{\displaystyle \frac{da_1}{dt}}+a_1\psi _1|{\displaystyle \frac{d}{dt}}|\psi _1+a_2\psi _1|{\displaystyle \frac{d}{dt}}|\psi _2`$ $`=`$ $`0`$ (59)
$`{\displaystyle \frac{da_2}{dt}}+a_2\psi _2|{\displaystyle \frac{d}{dt}}|\psi _2+a_1\psi _2|{\displaystyle \frac{d}{dt}}|\psi _1`$ $`=`$ $`0`$ (60)
We can rewrite this equation as a vector-matrix equation,

$$\frac{dv}{dt}=i\left(\begin{array}{cc}i\psi _1|\frac{d}{dt}|\psi _1& i\psi _1|\frac{d}{dt}|\psi _2\\ i\psi _2|\frac{d}{dt}|\psi _1& i\psi _2|\frac{d}{dt}|\psi _2\end{array}\right)v$$

where

$$v(t)=\left(\begin{array}{c}a_1(t)\\ a_2(t)\end{array}\right)$$

The formal solution to this equation can be written in the usual “Dyson perturbative expansion”:

$$v(s)=𝒫\mathrm{exp}\{i_i^fA^j(s)T_j𝑑s\}v(0)$$

where $`𝒫`$ indicated the path-ordering operation of non-commuting factors $`A^j(s)T_j`$. This non-abelian phases is in general very difficult to evaluate, because of the path ordering operation. Note that if the state starts in the degenerate subspace it always remains there according to the adiabatic theorem 555We mention that the $`SU(2)`$ Yang - Mills formalism is based on the non-abelian gauge invariance and can reproduce the weak interaction and the $`SU(3)`$ formalism due to Gell-Mann can be used to represent the strong interaction. These are just generalizations of the $`U(1)`$ formalism for Elactro-magnetism based of Weyl’s ideas. The interested reader is advised to read .

I would like to mention potential advantages of using topological evolution to implement quantum gates. First of all, there is no dynamical phase in the evolution. This is because we are using degenerate states to encode information so that the dynamical phase is the same for both states (and it factors out as it were). Also, all the errors stemming from the dynamical phase are automatically eliminated. Secondly, the states being degenerate do not suffer from any bit flip errors between the states (like the spontaneous emission). So, the evolution is protected against these errors as well. Thirdly, the size of the error depends on the area covered and is therefore immune to random noise (at least in the first order) in the driving of the evolution. This is because the area is preserved under such a noise as formally proven by Palma . Also, by tuning the parameters of the driving field it may be possible to make the phase independent of the area to a large extent and make it dependent only on a singular topological feature - such as in the Aharonov-Bohm effect where the flux can be confined to a small area - and this would then make the phase resistant under very general errors.

So, in order to see how this works in practice we take an atomic system as our model implementing the non-abelian evolution. We’ll see that quantum computation can easily be implemented in this way. The question, of course, is the one about the ultimate benefits of this implementation. Although there are some obvious benefits, as listed above, there are also some serious shortcomings, and so the jury is still out on this issue.

### 4.2 Example

Let’s look at the following $`4`$ level system analyzed by Unanyan, Shore and Bergmann . They considered a four level system with three degenerate levels $`1,3,4`$ and one level $`2`$ with a different energy as in Fig 7. This system stores one bit of information in the levels $`1`$ and $`2`$ (hence there is double the redundancy in the encoding of information). We have the following Hamiltonian

$$H(t)=\left(\begin{array}{cccc}0& P(t)& 0& 0\\ P(t)& 0& S(t)& Q(t)\\ 0& S(t)& 0& 0\\ 0& Q(t)& 0& 0\end{array}\right)$$

where $`P,Q,S`$ are some functions of time (to be chosen at leisure). It is not difficult to find eigenvalues and eigenvectors of this matrix (exercise!). There are two degenerate eigenvectors (with the corresponding zero eigenvalue for all times) which will be implementing our qubit and they are

$$\mathrm{\Phi }_1(t)=\left(\begin{array}{c}\mathrm{cos}\theta (t)\\ 0\\ \mathrm{sin}\theta (t)\\ 0\end{array}\right)$$

and

$$\mathrm{\Phi }_2(t)=\left(\begin{array}{c}\mathrm{sin}\varphi (t)\mathrm{sin}\theta (t)\\ 0\\ \mathrm{sin}\varphi (t)\mathrm{cos}\theta (t)\\ \mathrm{cos}\varphi (t)\end{array}\right)$$

where $`\mathrm{tan}\theta (t)=P(t)/Q(t)`$ and $`\mathrm{tan}\varphi (t)=Q(t)/\sqrt{P(t)^2+Q(t)^2}`$.

In the adiabatic limit (which we will assume here) these are the only important ones as the state will remain in their subspace throughout the evolution (this is guaranteed by the adiabatic theorem). Although, in general, the Dyson equation is difficult to solve, in this special example we can write down a closed form expression . The unitary matrix representing the geometrical evolution of the degenerate states is

$$B(t)=\left(\begin{array}{cc}\mathrm{cos}\gamma (t)& \mathrm{sin}\gamma (t)\\ \mathrm{sin}\gamma (t)& \mathrm{cos}\gamma (t)\end{array}\right)$$

where

$$\gamma (t)=\mathrm{sin}\varphi (t)\frac{d\theta }{dt}𝑑t$$
(61)
This therefore allows us to calculate the non-abelian phase for any closed path in the parametric space. After some time we suppose that the parameters return to their original value. So, at the end of the interaction we have the matrix

$$B(\mathrm{})=\left(\begin{array}{cc}\mathrm{cos}\gamma _f& \mathrm{sin}\gamma _f\\ \mathrm{sin}\gamma _f& \mathrm{cos}\gamma _f\end{array}\right)$$

where

$$\gamma _f=_c\frac{Q}{(P^2+S^2)\sqrt{Q^2+P^2+S^2}}(SdPPdS)$$
(62)
which can be evaluated using Stokes’ theorem (the phase will in general depend on the path, as explained before). So, we can have a non-abelian phase implementing a Hadamard gate. With two systems of this type (mutually interacting) we can implement a controlled Not gate and therefore (at least in principle) have a universal quantum computer (see ). As an exercise I leave it to the reader to implement Deutsch’s algorithm in the purely topological way.

## 5 Conclusions and Outlook

We have seen what geometric phases are and appreciated their importance in physics in general. They were shown to be linked to the modern ideas of gauge theories and differential geometry, in particular the idea of parallel transport. In addition to their fundamental value, they also have a potential to implement quantum gates that are, at least in principle, more reliable than any existing gates. In order to do so I have argued that a high degree of topological dependence has to be achieved - i.e. independence of global geometry, which is certainly not that easy in practice. These topological gates will most likely have to be combined with other error correcting mechanisms in order to make a reliable quantum computer. The exact engineering design will, in the end, depend on the actual medium that is chosen to support quantum computation. It is fair to say that when this review was completed (in December 2002) there was no fully fault tolerant implementation of quantum computation. Fortunately there has been a huge number of proposals to implement such computations with various solid-state systems (such as Josephson Junctions and Quantum Dots), Nuclear Magnetic Resonance, Trapped Atoms and so on, and the whole field is, therefore, very much alive at present.

Acknowledgments.  I have benefited greatly from discussions with J. Anandan, S. Bose, A. Carollo, A. Ekert, P. Falci, S. Fazio, I. Fuentes-Guridi, J. Jones, D. Markham, J. Pachos, M. Palma, M. Santos, J. Siewert and E. Sjöqvist on the subject of geometric phases. My research on this subject is supported by European Community, Engineering and Physical Research Council in UK, Hewlett-Packard and Elsag spa.


format: text

text:
# Entanglement generation and multiparticle interferometry with neutral atoms.

## Abstract

We study the preparation and manipulation of states involving a small number of interacting particles. By controlling the splitting and fusing of potential wells, we show how to interconvert Mott-insulator-like and trapped BEC-like states. We also discuss the generation of “Schrödinger cat” states by splitting a microtrap and taking into practical consideration the asymmetry between the resulting wells. These schemes can be used to perform multiparticle interferometry with neutral atoms, where interference effects can be observed only when all the participating particles are measured.

Entanglement is at the root of Bell’s theorem, which exposes the differences between quantum theory and a local classical theory based on elements of reality bell64 . The predictions of quantum mechanics have been experimentally observed with entangled Einstein-Podolsky-Rosen (EPR) pairs epr\_exp1 ; epr\_exp2  as well as Greenberger-Horne-Zeilinger (GHZ) triples pan00 . A related consequence of entanglement is the possibility of multiparticle interferometry. Given a maximally entangled system of $`N`$-particles (a “Schrödinger cat” state) a measurement of interference between different parts of the wave function corresponding to a single particle yields random results. It is only when performing a coincidence measurement on all $`N`$ particles that an interference pattern is revealed greenberger93 . Experimental confirmation of this result has been obtained using photonic EPR pairs epr\_exp2 ; ghosh87  and internal states of four ions in the same trap sackett00  but no experiments have been performed using a larger number of particles. The latest generation of experiments with photons rely on parametric down-conversion, which has the technical disadvantage of an exponentially decreasing number of useful counts as $`N`$ increases. Given that entanglement is the key ingredient in all quantum computation and quantum communication schemes, clean experimental studies of its consequences have become an active topic of research in the last decade.

In recent years several papers jaksch99 ; andersson00  have suggested the generation of entanglement between neutral atoms confined in traps by using their interaction in controlled atomic collisions. The atoms are guided in their motion and their evolution yields the required entanglement of internal states. Other schemes to achieve this sort of entanglement starting from BECs have been suggested bec\_entanglement . In this letter we present two general $`N`$-atom nonlinear processes. The first one is used to convert a Mott-insulator-like (MI) state Mott\_insulator  into a state with all particles in the (many-body) ground state of a single trap (BEC-like state); its reverse process converts the BEC state into a MI state. The second process is used to generate a Schrödinger cat state starting from a BEC state by controlling the splitting of the well. As an application of the processes we discuss a scheme for multiparticle interferometry with spatially separated paths.

In the first process, which is also stage I of the interferometry setup, we start with a collection of $`N`$ atoms in the ground states of $`N`$ independent traps (MI state). These separate atoms can be extracted from a reservoir using a quantum tweezer opt\_delivery  recently proposed by our group. Alternatively, single atoms stored and detected in micro-optical traps (which have been experimentally reported opt\_detection  but are in excited states of the trap) can be Raman cooled individually to the ground state. The BEC state (stage I, Fig. 1) is achieved by bringing together the $`N`$ wells adiabatically if the interaction between atoms is repulsive, as will be shown in detail below. This is a consequence of the quantum adiabatic theorem, since the MI state is the ground state when the wells are far apart. Our evolution is then represented by

$$|w_1w_2\mathrm{}w_N|\mathrm{\Psi }_I=|ww\mathrm{}w,$$
(1)
where the states are properly symmetrized bosonic states.

In the second process (stage II of multiparticle interferometry) the interaction is switched to attractive. This can be done by using a Feshbach resonance feshbach\_resonance . Starting from the BEC state, we slowly split the well into two approximately equal mictrotraps, which we label as $`L`$ and $`R`$. The lowest energy states are then the ones having all atoms in the left or in the right well. Since initially the system is in the ground state, by separating the traps at some slow rate $`v`$ when the wells are far apart we get a linear combination of these two nearly degenerate states, i.e. the system is in the Schrödinger cat state

$$|\mathrm{\Psi }_I|\mathrm{\Psi }_{II}=\alpha |LL\mathrm{}L+\beta e^{i\theta }|RR\mathrm{}R,$$
(2)
with $`\alpha `$, $`\beta `$, and $`\theta `$ real. For perfectly symmetric traps, $`\alpha =\beta `$ and $`\theta =0`$, but any asymmetry makes these parameters rate dependent, as will be discussed in detail below.

Additional processes are needed to realize multiparticle interferometry. During stage III, the interaction is switched back to repulsive and each of the two traps is separated to $`N`$. This stage can be seen as the inverse of stage I applied to the wells $`L`$ and $`R`$. Again, if the separation is done adiabatically the system remains in the ground state which in this case corresponds to a single atom in each one of the wells. The state is now

$$|\mathrm{\Psi }_{II}|\mathrm{\Psi }_{III}=\alpha |L_1L_2\mathrm{}L_N+\beta e^{i\theta }|R_1R_2\mathrm{}R_N.$$
(3)
Subsequently, the atoms in wells derived from the original $`R`$ well are subjected to additional phase shifts $`\varphi _1,\varphi _2\mathrm{}\varphi _N`$, which can be applied, for example, by adjusting the depth of the wells adiabatically.

In the final, stage IV of the scheme, we combine states $`L_i`$ and $`R_i`$ in a 50-50 beamsplitter andersson99 . Notice that in the experiment only one of these two is occupied so the interatomic interaction plays no role in this stage. We denote the outputs of each beamsplitter by $`A_i`$ and $`B_i`$ and assign a value of $`+1`$ to the measurement of an atom in channel $`A_i`$, and $`1`$ to the measurement of atom in channel $`B_i`$. The probability, $`P(+1)`$, that the product of all measurements gives $`+1`$ (for instance $`A_1B_2B_3`$ in the case of three atoms) is $`\left(1\alpha \beta \mathrm{cos}\left(\mathrm{\Delta }+\theta \right)\right)/2`$, where $`\mathrm{\Delta }=\underset{i=1}{\overset{N}{}}\varphi _i`$. The probability for the product to be $`1`$ is $`P(1)=1P(+1)`$, hence the expectation value over a large number of measurements is $`\alpha \beta \mathrm{cos}\left(\mathrm{\Delta }+\theta \right)`$. We would like to stress that a correlated measurement of less that $`N`$ atoms does not show any dependence on phase and appears random.

In order to obtain the relevant parameters for the operation of our inteferometer, we study the evolution of an $`N`$ particle system using optical microtraps. As an example, we numerically solve the Schrödinger equation in the case of three atoms in a quasi-1D configuration. This is achieved by strongly trapping the atoms in the perpendicular dimensions, effectively freezing these degrees of freedom. We scale the equations choosing units of length $`L_u=2\mu \mathrm{m}`$, of energy $`E_u=\mathrm{}^2/\left(2M_uL_u^2\right)`$ and of time $`t_u=\mathrm{}/E_u`$. The particle interaction is represented by a delta-function potential

$$U(x_1,x_2)=U_0\delta (x_1x_2).$$
(4)
The atoms are also subject to external potentials due to the optical traps, which in each stage are

$$\begin{array}{c}V_{I,III}(x,d)=\underset{i=1}{\overset{3}{}}(1+q_i)V(x,(i2)d),\\ V_{II}(x,d)=(1+q_1)V(x,d/2)+(1+q_2)V(x,+d/2),\end{array}$$
(5)
with

$$V(x,d)=V_0\mathrm{exp}\left(\frac{\left(x+d\right)^2}{2\sigma ^2}\right).$$
(6)
The $`q_i`$ parametrize the asymmetry between the intensities of the beams defining the different wells; we assume that these are $`10^4`$.

Let us consider first the evolution during the first and the third stages of the operation. There are four different energy scales in the problem. The first one is the energy difference between the energy levels localized in different wells, which we can estimate as $`E_{\mathrm{asym}}qV_0`$. The second one is the energy required to move one of the atoms to an already occupied well, estimated to be $`E_{\mathrm{int}}U_0/\sigma _0`$ where $`\sigma _0=(V_0/\sigma ^2)^{1/4}`$ is the width of the wave function in a well. The third scale is the energy $`E_{\mathrm{exc}}\sigma _0^2`$ required to put one of the atoms in an excited state of one of the traps. The last energy scale ($`E_D(\pi /ND)^2`$) is the energy required to excite the atoms out of the ground state when the distance between the wells is $`D2\sigma `$, at which time the trap can be approximated by a square well of width $`ND`$. We operate in the regime in which

$$E_{\mathrm{asym}}E_{\mathrm{int}},E_{\mathrm{exc}},E_D.$$
(7)
Figure 2 shows the dependence of the adiabatic levels on the separation $`d`$ during this stage. The presence of the small asymmetry in this stage does not affect the nature of the ground state, which is non-degenerate. Joining or separating the wells at a slow speed keeps the system in the ground state, i.e. the lowest curve in the figure. We can estimate the rate at which the adiabaticity is lost by applying the Landau-Zener formula LZformula , $`v_{\mathrm{ad}}(\mathrm{\Delta }E_{\mathrm{gap}})^2/(dE/dx)`$. The slope can be estimated as $`\sqrt{NV_0}/\sigma ^2`$. The size of the gap depends on which of the three large energy scales in (7) is the smallest. In the example that we are presenting, all three are roughly the same order of magnitude. The probabilities $`|a_i|^2=|\psi _i|\psi |^2`$ to find the system in the states $`|\psi _i`$ at the end of the evolution is plotted in Figure 3 as a function of the speed $`v`$. In our example, the critical rate is $`v_{cI,2}=0.35`$; the probability to find the system in other states is less than 0.01. For multiparticle interferometry it is critical not to accumulate an additional phase during the third process due to the asymmetry between the right and left set of wells. This gives rise to a lower bound for the allowed velocity, as explained below. For the parameters chosen in the figure this is $`v_{cI,1}=0.09`$.

Between these stages and stage I we need to change the sign of the effective interaction between the particles. For the cases we are considering, the particles remain the ground state with very high probability (of the order of 99%) even if this change is performed suddenly.

During stage II the adiabatic energy levels as a function of $`d`$ are shown in Figure 4. Once again we have four energy scales, which can be approximated by $`E_{\mathrm{asym}}NqV_0`$, $`E_{\mathrm{int}}(N1)|U_0|/\sigma _0`$, $`E_{\mathrm{exc}}\sigma _0^2`$, and $`E_D(\pi /2D)^2`$. Once again, we work in the regime in which (7) is valid. Separating the wells adiabatically maintains the system in the ground state, which corresponds to all $`N`$ atoms being in the lowest of the two wells, which is not the desired state. In order to mix the lowest two energy states we need to evolve the system non-adiabatically with respect to the lowest gap but at a slow enough speed to remain adiabatic with respect to the larger gap. Below $`v_{cII,2}=0.27`$ the probability to tunnel to these excited states is less then 0.01 and entanglement is obtained with $`\alpha \beta =0.99`$ or larger. On the other hand, the asymmetry yields a dephasing between the two parts of the wave function $`\theta =E_{\mathrm{asym}}t_{\mathrm{sep}}`$, where the separation time is inversely proportional to the velocity $`v`$. Allowing a maximum dephasing $`\varphi _{\mathrm{max}}`$, we must go faster than $`v_{cI,1}qV_{0,III}N/\varphi _{\mathrm{max}}`$. This calculation assumes, however, that the asymmetry is constant. In a practical situation, $`q`$ is driven by fluctuations in the laser power, and consequently the phase $`\theta `$ grows diffusively, as the square root of $`t_{\mathrm{sep}}`$ instead of linearly, making the condition less restrictive.

The only two conditions for the applicability of the method are related to the asymmetry of the potential. As long as condition (7) is met and as long as $`v_{c,2}`$ is larger than $`v_{c,1}`$, there is a range of velocities for which the operation is successful. The critical velocities have different dependence on $`N`$, so for fixed values of the parameters defining the potential and the interaction, there is a largest number of atoms for which this happens. However, by choosing a different set of parameters this condition can be relaxed. In particular, the strong $`N^2`$ dependence of the preparation of the MI state can be overcome by separating the atoms in series instead of doing it parallel (for $`N=2^n`$, we can think of $`n`$ steps in which each well is split into two).

Finally, numerical values for realistic experimental parameters are given. In the model described above the effective interaction between atoms is determined by the scattering length $`a`$ and the strength of the confinement in the transverse direction. The frequency $`\omega _{}`$ of the confinement in the case in which the system stays in the ground state of transverse motion may be expressed in terms of the dimensionless interaction parameter $`U_0`$ used above jaksch99  as

$$\omega _{}=\frac{U_0\mathrm{}}{4\left|a\right|M_uL_u}.$$
(8)
Hence it is desirable to use atoms with the largest product of mass and scattering length possible. In Table 1 we present the rescaled values used in the calculation for two workhorses of cold atom experiments, sodium and rubidium. The magnetic fields needed to observe Feshbach resonances in alkali atoms are typically hundreds of gauss feshbach\_resonance . In the proposed scheme for multiparticle interferometry one should work on the side of the resonance where the scattering length changes sign to avoid the losses associated with crossing the resonance.

We acknowledge support from the NSF, the R.A. Welch Foundation, MGR also acknowledges support from the Sid W. Richardson Foundation.


text:
# 𝑃^𝑓≠𝑁𝑃^𝑓 for almost all 𝑓

## 1 Introduction

After establishing $`PNP`$ for infinite time Turing machines, Ralf-Dieter Schindler in  introduced the more general question of whether $`P^f=NP^f`$ for these machines. The classes are defined as follows:

###### Definition 1.1

Let $`f:^\omega 2\omega _1`$ and $`A^\omega 2`$.

(A) We say that $`AP^f`$ if there is an (infinite time) Turing machine computable function $`\phi _e`$ so that
(i) $`A`$ is decidable by $`\phi _e`$, that is $`xA`$ if and only if $`\phi _e(x)1`$, and
(ii) $`z^\omega 2\phi _e(z)`$ in at most $`f(z)`$ many steps.

(B) We say that $`ANP^f`$ if there is a Turing machine computable function $`\phi _e`$ so that
(i) $`xA`$ if and only if there exists $`y^\omega 2`$ so that $`\phi _e(xy)1`$, and
(ii) $`z=(xy)^\omega 2\phi _e(z)`$ in at most $`f(x)`$ many steps.

The function $`f`$ plays the role here of the class of polynomials in the classical $`P=NP`$ question, bounding the length of the allowed computations. Because of this, one is primarily interested here in the functions $`f`$ which are Turing invariant, in the sense that if $`x`$ and $`y`$ are Turing equivalent, then $`f(x)=f(y)`$. Indeed, since one might expect that a more complicated input should be allowed more time for computation, it is natural to restrict attention only to the functions $`f`$ for which $`x_Ty`$ implies $`f(x)f(y)`$. The main results of this article, however, do not happen to rely on these assumptions. Since the computations allow for infinite input, one might usually want to assume that $`f(x)`$ is infinite.

If the value of $`f(x)`$ is some constant $`\alpha `$ then the classes $`P^f`$ lie strictly within the Borel hierarchy ( Lemma 2.7). If $`f(x)=\omega _1^x`$ then $`P^f`$ coincides with hyperarithmetic (and so we are really still within the realms of Kleene recursion e.g. see ). When $`f(x)>\omega _1^x`$ for all $`x`$ we then truly enter for the first time the world of sets that are essentially computed by infinite time Turing machines (see  for the basic concepts).  raises two questions concerning these classes for such functions dominating $`f(x)=\omega _1^x`$.

Note that unlike the basic notions of $`P`$ and $`NP`$ Schindler defined in §2 of , his class $`NP^f`$ is not, in general, just the projection of $`P^f`$.

We wish to prove that for almost all functions $`f`$ the classes $`P^f`$ and $`NP^f`$ are different. Given the extra information that the verifying witness $`y`$ can encode, this is, or should be, unsurprising. The first point to note is that if the values $`f`$ takes are sufficiently large, they will exceed the times needed by a machine to establish membership of any decidable set.

We recall a definition from :

###### Definition 1.2

$`\lambda ^x=_{df}sup\{\alpha e\phi _e(x)yyWOrk(y)=\alpha \}`$.

Equivalently (and the reader may take this as a definition):

###### Fact 1.3

( Theorem 1.1) $`\lambda ^x`$ is the supremum of halting times of any Turing computable function on input $`x`$.

Implicit in this latter result—when taken with the definition of decidable sets of reals —(see the discussion in ) is the following characterisation of such sets.

###### Fact 1.4

$`A^\omega 2`$ is decidable if and only if there are $`\mathrm{\Sigma }_1`$ formulae in the language of set theory $`\phi _0(v_0),\phi _1(v_0)`$ so that

$$xAL_{\lambda ^x}[x]\phi _0[x]L_{\lambda ^x}[x]\neg \phi _1[x]$$

Clearly then:

###### Lemma 1.5

If $`\lambda ^xf(x)`$ for all $`x`$, then $`P^f`$ is the class of decidable sets.

We recall a definition from :

###### Definition 1.6

$`\mathrm{\Sigma }^x=_{df}sup\{\alpha \text{ a code }xWO\text{ for }\alpha \text{ occurs on a tape }`$
of some computation $`\phi _e(x)`$ at some time $`\}`$

(Thus $`\mathrm{\Sigma }^x`$ is the supremum of ordinals with so-called accidentally writable (relative to $`x`$) codes, as defined in  p. 580.) It is shown in  that (i) $`\mathrm{\Sigma }^x`$ is the least $`\sigma `$ so that $`L_\sigma [x]`$ has a proper $`\mathrm{\Sigma }_2`$-elementary substructure: and in  that (ii) $`L_{\mathrm{\Sigma }^x}[x]`$ is inadmissible.

Our first theorem is that any function $`f`$ that dominates the function $`g(x)=\mathrm{\Sigma }^x`$ separates the classes $`NP^f`$ and $`P^f`$. This answers Question 2 of  “almost everywhere”:

###### Theorem 1.7

Let $`f`$ satisfy $`f(x)\mathrm{\Sigma }^x`$ for all $`x`$. Then $`NP^fP^f`$.

The next theorem answers Question 1 of . Let $`f_0`$ be defined as $`f_0(x)=\omega _1^x+\omega `$.

###### Theorem 1.8

$`NP^{f_0}P^{f_0}`$.

In  the classes $`P^{f_0}`$ and $`NP^{f_0}`$ are denoted $`P^{++}`$ and $`NP^{++}`$, respectively, so we have shown $`P^{++}NP^{++}`$, the question left open in . As  points out, of course $`P^{f_0}`$ contains all $`\mathrm{\Sigma }_1^1`$ and $`\mathrm{\Pi }_1^1`$ sets. It is not hard to see that if $`A\mathrm{Diff}(<\omega _1^{ck},\mathrm{\Sigma }_1^1)`$ the Hausdorff difference hierarchy for levels below the first non-recursive ordinal, then $`AP^{f_0}`$.

Variants of these methods will also show that many other functions whose range falls between these two ordinals will also separate these two classes. We have not attempted an exhaustive classification.

Suppose $`\varphi _e:^\omega 2N`$ is total. Then the length of the computation $`\varphi _e(x)`$, $`\nu _x`$ say, defines for us a “clock”. Namely let $`f(x)=\nu _x`$; suppose for convenience $`\nu _x`$ is always of limit length and at least $`\omega ^\omega `$.

###### Theorem 1.9

With $`f`$ as above: $`NP^fP^f`$.

## 2 Preliminaries

We shall let $`\omega _1^x`$ stand for the first ordinal not recursive in $`x`$. Then $`L_{\omega _1^x}[x]`$ is an admissible  set. We refer the reader to  for an account of admissible sets and their basic properties. We shall use the following notation for the machine configurations. Let the cells of the tape be enumerated $`C_i|i<\omega `$ with the cell $`C_i`$ having value $`C_i(\xi )`$ at time $`\xi `$. We assume that the first $`n`$ blocks on the tape are enumerated by $`C_i|i<3n`$ with $`C_0,C_1,C_2`$ being the leftmost output,scratch, and input cells respectively. A snapshot of the tape at time $`\gamma `$ is then a function $`s^\omega 2`$ coding these cell values, with $`s(i)=C_i(\gamma )`$ (possibly also allowing it to encode somewhere internal states, the location of the head and the instruction of the program about to be performed). A halting computation is then entirely given by the wellordered snapshot sequence of computations of the length of the computation. The machine is considered to be specified by a finite program, just as for ordinary Turing machines, although the head is allowed to read, and write to, triples of cells at any one stage. Thus a typical instruction might be of the form $`(q_i,j,j^{},X,q_k)`$ where $`j,j^{}^32`$, interpreted to mean that in state i viewing cells $`C_{3l},C_{3l},C_{3l+2}`$ with values $`j(0),j(1),j(2)`$ the machine moves to state $`q_k`$, changes the cell values to those of $`j^{}`$ and moves one unit in the direction $`X\{L,R\}`$ (for Left and Right). The machine has however a special limit state $`q_L`$ (and at limit times it is in this state viewing $`C_0,C_1,C_2`$). The machine may thus halt at a limit time if it contains a quadruple of the form $`(q_L,j,j^{},q_H)`$. Note however that executing this last step of computation means that it changes the entries of $`C_0,C_1,C_2`$ to those given by $`j^{}`$. It is this feature that allows the classes $`P^{f_0}`$ to be closed under complementation: an “accepting” entry of $`C_0`$ as 1 can be switched to a “rejecting” zero at the last moment. To be completely clear, if the machine executes the halt instruction at the limit stage $`\nu `$, we reiterate that the final value is $`C_i(\nu +1)=j^{}(i)`$, which might differ from the limit value $`C_i(\nu )=j(i)`$.

We shall use the following fact.

###### Fact 2.1

 There is an index $`e_0\omega `$ so that, uniformly, for any $`x^\omega 2`$ $`\{e_0\}^x`$ is an illfounded linear ordering of $`\omega `$, recursive in $`x`$, with wellfounded part of order type $`\omega _1^x`$.

We use this index to give us a “canonical $`\omega _1^x+\omega `$-clock”: an algorithm that halts in exactly $`\omega _1^x+\omega `$ steps. (The following argument is the “uniform in $`x`$” version of that of Theorem 3.2 of .) The algorithm does the following: it first computes the field of the relation $`<_R=\{e_0\}^x`$ and then proceeds, by picking the least element of the field, $`n`$ say, in $`\omega `$ many steps to find the $`<_R`$-least element below $`n`$ of the ordering. It then, in another $`\omega `$ many steps, proceeds to strike out all mention of this element from the field of $`\{e_0\}^x`$; it then picks an element $`n^{}`$ of the field that is left and searches for the next $`<_R`$-least element below this $`n^{}`$; at limit stages below $`\omega _1^x`$ the procedure continues smoothly as the wellfounded part of $`<_R`$ has order type $`\omega _1^x`$. However in the interval $`(\omega _1^x,\omega _1^x+\omega )`$ it searches in vain for a least element. It chooses some $`\overline{n}`$ in the field that is left. We may assume that each time it descends in $`<_R`$ it flashes a signal in $`C_2`$, by alternating in the next 3 stages the value of $`C_2`$ to be “0,1,0”. After $`\omega `$ many stages, by the limsup rule of the machines, the value $`C_2(\omega _1^x+\omega )=1`$, and moreover this is the first time this happens at a limit stage. We assume then the program has been written so as to immediately halt if this occurs.

An alternative $`\omega _1^x+\omega `$ clock is obtained by the algorithm that on input $`x`$ simulates all computations on input $`x`$, looking for a stage at which none of the programs halt. Since $`\omega _1^x`$ is the least such stage, and it takes $`\omega `$ many steps to recognize that this situation has occurred, the algorithm can halt exactly at $`\omega _1^x+\omega `$.

###### Definition 2.2

$`\zeta ^x=_{df}sup\{\alpha ey\gamma \delta >\gamma \text{ }yWO\text{ lies on the output tape }`$
$`\phi _e(x)`$ at time $`\delta rk(y)=\alpha \}.`$

We shall appeal to the following fact:

###### Fact 2.3

(“$`(\lambda ,\zeta ,\mathrm{\Sigma })`$ Theorem”)

(i)( cf.  2.3.) For any computation of the form $`\varphi _e(x)`$, the snapshot at time $`\zeta `$, $`s_\zeta `$, is exactly that at time $`\mathrm{\Sigma }^x`$, $`s_\mathrm{\Sigma }`$; they are both settled snapshots, i.e. they are destined to recur on a closed and unbounded class of ordinals;

(ii) ( 2.1,2.3) if $`\xi `$ is the least $`\xi `$ satisfying $`L_\xi [x]_{\mathrm{\Sigma }_2}L_{\mathrm{\Sigma }^x}[x]`$, then (a) $`\xi =\zeta ^x`$ and (b) $`(\lambda ^x,\zeta ^x,\mathrm{\Sigma }^x)`$ is the lexicographic least increasing triple $`(\lambda ,\zeta ,\mathrm{\Sigma })`$ satisfying $`L_\lambda [x]_{\mathrm{\Sigma }_1}L_\zeta [x]_{\mathrm{\Sigma }_2}L_\mathrm{\Sigma }[x]`$.

By  (Claim (ii) of 3.4) there are computations $`\varphi _{q_0}`$ so that for any input $`x`$, $`(\zeta ^x,\mathrm{\Sigma }^x)`$ is the lexicographically (on $`On\times On`$) least pair of ordinals with repeating snapshots $`(s_{\zeta ^x},s_{\mathrm{\Sigma }^x})`$: running a universal machine provides such. (In fact, any computation on input $`x`$ which does not repeat before $`\lambda ^x`$ is such an example. In such a case it is the snapshot $`s_{\zeta ^x}`$ that provides a parameter witnessing the inadmissability of $`L_{\mathrm{\Sigma }^x}[x]`$ \- cf. , 3.4) In general then, this pair of snapshots witnesses that the computation is either halted or in an infinite loop.

## 3 Separating the classes

Proof of Theorem 1.7. By our observation in the introduction, under these assumptions $`P^f`$ is the class of decidable sets of reals. Let $`H=\{p,x\omega \times ^\omega 2\varphi _p(x)\}`$. Then $`H`$ is the complete set coding the halting problem for sets of reals. $`H`$ is undecidable, but the above arguments, together with the $`(\lambda ,\zeta ,\mathrm{\Sigma })`$ Theorem will show that $`HNP^f`$.

It will suffice to verify whether $`\varphi _e(x)`$ by the following method.

We consider informally a Turing machine computable algorithm $`P_n`$ that effects the following:

$`P_n`$ on input $`exy`$:
(i) First checks whether $`y`$ codes an $`\omega `$-model containing (an isomorphic copy of) $`x`$ and:

$$𝒜=\omega ,y\mathrm{`}\mathrm{`}KPV=L[x]\mathrm{\Sigma }^x\text{ exists}\varphi _e(x).\mathrm{"}$$

By way of explanation: we intend that $`𝒜`$ thinks there is a least initial segment of its $`L[x]`$-hierarchy with a proper $`\mathrm{\Sigma }_2`$ elementary substructure - this is the import of “$`\mathrm{\Sigma }^x`$ exists.” This is an arithmetic condition on $`xy`$ and thus can be checked by $`P_n`$ in $`<\omega ^\omega `$ many steps. If this fails for $`y`$ then $`P_n(exy)0`$ thus halting with a zero in the first cell $`C_0`$ of the output tape.

(ii) Otherwise a preliminary “1” is written to $`C_0`$ and then $`P_n`$ proceeds to check if $`WFP(𝒜)`$ contains the true $`\mathrm{\Sigma }^x`$. However we first dispose of the part of the model containing all sets of $`(L[x]`$-rank$`)^𝒜(\mathrm{\Sigma }^x)^𝒜`$. We simply eliminate all reference to these in $`y`$, thus in effect rewriting $`y`$ as some new real $`\overline{y}`$. However this is again a simple operation, and can be done in, say, $`\omega ^2`$ steps (note that $`y`$ has some integer $`n`$ which denotes the $`(\mathrm{\Sigma }^x)^𝒜`$ so it is a trivial matter to do this). The process then proceeds to check for the wellfoundedness of the ordinals of this new $`\omega `$-model $`\overline{𝒜}=\omega ,\overline{y}`$ determined by the initial segment $`(\mathrm{\Sigma }^x)^𝒜`$ in the usual way by erasing integers from the field of its ordinals.

If the model $`\overline{𝒜}`$ is wellfounded then this process takes the true $`\mathrm{\Sigma }^x`$ many steps, (note that $`(\mathrm{\Sigma }^x)^𝒜\mathrm{\Sigma }^x`$ as there is $`n`$ denoting $`(\mathrm{\Sigma }^x)^𝒜`$ and the property of an ordinal being $`\mathrm{\Sigma }^x`$ is absolute), and furthermore the model $`\overline{𝒜}`$ is correct about $`\varphi _e(x)`$. Using the trick of keeping track of when the least (in some standard ordering of $`\omega \times \omega `$) pair is erased we may realise also that the field of the ordering of $`On^{\overline{𝒜}}`$ has become empty (cf.  the proof of Theorem 3.1 in ). If so it can halt exactly at the $`\mathrm{\Sigma }^x`$’th step with the required $`1`$ in $`C_0`$.

If the model $`\overline{𝒜}`$ is illfounded (and hence $`(\mathrm{\Sigma }^x)^𝒜`$ is in the illfounded part of the original $`On^𝒜`$), then in fact $`\mathrm{\Sigma }^xWFP(\overline{𝒜})=WFP(𝒜)`$: this is because (a) we cannot have $`\mathrm{\Sigma }^xWFP(\overline{𝒜})`$ (as otherwise $`𝒜`$ would recognize it as $`\mathrm{\Sigma }^x`$); (b) but neither can $`WFP(\overline{𝒜})=\mathrm{\Sigma }^x`$ (as $`L_{\mathrm{\Sigma }^x}[x]`$ is inadmissible, and this would contradict the Truncation Lemma ().

Hence any instance of illfoundedness in $`(On)^{\overline{𝒜}}`$ will be detected before the true $`\mathrm{\Sigma }^x`$ many steps have been taken. This leaves time to change the contents of $`C_0`$ to a zero, and halt \- here before $`\mathrm{\Sigma }^x`$ many steps have been taken.

In each case then $`P_n(exy)`$ halts in no more than $`\mathrm{\Sigma }^x`$ many steps with the correct output.

The algorithm above can be made more time efficient, so that confirming instances of the decision problem are settled more quickly. This modified algorithm can be made to actually follow the naive idea that to determine whether $`\varphi _e(x)`$, one should simply simulate the computation $`\varphi _e(x)`$ to see if it halts, and somehow end simulations that have gone on too long. The point is that the model-checking method of the previous argument, where one checks whether $`\overline{𝒜}`$ is well-founded, is essentially a nondeterministic clock for $`\mathrm{\Sigma }^x`$, in the sense that it halts at time $`\mathrm{\Sigma }^x`$ for certain witnesses $`y`$, and before $`\mathrm{\Sigma }^x`$ for all other witnesses. Our modified algorithm, therefore, is simply to run such a clock alongside the computation of $`\varphi _e(x)`$, and accept the input if the computation halts before the clock runs out. Since in the worst case the clock runs to time $`\mathrm{\Sigma }^x`$, this algorithm nondeterministically decides whether $`\varphi _e(x)`$ in time $`\mathrm{\Sigma }^x`$. But the point is that affirmative instances are decided much earlier, in time before $`\lambda ^x`$, because this is when the halting computations actually halt.

The theorem can be improved by ignoring the bold-face context of the situation:

###### Theorem 3.1

Suppose that $`f(p)\mathrm{\Sigma }`$ for every finite $`p`$ and $`f(x)\omega `$ for all other reals $`x`$. Then $`NP^fP^f`$.

Proof: The idea is that the (weak) halting problem $`h=\{p\phi _p(0)\}`$ will be in $`NP^f`$ but not in $`P^f`$. It clearly is not in $`P^f`$, since it is not decidable. But one can see it is in $`NP^f`$ by the following algorithm: on input $`xy`$, first check whether $`x`$ is a finite $`p`$ or not. If not, then halt and reject the input. Otherwise, carry out the algorithm of Theorem 1.7 on the input $`p0y`$. With suitable choice of $`y`$, this will decide whether $`(p,0)H`$, which is equivalent to $`ph`$, in at most $`\mathrm{\Sigma }^0=\mathrm{\Sigma }`$ many steps, as desired.

Proof of Theorem 1.9 Let $`H_f=\{p,x\omega \times ^\omega 2\varphi _p(x)\text{ in }\nu _x\text{ steps }\}`$

(1) $`H_fP^f`$.

Proof: Let $`r`$ be the partial function defined as follows:

$$r(y)=\{\begin{array}{cc}0& \text{ if }y=p,xyH_f\hfill \\ & \text{ otherwise}\hfill \end{array}$$

If “$`yH_f`$” were decidable by an algorithm that always halted in at most $`\nu _y`$ steps then $`r`$ would also be computable by an algorithm $`P_m`$, that if it converged, would do so in $`\nu _y`$ steps. (We could obtain a program for $`r`$ by simply changing the behaviour of that of the former algorithm by switching at the very last limit step where it halted on a 1, into some non-halting loop.) Let $`\varphi _m:^\omega 2\omega `$ be this latter function. Let $`c_0`$ be the constant zero function. However then

$$\begin{array}{ccc}m,c_0H_f\hfill & & \hfill \varphi _m(m,c_0)\text{ in }\nu _x\text{ steps }\\ & & \hfill r(m,c_0)=0m,c_0H_f\end{array}$$

a contradiction.

(2) $`H_fNP^f`$.

Proof: We use the ideas from the proof of Theorem 1.7. We devise an algorithm $`P_n`$ to verify (2). $`P_n`$ on input $`pxy`$:

(i) First checks whether $`y`$ codes an $`\omega `$-model containing (an isomorphic copy of) $`x`$ and:

$$𝒜=\omega ,y\mathrm{`}\mathrm{`}KPV=L[x]\varphi _p(x)\text{ in }\varphi _e(x)=\nu _x\text{ steps}.\mathrm{"}$$

This is again an arithmetic condition on $`xy`$ and thus can be checked by $`P_n`$ in $`<\omega ^\omega `$ many steps. If this fails for $`y`$ then $`P_n(pxy)0`$.

(ii) Otherwise a preliminary “1” is written to $`C_0`$ and then $`P_n`$ proceeds to check if $`WFP(𝒜)`$ contains the true $`\nu _x`$. As before we dispose of the part of the model containing all sets of $`(L[x]`$-rank$`)^𝒜(\nu ^x)^𝒜`$. The process then proceeds to check for the wellfoundedness of this new initial segment model $`\overline{𝒜}`$ up to $`On^{\overline{𝒜}}(\nu _x)^𝒜`$. We use that  (Theorem 8.8) shows $`\nu _x`$ is not an $`x`$-admissible ordinal.

If the model is wellfounded then this process takes the true $`\nu _x`$ many steps, thus it can halt exactly at the $`\nu _x`$’th step with the required $`1`$ in $`C_0`$.

Arguing as before using the cited inadmissibility of $`L_{\nu _x}[x]`$, the wellfounded part of $`𝒜`$ cannot have rank exactly the true $`\nu _x`$; hence we are justified in testing only the initial segment of the ordinals of $`\overline{𝒜}`$ determined by $`(\nu _x)^𝒜`$. Then any instance of illfoundedness will be encountered strictly before $`\nu _x`$ many steps have been taken.

In each case then $`P_n(pxy)`$ halts in no more than $`\nu _x`$ many steps with the correct output.

As a final comment some of the above discussion may lead one to considering the class of sets $`A`$ such that $`xA`$ and $`xA`$ can each be verified quickly, that is, such that there are two programs, such that $`xA`$ if and only if there is a witness $`y`$ such that $`xy`$ is accepted by the first program, and $`xA`$ if and only if there is a witness $`y`$ such that $`xy`$ is accepted by the second program, and both programs halt on any input $`xy`$ in time before $`f(x)`$ if they halt at all. That is, both $`xA`$ and $`xA`$ can be verified quickly, with the correct choice of verifying witnesses, but there is no insistence that the programs compute quickly (or even halt at all) when given irrelevant witnesses verifying nothing. B. Löwe has pointed out that such a class of sets corresponds to a notion of $`NPTIME^fco`$-$`NPTIME^f`$, but we have made no investigation of such concepts.