\documentstyle{article}
\textheight 19.3 true cm
\textwidth 12.2 true cm

\begin{document}
\title{{Halting probability amplitude of quantum computers}\thanks{The
quantum omega was invented in a meeting of G. Chaitin,
A. Zeilinger and the author (K. S.) in a Viennese coffee house
(Caf\'{e} Br\"aunerhof) in January 1991.
Thus, the group should be credited for the original invention,
whereas any blame should remain with the author.}
}
\author{ K. Svozil\\
Institute for Theoretical Physics, Technische Univers\"at Wien,\\
 Wiedner Hauptstra\ss e 8--10/136, A-1040 Vienna, Austria\\
e-mail:svozil@tph.tuwien.ac.at
}

\maketitle

\begin{abstract}
The classical halting
probability
$\Omega$ introduced by Chaitin is generalized to quantum
computations.
 \end{abstract}
\begin{flushright}
{\scriptsize omega.tex}
\end{flushright}

Chaitin's $\Omega$ \cite{chaitin,solovay,calude} is a magic
number.
It is a measure for arbitrary programs to take a finite number of
execution steps and
then halt.
It contains the solution of all halting problems, and hence of
questions codable into halting problems, such as Fermat's theorem.
It contains the solution of the question of whether or not a particular
exponential Diophantine equation
has infinitely many or a finite number of solutions.
And, since $\Omega$ is provable ``algorithmically incompressible,'' it
is Martin-L\"of/Chaitin/Solovay random. Therefore, $\Omega$ is both: a
mathematicians ``fair coin,''  and a formalist's nightmare.

Here, $\Omega$ is generalized to quantum computations.

 Consider a (not necessarily universal) quantum computer $C$ and its
$i$th
 program $p_i$,
 which, at time $t\in {\bf Z}$, can be described by a quantum state
\cite{a:8,be,deutsch-85,f-85,peres-85,b-86,m-86,deutsch:89,deutsch:92})
\begin{equation}
\vert C(t, p_i)\rangle
\quad .
\label{e:om1}
\end{equation}
A typical realisation of $C$ would be by an array of
generalized four-port beam splitters \cite{zeilinger}.

