% -*- Mode:Text -*-
%N. Margolus and L. Levitin
%The maximum speed of dynamical evolution
\def\mail{margolus nhm@mit.edu }

\documentstyle{elsart}
\begin{document}

\newcommand{\eqlabel}[1]{\label{eq.#1}}
\newcommand{\eq}[1]{(\ref{eq.#1})}	% Ref. to equation

\newcommand{\bra}[1]{\mbox{$\left\langle #1 \right|$}}
\newcommand{\ket}[1]{\mbox{$\left| #1 \right\rangle$}}
\newcommand{\braket}[2]{\mbox{$\left\langle #1 | #2 \right\rangle$}}
\newcommand{\av}[1]{\mbox{$\left| #1 \right|$}}
\newcommand{\ve}{\varepsilon}
\newcommand{\osc}{{\mbox{\rm \scriptsize osc}}}
\newcommand{\tot}{{\mbox{\rm \scriptsize tot}}}
\newcommand{\ground}{{\mbox{\rm \scriptsize ground}}}
\renewcommand{\max}{{\mbox{\rm \scriptsize max}}}
\renewcommand{\min}{{\mbox{\rm \scriptsize min}}}

\begin{frontmatter}
 \title{The maximum speed of dynamical evolution}

 \author{Norman Margolus\thanksref{nsf-darpa}}
 \address{Boston University Center for Computational
 Science\\ and MIT Artificial Intelligence Laboratory}

 \author{Lev B. Levitin}
 \address{Boston University Department of
                Electrical and Computer Engineering}
 \thanks[nsf-darpa]{Supported by NSF grant DMS-9596217 and
 by DARPA contract DABT63-95-C-0130}

%\date{17 October 1997}

\journal{Physica D}
\volume{120}
\pubyear{1998}
\firstpage{188}
\lastpage{195}

 \begin{abstract}
 We discuss the problem of counting the maximum number of distinct
states that an isolated physical system can pass through in a given
period of time---its {\em maximum speed of dynamical evolution}.
Previous analyses have given bounds in terms of $\Delta E$, the
standard deviation of the energy of the system; here we give a strict
bound that depends only on $E-E_0$, the system's average energy minus
its ground state energy.  We also discuss bounds on information
processing rates implied by our bound on the speed of dynamical
evolution.  For example, adding one Joule of energy to a given
computer can never increase its processing rate by more than about
$3\times 10^{33}$ operations per second.
 \end{abstract}
 \end{frontmatter}

\section{Introduction}\label{intro}

In the realm of computation, the first two quantitative questions that
one is likely to ask about a machine are {\em (i) How much memory does
it have?} and {\em (ii) How fast does it run?}  In exploring the
computational limits of physical dynamics, one might try to ask the
same questions about an arbitrary physical system.

Question {\em (i)} essentially asks, ``How many distinct states can my
system be put into, subject to whatever physical constraints I have?''
This is really a very old question: the correct counting of physical
states is the problem that led to the introduction of Planck's
constant into physics\cite{planck}, and is the basis of all of quantum
statistical mechanics.  This question can be answered by a detailed
quantum mechanical counting of distinct (mutually orthogonal) states.
It can also be well approximated in the macroscopic
limit\cite{huang,wang} by simply computing the volume of phase space
accessible to the system, in units where Planck's constant is 1.

\smallskip

Question {\em (ii)} will be the focus of this paper.  This question
can be asked with various levels of sophistication.  Here we will
discuss a particularly simple measure of speed: the maximum number of
distinct states that the system can pass through, per unit of time.
For a classical computer, this would correspond to the maximum
number of operations per second.

For a quantum system, the notion of distinct states is well defined:
two states are distinct if they are orthogonal.  The connection
between orthogonality and rate of information processing has
previously been
discussed\cite{levitin,benioff,feynman,marg86,marg89,biafore}, but no
universal bound on computation rate was proposed.  The minimum time
needed for a quantum system to pass from one orthogonal state to
another has also previously been characterized, in terms of the
standard deviation of the energy $\Delta
E$\cite{mandelstam,peres,vaidman,pfeifer,braunstein}.  This bound
places no limit, however, on how fast a system with bounded average
energy can evolve (since $\Delta E$ can be arbitrarily large with
fixed $E$).  Bounds based directly on the average energy $E$ have
previously been proposed\cite{bremermann,bekenstein}, but these bounds
apply to the rate of communication of bits, rather than to the rate of
orthogonal evolution: difficulties associated with such bit-related
bounds are discussed in \cite{levitin}.  The new bounds derived in
this paper are also based on average energy, but they apply to rates
of orthogonal evolution.  For an ordinary macroscopic system, these
bounds are achievable: we show that adding energy increases the
maximum rate at which such a system can pass through a sequence of
mutually orthogonal states by a proportionate amount.

There has recently been much interest in the possibilities of {\em
quantum computers}: computers that can operate on superpositions of
computational states\cite{steane}.  Even isolated quantum computers
will, in general, pass through sequences of (nearly) mutually
orthogonal states in the course of their complicated time evolutions.
At the least, an efficient quantum computation should, for some
initial states, have a final state that is reasonably distinct from
its initial state.  Thus a bound on the rate of orthogonal evolution
is relevant in this case as well.


% may want to remove this from PhysComp submission:
\clearpage

\section{Maximum rate of dynamics}\label{speed}

In the energy basis, quantum time evolutions are constructed out of
superpositions of frequency components.  One might expect from this
that, given a maximum energy eigenvalue, the frequency with
which states can change should be bounded by
 \begin{equation}\eqlabel{maxbound}
\nu_\perp \leq {E_\max \over h}
\end{equation}
 If we take our zero of energy at the ground state of the
system,\footnote{In all of this discussion, if for some reason no
energies below some $E_\min$ are allowed, we should take our zero of
energy there instead.} and consider long evolutions, then this
relation is true, as we will discuss below.  We will also show that,
given a fixed average energy $E$ (rather than a fixed maximum), there
is a similar bound
 \begin{equation}\eqlabel{longbound}
\nu_\perp \leq {2 E \over h},
\end{equation}
 where again we have taken our zero of energy at the ground state.
This equation has the following interpretation: in appropriate units,
the average energy of a macroscopic system is equal to the maximum
number of orthogonal states that the system can pass through per unit
of time.  This is the maximum rate that can be sustained for a long
evolution---the rate at which a system can oscillate between two
states is twice as great.


\subsection{Orthogonality time}\label{orthtime}

We begin our analysis by discussing the question of the minimum time
needed for {\em any} state of a given physical system to evolve into
an orthogonal state.

An arbitrary quantum state can be written as a superposition of energy
eigenstates
 \begin{equation}\eqlabel{super}
\ket{\psi_0} = \sum_n c_n \ket{E_n}
\end{equation}
 Here and throughout this paper we assume that our system has a
discrete spectrum, and that the states have been numbered so that the 
energy eigenvalues $\{E_n\}$ associated with the states
$\{\ket{E_n}\}$ are non-decreasing.  To simplify formulas, we will
choose our zero of energy so that $E_0=0$.

 Let $\tau_\perp$ be the time it takes for \ket{\psi_0} to evolve into
an orthogonal state.  We will now show that, with a fixed average
energy $E$, it is always true that 
 \begin{equation}\eqlabel{tauperp0}
\tau_\perp \geq {h \over 4 E}.
\end{equation}
  This result is somewhat surprising, since earlier results gave a
bound only in terms of $\Delta E$
 \begin{equation}\eqlabel{tauperpge}
\tau_\perp \geq {h \over 4 \Delta E}
\end{equation}
 This earlier bound would suggest that, given a fixed average energy,
one could construct a state with a very large $\Delta E$ in order to
achieve an arbitrarily short $\tau_\perp$.  We will show that this is
not the case.

\medskip
Let us begin by observing that
if \ket{\psi_0} is evolved for a time $t$ it becomes
 \begin{equation}\eqlabel{super1}
\ket{\psi_t} = \sum_n c_n e^{-i{E_n t \over \hbar}}\ket{E_n}
\end{equation}
Now we let
 \begin{equation}\eqlabel{orthog}
S(t) = \braket{\psi_0}{\psi_t} = \sum_{n=0}^\infty \av{c_n}^2 e^{-i{E_n t \over \hbar}} 
\end{equation}
 We want to find the smallest value of $t$ such that $S(t)$=0.  To do
this, we note that
 \newcommand{\eth}{{E_n t \over \hbar}}
\newcommand{\re}{\mbox{\rm Re}}
\newcommand{\im}{\mbox{\rm Im}}
 \begin{eqnarray}\eqlabel{reim}
\re(S) & = & \sum_{n=0}^\infty \av{c_n}^2 \cos(\eth) \nonumber\\
& \geq &
\sum_{n=0}^\infty \av{c_n}^2
\left( 1 - {2 \over \pi}(\eth + \sin(\eth))\right) \nonumber\\
& = & 1 - {2 E \over \pi \hbar}t + {2\over\pi}\im(S),
\end{eqnarray}
 where we have used the inequality $\cos x \geq 1 -
{2\over\pi}(x+\sin x)$, valid for $x\geq 0$.  But for any
value of $t$ for which $S(t)=0$, both $\re(S)=0$ and
$\im(S)=0$, and so Eq.~\eq{reim} becomes
 \begin{equation}
0 \geq 1- {4Et\over h}
\end{equation}
 Thus the earliest that $S(t)$ can possibly equal zero is when
$t=h/4E$, which proves Eq.~\eq{tauperp0}.  Of course Eq.~\eq{reim}
also gives approximately the same bound on how quickly we can have
approximate orthogonality, since if $\av{S(t)}$ is small, then so are
$\re(S)$ and $\im(S)$.


% Of course the same argument applies to approximate orthogonality.

\smallskip

This bound is achievable if the spectrum of energies includes the
energy $2E$ (and is very nearly achievable if the spectrum includes a
value very close to this, as we would expect, for example, for any
ordinary macroscopic system).  In this case, we let
 \begin{equation}\eqlabel{fastest0}
\ket{\psi_0} = {\ket{0} + \ket{2E} \over \sqrt{2}}
\end{equation}
 which has average energy $E$.  This evolves in a time $t=h/4 E$ into
 \begin{equation}\eqlabel{fastest1}
\ket{\psi_t} = {\ket{0} - \ket{2E} \over \sqrt{2}}
\end{equation}
 which is orthogonal to \ket{\psi_0}.  If we evolve for the same
interval again, we will be back to \ket{\psi_0}: the evolution
oscillates between these two orthogonal states.  For these states,
$\Delta E = E$, and so both of the bounds Eq.~\eq{tauperp0} and
Eq.~\eq{tauperpge} are achieved.

There are also cases where Eq.~\eq{tauperp0} gives a much better bound
than Eq.~\eq{tauperpge}.  Consider, for example, the state
 \begin{equation}\eqlabel{bigdelta0}
\ket{\psi_0} \quad = \quad a\left(\ket{0} + \ket{\varepsilon}\right)
             \quad + \quad
               b\left(\ket{n\varepsilon} + \ket{(n+1)\varepsilon}\right)
\end{equation}
 which evolves into an orthogonal state in a time $\tau_\perp=h/2
\varepsilon$.  Given $E$, as long as we choose $\varepsilon < 2E$
(i.e., $\tau_\perp > h/4E$) the average energy of the first pair of
kets will be less than $E$.  Given $\varepsilon$, for large enough $n$
the average energy of the second pair of kets will be greater than
$E$.  Then we can always find coefficients $a$ and $b$ that make the
average energy of $\ket{\psi_0}$ be $E$ and also normalize the state.
But this state has a $\Delta E$ that depends on our choice of $n$: in
fact $\Delta E = \Theta(\sqrt{n})$.  With fixed $E$, $\Delta E$ can be
as large as we like.  Thus in this case, Eq.~\eq{tauperpge} is not a
useful bound and Eq.~\eq{tauperp0} is optimal.


\subsection{Cycles of orthogonal states}\label{cycles}

In the discussion above, we have seen that a quantum system with
average energy $E$ can be made to oscillate between two orthogonal
states with a frequency of $4E/h$.  Now we address the question of how
fast a quantum system can run through a long sequence of mutually
orthogonal states.  We begin by considering the very restricted set of
evolutions that pass through an exact cycle of $N$ mutually orthogonal
states at a constant rate.  In this case it is easy to show (see
Appendix~\ref{exact.orthog}) that
 \begin{equation}\eqlabel{tauofm}
 \tau_\perp\geq{N-1 \over N} {h \over 2E}
\end{equation}
 Thus for very long evolutions that form a closed cycle, the maximum
transition rate between orthogonal states is only half as great as it
is for an oscillation between two states.  In the next section, we
will show that this long-sequence asymptotic rate is achievable in
principle for any ordinary macroscopic system.  Here we will first
give an example of a system for which an {\em exact} cycle of $N$
mutually orthogonal states ({\em cf.} \cite{peg}) achieves this bound.

The one-dimensional harmonic oscillator has an exact cycle after some
period $\tau$.  Taking our ground-state energy to be zero, all of the
energy eigenvalues are multiples of $\varepsilon_1=h/\tau$.  Let
 \begin{equation}\eqlabel{psimax}
\ket{\psi_0} = \sum_{n=0}^{N-1} {1\over \sqrt{N}} \ket{n \varepsilon_1}
\end{equation}
 If our system passes through $N$ mutually orthogonal states in time
$\tau$, then the average time to pass between consecutive orthogonal
states is $\tau_\perp=\tau/N$.  Noting that
$\varepsilon_1\tau_\perp/\hbar=2\pi / N$, we see that the state
obtained from $\ket{\psi_0}$ after $m$ time intervals of length
$\tau_\perp$ is
 \begin{equation}
\ket{\psi_m}=\sum_{n=0}^{N-1}  {1\over \sqrt{N}} e^{-{2\pi i n m \over N}}
\ket{n\varepsilon_1}
\end{equation}
 and so
 \begin{equation}
\braket{\psi_{m'}}{\psi_m}
= \sum_{n=0}^{N-1} {1\over N} e^{{2\pi i n \over N} (m'-m)} = \delta_{m'm}
\end{equation}
  Now we can calculate the relationship between $E$ and $\tau_\perp$.
 \begin{equation}\eqlabel{e.sho}
 \bra{\psi_0}H\ket{\psi_0}
    = \varepsilon_1 \sum_{n=0}^{N-1} {n\over N}
    = \varepsilon_1 \left({N-1 \over 2}\right)
    = \left({h \over N\tau_\perp}\right) \left({N-1 \over 2}\right)
\end{equation}
  and so
 \begin{equation}
 \tau_\perp = {N-1 \over N} {h \over 2E}
\end{equation}


\subsection{Long sequences of orthogonal states}\label{longseq}

Now we turn to the question of whether ordinary macroscopic physical
systems can also run through long sequences of mutually orthogonal
states with $\tau_\perp=h/2E$.  We will show by construction that they
can.  As in the discussion above, we will not need to use arbitrarily
large eigenvalues to achieve this rate, and so our state can be
written
 \begin{equation}\eqlabel{psigen}
\ket{\psi_0} = \sum_{n=0}^{N-1} c_n \ket{E_n}
\end{equation}
 Now we simply let
 \begin{equation} c_n = \sqrt{E_{n+1} - E_n \over E_N}.
\end{equation}
 This definition of $c_n$ generalizes our example from the previous
section: for the special case of $E_n=n\ve_1$, Eq.~\eq{psigen} reduces
to Eq.~\eq{psimax}, which achieves $\tau_\perp=h/2E$ in the
macroscopic limit.  Notice also that, with this definition of $c_n$,
states with degenerate energy eigenvalues are not repeated in our
superposition (they get a coefficient of zero, since the $E_n$'s are
numbered in non-decreasing order).  This definition of $c_n$ always
gives normalized states, since
 \begin{equation}\eqlabel{norm}
\braket{\psi_0}{\psi_0} = \sum_{n=0}^{N-1} {E_{n+1}-E_n \over E_N} = 1
\end{equation}
 We can calculate the average energy in the state \ket{\psi_0}.  This is just
\begin{equation}\eqlabel{avge}
\bra{\psi_0}H\ket{\psi_0} = \sum_{n,n'}
c^*_{n'}c_n E_n\braket{E_{n'}}{E_n} %\nonumber\\
= \sum_{n=0}^{N-1}
{E_{n+1}-E_n \over E_N} E_n
\end{equation}
 For $N\gg 1$ and $c_n \ll 1$, we can approximate this sum by an integral.
Letting $x=n/N$ and $\ve(x) = E_n/E_N$, we have
 \begin{equation}\eqlabel{longav}
\bra{\psi_0}H\ket{\psi_0} \approx E_N \int_0^1
\ve {d\ve \over dx} dx %\nonumber\\
= {E_N \over 2} \int_0^1 {d \over dx} \ve^2 dx %\nonumber\\
= {E_N \over 2}
\end{equation}
 In Appendix~\ref{integrals} we estimate the corrections to this
approximation, which vanish for large $N$.  Thus, with this definition
of $c_n$, by giving equal weight to equal energy intervals we get an
average energy that is half of the maximum energy, just as in the
limiting case considered in Eq.~\eq{e.sho}.


 Now the state obtained from \ket{\psi_0} after $m$ intervals of
length $\tau_\perp=h/2E=h/E_N$ is
 \begin{equation}
\ket{\psi_m} = \sum_n c_n e^{-2\pi i m {E_n \over E_N}}\ket{E_n}
\end{equation}
 and so
 \begin{eqnarray}\eqlabel{m'm}
\braket{\psi_{m'}}{\psi_m}
& = &
\sum_{n,n'} c^*_{n'}c_n e^{2\pi i{1 \over E_N}(m' E_{n'}-m E_n)}
\braket{E_{n'}}{E_n} \nonumber\\
& = & \sum_{n=0}^{N-1}
{E_{n+1}-E_n \over E_N} e^{2\pi i{E_n \over E_N}(m'-m)}
\end{eqnarray}
 As we've seen, this is equal to 1 if $m'=m$.  Let $k= m'-m \ne 0$, and
again let $x=n/N$ and $\ve(x) = E_n/E_N$.  Then
 \begin{equation}\eqlabel{m'm0}
\braket{\psi_{m'}}{\psi_m}
\approx
\int_0^1 {d\ve \over dx} e^{2\pi i k\ve} dx %\nonumber\\
=
\int_0^1 {{d \over dx} e^{2\pi i k\ve} \over 2\pi i k} dx %\nonumber\\
= 0
\end{equation}
 A more careful analysis (see Appendix~\ref{integrals}) verifies that
the corrections to this approximate calculation vanish for large $N$.
Thus we can run through a long sequence of nearly orthogonal states at
the rate $\nu_\perp=2E/h=E_\max/h$.


\section{Interpretation}

% adding  energy to a system adds computing power!!!!!

For an isolated macroscopic system $s$ with average energy $E^{(s)}$,
we have seen that we can construct a state that evolves at a rate
$\nu_\perp^{(s)}=2E^{(s)}/h$.  If we had many non-interacting
macroscopic subsystems, we would have an average energy for the
combined system of $E_\tot=\sum_s E^{(s)}$.  Our construction of the
previous section applies prefectly well to such a composite system,
and in particular lets us construct a state for this combination of
non-interacting subsystems that evolves at a rate of $\nu_\perp =
2E_\tot/h = \sum_s 2E^{(s)}/h = \sum_s \nu_\perp^{(s)}$.  Thus if we
subdivide our total energy between separate subsystems, the maximum
number of orthogonal states per unit time for the combined system is
just the sum of the maximum number for each subsystem taken
separately.  This is analogous to the case in a parallel computer,
where the total number of operations per second for the whole machine
is just the sum of the number of operations per second performed by
the various pieces.  Our result should be interpreted in a similar
manner: average energy tells us the maximum possible rate at which
distinct changes can occur in our system.

It is interesting to ask how this connection between energy and
maximum possible number of changes looks in a semi-classical limit.
As a simple example, let us consider a single-speed lattice
gas\cite{fhp}.  This is a classical gas model in which identical
particles are distributed on a regular lattice.  Each particle
moves from one lattice site to an adjacent site in time $\delta T$.
At the end of each $\delta T$ interval, all energy is kinetic, and all
particles have the same energy $\delta E$.  Thus if the total energy
is $E$, then $E/\delta E$ is equal to the number of particles, and so
the maximum number of spots that can change per unit of time is equal
to $2E/\delta E$: $E/\delta E$ spots can be vacated, and $E/\delta E$
new spots occupied.  Fewer spots will change if some particles move to
spots that were previously occupied, but we can never have more than
$2E/\delta E$ changes in time $\delta T$.  Thus if we impose the
constraint on this lattice system that $\delta E \delta T \ge h$, our
bound on the rate at which spots can change becomes
$\nu_{\mbox{\rm\scriptsize change}} \le 2E/\delta E \delta T \le
2E/h$.

It is also interesting to ask how this connection between energy and
orthogonal evolution looks in different inertial reference frames.
Clearly we will see some orthogonal states that are purely an artifact
of our choice of reference frame.  For example, an isolated stationary
atom in an exact energy eigenstate never transitions to an orthogonal
state, but if we view this same atom from a moving frame we will see a
sequence of distinct position states.  If we are interested in a bound
on ``useful'' dynamics (e.g., on computation), then we shouldn't count
extra states that arise just from the state of motion of the observer.
The obvious solution is to define the amount of ``useful'' dynamics to
be the number of orthogonal states that the system passes through in
its rest frame (center of momentum frame).  As long as our
non-relativistic analysis is valid in the rest frame, we can infer
that (in that frame) a system with total relativistic energy $E_r$
cannot pass through more than $2 E_r t_r /h$ different orthogonal
states in time $t_r$.  Then in any frame, we can compute this bound on
``useful'' evolution, since $E_r t_r = p_\mu x^\mu$.  In a frame in
which the system starts at the origin at time $t=0$ and moves in the
positive $x$ direction with a momentum of magnitude $p$, our bound is
$(2/h) (Et - px)$: from the time component of the bound we subtract a
space component.  Note that we subtract one orthogonal state for each
shift of a distance $h/2p$ ({\em cf.}  \cite{braunstein,yu}).


\section{Conclusion}

The average energy $E$ (above the ground state) of an isolated
physical system tells us directly the maximum number of mutually
orthogonal states that the system can pass through per unit of time.
Thus if the system is a computer, this quantity is a simple physical
measure of its maximum possible {\em processing rate}.

Equivalently we can say that $Et$ counts orthogonal states in time.
Just as accessible phase-space volume tells us the number of distinct
states that a macroscopic physical system can be put into, $Et$
``action volume'' tells us the number of distinct states that a system
with energy $E$ can pass through in time $t$.


\section*{Acknowledgments}

Margolus would like to thank Ed Fredkin, who first made him aware of
the question, ``How can we physically quantify computation.''  He and
Tom Toffoli have encouraged Margolus and inspired him in his studies
of the mechanics of information in physics.  Margolus would also like
to thank Mark Smith, Sandu Popescu, Tom Knight and Gerry Sussman for
useful comments and discussions.

Both authors would like to thank Elsag-Bailey and the
I.S.I. Foundation for the opportunity to work together on this
research at their 1996 Quantum Computing Workshop in Turin, Italy.

\appendix

\section{Minimum orthogonality time for exact cycles}\label{exact.orthog}

If we demand that the evolution should {\em exactly} cycle after $N$
steps, this condition puts a severe restriction on the energy
eigenfunctions that can contribute to our initial state.  If
$\ket{E_j}$ contributes to $\ket{\psi_0}$, and if our cycle length is
$\tau$, then we must have that $E_j \tau /\hbar = 2 \pi k_j$ for some
integer $k_j$, which means that $E_j = k_j \varepsilon_1$, where
$\varepsilon_1=h/\tau$.  Thus our initial state must have the form
 \begin{equation}
\ket{\psi_0} = \sum_{n=0}^{\infty} c_n \ket{n \varepsilon_1}
\end{equation}
 For simplicity, we have not included degenerate energy eigenfunctions
in our superposition---adding these would not affect our conclusions.
Thus the assumption of exact periodicity restricts us to systems with
energy eigenvalues that are a subset of a one dimensional harmonic
oscillator spectrum, in which all energies are multiples of $h/\tau$.

As in Section~\ref{cycles}, we see that the state obtained from
$\ket{\psi_0}$ after $m$ time intervals of length $\tau_\perp=\tau/N$
is
 \begin{equation}
\ket{\psi_m}=\sum_{n=0}^{\infty} c_n e^{-{2\pi i n m \over N}}
\ket{n\varepsilon_1}
\end{equation}
 and so
 \begin{equation}
\braket{\psi_{m'}}{\psi_m}
= \sum_{n=0}^{\infty} \av{c_n}^2 e^{{2\pi i n \over N} (m'-m)}
\end{equation}
 There are actually only $N$ distinct values of the exponential that
appears in this sum, since for any integer $l$, $e^{{2\pi i (n +lN)
\over N} (m'-m)} = e^{{2\pi i n \over N} (m'-m)}$.  We can collect
together all $c_n$'s that multiply each distinct value: let
$\av{d_n}^2=\sum_{l=0}^\infty \av{c_{n+lN}}^2$.  Then
 \begin{equation}\eqlabel{d.orthog}
\braket{\psi_{m'}}{\psi_m}
= \sum_{n=0}^{N-1} \av{d_n}^2 e^{{2\pi i n \over N} (m'-m)} %\nonumber\\
= \delta_{m'm}
\end{equation}
 since these states are supposed to be orthogonal.  This last equality
will obviously be true if we let $\av{d_n}^2=1/N$ for all $n$'s.  In
fact, since there are $N$ different possible values of $m'-m$,
Eq.~\eq{d.orthog} constitutes $N$ linearly independent equations with
$N$ unknown coefficients, and so this solution is unique.  Thus by
picking any set of $\av{c_n}^2$'s that add up to make all the
$\av{d_n}^2$'s equal to $1/N$, we obtain a state $\ket{\psi_0}$ that
evolves at a constant rate through a sequence of $N$ mutually
orthogonal states in time $\tau$.

Now we can calculate the relationship between the average energy and
the orthogonality time.
 \begin{equation}
E=\varepsilon_1 \sum_{n=0}^\infty \av{c_n}^2 n
= \varepsilon_1 \sum_{n=0}^{N-1} \sum_{l=0}^\infty \av{c_{n+lN}}^2 (n + lN)
\end{equation}
 but $\sum_{l=0}^\infty \av{c_{n+lN}}^2 (n + lN)\geq
\sum_{l=0}^\infty \av{c_{n+lN}}^2 n = n\av{d_n}^2$, and since
$\av{d_n}^2=1/N$, 
 \begin{equation}\eqlabel{e.tau}
E \geq \varepsilon_1 \sum_{n=0}^{N-1} {n \over N} =
\varepsilon_1 \left({N-1 \over 2}\right)
\end{equation}
 Since $\varepsilon_1 = h/\tau = h/ N\tau_\perp$, this establishes
Eq.~\eq{tauofm}.  Note that we get equality in Eq.~\eq{tauofm} only
for the state given in Eq.~\eq{psimax}.

 We can also argue that if we don't use energy eigenvalues larger than
$E_\max = \varepsilon_1 (N-1)$, then there are at most $N$ eigenstates
in our superposition, and so we can pass through at most $N$ different
orthogonal states in time $\tau$.  Thus
 \begin{equation}\eqlabel{e.extra}
\tau_\perp \geq {\tau \over N} = {h \over \varepsilon_1 N} =
\left({h \over E_\max}\right) \left({N-1 \over N}\right)
\end{equation}
 which yields Eq.~\eq{maxbound} for a long exact cycle.


\section{Approximating sums}\label{integrals}

Here we estimate the corrections to the average energy and scalar
product computed in Section~\ref{longseq}.

Letting $\ve_n={E_n/E_N}$ and $\delta_n=\ve_{n+1}-\ve_n$,
Eq.~\eq{avge} becomes
 \begin{eqnarray}\eqlabel{avge2}
\bra{\psi_0}H\ket{\psi_0}& = & E_N \sum_{n=0}^{N-1}
(\ve_{n+1}-\ve_n) \ve_n \nonumber\\
& = &
{E_N\over2} \sum_{n=0}^{N-1} \left[
(\ve_{n+1}^2 - \ve_n^2) - (\ve_{n+1}-\ve_n)^2 \right]  \nonumber\\
& = &
{E_N\over2} \left[1 - \sum_{n=0}^{N-1} 
\delta_n^2 \right]  \nonumber\\
\end{eqnarray}
 Now, for any ordinary macroscopic system, from general properties of
the density of states\cite{reif} we know that for large $n$, $E_n \sim
n^c$, where $c$ is a positive constant much less that one.  From this
we can show that $\sum \delta_n^2 = O(1/N^{2c})$.

Similarly, letting $\alpha=2\pi (m'-m)=2\pi k$, Eq.~\eq{m'm} becomes
 \begin{eqnarray}\eqlabel{orthodev}
\braket{\psi_{m'}}{\psi_m}
& = &
\sum_{n=0}^{N-1}
\delta_n e^{i\alpha \ve_n} \nonumber\\
& = &
{1\over i\alpha}\sum_{n=0}^{N-1}e^{i\alpha \ve_n}\left[
(e^{i\alpha \delta_n}-1)
- \sum_{j=2}^\infty {(i\alpha\delta_n)^j \over j!}
\right] \nonumber\\
& = &
-{1\over i\alpha}\sum_{n=0}^{N-1}
 \sum_{j=2}^\infty e^{i\alpha \ve_n}{(i\alpha\delta_n)^j \over j!}
\end{eqnarray}
 Again making the assumption that $E_n \sim n^c$ for large $n$, we can
show that the magnitude of this sum is $O(k/N^{2c})$.


\begin{thebibliography}{99}

        \bibitem{aharonov} J. Anandan and Y. Aharonov,
Geometry of quantum evolution, {\em Phys.\ Rev.\ Lett.\ \bf 65}
(1990), 1697--1700.
        \bibitem{benioff} P. A. Benioff, Quantum mechanical
Hamiltonian models of discrete processes that erase their own
histories: application to Turing machines, {\em Int.\ J.\ Theor.\
Physics \bf 21} (1982), 177--202.
        \bibitem{bekenstein} J. D. Bekenstein, Entropy content and
information flow in systems with limited energy, {\em Phys.\ Rev.\
D. \bf 30} (1984), 1669--1679.
        \bibitem{biafore} M. Biafore, {\em Few-body cellular
automata,} MIT Ph.D. Thesis (1993), available as MIT/LCS/TR-597 (MIT
Laboratory for Computer Science, 1993).
        \bibitem{braunstein} S. Braunstein, C. Caves and G. Milburn,
Generalized uncertainty relations: theory, examples, and Lorentz
invariance, {\em Ann.\ Phys.} {\bf 247} (1996), 135--173.
        \bibitem{bremermann} H. J. Bremermann, Quantum noise and
information, in: {\em Proceedings of the 5th Berkeley Symposium on
Mathematical Statistics and Information,} (University of California
Press, Berkeley, Vol.\ 4, 1967), 15--22.
        \bibitem{feynman} R. P. Feynman, Quantum mechanical
computers, {\em Opt. News} {\bf 11} (1985).
        \bibitem{fhp} U. Frisch, B. Hasslacher, and
Y. Pomeau, Lattice-gas automata for the Navier-Stokes
equation, {\em Phys.\ Rev.\ Lett.} {\bf 56} (1986), 1505--1508.
        \bibitem{huang} K. Huang, {\em Statistical Mechanics,} (Wiley
1963).
        \bibitem{mandelstam} L. Mandelstam and I. Tamm, The
uncertainty relation between energy and time in nonrelativistic
quantum mechanics, {\em J. Phys. (USSR) \bf 9}, (1945), 249--254.
        \bibitem{planck} M. Planck, {\em The Theory of Heat Radiation}
(Dover, New York, 1991).  Translated from {\em Vorlesungen \"uber die
Theorie der W\"armestrahlung} (Blakiston, 1914).
        \bibitem{levitin} L. B. Levitin, Physical limitations of
rate, depth, and minimum energy in information processing, {\em
Int.\ J.\ Theor.\ Phys.} {\bf 21} (1982), 299--309.
        \bibitem{marg86} N. Margolus, Quantum computation, in: Daniel
Greenberger ed., {\em New Techniques and Ideas in Quantum Measurement
Theory} (New York Academy of Sciences 1986), 487--497.
        \bibitem{marg89} N. Margolus, Parallel quantum computation, in:
Wojciech Zurek ed., {\em Complexity, Entropy, and the Physics of
Information} (Addison-Wesley, 1990).
	\bibitem{peg} D. T. Pegg and S. M. Barnett, Quantum optical
phase, {\em J.\ Mod.\ Opt.\ \bf 44} (1997), 225--264.
        \bibitem{peres} A. Peres, {\em Quantum Theory: Concepts and
Methods}, (Kluwer Academic Publishers, Hingham, MA, 1995).
	\bibitem{pfeifer} P. Pfeifer, How fast can a quantum state
change with time? {\em Phys.\ Rev.\ Lett.\ \bf 70} (1993),
3365--3368.
        \bibitem{reif} F. Reif, {\em Fundamentals of Statistical
and Thermal Physics}, (McGraw-Hill Series in Fundamentals of Physics, 1965).
        \bibitem{steane} A. Steane, Quantum computing, {\em Reports on
Progress in Physics} (1997, to appear).  Preprint available as {\tt quant-ph/9708022}.
        \bibitem{vaidman} L. Vaidman, Minimum time for the
evolution to an orthogonal quantum state, {\em Am.\ J. Phys.\ \bf
60} (1992), 182--183; L. Vaidman and O. Belkind, Strict bounds on
Franson inequality, preprint {\tt quant-ph/9707060}.
        \bibitem{wang} L. Wang, On the classical limit of phase-space
formulation of quantum mechanics: entropy, {\em J. Math.\ Phys.\ \bf
27} (1986), 483--487.
        \bibitem{yu} T. Yu, A note on the uncertainty relation between
the position and momentum, {\em Phys.\ Lett. A \bf 223} (1996), 9--11.

  \end{thebibliography}


\end{document}