In what follows we shall assume that the program $p_i$ is
coded {\em classically.} That is, we choose a finite code alphabet $A$
and denote by $A^\ast$ the set of all strings over $A$.
Any program $p_i$ is coded as a classical sequence
$\#(p_i)=s_{1i}s_{2i}\cdots s_{ni}\in A^\ast $, $s_{ji}\in A$.
(In what follows, $\# (p_i)$ will be abbreviated by $p_i$.)
We assume prefix coding
\cite{hamming,chaitin,svozil,calude}; i.e., the domain of $C$ is
prefix-free such that no admissible program is the prefix of another
admissible program.
Furthermore, without loss of generality, we consider only empty input
strings.

In quantum information theory, the state
$\vert C(t, p_i)\rangle $
of the computer $C$ with
program $p_i$ is
representable by quantum bits
(qbits).
Every qbit is in a coherent superposition of the classical bit basis
$\vert  {\bf 0} \rangle $ and
$\vert  {\bf 1} \rangle $.
 Assume that
 the states
(\ref{e:om1})
are  orthogonal and
 normalized.
 The computer $C$ evolves according to a unitary
operator
$U$  such that
 (discrete time evolution)
 \begin{eqnarray}
 \vert C(t,p_i) \rangle &=&U\vert C(t-1, p_i)\rangle \\
&=&U^t\vert C(0,p_i)\rangle
 \quad
 . \end{eqnarray}

More specifically,
a quantum computer can be in a coherent superposition of the
halting and the non-halting state
\cite{deutsch-85,sv:94}
 \begin{equation}
\vert a,b\rangle  =a\vert {\tt HALT}\rangle
 +b\vert {\tt GO}\rangle \quad ,\qquad \vert a\vert^2 +\vert b\vert^2=1
 \end{equation}
We shall call this quantum bit $\vert a,b\rangle$ the {\em halting bit.}
The symbols
``$\vert {\tt HALT}\rangle $''
and
``$\vert {\tt GO}\rangle $''
represent orthonormal vectors \cite{orthon}
 in the twodimensional complex
Hilbert space spanned by them.
Let the halting state $\vert e^{i\varphi },0\rangle =\vert {\tt
HALT}\rangle
$, $\varphi \in R$ be the physical realization that the computer has
``halted;''
likewise let
$\vert 0,e^{i\varphi }\rangle =\vert {\tt GO}\rangle$,
$\varphi \in R$ be the physical realization that the computer has not
``halted.''
Note that, since quantum computations are governed by unitary evolution
laws which are reversible, the halting state does not mean that the
computer does not change as time evolves. It just means that it has set
a signal --- the halting bit --- to indicated that it has finished its
task.
$a$ and $b$ are complex numbers which are a quantum mechanical measure
of the probability amplitude that the computer is in the halting and the
non-halting states, respectively.
(The corresponding probabilities are $\vert a\vert^2$
and $\vert a\vert^2$, respectively.)
One
important feature of the quantum information concept ist that it does
not
merely allow two-valued states but a coherent superposition thereof.

In the orthonormal halting basis $\{ \vert  {\tt HALT}\rangle  ,\vert
{\tt GO}\rangle
\}$,
the computer $C$ with
classical input
$p_i$ can be represented by
 \begin{equation}
 \vert C(t,p_i) \rangle   =
\vert {\tt HALT} \rangle
\langle {\tt
HALT}\vert
 C(t,p_i)\rangle
+
\vert {\tt GO} \rangle
\langle {\tt
GO}\vert
C(t,p_i)\rangle
\quad .
\label{e:kso}
 \end{equation}

In the spirit of quantum recursion theory \cite{sv:94}, assume
that initially,
i.e., at time $t=0$, the computer is prepared such that its halting bit
is in a coherent 50:50-superposition; i.e.,
in terms of the halting basis,
 \begin{equation}
 \vert C(0,p_i) \rangle   =
{1\over \sqrt{2}}\left( \vert {\tt HALT} \rangle
+
\vert {\tt GO} \rangle \right)
\label{e:kso0}
 \end{equation}
for all $p_i\in A^\ast$.
This corresponds to the fact that initially it is unknown whether or not
the computer halts on $p_i$.
When during the time evolution the  computer has completed its task,
the halting bit value is switched to $\vert {\tt
HALT}\rangle$ by some internal operation,
otherwise it
remains in the  coherent 50:50-superposition
of equation (\ref{e:kso0}).
[Alternatively, the computer could be initially prepared
in the non-halting state $\vert {\tt GO}\rangle $.
After completion of the
task, the halting bit is again
switched to
the halting state $\vert {\tt HALT}\rangle$.
In this case, the subtractions of $\langle {\tt GO}\vert
C(t,p_i) \rangle
$ in equations
(\ref{e:qo}),
(\ref{e:qop}) and
(\ref{e:qop1}) below would have to be eliminated.]



In analogy to the fully classical case \cite{chaitin,solomonoff,calude},
the quantum halting amplitude $\Omega $ can be defined
 as a weighted expectation over all computations of $C$ with classical
input
$p_i$ ($\vert p_i\vert $ stands for the length of $p_i$)
 \begin{equation}
   \Omega \equiv
\lim_{t\rightarrow
\infty }
\sum_{p_i}
2^{-\vert p_i\vert
}
\left[ \langle  {\tt HALT} \vert  C(t,p_i) \rangle
-\langle  {\tt GO} \vert  C(t,p_i) \rangle \right]
\quad .
\label{e:qo}
 \end{equation}

Likewise, for particular output states
$\vert s\rangle
$,
 \begin{equation}
  \Upsilon ( \vert s\rangle )  \equiv \lim_{t\rightarrow \infty}
\sum_{\vert C(t,p_i)\rangle =\vert s\rangle }
2^{-\vert p_i\vert
}
\left[
\langle  {\tt HALT} \vert  C(t,p_i) \rangle
-\langle  {\tt GO} \vert  C(t,p_i) \rangle \right]
\quad .
\label{e:qop}
 \end{equation}
For a set of output states
 $S=\{
\vert s_1\rangle ,
\vert s_2\rangle ,
\vert s_3\rangle ,
\ldots
,\vert s_n\rangle\}$
 which correspond to mutually orthogonal
vectors in Hilbert space,
 \begin{equation}
  \Upsilon ( S )  \equiv \lim_{t\rightarrow \infty}
\sum_{\vert C(t,p_i)\rangle \in S }
2^{-\vert p_i\vert
}
\left[ \langle  {\tt HALT} \vert  C(t,p_i) \rangle
-\langle  {\tt GO} \vert  C(t,p_i) \rangle \right]
\quad .
\label{e:qop1}
 \end{equation}

For nontrivial choices of the quantum computer $C$,
several remarks are in order.
(In what follows, we mention only $\Omega$, but the comments apply to
$\Upsilon$ as well.)

First, note that if the program is also
coded in qbits, the above sum becomes an
integral over continuously many states per code symbol of the programs.
In this case, the Kraft sum needs not converge.

Second, just as for the classical analogue it is possible to ``compute''
$\Omega $ as a limit from below
by considering
in the $t$'th computing step (time $t$) all programs of length $t$
which have already halted.
(This ``computation'' suffers
from a radius of convergence which decreases slower than any recursive
function.)

Third,
the quantum $\Omega$ is complex.
$\vert \Omega \vert^2$ can be interpreted as a measure for the halting
probability of
$C$; i.e., the probability that an arbitrary (prefix-free) program
halts on
$C$.
Both, the relative phases of approximations of $\Omega$, as well as
approximations to $\vert \Omega \vert^2$ are measurable.


Finally,
any irreversible measurement of $\vert \Omega \vert^2$
causes a state collapse.
Since $\vert  C(t,p_i)\rangle $ may not be in a
pure state, the  series in
 (\ref{e:qo}) and
 (\ref{e:qop})
will not be uniquely defined even for {\em finite} times.
The {\em nondeterministic} character of $\Omega$ is not only based
on classical recursion theoretic arguments \cite{chaitin} but
also on the physical proposition that  God plays the
quantum dice.



\begin{thebibliography}{99}



\bibitem{chaitin}
G. J. Chaitin, {\sl Information, Randomness and Incompleteness, Second
edition}
(World Scientific, Singapore, 1987, 1990);
{\sl Algorithmic Information Theory}
(Cambridge University Press, Cambridge, 1987);
{\sl Information-Theoretic Incompleteness}
(World Scientific, Singapore, 1992).

\bibitem{solovay}
R. M. Solovay, {\it unpublished manuscript}.

\bibitem{calude}
C. Calude,
{\sl Information and Randomness --- An Algorithmic Perspective}
(Springer, Berlin, 1994).

%The quantum omega was invented in a meeting of G.
%Chaitin, A. Zeilinger and the author (K. S.) in a Viennese coffee house
%(Caf\'{e} Br\"aunerhof) in January 1991.
%Thus, the group should be credited for the original invention,
%whereas any blame should remain with the author.

 \bibitem{a:8}
 D. Z. Albert, {\sl Phys. Lett.} {\bf 98A}, 249 (1983).

 \bibitem{be}
 P. Benioff, {\sl J. Stat. Phys.} {\bf 29}, 515 (1982);
{\sl Phys. Rev. Lett.} {\bf 48}, 1581 (1982).

 \bibitem{deutsch-85}
 D. Deutsch, {\sl Proc. R. Soc. Lond.} {\bf A 400}, 97 (1985).

 \bibitem{f-85}
R. P. Feynman, {\sl Opt. News} {\bf 11}, 11 (1985).

 \bibitem{peres-85}
 A. Peres, {\sl Phys. Rev.} {\bf A32}, 3266 (1985).

 \bibitem{b-86}
 P. Benioff, {\sl Annals New York Akademy of Sciences} {\bf 480}, 475
 (1986).

 \bibitem{m-86}
 N. Margolus, {\sl Annals New York Akademy of Sciences} {\bf 480}, 487
 (1986).

 \bibitem{deutsch:89}
 D. Deutsch, {\sl Proc. R. Soc. Lond.} {\bf A 425}, 73 (1989).


 \bibitem{deutsch:92}
 D. Deutsch and R. Jozsa, {\sl Proc. R. Soc. Lond.} {\bf A 439}, 553
(1992).

 \bibitem{zeilinger}
A. Zeilinger,
{\sl Am. J. Phys.} {\bf 49}, 882 (1981);
M. Reck, A. Zeilinger, H. J. Bernstein and P. Bertani,
{\sl Phys. Rev. Lett.} {\bf 73}, 58 (1994).

 \bibitem{hamming}
 R. W. Hamming, {\sl Coding and Information Theory, Second Edition}
 (Prentice-Hall, Englewood Cliffs, New Jersey, 1980).



%\bibitem{godel}
%K. G\"odel, {\sl Monatshefte f\"ur Mathematik und Physik}
%{\bf 38}, 173 (1931);
%English translation in
% M. Davis, {\sl Computability \& Unsolvability}
% (McGraw-Hill, New York, 1958) and in
% K. G\"odel, {\sl Collected Works, Volume I, Publications 1929-1936},
% ed. by S. Feferman, J. W. Dawson, Jr., St. C. Kleene, G. H. Moore, R.
% M. Solovay, J. van Heijenoort (Oxford University Press, Oxford, 1986).


\bibitem{svozil}
K. Svozil,  {\sl Randomness and Undecidability in Physics}
(World Scientific, Singapore, 1993).

\bibitem{sv:94}
K. Svozil,
{\sl On the computational power of physical systems,
undecidability, the consistency of phenomena and
 the practical uses of paradoxa}, in
{\sl International Conference  on Fundamental Problems in
Quantum Theory}, ed. by D. Greenberger (New
York Academy of Sciences, in print);
 {\sl Quantum recursion theory}, TU Vienna preprint.

\bibitem{orthon}
Let $d(\cdot ,\cdot )$ be the inner product of the Hilbert space.
Let further be $\langle x\vert y\rangle := d(\vert x\rangle , \vert
y\rangle
)$. Orthonormality states that
$\langle {\tt HALT} \vert {\tt HALT}\rangle =
\langle {\tt GO} \vert {\tt GO}\rangle =1$ and
$\langle {\tt HALT} \vert {\tt GO}\rangle =
\langle {\tt GO} \vert {\tt HALT}\rangle =0$.

 \bibitem{solomonoff}
 R. J. Solomonoff, {\sl Information and Control} {\bf 7}, 1 (1964);
 {\sl IEEE Transactions on Information Theory} {\bf
 IT-24}, 422 (1978).

\end{thebibliography}
\end{document}