\documentclass[%
 %reprint,
 %superscriptaddress,
 %groupedaddress,
 %unsortedaddress,
 %runinaddress,
 %frontmatterverbose,
 preprint,
 showpacs,
 showkeys,
 %preprintnumbers,
 %nofootinbib,
 %nobibnotes,
 %bibnotes,
 amsmath,
 amssymb,
 aps,
 % prl,
 pra,
 % prb,
 % rmp,
 %prstab,
 %prstper,
 %longbibliography,
 %floatfix,
 %lengthcheck,%
 ]{revtex4-1}
 %\bibliographystyle{apsrev4-1}

% \usepackage{hyperref}
 \usepackage{graphicx}% Include figure files

%\usepackage{cdmtcs}

\begin{document}


%\cdmtcsauthor{Cristian S. Calude, Michael J. Dinneen, Monica Dumitrescu and Karl Svozil}
%\cdmtcstitle{Experimental Evidence of Quantum Randomness Incomputability}
%\cdmtcsaffiliation{Department of Computer Science, University of Auckland, \\ Faculty of Mathematics and Computer Science, University of Bucharest, \\Vienna University of Technology}
%\cdmtcstrnumber{382}
%\cdmtcsdate{April 2010}
%\colourcoverpage
\sloppy

\title{Experimental Evidence of Quantum Randomness Incomputability}


\author{Cristian S. Calude}
\email{cristian@cs.auckland.ac.nz}
\homepage{http://www.cs.auckland.ac.nz/~cristian}

\author{Michael J. Dinneen}
\email{mjd@cs.auckland.ac.nz}
\homepage{http://www.cs.auckland.ac.nz/~mjd}

\affiliation{Department of Computer Science, University of Auckland,
Private Bag 92019, Auckland, New Zealand}

\author{Monica Dumitrescu}
\affiliation{Faculty of Mathematics and Computer Science, University of Bucharest,
Str. Academiei 14, 010014 Bucharest, Romania}
\email{mdumi@fmi.unibuc.ro}
\homepage{http://fmi.unibuc.ro/ro/dumitrescu\_monica}


\author{Karl Svozil}
\affiliation{Institute for Theoretical Physics, {\it Vienna} University of Technology,
Wiedner Hauptstrasse 8-10/136, 1040 {\it Vienna},  Austria}
\email{svozil@tuwien.ac.at}
\homepage{http://tph.tuwien.ac.at/~svozil}


\date{\today}

\begin{abstract}
In contrast with software-generated randomness (called pseudo-randomness), quantum randomness is provable incomputable, i.e.\ it is not exactly reproducible by any algorithm.
  We provide experimental evidence of  incomputability --- an asymptotic property --- of quantum randomness by
  performing finite tests of randomness inspired by algorithmic information theory.
\end{abstract}

\pacs{03.67.Lx, 05.40.-a, 03.65.Ta, 03.67.Ac, 03.65.Aa}
\keywords{quantum randomness, quantum indeterminism, random processes, quantum algorithms}
\preprint{CDMTCS preprint nr. 382/2010}
\maketitle


\section{Quantum indeterminacy}

The irreducible indeterminacy of individual quantum processes postulated by
Born~\cite{born-26-1,born-26-2,zeil-05_nature_ofQuantum}
implies that there exist physical ``oracles,'' which are capable to effectively produce outputs which are incomputable.
Indeed, quantum indeterminism has been proved~\cite{2008-cal-svo} under some  ``reasonable'' side assumptions implied by
Bell-, Kochen-Specker- and Greenberger-Horne-Zeilinger-type theorems.
Yet, as quantum indeterminism is nowhere formally specified,
it is important to investigate which (classes of) measurements lead to randomness,
what are the reasons for possible distinctions,
whether or not the kinds of randomness ``emerging'' in different classes of quantum measurements are ``the same'' or ``different,''
and what are the phenomenologies or signatures of these randomness classes.
Questions about ``degrees of (algorithmic) randomness" are studied in algorithmic information theory.
Here are just four types, among an infinity of others:
(i) standard pseudo-randomness produced by
software  like {\it Mathematica} or {\it Maple}  which
are not only Turing computable but cyclic;
(ii) pseudo-randomness
produced by software which is Turing computable but not cyclic
(e.g., digits of $\pi$, the ratio between the circumference and the diameter of an ideal circle, or Champernowne's constant);
(iii) Turing incomputable, but not
algorithmically random;
(iv) algorithmically random~\cite{MartinL�f1966602,chaitin:01,calude:02}.
One can ask: in which
of these four classes do we find quantum randomness?
Operationally, in the extreme form, Born's postulate could be interpreted to allow for the production of  ``random'' finite strings;
hence quantum randomness could be of type (iv).
(Here the quotation mark refers to the fact that randomness for finite strings is too ``subjective''
to be meaningful for our analysis.
The  legitimacy of the experimental approach comes from  characterizations of  random sequences
in terms of the degrees of incompressibility of their finite prefixes.~\cite{MartinL�f1966602,chaitin:01,calude:02}.)
A sequence which is not algorithmically random but Turing incomputable can, for instance, be obtained from an algorithmically random sequence $x_{1}x_{2}\cdots x_{n}\cdots $ by inserting a 0 in between any adjacent original bits, i.e.\ obtaining the sequence $x_{1}0x_{2}0\cdots 0x_{n}0\cdots $ This transformation destroys algorithmic randomness because obvious correlations have appeared; Turing incomputability is invariant under this transformation because a copy of the original sequence is embedded in the new one.
Yet much more subtler correlations among subsequences of Turing incomputable
sequences may exist, thus making them compressible and algorithmically nonrandom.
There is no {\em a priori} reason to interpret Born's indeterminism by its strongest formal expression; i.e.,
in terms of algorithmic randomness.

Quantum randomness produced by quantum
systems which have no classical interpretation is provable~\cite{2008-cal-svo} Turing
incomputable. More precisely, if the experiment would run under ideal
conditions ``to infinity,'' the resulting infinite sequence of bits would be
Turing incomputable; i.e., no Turing machine (or algorithm) could
reproduce exactly this infinite sequence of digits. This result has many consequence; here is one example.
The experiment could produce a billion of 0s, but not all bits produced will be 0.
A stronger form of incomputability holds true:  every Turing machine (or algorithm) can reproduce exactly
only finitely many scattered digits of that infinite sequence.
Yet this proof stops short of showing that the sequence produced by such a quantum
experiment is algorithmically random; i.e., it is unknown whether or not such
a sequence is or is not algorithmically random.
One of the strategies toward answering this question is to empirically perform tests
``against'' the algorithmic randomness hypothesis.

Our (more modest) aim is to present tests capable of  distinguishing computable
from incomputable sources of ``randomness'' by examining (long, but) finite prefixes of infinite sequences.
Such differences are guaranteed to exist by ~\cite{2008-cal-svo}, but,
because computability is an asymptotic property,
there was no guarantee that finite tests can ``pick'' differences in the prefixes we have analyzed.%~\footnote{Many inconclusive tests have been discarded.}.


\section{Tests of experimental quantum indeterminacy}


Based on Born's postulate, several quantum random number generators based on beam splitters
have recently been proposed and
realized~\cite{svozil-qct,rarity-94,zeilinger:qct,stefanov-2000,0256-307X-21-10-027,wang:056107,fiorentino:032334,svozil-2009-howto}.
In what follows a detailed analysis of bit strings of length $2^{32}$ obtained by
two such quantum random number generators will be presented --- the first analysis of
a set of quantum bits of this size (the size correlates well with  the square root of the cycle length used by cyclic pseudo-random generators; randomness properties of longer strings generated in this way  are impaired).
We will  compare  the performance of quantum random number generators
with  software-generated number generators on randomness inspired by algorithmic information theory
(which complement  some commonly used statistical tests implemented in ``batteries'' of test suites such as, for instance,
{\em diehard}~\cite{diehard},
{\it NIST}~\cite{Rukhin-nist},
or {\it TestU01}~\cite{1268777}).
The standard test suites are often based on
tests which are not designed for physical random number generators,
but rather to quantify the quality of the cyclic pseudo-random numbers generated by algorithms.
As we would like to separate ``truly'' random sequences from software-generated random sequences,
the emphasis is on the former type of  tests.


The tests based on algorithmic information theory directly
analyze randomness, and thus the strongest possible form of incomputability. They differ from tests employed in the standard  randomness batteries as they depend on irreducible algorithmic information content,
which is  constant for algorithmic pseudo-random sequences.
Some tests are related to each other, as for instance  sequences which are not Borel normal (cf. below) could be algorithmically compressed;
the analysis of results helps understanding subtle differences at the edge of incomputability/algorithmic randomness. All tests depend on the size of the analyzed strings; the legitimacy of our approach is given by the fact that algorithmic randomness of an infinite sequence can be ``uniformly read'' in its prefixes (cf. \cite{calude:02}).




\section{Data sources}

The analyzed quantum data consist of
10 quantum random strings generated with the commercially available {\it Quantis} device~\cite{Quantis},
based on research of a group in Geneva~\cite{stefanov-2000},
as well as
10 quantum random strings generated by the {\it Vienna} {\it IQOQI} group~\cite{Vienna}.
The pseudo-random data consist of
10 pseudo-random strings  produced by {\it Mathematica}~6~\cite{MRG}, and
10 pseudo-random strings  produced by  {\it Maple}~11~\cite{MAPLE},
as well as
10 strings of $2^{32}$ bits from the binary expansion of $\pi$
obtained from the {U}niversity of {T}okyo's supercomputing center~\cite{pi}.

The signals of the {\it Quantis} device are generated
by a light emitting diode producing photons which are then transmitted toward a beam splitter (a semi-transparent
mirror) and two successive  single-photon detectors (detectors with single-photon resolution)
to record the outcomes associated with the symbols ``$0$'' and ``$1$,'' respectively~\cite{Quantis}.
Due to hardware imbalances which are difficult to overcome at this level,
Quantis processes this raw data by un-biasing the sequence by a von Neumann type normalization:
The biased raw sequence of zeroes and ones is partitioned into
fixed subsequences of length two; then the even parity sequences ``$00$'' and ``$11$'' are discarded,
and only the odd parity ones ``$01$'' and ``$10$'' are kept.
In a second step, the remaining sequences are mapped into the single symbols $01 \mapsto 0$ and  $10 \mapsto 1$,
thereby extracting a new unbiased sequence at the cost of a loss of original bits~\cite[p. 768]{von-neumann1}.

This normalization method requires that the events are (temporally) uncorrelated and thus independent.
(For the sake of a simple counterexample, the von Neumann normalization of
the sequences $010101 \cdots $ or $1100110011 \cdots $ are the constant-0 sequence $000\cdots$ and the empty sequence.)
Under the independence hypothesis,  the normalized sequences  are Borel normal~\cite{borel:09}; e.g., all finite subsequences
of length $n$ occur with their expected asymptotic frequencies $2^{-n}$.
(Alas, see \cite{Hertling:jucs_8_2:simply_normal_numbers_to}
for some pitfalls when transforming such sequences.)


The signals of the Vienna Institute for Quantum Optics and Quantum
Information (IQOQI)
group were generated with photons from a weak blue LED light source which impinged on a
beam splitter
without any polarization sensitivity with two output ports associated
with the codes ``0'' and ``1,'' respectively~\cite{zeilinger:qct}.
There was {\em no} pre- or post-processing of the raw data stream,
in particular no von Neumann normalization as discussed for the Quantis device;
however the output was constantly monitored
(the exact method is subject to a patent pending).
In very general terms, the setup needs to be running for at least one
day to reach a stable operation.
There is a regulation mechanism which keeps track of the bias between
``0'' and ``1,''
and  tunes the random generator for perfect symmetry.
Each data file was created in one continuous run of the device
lasting over hours.

We have employed the {\it extended cellular automaton generator} default of {\it Mathematica}~6's pseudo-random function.
It is based on a particular five-neighbor rule, so each new cell depends on five nonadjacent cells from the previous step~\cite{MRG}.
{\it Maple}~11 uses a Mersenne Twister algorithm to generate a random pseudo-random output~\cite{MAPLE}.



\section{Testing incomputability and randomness}

The  tests  we performed can be grouped into: (i) two tests based on algorithmic information theory,
(ii) statistical tests involving frequency counts (Borel normality test), (iii)
a test based on Shannon's information theory, and (iv) a test based on random walks.




In Figures~\ref{fig:example3}--\ref{fig:example5} the graphical representation of the results is rendered in terms of
box-and-whisker plots, which characterize
groups of numerical data through five characteristic summaries:
test minimum value, first quantile (representing one fourth of the test data),
median or second quantile (representing half of the test data),
third quantile (representing three fourths of the test data),
and test maximum value. Mean and standard deviation of the data representing the results of the tests are calculated.
Tables containing the experimental data and the programs used
to generate the data can be downloaded from our extended paper~\cite{CDMTCS372}.

%\begin{figure*}[htbp] %  figure placement: here, top, bottom, or page
%\begin{tabular}{cc}
%   \includegraphics[width=2.7in]{2010-QvPR-boxbookstack} &
%   \includegraphics[width=2.5in]{2010-QvPR-boxsolovey}  \\
%a)&b)\\
%   \includegraphics[width=2.53in]{2010-QvPR-boxborelk2}    &
%   \includegraphics[width=2.5in]{2010-QvPR-boxLentropy}    \\
%c)&d)\\
%   \includegraphics[width=2.7in]{2010-QvPR-boxrandomwalk}&\\
%e)                                \\
%\end{tabular}
%\caption{(Color online) Box-and-whisker plot for the results a) of  the ``book stack'' randomness test;
%b) based on the Solovay-Strassen probabilistic primality test;
%c) for tests of the Borel normality property;
%d) for average results in ``sliding window'' estimations of the Shannon entropy;
%e) of the random walk tests.}
%   \label{f1-2010-qrat}
%\end{figure*}


\subsection{Book stack randomness test}

The {\em book stack}
(also known as ``move to front'')
test~\cite{MR2099021,MR2162569} is based on the fact that compressibility is a symptom of less randomness.

The results, presented in
%Table~\ref{table8} and
Figure~\ref{fig:example3} and Table~\ref{tab:3}, are derived from the original count, the count after the application
of the transformation, and the difference.  The key metric for this test is
the count of ones after the transformation.  The book stack encoder does
not compress data but instead rewrites each byte with its index (from
the top/front) with respect to its input characters being
stacked/moved-to-front.
Thus, if a lot of repetitions occur (i.e., a symptom of
non-randomness), then the output  contains more zeros than ones due to
the sequence of indices generally being smaller numerically.

\begin{figure}[htbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=5in]{2010-QvPR-boxbookstack}
   \caption{(Color online) Box-and-whisker plot for the results of  the ``book stack'' randomness test.}
   \label{fig:example3}
\end{figure}

\begin{table}
\caption{Statistics for the results of  the ``book stack'' randomness
test.}\label{tab:3}
\begin{center}
\begin{tabular}
[c]{ c c c c c c c c }%
\hline\hline
Descriptive statistics & min & Q1 & median & Q3 & max & mean & sd\\\hline
Maple & 7964 & 34490 & 49220 & 69630 & 108700 & 53410 & 33068.58\\
Mathematica & 4508 & 13020 & 24110 & 43450 & 62570 & 27940 & 19406.03\\
Quantis & 28600 & 60480 & 87780 & 106700 & 156100 & 89990 & 41545.76\\
Vienna & 9110 & 38420 & 57720 & 73220 & 97660 & 53860 & 27938.92\\
$\pi$ & 8551 & 35480 & 42100 & 52870 & 78410 & 41280 & 20758.46\\\hline\hline
\end{tabular}
\end{center}
\end{table}


\subsection{Solovay-Strassen probabilistic primality test}

The second algorithmic test, based on the {\em Solovay-Strassen probabilistic primality test},
uses  Carmichael (composite) numbers which are ``difficult'' to  factor, to determine the quality of randomness
by computing how fast the probabilistic primality test reaches the verdict ``composite'' \cite{solovay:84,ch-schw-78}.
All Carmichael numbers less than $10^{16}$ have been used~\cite{Pinch,Pinch07}.


To test whether  a positive integer
$n$ is prime, we take $k$ natural numbers uniformly distributed between 1
and $n - 1$, inclusive, and, for each one $i$, check whether the predicate
$W (i, n)$ holds.  If this is the case we say that
``$i$ is a witness of $n$'s compositeness''.
If $W (i, n)$ holds for at least one $i$ then $n$ is
composite; otherwise, the test is inconclusive, but in this case if one declares $n$ to be  prime then the
 probability to be wrong is smaller than $ 2^{-k}$.

 This is due to the fact that
 at least half  $i$'s from $1$ to $ n - 1$ satisfy $W (i, n)$  if $n$ is indeed composite,
 and {\it none} of them satisfy $W (i, n)$ if $n$ is prime~\cite{solovay:84}.
Selecting $k$ natural numbers  between 1
and $n - 1$ is the same as choosing a binary string $s$ of length $n-1$ with $k$ $1$'s
such that the $i$th bit is 1 iff $i$ is selected.
Ref.~\cite{ch-schw-78} contains a  proof that, if $s$ is a long enough   algorithmically random binary string,
then $n$ is prime iff $Z(s,n)$ is true,
where $Z$ is a predicate constructed directly from conjunctions of negations of  $W$~\footnote{
In fact, every  ``decent'' Monte Carlo simulation algorithm in  which  tests are chosen according to an
algorithmic random string produces a result
which is not only true with high probability, but {\it rigorously correct}~\cite{MR757602}.}.

A Carmichael number is a composite positive integer $k$ satisfying the congruence $b^{k-1} \equiv 1 ({\rm mod } \, k)$
for all integers $b$ relative prime to $k$.
Carmichael numbers are composite, but are difficult to factorize and thus are ``very similar'' to primes;
they are sometimes called pseudo-primes.
Carmichael numbers can fool Fermat's primality test, but less   the Solovay-Strassen test.
With increasing values, Carmichael numbers
become ``rare''~\footnote{There are 1,401,644 Carmichael numbers in the interval $[1, 10^{18}]$.}.


The fourth test uses Solovay-Strassen probabilistic primality test for
Carmichael numbers (composite) with prefixes of the sample strings as the binary
string $s$. We used the Solovay-Strassen  test for all Carmichael numbers less
than $10^{16}$---computed in Ref.~\cite{Pinch,Pinch07}---with numbers selected according to increasing prefixes of each sample string till the algorithm returns
a non-primality verdict. The metric is given by the length of the sample used to
reach the correct
verdict of non-primality for all of the 246683 Carmichael numbers less than
$10^{16}$.  [We started with $k=1$ tests (per each Carmichael number) and increase $k$
until the metric goal is met; as $k$ increases we always use new bits (never
recycle) from the sample source strings.]
The results are presented in
%Table~\ref{table5} and
Figure~\ref{fig:example4} and Table~\ref{tab:4}.

\begin{figure}[htbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=5in]{2010-QvPR-boxsolovey}
   \caption{(Color online) Box-and-whisker plot for the results based on the Solovay-Strassen probabilistic primality test.}
   \label{fig:example4}
\end{figure}

\begin{table}
   \caption{Statistics for the results based on the
Solovay-Strassen probabilistic primality test.}\label{tab:4}
\begin{center}
\begin{tabular}
[c]{ c c c c c c c c }%
\hline\hline
Descriptive statistics & min & Q1 & median & Q3 & max & mean & sd\\\hline
Maple & 93.0 & 96.0 & 101.0 & 113.5 & 120.0 & 104.9 & 10.57723\\
Mathematica & 93.0 & 97.0 & 109.0 & 132.3 & 142.0 & 113.5 & 19.60867\\
Quantis & 99.0 & 103.3 & 113.0 & 121.3 & 130.0 & 112.6 & 10.66875\\
Vienna & 82.0 & 100.3 & 104.5 & 109.0 & 119.0 & 103.5 & 11.03781\\
$\pi$ & 84.0 & 91.75 & 106.0 & 110.8 & 128.0 & 104.7 & 10.66875\\\hline  \hline
\end{tabular}
\end{center}
\end{table}

\subsection{Borel normality test}

{\em Borel normality} --- requesting that
every  binary string appears in the sequence with the correct probability $2^{-n}$ for a string of length $n$ ---
served as the first mathematical definition of randomness~\cite{borel:09}.
A sequence is (Borel) normal if every  binary string appears in the sequence with the right probability
(which is $2^{-n}$ for a string of length $n$).
A  sequence is normal if and only  it  is incompressible by any information lossless finite-state compressor~\cite{ZL:1978}, so  normal sequences are  those sequences  that appear random to any finite-state machine.


Every algorithmic random infinite sequence is Borel normal~\cite{DBLP:conf/dlt/Calude93}.
 The converse implication is not true:
there exist computable normal sequences (e.g.,  Champernowne's constant).


Normality is invariant under finite variations: adding, removing, or changing a finite number of bits in any normal sequence leaves it normal. Further, if a sequence satisfies the normality condition
for strings of length $n+1$, then it also satisfies normality for strings of length $n$, but the converse is not true.

Normality was transposed to  strings in Ref.~\cite{DBLP:conf/dlt/Calude93}. In this process one  has to replace limits with inequalities. As a consequence, the above two properties, which are valid for sequences, are no longer true for strings.



%We denote by  $N_{i}(x)$ the number
%of  occurrences of the letter $i\in \{0,1\}$ in the string $x$.
%A  string $x$ is called
% $\varepsilon${\bf -limiting} ($\varepsilon $ is a fixed positive real)
%if it satisfies the inequality ($|x|$ is the length of $x$ considered as a string over $\{0,1\}$):
%$| N_{i}(x)/|x| - 1/2| \leq \varepsilon$, for $i=1,2$.
For any fixed  integer $m > 1$, consider the alphabet $B_{m} = \{0,1\}^{m}$ consisting of all binary strings of length $m$,
 and for
every $1 \leq i \leq 2^{m}$ denote by $N_{i}^{m}$ the
 number of occurrences of the lexicographical $i$th binary string of length $m$ in the string $x$ (considered over the alphabet $B_{m}$).
 By $|x|_{m}$ we denote the length of $x$.
 A string $x$ is Borel normal if
  for every natural $1 \leq m \leq \log_{2}\log_{2} |x|,$
  \[
\left| \frac{N_{j}^{m}(x)}{|x|_{m}} -  2^{-m} \right| \leq
\sqrt\frac{\log_{2}|x|}{|x|}\raisebox{0.5ex}{,}\]
for every $1 \leq j \leq 2^{m}$.
In Ref.~\cite{DBLP:conf/dlt/Calude93}
it is shown that almost all algorithmic random strings are Borel normal.

In the first test
we  count the maximum, minimum and difference of non-overlapping occurrences of  $m$-bit ($m=1,\ldots , 5$) strings  in
each sample string.   Then we tested the Borel normality property for each sample string and found that
almost all strings pass the  test,  with some notable exceptions.
We found that several of the Vienna sequences failed the expected count range for
$m=2$ and a few of the Vienna sequences were outside the expected range for $m=3$
and $m=4$ (some less then the expected minimum count and some more than the expected
maximum count).  The only other bit sequence that was outside the expected range
count was one of the Mathematica sequences that had a too big of a count for $k=1$.
%
Figure~\ref{fig:example1} depicts a box-and-whisker plot of the
results. This is followed by statistical (numerical) details
in Table~\ref{tab:1}.



\begin{figure}[htbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=5in]{2010-QvPR-boxborelk2}
   \caption{(Color online) Box-and-whisker plot for the results for tests of the Borel normality property.}
   \label{fig:example1}
\end{figure}

\begin{table}
\caption{Statistics for the results for tests of the Borel normality property.}\label{tab:1}
\begin{center}
\begin{tabular}
[c]{c c c c c c c c c c c c c c c }%
\hline\hline
Descriptive statistics & min & Q1 & median & Q3 & max & mean & sd\\\hline
Maple & 22430 & 47170 & 61990 & 76130 & 94510 & 60210 & 21933.52\\
Mathematica & 8572 & 25500 & 40590 & 55650 & 86430 & 41870 & 23229.77\\
Quantis & 146800 & 185100 & 210500 & 226600 & 260000 & 207200 & 33515.65\\
Vienna & 77410 & 340200 & 350500 & 392500 & 260000 & 337100 & 103354.3\\
$\pi$ & 14260 & 28860 & 40880 & 47860 & 79030 & 40220 & 17906.21\\\hline\hline
\end{tabular}
\end{center}
\end{table}



\subsection{Test based on Shannon's information theory}

The next test
computes  ``sliding window'' estimations of the Shannon entropy $L_n^1, \ldots ,L_n^t$ according to the method described in
\cite{Wyner}: a smaller  entropy is a symptom of  less randomness.
The results are presented in
%Table~\ref{table6} and
Figure~\ref{fig:example2} and Table~\ref{tab:2}.

\begin{figure}[htbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=5in]{2010-QvPR-boxLentropy}
   \caption{(Color online) Box-and-whisker plot for average results in ``sliding window'' estimations of the Shannon entropy.}
   \label{fig:example2}
\end{figure}


\begin{table}
\caption{Statistics for average results in ``sliding window''
estimations of the Shannon entropy.}\label{tab:2}
\begin{center}
\begin{tabular}
[c]{c c c c c c c c c c c c c c c }%
\hline\hline
Descriptive statistics & min & Q1 & median & Q3 & max & mean & sd\\\hline
Maple & 0.9772 & 0.9781 & 0.9784 & 0.9787 & 0.9788 & 0.9783 & 0.0005231617\\
Mathematica & 0.9776 & 0.9781 & 0.9783 & 0.9785 & 0.9800 & 0.9783 & 0.0006654936\\
Quantis & 0.9779 & 0.9783 & 0.9783 & 0.9786 & 0.9795 & 0.9784 & 0.0004522699\\
Vienna & 0.9772 & 0.9777 & 0.9784 & 0.9790 & 0.9792 & 0.9783 & 0.0006955834\\
$\pi$ & 0.9779 & 0.9784 & 0.9788 & 0.9790 & 0.9799 & 0.9788 & 0.0006062724\\\hline\hline
\end{tabular}
\end{center}
\end{table}


\subsection{Test based on random walks}

A symptom of non-randomness of a string is detected when the plot generated by viewing a sample sequence as
a 1D random walk meanders ``less  away''
from the starting point (both ways); hence the max-min range is the metric.


The fifth test
is thus based on viewing a  random
sequence as a one-dimensional {\em random walk;}
whereby the successive bits, associated  with an increase of one unit {\it per} bit of the $x$-coordinate,
are interpreted as follows: $1=$``move up,'' and  $0=$``move down'' on the $y$-axis.
In this way a measure is obtained for how far away one can reach from the starting point
(in either positive or negative) from the starting $y$-value of $0$ that one can reach using
successive bits of the sample sequence.
%to move up or down.
%Table~\ref{table9} and
Figure~\ref{fig:example5} and Table~\ref{tab:5} summarize the results.

\begin{figure}[htbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=5in]{2010-QvPR-boxrandomwalk}
   \caption{(Color online) Box-and-whisker plot for the results of the random walk tests.}
   \label{fig:example5}
\end{figure}

\begin{table}
\caption{Statistics for the results of the random walk tests.}\label{tab:5}
\begin{center}
\begin{tabular}
[c]{ c c c c c c c c }%
\hline\hline
Descriptive statistics & min & Q1 & median & Q3 & max & mean & sd\\\hline
Maple & 67640 & 88730 & 126400 & 162500 & 180500 & 125300 & 42995.59\\
Mathematica & 73500 & 84760 & 98110 & 103400 & 120300 & 96450 & 14685.34\\
Quantis  & 138200 & 161600 & 209000 & 250200 & 294200 & 211300 & 55960.23\\
Vienna & 92070 & 130200 & 155600 & 167600 & 226900 & 152900 & 36717.55\\
$\pi$ & 58570 & 70420 & 82800 & 91920 & 107500 & 82120 & 14833.75\\\hline\hline
\end{tabular}
\end{center}
\end{table}







\section{Statistical analysis of randomness tests results}


In what follows
the significance of results corresponding to each randomness test applied to all five sources have
been analyzed by means of some statistical comparison tests.
The Kolmogorov-Smirnov test  for two samples~\cite{Conover}
determines if two datasets differ significantly.
This test has the advantage of making no prior assumption about the distribution of data;
i.e., it is non-parametric and distribution free.

The Kolmogorov-Smirnov test returns a $p$-value,
and the decision ``the difference between the two datasets is statistically
significant" is accepted if the $p$-value {\em is less than $0.05$;}
or, stated pointedly, if the
probability of taking a wrong decision is less than $0.05$. Exact $p$-values are
only available for the two-sided two-sample tests with no ties.

In some cases we have tried to double-check the decision  ``no significant
differences between the datasets"  at the price of a supplementary, plausible
distribution assumption. Therefore, we have performed the Shapiro-Wilk test  for normality
\cite{Shapiro-Wilk} and, if normality is not rejected, we have assumed that the
datasets have normal (Gaussian) distributions.
In order to be able to compare the expected values (means) of the two samples,
the Welch $t$-test~\cite{Welch}, which is a version of Student's test, has been applied.
In order to emphasize the relevance of p-values less than 0.05 associated with Kolmogorov-Smirnov,
Shapiro-Wilk and Welch's $t$-tests, they are printed in boldface and discussed in the text.

\subsection{Book stack randomness test}

The results of the Kolmogorov-Smirnov test associated with the ``book-stack" tests are enumerated in Table~\ref{tab:8}.
Statistically significant differences are identified for
Quantis {\it versus} Mathematica and $\pi$.
\begin{table}
\caption{Kolmogorov-Smirnov test for the ``book-stack'' tests.}\label{tab:8}
 \begin{center}
 \begin{tabular}
[c]{ c c c c c }
\hline\hline
Kolmogorov-Smirnov test $p$-values & Mathematica & Quantis & Vienna & $\pi$ \\\hline
Maple  & 0.4175 & 0.1678 & 0.9945 & 0.4175\\
Mathematica &  & \bf{0.0021} & 0.1678 & 0.4175\\
Quantis &  &  & 0.1678 & \bf{0.0123}\\
Vienna &  &  &  & 0.4175\\\hline\hline
\end{tabular}
\end{center}
\end{table}


As more compression is a symptom of less randomness,  the corresponding ranking of
samples is as follows:
$\langle \text{Quantis} \rangle  = 89988.9 > \langle \text{Vienna} \rangle  = 53863.8  >  \langle \text{Maple} \rangle  =
53411.6 > \langle  \pi \rangle  = 41277.5  >  \langle \text{Mathematica} \rangle  = 27938.3$.
The Shapiro-Wilk tests results are presented in  Table~\ref{tab:9}.

\begin{table}
\caption{Shapiro-Wilk test for the ``book-stack'' tests.}\label{tab:9}
\begin{center}
\begin{tabular}
[c]{ c c c c c c }\hline\hline
Shapiro-Wilk test & Maple & Mathematica & Quantis & Vienna  & $\pi$\\\hline
$p$-value  & 0.7880 & 0.4819 & 0.7239 & 0.8146 &
0.5172\\\hline\hline
\end{tabular}
\end{center}
\end{table}

Since normality is not rejected for any string, we apply the Welch's $t$-test
for the comparison of means. The results are enumerated in Table~\ref{tab:10}.
Significant differences between the means are identified for the following sources:
(i) Quantis {\it versus} all other sources (Maple, Mathematica, Vienna, $\pi$); and
(ii)
Vienna {\it versus} Mathematica and Maple (as already mentioned).



\begin{table}
\caption{Welch's $t$-test for the ``book-stack'' tests.}\label{tab:10}
\begin{center}
\begin{tabular}
[c]{ c c c c c }\hline\hline
$p$-value & Mathematica & Quantis & Vienna & $\pi$\\\hline
Maple  & 0.0535 & \bf{0.0436} & 0.974 & 0.3412\\
Mathematica &  & \bf{0.0009} & \bf{0.0283} & 0.1551\\
Quantis  &  &  & \bf{0.0368} & \bf{0.0054}\\
Vienna &  &  &  & 0.2690\\\hline\hline
\end{tabular}
\end{center}
\end{table}


\subsection{Solovay-Strassen probabilistic primality test}


The Kolmogorov-Smirnov test results for this test are presented in Table~\ref{tab:11},
where no significant differences are detected.

The Shapiro-Wilk test results are presented in Table~\ref{tab:12}.
Since there is no clear
pattern of normality for the data, the application of Welch's $t$-test is not
appropriate.
\begin{table}
\caption{Kolmogorov-Smirnov test for the Solovay-Strassen tests.}\label{tab:11}
 \begin{center}
 \begin{tabular}
[c]{ c c c c c }
\hline\hline
Kolmogorov-Smirnov test $p$-values & Mathematica & Quantis & Vienna & $\pi$ \\\hline
Maple  & 0.7591 & 0.4005 & 0.7591 & 0.7591\\
Mathematica &  & 0.7591 & 0.7591 & 0.7591\\
Quantis &  &  & 0.4005 & 0.7591\\
Vienna &  &  &  & 0.9883\\\hline\hline
\end{tabular}
\end{center}
\end{table}


\begin{table}
\caption{Shapiro-Wilk test for the Solovay-Strassen tests.}\label{tab:12}
\begin{center}
\begin{tabular}
[c]{ c c c c c c }\hline\hline
Shapiro-Wilk test & Maple & Mathematica & Quantis  & Vienna  & $\pi$\\\hline
$p$-value & 0.0696 & \bf{0.0363} &
0.4378 & 0.6963 & 0.4315\\\hline\hline
\end{tabular}
\end{center}
\end{table}



\subsection{Borel test of normality}



The results of the Kolmogorov-Smirnov test are presented in Table~\ref{tab:5b}.
\begin{table}
\caption{Kolmogorov-Smirnov test for the Borel normality tests.}\label{tab:5b}
 \begin{center}
 \begin{tabular}
[c]{ c c c c c }
\hline\hline
Kolmogorov-Smirnov test $p$-values & Mathematica & Quantis & Vienna & $\pi$ \\\hline
Maple & 0.4175 &$\mathbf{< 10^{-4}}$%\bf{0.00001083}
& \bf{0.0002}
& 0.1678\\
Mathematica &  & $\mathbf{< 10^{-4}}$% \bf{0.00001083}
& \bf{0.0002} & 0.9945\\
Quantis &  &  & \bf{0.0002} & $\mathbf{< 10^{-4}}$%0.00001083
\\
Vienna &  &  &  & \bf{0.0002}\\\hline\hline
\end{tabular}
\end{center}
\end{table}
Statistically significant differences are identified for
(i) Quantis {\it versus}  Maple,  Maple, Mathematica and $\pi$;
(ii) Vienna {\it versus}  Maple, Mathematica and $\pi$; and
(iii) Quantis {\it versus}  Vienna.


Note that
\begin{enumerate}

\item Pseudo-random strings pass the Borel normality test for comparable, relatively small (with respect to quantum strings; cf. below),
numbers of counts:
if the angle brackets   $\langle x \rangle$ stand for the statistical mean of tests on $x$, then
 $\langle \text{Maple} \rangle  = 60210$, $\langle \text{Mathematica} \rangle  = 41870$,
$\langle  \pi \rangle  = 40220$).


\item Quantum strings pass the Borel normality test only for ``much larger numbers''
of counts
($\langle \text{Quantis} \rangle  = 207200$, $\langle \text{Vienna} \rangle  = 337100$).


%\item Normality  was rejected by the Shapiro-Wilk test only for Vienna.


%\item Statistically significant difference between the results of the BNTest applied for Vienna and Quantis is established by means of the ks.test for two samples

\end{enumerate}
As a result, the Borel normality test detects and identifies
statistically significantly differences between all pairs of computable and incomputable  sources of ``randomness.''

\subsection{Test based on Shannon's information theory}

 The results of the Kolmogorov-Smirnov test are presented in  Table~\ref{tab:6}.
No significant differences are detected. The descriptive statistics
data for the results of this test  indicates almost identical
distributions corresponding to the five sources.



\begin{table}
\caption{Kolmogorov-Smirnov test for Shannon's information theory tests.}\label{tab:6}
 \begin{center}
 \begin{tabular}
[c]{ c c c c c }
\hline\hline
Kolmogorov-Smirnov test $p$-values & Mathematica & Quantis & Vienna & $\pi$ \\\hline
Maple & 0.7870 & 0.7870 & 0.7870 & 0.1678\\
Mathematica &  & 0.7870 & 0.4175 & 0.0525\\
Quantis &  &  & 0.4175 & 0.1678\\
Vienna &  &  &  & 0.4175\\\hline\hline
\end{tabular}
\end{center}
\end{table}



The results of the Shapiro-Wilk test associated with a test based on Shannon's information theory are presented in Table~\ref{tab:7}.
Since there is no clear
pattern of normality for the data, the application of Welch's $t$-test is not
appropriate.


\begin{table}
\caption{Shapiro-Wilk test for Shannon's information theory tests.}\label{tab:7}
\begin{center}
\begin{tabular}
[c]{ c c c c c c }\hline\hline
Shapiro-Wilk test & Maple & Mathematica & Quantis  & Vienna  & $\pi$\\\hline
$p$-value & 0.1962 & \bf{0.0189} &
\bf{0.0345} & 0.3790 & 0.8774\\\hline\hline
\end{tabular}
\end{center}
\end{table}






\subsection{Test based on random walks}


The Kolmogorov-Smirnov test results associated with test based on random walks are presented in Table~\ref{tab:13}.
Statistically significant differences are identified for:
(i) Quantis {\it versus} all other sources (Maple, Mathematica, Vienna and $\pi$);
(ii) Vienna {\it versus} Mathematica, Vienna (as already
mentioned) and  $\pi$;  and
(iii) Maple {\it versus} $\pi$.

Quantum strings move farther away from the starting point than the pseudo-random strings; i.e.,
$\langle \text{{\it Quantis}} \rangle > \langle \text{{\it Vienna}} \rangle > \langle \text{{\it Maple}} \rangle >  \langle \text{{\it Mathematica}} \rangle > \langle \pi \rangle  $.


\begin{table}
\caption{Kolmogorov-Smirnov test for the random walk tests.}\label{tab:13}
 \begin{center}
 \begin{tabular}
[c]{ c c c c c }
\hline\hline
Kolmogorov-Smirnov test $p$-values & Mathematica & Quantis & Vienna & $\pi$ \\\hline
Mathematica & 0.1678 & \bf{0.0123} & 0.4175 & 0.0525\\
Quantis &  & $\mathbf{< 10^{-4}}$ & \bf{0.0021} & 0.1678\\
Vienna &  &  & 0.0525 & $\mathbf{< 10^{-4}}$\\
$\pi$ &  &  &  & \bf{0.0002}\\\hline\hline
\end{tabular}
\end{center}
\end{table}



Note that quantum strings move farther away from the starting point than the pseudo-random strings; i.e.,
$\langle \text{{\it Quantis}} \rangle > \langle \text{{\it Vienna}} \rangle > \langle \text{{\it Maple}} \rangle >  \langle \text{{\it Mathematica}} \rangle > \langle \pi \rangle  $.
It was quite natural to double-check the conclusion  ``Quantis and Vienna do not
exhibit significant differences.'' Hence we run the Shapiro-Wilk test, which concludes
that normality is not rejected; cf. Table~\ref{tab:14}.


\begin{table}
\caption{Shapiro-Wilk test for the random walk tests.}\label{tab:14}
\begin{center}
\begin{tabular}
[c]{ c c c c c c }\hline\hline
Shapiro-Wilk test & Maple & Mathematica & Quantis & Vienna  & $\pi$\\\hline
$p$-value & 0.2006 & 0.9268 & 0.5464 & 0.8888 &
0.9577\\\hline\hline
\end{tabular}
\end{center}
\end{table}

Next, we apply the Welch's $t$-test for the comparison of means. The
results are given in Table~\ref{tab:15}.
Significant differences between the means are identified for the
following sources:
(i) Quantis {\it versus} all other sources (Maple, Quantis, Vienna, $\pi$);
(ii)
Vienna {\it versus} Mathematica), Quantis (as already mentioned) and $\pi$;
(iii) Maple {\it versus} $\pi$.

\begin{table}
\caption{Welch's $t$-tests for the random walk tests.}\label{tab:15}
\begin{center}
\begin{tabular}
[c]{ c c c c c }\hline\hline
$p$-value & Mathematica & Quantis & Vienna & $\pi$\\\hline
Maple & 0.06961 & \bf{0.0013} & 0.1409 & \bf{0.0119}\\
Mathematica &  & $\mathbf{< 10^{-4}}$ & \bf{0.0007} & \bf{0.0435}\\
Quantis &  &  & \bf{0.0143} & $\mathbf{< 10^{-4}}$\\
Vienna &  &  &  & \bf{0.0001}\\\hline\hline
\end{tabular}
\end{center}
\end{table}




\section{Summary}

Tests based on algorithmic information theory
analyze algorithmic randomness,  the strongest possible form of incomputability.
In this respect they differ from tests employed in the standard test batteries,
as the former depend on irreducible algorithmic information content,
which is constant for algorithmic pseudo-random generators.
Thus the set of randomness tests performed for our analysis could in principle be expected to be
``more sensitive'' with respect to differentiating
between quantum randomness and algorithmic types of ``quasi-randomness'' than statistical tests alone.

All tests have produced evidence --- with different degrees of statistical significance --- of differences between quantum and non-quantum sources.
In summary:

\begin{enumerate}
\item
For the test for Borel normality --- the strongest discriminator test --- statistically significant differences between the distributions of datasets are identified for
(i) {\it Quantis} versus {\it Maple}, {\it Mathematica} and $\pi$; (ii) {\it Vienna} versus {\it Maple}, {\it Mathematica} and $\pi$; and (iii) {\it Quantis} versus {\it Vienna}.

Not only that the average number of counts is larger for quantum sources, but the
increase is quite significant: {\it Quantis}  is $3.5-5$ times larger than the corresponding average number
of counts for software-generated sources, and {\it Vienna} is $5-8$ times larger than
those values.
\item
For the test based on random walks, statistically significant differences between the distributions of datasets are identified for:
(i) {\it Quantis} versus all other sources ({\it Maple}, {\it Mathematica}, {\it Vienna} and $\pi$);
(ii) {\it Vienna} versus {\it Mathematica}, {\it Vienna} and $\pi$. Quantum strings move farther away from the starting point than the pseudo-random strings; i.e.,
$\langle \text{{\it Quantis}} \rangle > \langle \text{{\it Vienna}} \rangle > \langle \text{{\it Maple}} \rangle >  \langle \text{{\it Mathematica}} \rangle > \langle \pi \rangle  $.

\item
For the ``book-stack'' test, significant differences between the means are identified for the following sources: (i) {\it Quantis} versus all other sources ({\it Maple}, {\it Mathematica}, {\it Vienna}, $\pi$);
and (ii) {\it Vienna} versus {\it Mathematica} and {\it Maple}.


\item
For the test based on Shannon's information theory, as well as for the Solovay-Strassen test, {\em no significant differences} among the five chosen sources are detected. In the first case the reason may come from the fact  that averages are the same for all samples. In the second case  the reason  may be due to the fact that the test is based solely on the behavior of algorithmic random strings and not on a specific property of randomness.


\end{enumerate}


We close with a cautious remark about the impossibility to formally or experimentally ``prove absolute randomness.''
Any claim of randomness can only be secured  {\em relative} to, and
{\em with respect} to, a more or less large class of laws or behaviors, as
it is impossible to inspect the hypothesis against an infinity of --- and even less so all --- conceivable laws.
To rephrase a statement about computability~\cite[p. 11]{davis-58}, {\em ``how can we ever exclude the possibility of our
presented, some day (perhaps by some extraterrestrial visitors), with a (perhaps
extremely complex) device  that ``computes'' and ``predicts''
a certain type of hitherto ``random'' physical behavior?''}


\section*{Acknowledgements}

We are grateful to  Thomas Jennewein and Anton Zeilinger for providing us with the quantum random bits produced at the University of  Vienna by  Vienna IQOQI group, for the description of their method, critical comments and  interest in this research.

We thank: a) Alastair Abbott, Hector Zenil and Boris Ryabko for interesting comments, b)
Ulrich Speidel for his tests for which some partial results have been reported in our extended paper~\cite{CDMTCS372},
c) Stefan Wegenkittl for critical comments of various drafts of this paper and his suggestions  to exclude  some tests,
d) the anonymous Referees for constructive suggestions.


Calude gratefully  acknowledges the support of  the Hood Foundation  and the  Technical University of  Vienna. Svozil  gratefully  acknowledges support of the CDMTCS at the University of Auckland, as well as of the Ausseninstitut of the Vienna University of Technology.


%\bibliography{svozil}


%Merlin.mbs v4.21 2009-07-09.
\begin{thebibliography}{10}%
\makeatletter
\providecommand \@ifxundefined [1]{%
 \ifx #1\undefined \expandafter \@firstoftwo
 \else \expandafter \@secondoftwo
\fi
}%
\providecommand \@ifnum [1]{%
 \ifnum #1\expandafter \@firstoftwo
 \else \expandafter \@secondoftwo
\fi
}%
\providecommand \enquote [1]{``#1''}%
\providecommand \bibnamefont  [1]{#1}%
\providecommand \bibfnamefont [1]{#1}%
\providecommand \citenamefont [1]{#1}%
\providecommand\href[0]{\@sanitize\@href}%
\providecommand\@href[1]{\endgroup\@@startlink{#1}\endgroup\@@href}%
\providecommand\@@href[1]{#1\@@endlink}%
\providecommand \@sanitize [0]{\begingroup\catcode`\&12\catcode`\#12\relax}%
\@ifxundefined \pdfoutput {\@firstoftwo}{%
 \@ifnum{\z@=\pdfoutput}{\@firstoftwo}{\@secondoftwo}%
}{%
 \providecommand\@@startlink[1]{\leavevmode\special{html:<a href="#1">}}%
 \providecommand\@@endlink[0]{\special{html:</a>}}%
}{%
 \providecommand\@@startlink[1]{%
  \leavevmode
  \pdfstartlink
   attr{/Border[0 0 1 ]/H/I/C[0 1 1]}%
   user{/Subtype/Link/A<</Type/Action/S/URI/URI(#1)>>}%
  \relax
 }%
 \providecommand\@@endlink[0]{\pdfendlink}%
}%
\providecommand \url  [0]{\begingroup\@sanitize \@url }%
\providecommand \@url [1]{\endgroup\@href {#1}{\urlprefix}}%
\providecommand \urlprefix [0]{URL }%
\providecommand \Eprint[0]{\href }%
\@ifxundefined \urlstyle {%
  \providecommand \doi [1]{doi:\discretionary{}{}{}#1}%
}{%
  \providecommand \doi [0]{doi:\discretionary{}{}{}\begingroup
  \urlstyle{rm}\Url }%
}%
\providecommand \doibase [0]{http://dx.doi.org/}%
\providecommand \Doi[1]{\href{\doibase#1}}%
\providecommand \bibAnnote [3]{%
  \BibitemShut{#1}%
  \begin{quotation}\noindent
    \textsc{Key:}\ #2\\\textsc{Annotation:}\ #3%
  \end{quotation}%
}%
\providecommand \bibAnnoteFile [2]{%
  \IfFileExists{#2}{\bibAnnote {#1} {#2} {\input{#2}}}{}%
}%
\providecommand \typeout [0]{\immediate \write \m@ne }%
\providecommand \selectlanguage [0]{\@gobble}%
\providecommand \bibinfo [0]{\@secondoftwo}%
\providecommand \bibfield [0]{\@secondoftwo}%
\providecommand \translation [1]{[#1]}%
\providecommand \BibitemOpen[0]{}%
\providecommand \bibitemStop [0]{}%
\providecommand \bibitemNoStop [0]{.\EOS\space}%
\providecommand \EOS [0]{\spacefactor3000\relax}%
\providecommand \BibitemShut [1]{\csname bibitem#1\endcsname}%
%</preamble>
\bibitem{born-26-1}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{M.}~\bibnamefont{Born}},\ }%
  \bibfield{journal}{%
  \Doi{10.1007/BF01397477}{\bibinfo {journal} {Zeitschrift f{\"{u}}r Physik}}\
  }%
  \textbf{\bibinfo {volume} {37}},\ \bibinfo {pages} {863} (\bibinfo {year}
  {1926}),\ \url{http://dx.doi.org/10.1007/BF01397477}%
  \bibAnnoteFile{NoStop}{born-26-1}%
\bibitem{born-26-2}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{M.}~\bibnamefont{Born}},\ }%
  \bibfield{journal}{%
  \Doi{10.1007/BF01397184}{\bibinfo {journal} {Zeitschrift f{\"{u}}r Physik}}\
  }%
  \textbf{\bibinfo {volume} {38}},\ \bibinfo {pages} {803} (\bibinfo {year}
  {1926}),\ \url{http://dx.doi.org/10.1007/BF01397184}%
  \bibAnnoteFile{NoStop}{born-26-2}%
\bibitem{zeil-05_nature_ofQuantum}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{A.}~\bibnamefont{Zeilinger}},\ }%
  \bibfield{journal}{%
  \Doi{10.1038/438743a}{\bibinfo {journal} {Nature}}\ }%
  \textbf{\bibinfo {volume} {438}},\ \bibinfo {pages} {743} (\bibinfo {year}
  {2005}),\ \url{http://dx.doi.org/10.1038/438743a}%
  \bibAnnoteFile{NoStop}{zeil-05_nature_ofQuantum}%
\bibitem{2008-cal-svo}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{C.~S.}\ \bibnamefont{Calude}}\ and\ \bibinfo
  {author} {\bibfnamefont{K.}~\bibnamefont{Svozil}},\ }%
  \bibfield{journal}{%
  \Doi{10.1166/asl.2008.016}{\bibinfo {journal} {Advanced Science Letters}}\ }%
  \textbf{\bibinfo {volume} {1}},\ \bibinfo {pages} {165} (\bibinfo {month}
  {December}\ \bibinfo {year} {2008}),\
  \Eprint{http://arxiv.org/abs/arXiv:quant-ph/0611029}{arXiv:quant-ph/0611029}%
,\ \url{http://www.ingentaconnect.com/content/asp/asl/2008/00000001/00000002/a%
rt00004}%
  \bibAnnoteFile{NoStop}{2008-cal-svo}%
\bibitem{MartinL�f1966602}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{P.}~\bibnamefont{Martin-L{\"{o}}f}},\ }%
  \bibfield{journal}{%
  \Doi{10.1016/S0019-9958(66)80018-9}{\bibinfo {journal} {Information and
  Control}}\ }%
  \textbf{\bibinfo {volume} {9}},\ \bibinfo {pages} {602} (\bibinfo {year}
  {1966}),\ ISSN \bibinfo {issn} {0019-9958},\
  \url{http://dx.doi.org/10.1016/0030-4018(87)90271-9}%
  \bibAnnoteFile{NoStop}{MartinL�f1966602}%
\bibitem{chaitin:01}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{G.~J.}\ \bibnamefont{Chaitin}},\ }%
  \emph{\bibinfo {title} {Exploring Randomness}}\ (\bibinfo {publisher}
  {Springer Verlag},\ \bibinfo {address} {London},\ \bibinfo {year} {2001})%
  \bibAnnoteFile{NoStop}{chaitin:01}%
\bibitem{calude:02}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{C.}~\bibnamefont{Calude}},\ }%
  \emph{\bibinfo {title} {Information and Randomness---An Algorithmic
  Perspective}},\ \bibinfo {edition} {2nd}\ ed.\ (\bibinfo {publisher}
  {Springer},\ \bibinfo {address} {Berlin},\ \bibinfo {year} {2002})%
  \bibAnnoteFile{NoStop}{calude:02}%
\bibitem{svozil-qct}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{K.}~\bibnamefont{Svozil}},\ }%
  \bibfield{journal}{%
  \Doi{10.1016/0375-9601(90)90408-G}{\bibinfo {journal} {Physics Letters A}}\
  }%
  \textbf{\bibinfo {volume} {143}},\ \bibinfo {pages} {433} (\bibinfo {year}
  {1990}),\ \url{http://dx.doi.org/10.1016/0375-9601(90)90408-G}%
  \bibAnnoteFile{NoStop}{svozil-qct}%
\bibitem{rarity-94}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{J.~G.}\ \bibnamefont{Rarity}}, \bibinfo
  {author} {\bibfnamefont{M.~P.~C.}\ \bibnamefont{Owens}},\ and\ \bibinfo
  {author} {\bibfnamefont{P.~R.}\ \bibnamefont{Tapster}},\ }%
  \bibfield{journal}{%
  \Doi{10.1080/09500349414552281}{\bibinfo {journal} {Journal of Modern
  Optics}}\ }%
  \textbf{\bibinfo {volume} {41}},\ \bibinfo {pages} {2435} (\bibinfo {year}
  {1994}),\ \url{http://dx.doi.org/10.1080/09500349414552281}%
  \bibAnnoteFile{NoStop}{rarity-94}%
\bibitem{zeilinger:qct}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{T.}~\bibnamefont{Jennewein}}, \bibinfo
  {author} {\bibfnamefont{U.}~\bibnamefont{Achleitner}}, \bibinfo {author}
  {\bibfnamefont{G.}~\bibnamefont{Weihs}}, \bibinfo {author}
  {\bibfnamefont{H.}~\bibnamefont{Weinfurter}},\ and\ \bibinfo {author}
  {\bibfnamefont{A.}~\bibnamefont{Zeilinger}},\ }%
  \bibfield{journal}{%
  \Doi{10.1063/1.1150518}{\bibinfo {journal} {Review of Scientific
  Instruments}}\ }%
  \textbf{\bibinfo {volume} {71}},\ \bibinfo {pages} {1675} (\bibinfo {year}
  {2000}),\ \Eprint{http://arxiv.org/abs/quant-ph/9912118}{quant-ph/9912118},\
  \url{http://dx.doi.org/10.1063/1.1150518}%
  \bibAnnoteFile{NoStop}{zeilinger:qct}%
\bibitem{stefanov-2000}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{A.}~\bibnamefont{Stefanov}}, \bibinfo
  {author} {\bibfnamefont{N.}~\bibnamefont{Gisin}}, \bibinfo {author}
  {\bibfnamefont{O.}~\bibnamefont{Guinnard}}, \bibinfo {author}
  {\bibfnamefont{L.}~\bibnamefont{Guinnard}},\ and\ \bibinfo {author}
  {\bibfnamefont{H.}~\bibnamefont{Zbinden}},\ }%
  \bibfield{journal}{%
  \Doi{10.1080/095003400147908}{\bibinfo {journal} {Journal of Modern Optics}}\
  }%
  \textbf{\bibinfo {volume} {47}},\ \bibinfo {pages} {595} (\bibinfo {year}
  {2000}),\ \url{http://dx.doi.org/10.1080/095003400147908}%
  \bibAnnoteFile{NoStop}{stefanov-2000}%
\bibitem{0256-307X-21-10-027}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{M.}~\bibnamefont{Hai-Qiang}}, \bibinfo
  {author} {\bibfnamefont{W.}~\bibnamefont{Su-Mei}}, \bibinfo {author}
  {\bibfnamefont{Z.}~\bibnamefont{Da}}, \bibinfo {author}
  {\bibfnamefont{C.}~\bibnamefont{Jun-Tao}}, \bibinfo {author}
  {\bibfnamefont{J.}~\bibnamefont{Ling-Ling}}, \bibinfo {author}
  {\bibfnamefont{H.}~\bibnamefont{Yan-Xue}},\ and\ \bibinfo {author}
  {\bibfnamefont{W.}~\bibnamefont{Ling-An}},\ }%
  \bibfield{journal}{%
  \Doi{10.1088/0256-307X/21/10/027}{\bibinfo {journal} {Chinese Physics
  Letters}}\ }%
  \textbf{\bibinfo {volume} {21}},\ \bibinfo {pages} {1961} (\bibinfo {year}
  {2004}),\ \url{http://dx.doi.org/10.1088/0256-307X/21/10/027}%
  \bibAnnoteFile{NoStop}{0256-307X-21-10-027}%
\bibitem{wang:056107}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{P.~X.}\ \bibnamefont{Wang}}, \bibinfo
  {author} {\bibfnamefont{G.~L.}\ \bibnamefont{Long}},\ and\ \bibinfo {author}
  {\bibfnamefont{Y.~S.}\ \bibnamefont{Li}},\ }%
  \bibfield{journal}{%
  \Doi{10.1063/1.2338830}{\bibinfo {journal} {Journal of Applied Physics}}\ }%
  \textbf{\bibinfo {volume} {100}},\ \bibinfo {eid} {056107} (\bibinfo {year}
  {2006}),\ \url{http://dx.doi.org/10.1063/1.2338830}%
  \bibAnnoteFile{NoStop}{wang:056107}%
\bibitem{fiorentino:032334}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{M.}~\bibnamefont{Fiorentino}}, \bibinfo
  {author} {\bibfnamefont{C.}~\bibnamefont{Santori}}, \bibinfo {author}
  {\bibfnamefont{S.~M.}\ \bibnamefont{Spillane}}, \bibinfo {author}
  {\bibfnamefont{R.~G.}\ \bibnamefont{Beausoleil}},\ and\ \bibinfo {author}
  {\bibfnamefont{W.~J.}\ \bibnamefont{Munro}},\ }%
  \bibfield{journal}{%
  \Doi{10.1103/PhysRevA.75.032334}{\bibinfo {journal} {Physical Review A
  (Atomic, Molecular, and Optical Physics)}}\ }%
  \textbf{\bibinfo {volume} {75}},\ \bibinfo {eid} {032334} (\bibinfo {year}
  {2007}),\ \url{http://dx.doi.org/10.1103/PhysRevA.75.032334}%
  \bibAnnoteFile{NoStop}{fiorentino:032334}%
\bibitem{svozil-2009-howto}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{K.}~\bibnamefont{Svozil}},\ }%
  \bibfield{journal}{%
  \Doi{10.1103/PhysRevA.79.054306}{\bibinfo {journal} {Physical Review A
  (Atomic, Molecular, and Optical Physics)}}\ }%
  \textbf{\bibinfo {volume} {79}},\ \bibinfo {eid} {054306} (\bibinfo {year}
  {2009}),\ \Eprint{http://arxiv.org/abs/arXiv:0903.2744}{arXiv:0903.2744},\
  \url{http://dx.doi.org/10.1103/PhysRevA.79.054306}%
  \bibAnnoteFile{NoStop}{svozil-2009-howto}%
\bibitem{diehard}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{G.}~\bibnamefont{Marsaglia}},\ }%
  \enquote{\bibinfo {title} {The {M}arsaglia random number {CDROM} including
  the diehard battery of tests of randomness},}\  (\bibinfo {year} {1995}),\
  \url{http://www.stat.fsu.edu/pub/diehard/}%
  \bibAnnoteFile{NoStop}{diehard}%
\bibitem{Rukhin-nist}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{A.}~\bibnamefont{Rukhin}}, \bibinfo {author}
  {\bibfnamefont{J.}~\bibnamefont{Soto}}, \bibinfo {author}
  {\bibfnamefont{J.}~\bibnamefont{Nechvatal}}, \bibinfo {author}
  {\bibfnamefont{M.}~\bibnamefont{Smid}}, \bibinfo {author}
  {\bibfnamefont{E.}~\bibnamefont{Barker}}, \bibinfo {author}
  {\bibfnamefont{S.}~\bibnamefont{Leigh}}, \bibinfo {author}
  {\bibfnamefont{M.}~\bibnamefont{Levenson}}, \bibinfo {author}
  {\bibfnamefont{M.}~\bibnamefont{Vangel}}, \bibinfo {author}
  {\bibfnamefont{D.}~\bibnamefont{Banks}}, \bibinfo {author}
  {\bibfnamefont{A.}~\bibnamefont{Hekert}}, \bibinfo {author}
  {\bibfnamefont{J.}~\bibnamefont{Dray}},\ and\ \bibinfo {author}
  {\bibfnamefont{S.}~\bibnamefont{Vo}},\ }%
  \emph{\bibinfo {title} {A Statistical Test Suite for Random and Pseudorandom
  Number Generators for Cryptographic Applications. NIST Special Publication
  800-22}}\ (\bibinfo {publisher} {National Institute of Standards and
  Technology (NIST)},\ \bibinfo {year} {2001})\
  \url{http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22b.pdf}%
  \bibAnnoteFile{NoStop}{Rukhin-nist}%
\bibitem{1268777}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{P.}~\bibnamefont{L'Ecuyer}}\ and\ \bibinfo
  {author} {\bibfnamefont{R.}~\bibnamefont{Simard}},\ }%
  \bibfield{journal}{%
  \Doi{10.1145/1268776.1268777}{\bibinfo {journal} {ACM Transactions on
  Mathematical Software (TOMS)}}\ }%
  \textbf{\bibinfo {volume} {33}},\ \bibinfo {pages} {22} (\bibinfo {year}
  {2007}),\ ISSN \bibinfo {issn} {0098-3500},\
  \url{http://dx.doi.org/10.1145/1268776.1268777}%
  \bibAnnoteFile{NoStop}{1268777}%
\bibitem{Quantis}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibnamefont{{ID Quantique SA}}},\ }%
  \emph{\bibinfo {title} {{QUANTIS}. Quantum number generator}}\ (\bibinfo
  {publisher} {idQuantique},\ \bibinfo {address} {Geneva, Switzerland},\
  \bibinfo {year} {2001-2010})\
  \url{http://www.idquantique.com/images/stories/PDF/quantis-random-generator/%
quantis-whitepaper.pdf}%
  \bibAnnoteFile{NoStop}{Quantis}%
\bibitem{Vienna}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibnamefont{{{I}nstitut f{\"{u}}r {Q}uantenoptik und
  {Q}uanteninformation ({IQOQI})}}},\ }%
  \emph{\bibinfo {title} {Quantum number generator}}\ (\bibinfo {year} {2003})\
  \bibinfo {note} {personal communication}%
  \bibAnnoteFile{NoStop}{Vienna}%
\bibitem{MRG}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibnamefont{{Wolfram Research, Inc.}}},\ }%
  \emph{\bibinfo {title} {{M}athematica Edition: {V}ersion 6.0. {M}athematica
  random generator. {ExtendedCA} default."}}\ (\bibinfo {publisher} {Wolfram
  Research, Inc.},\ \bibinfo {address} {Waterloo, Ontario},\ \bibinfo {year}
  {2007})\
  \url{http://reference.wolfram.com/mathematica/tutorial/RandomNumberGeneratio%
n.html}%
  \bibAnnoteFile{NoStop}{MRG}%
\bibitem{MAPLE}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibnamefont{Maplesoft}},\ }%
  \emph{\bibinfo {title} {{M}aple Edition: {V}ersion 11. Maple random
  generator}}\ (\bibinfo {publisher} {Maplesoft},\ \bibinfo {address}
  {Champaign, Illinois},\ \bibinfo {year} {2007})\
  \url{http://www.maplesoft.com/support/help/Maple/view.aspx?path=rand}%
  \bibAnnoteFile{NoStop}{MAPLE}%
\bibitem{pi}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{Y.}~\bibnamefont{Kanada}}\ and\ \bibinfo
  {author} {\bibfnamefont{D.}~\bibnamefont{Takahashi}},\ }%
  \enquote{\bibinfo {title} {Calculation of $\pi$ up to 4,294,960,000 decimal
  digits},}\  (\bibinfo {year} {1995}),\ \url{ftp://pi.super-computing.org}%
  \bibAnnoteFile{NoStop}{pi}%
\bibitem{von-neumann1}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{J.}~\bibnamefont{von Neumann}},\ }%
  \bibfield{journal}{%
  \bibinfo {journal} {National Bureau of Standards Applied Math Series}\ }%
  \textbf{\bibinfo {volume} {12}},\ \bibinfo {pages} {36} (\bibinfo {year}
  {1951}),\ \bibinfo {note} {reprinted in {\sl John von Neumann, Collected
  Works, (Vol. V)}, A. H. Traub, editor, MacMillan, New York, 1963, p.
  768--770.}%
  \bibAnnoteFile{Stop}{von-neumann1}%
\bibitem{borel:09}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{{\'{E}}.}~\bibnamefont{Borel}},\ }%
  \bibfield{journal}{%
  \Doi{10.1007/BF03019651}{\bibinfo {journal} {Rendiconti del Circolo
  Matematico di Palermo (1884 - 1940)}}\ }%
  \textbf{\bibinfo {volume} {27}},\ \bibinfo {pages} {247} (\bibinfo {year}
  {1909}),\ \url{http://dx.doi.org/10.1007/BF03019651}%
  \bibAnnoteFile{NoStop}{borel:09}%
\bibitem{Hertling:jucs_8_2:simply_normal_numbers_to}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{P.}~\bibnamefont{Hertling}},\ }%
  \bibfield{journal}{%
  \Doi{10.3217/jucs-008-02-0235}{\bibinfo {journal} {Journal of Universal
  Computer Science}}\ }%
  \textbf{\bibinfo {volume} {8}},\ \bibinfo {pages} {235} (\bibinfo {year}
  {2002}),\ \url{http://dx.doi.org/10.3217/jucs-008-02-0235}%
  \bibAnnoteFile{NoStop}{Hertling:jucs_8_2:simply_normal_numbers_to}%
\bibitem{CDMTCS372}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{C.~S.}\ \bibnamefont{Calude}}, \bibinfo
  {author} {\bibfnamefont{M.~J.}\ \bibnamefont{Dinneen}}, \bibinfo {author}
  {\bibfnamefont{M.}~\bibnamefont{Dumitrescu}},\ and\ \bibinfo {author}
  {\bibfnamefont{K.}~\bibnamefont{Svozil}},\ }%
  \emph{\bibinfo {title} {How Random Is Quantum Randomness? (Extended
  Version)}},\ \bibinfo {type} {Report {CDMTCS}-372}\ (\bibinfo {institution}
  {Centre for Discrete Mathematics and Theoretical Computer Science, University
  of Auckland, Auckland, New Zealand},\ \bibinfo {year} {2009})\
  \Eprint{http://arxiv.org/abs/arXiv:0912.4379}{arXiv:0912.4379},\
  \url{http://arxiv.org/abs/0912.4379}%
  \bibAnnoteFile{NoStop}{CDMTCS372}%
\bibitem{MR2099021}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{B.~Y.}\ \bibnamefont{Ryabko}}\ and\ \bibinfo
  {author} {\bibfnamefont{A.~I.}\ \bibnamefont{Pestunov}},\ }%
  \bibfield{journal}{%
  \bibinfo {journal} {Problemy Peredachi Informatsii}\ }%
  \textbf{\bibinfo {volume} {40}},\ \bibinfo {pages} {73} (\bibinfo {year}
  {2004}),\ ISSN \bibinfo {issn} {0555-2923}%
  \bibAnnoteFile{NoStop}{MR2099021}%
\bibitem{MR2162569}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{B.~Y.}\ \bibnamefont{Ryabko}}\ and\ \bibinfo
  {author} {\bibfnamefont{V.~A.}\ \bibnamefont{Monarev}},\ }%
  \bibfield{journal}{%
  \bibinfo {journal} {J. Statist. Plann. Inference}\ }%
  \textbf{\bibinfo {volume} {133}},\ \bibinfo {pages} {95} (\bibinfo {year}
  {2005}),\ ISSN \bibinfo {issn} {0378-3758}%
  \bibAnnoteFile{NoStop}{MR2162569}%
\bibitem{solovay:84}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{R.}~\bibnamefont{Solovay}}\ and\ \bibinfo
  {author} {\bibfnamefont{V.}~\bibnamefont{Strassen}},\ }%
  \bibfield{journal}{%
  \Doi{10.1137/0206006}{\bibinfo {journal} {SIAM Journal on Computing}}\ }%
  \textbf{\bibinfo {volume} {6}},\ \bibinfo {pages} {84} (\bibinfo {year}
  {1977}),\ \bibinfo {note} {corrigendum in Ref.~\cite{solovay:118}},\
  \url{http://dx.doi.org/10.1137/0206006}%
  \bibAnnoteFile{NoStop}{solovay:84}%
\bibitem{ch-schw-78}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{G.~J.}\ \bibnamefont{Chaitin}}\ and\
  \bibinfo {author} {\bibfnamefont{J.~T.}\ \bibnamefont{Schwartz}},\ }%
  \bibfield{journal}{%
  \Doi{10.1002/cpa.3160310407}{\bibinfo {journal} {Communications on Pure and
  Applied Mathematics}}\ }%
  \textbf{\bibinfo {volume} {31}},\ \bibinfo {pages} {521} (\bibinfo {year}
  {1978}),\ \url{http://dx.doi.org/10.1002/cpa.3160310407}%
  \bibAnnoteFile{NoStop}{ch-schw-78}%
\bibitem{Pinch}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{R.~G.}\ \bibnamefont{Pinch}},\ }%
  \enquote{\bibinfo {title} {The {C}armichael numbers up to $10^{16}$},}\
  (\bibinfo {year} {1998}),\
  \Eprint{http://arxiv.org/abs/arXiv:math.NT/9803082}{arXiv:math.NT/9803082},\
  \url{http://arxiv.org/abs/math.NT/9803082}%
  \bibAnnoteFile{NoStop}{Pinch}%
\bibitem{Pinch07}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{R.~G.}\ \bibnamefont{Pinch}},\ }%
  in\ \emph{\bibinfo {booktitle} {Proceedings of Conference on Algorithmic
  Number Theory 2007. {TUCS} General Publication No 46}},\ \bibinfo {editor}
  {edited by\ \bibinfo {editor} {\bibfnamefont{A.-M.}\
  \bibnamefont{Ernvall-Hyt{\"{o}}nen}}, \bibinfo {editor}
  {\bibfnamefont{M.}~\bibnamefont{Jutila}}, \bibinfo {editor}
  {\bibfnamefont{J.}~\bibnamefont{Karhum{\"{a}}ki}},\ and\ \bibinfo {editor}
  {\bibfnamefont{A.}~\bibnamefont{Lepist{\"{o}}}}}\ (\bibinfo {publisher}
  {Turku Centre for Computer Science},\ \bibinfo {address} {Turku, Finland},\
  \bibinfo {year} {2007})\ pp.\ \bibinfo {pages} {129--131},\
  \url{http://tucs.fi/publications/attachment.php?fname=G46.pdf}%
  \bibAnnoteFile{NoStop}{Pinch07}%
\bibitem{Note1}%
  \BibitemOpen
  \bibinfo {note} {In fact, every ``decent'' Monte Carlo simulation algorithm
  in which tests are chosen according to an algorithmic random string produces
  a result which is not only true with high probability, but {\protect \it
  rigorously correct}~\cite {MR757602}.}%
  \bibAnnoteFile{Stop}{Note1}%
\bibitem{Note2}%
  \BibitemOpen
  \bibinfo {note} {There are 1,401,644 Carmichael numbers in the interval $[1,
  10^{18}]$.}%
  \bibAnnoteFile{Stop}{Note2}%
\bibitem{ZL:1978}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{J.}~\bibnamefont{Ziv}}\ and\ \bibinfo
  {author} {\bibfnamefont{A.}~\bibnamefont{Lempel}},\ }%
  \bibfield{journal}{%
  \bibinfo {journal} {IEEE Transactions on Information Theory}\ }%
  \textbf{\bibinfo {volume} {24}},\ \bibinfo {pages} {530} (\bibinfo {year}
  {1978}),\
  \url{http://www.di.uevora.pt/~mjsb/TI-03/Artigos/ziv78compression.pdf}%
  \bibAnnoteFile{NoStop}{ZL:1978}%
\bibitem{DBLP:conf/dlt/Calude93}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{C.}~\bibnamefont{Calude}},\ }%
  in\ \emph{\bibinfo {booktitle} {Developments in Language Theory}},\ \bibinfo
  {editor} {edited by\ \bibinfo {editor}
  {\bibfnamefont{G.}~\bibnamefont{Rozenberg}}\ and\ \bibinfo {editor}
  {\bibfnamefont{A.}~\bibnamefont{Salomaa}}}\ (\bibinfo {publisher} {World
  Scientific},\ \bibinfo {address} {Singapore},\ \bibinfo {year} {1994})\ pp.\
  \bibinfo {pages} {113--129},\ ISBN \bibinfo {isbn} {981-02-1645-9}%
  \bibAnnoteFile{NoStop}{DBLP:conf/dlt/Calude93}%
\bibitem{Wyner}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{A.~D.}\ \bibnamefont{Wyner}},\ }%
  \bibfield{journal}{%
  \bibinfo {journal} {IEEE Information Theory Society}}%
   (\bibinfo {year} {1994}),\
  \url{http://www.itsoc.org/people/awards-and-honors/claude-e.-shannon-award/W%
yner94Shannon.pdf/view}%
  \bibAnnoteFile{NoStop}{Wyner}%
\bibitem{Conover}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{W.~J.}\ \bibnamefont{Conover}},\ }%
  \emph{\bibinfo {title} {Practical Nonparametric Statistics}}\ (\bibinfo
  {publisher} {John Wiley \& Sons},\ \bibinfo {address} {New York},\ \bibinfo
  {year} {1999})\ p.\ \bibinfo {pages} {584}%
  \bibAnnoteFile{NoStop}{Conover}%
\bibitem{Shapiro-Wilk}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{S.~S.}\ \bibnamefont{Shapiro}}\ and\
  \bibinfo {author} {\bibfnamefont{M.~B.}\ \bibnamefont{Wilk}},\ }%
  \bibfield{journal}{%
  \Doi{10.1093/biomet/52.3-4.591}{\bibinfo {journal} {Biometrika}}\ }%
  \textbf{\bibinfo {volume} {52}},\ \bibinfo {pages} {591} (\bibinfo {year}
  {2005}),\ \url{http://dx.doi.org/10.1093/biomet/52.3-4.591}%
  \bibAnnoteFile{NoStop}{Shapiro-Wilk}%
\bibitem{Welch}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{B.~L.}\ \bibnamefont{Welch}},\ }%
  \bibfield{journal}{%
  \bibinfo {journal} {Biometrika}\ }%
  \textbf{\bibinfo {volume} {34}} (\bibinfo {year} {1947}),\ \doi{\bibinfo
  {doi} {10.1093/biomet/34.1-2.28}},\
  \url{http://dx.doi.org/10.1093/biomet/34.1-2.28}%
  \bibAnnoteFile{NoStop}{Welch}%
\bibitem{davis-58}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{M.}~\bibnamefont{Davis}},\ }%
  \emph{\bibinfo {title} {Computability and Unsolvability}}\ (\bibinfo
  {publisher} {McGraw-Hill},\ \bibinfo {address} {New York},\ \bibinfo {year}
  {1958})%
  \bibAnnoteFile{NoStop}{davis-58}%
\bibitem{solovay:118}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{R.}~\bibnamefont{Solovay}}\ and\ \bibinfo
  {author} {\bibfnamefont{V.}~\bibnamefont{Strassen}},\ }%
  \bibfield{journal}{%
  \Doi{10.1137/0207009}{\bibinfo {journal} {SIAM Journal on Computing}}\ }%
  \textbf{\bibinfo {volume} {7}},\ \bibinfo {pages} {118} (\bibinfo {year}
  {1978}),\ \url{http://dx.doi.org/10.1137/0207009}%
  \bibAnnoteFile{NoStop}{solovay:118}%
\bibitem{MR757602}%
  \BibitemOpen
  \bibfield{author}{%
  \bibinfo {author} {\bibfnamefont{C.}~\bibnamefont{Calude}}\ and\ \bibinfo
  {author} {\bibfnamefont{M.}~\bibnamefont{Zimand}},\ }%
  \bibfield{journal}{%
  \bibinfo {journal} {Internat. J. Comput. Math.}\ }%
  \textbf{\bibinfo {volume} {16}},\ \bibinfo {pages} {47} (\bibinfo {year}
  {1984}),\ ISSN \bibinfo {issn} {0020-7160}%
  \bibAnnoteFile{NoStop}{MR757602}%
\end{thebibliography}%

\end{document}


Needs["StatisticalPlots`"]

data1 = {163499, 67640, 180476, 144104, 108686, 159674, 106771,
   168633, 82720, 70857};
data2 = {82269, 92240, 96932, 101087, 73497, 81002, 99287, 113792,
   120271, 104109};
data3 = {155095, 239443, 180952, 149925, 283090, 253755, 294171,
   138175, 222444, 195497};
data4 = {126096, 92066, 142608, 157003, 226877, 178198, 154246,
   169242, 162837, 119562};
data5 = {68365, 84019, 91090, 58568, 107524, 92196, 67027, 76567,
   81577, 94227};

BoxWhiskerPlot[data3, data4, data1, data2, data5,
 BoxOrientation -> Vertical, FrameStyle -> Directive[Black, 20],
 AspectRatio -> 0.7,
 FrameTicks -> {{{3, "Maple"}, {4, "Mathematica"}, {1, "Quantis"}, {2,
      "Vienna"}, {5, "\[Pi]"}}, {{55000,
     ScientificForm[55000.0]}, {100000,
     ScientificForm[100000.0]}, {150000,
     ScientificForm[150000.0]}, {200000,
     ScientificForm[200000.0]}, {250000,
     ScientificForm[250000.0]}, {290000, ScientificForm[300000.0]}},
   None, None},
 BoxFillingStyle -> {Hue[0.25], Hue[0.25], Hue[0.5], Hue[0.5],
   Hue[0.15]}, BoxMedianStyle -> {{Red, Thick}}]

Export["/mytex/2010-QvPR-boxrandomwalk.eps", %, "EPS",
 ImageSize -> 500]

(******************************************************************)

sol1 = {96, 103, 120, 96, 112, 114, 93, 99, 96, 120};
sol2 = {139, 108, 140, 100, 112, 95, 96, 93, 110, 142};
sol3 = {101, 130, 110, 119, 104, 122, 103, 122, 99, 116};
sol4 = {100, 101, 115, 101, 119, 108, 109, 82, 91, 109};
sol5 = {100, 112, 128, 127, 105, 107, 88, 89, 107, 84};

BoxWhiskerPlot[sol3, sol4, sol1, sol2, sol5,
 BoxOrientation -> Vertical, FrameStyle -> Directive[Black, 20],
 AspectRatio -> 0.7,
 BoxLabels -> {"Quantis", "Vienna", "Maple", "Mathematica", "\[Pi]"},
 BoxFillingStyle -> {Hue[0.25], Hue[0.25], Hue[0.5], Hue[0.5],
   Hue[0.15]}, BoxMedianStyle -> {{Red, Thick}}]


Export["/mytex/2010-QvPR-boxsolovey.eps", %, "EPS", ImageSize -> 500]

(******************************************************************)

book1 = {72007, 62480, 7964, 108708, 38888, 98352, 14247, 55366,
   33028, 43076};
book2 = {13838, 62573, 12750, 46178, 35267, 8080, 4508, 47968, 23936,
   24285};
book3 = {28602, 156094, 83102, 49548, 92463, 151787, 100500, 108711,
   56417, 72665};
book4 = {53202, 15692, 9110, 97657, 75516, 62242, 36805, 71305, 73864,
    43245};
book5 = {47816, 10319, 41887, 39543, 8551, 34127, 54560, 55254, 42310,
    78408};


BoxWhiskerPlot[book3, book4, book1, book2, book5,
 BoxOrientation -> Vertical, FrameStyle -> Directive[Black, 20],
 AspectRatio -> 0.7,
 FrameTicks -> {{{3, "Maple"}, {4, "Mathematica"}, {1, "Quantis"}, {2,
      "Vienna"}, {5, "\[Pi]"}}, {{20000,ScientificForm[20000.0]}, {40000,ScientificForm[40000.0]},
    {60000, ScientificForm[60000.0]}, {80000,
     ScientificForm[80000.0]}, {100000,ScientificForm[100000.0]}, {120000,
     ScientificForm[120000.0]}, {140000, ScientificForm[140000.0]}},
    None, None},
 BoxLabels -> {"Maple", "Mathematica", "Quantis", "Vienna", "\[Pi]"},
 BoxFillingStyle -> {Hue[0.25], Hue[0.25], Hue[0.5], Hue[0.5],
   Hue[0.15]}, BoxMedianStyle -> {{Red, Thick}}]


Export["/mytex/2010-QvPR-boxbookstack.eps", %, "EPS", ImageSize -> 500]

(******************************************************************)

borel1 = {67024, 76399, 94505, 46558, 56951, 75311, 36380, 77506,
   49000, 22430};
borel2 = {39205, 49794, 8572, 57601, 31807, 17631, 62243, 86430,
   41983, 23403};
borel3 = {185680, 214267, 184965, 146802, 242861, 206682, 260048,
   180352, 222555, 228005};
borel4 = {458580, 386315, 394588, 356342, 339870, 273687, 77413,
   344591, 398306, 341092};
borel5 = {26376, 42285, 36301, 79027, 41745, 22645, 14256, 49716,
   49857, 40005};

BoxWhiskerPlot[borel3, borel4, borel1, borel2, borel5,
 BoxOrientation -> Vertical, FrameStyle -> Directive[Black, 20],
 AspectRatio -> 0.7,
 FrameTicks -> {{{3, "Maple"}, {4, "Mathematica"}, {1, "Quantis"}, {2,
      "Vienna"}, {5, "\[Pi]"}}, {{0, "0"}, {100000,
     ScientificForm[100000.0]}, {200000,
     ScientificForm[200000.0]}, {300000,
     ScientificForm[300000.0]}, {400000, ScientificForm[400000.0]}},
   None, None},
 BoxLabels -> {"Maple", "Mathematica", "Quantis", "Vienna", "\[Pi]"},
 BoxFillingStyle -> {Hue[0.25], Hue[0.25], Hue[0.5], Hue[0.5],
   Hue[0.15]}, BoxMedianStyle -> {{Red, Thick}}]

Export["/mytex/2010-QvPR-boxborelk2.eps", %, "EPS", ImageSize -> 500]
(******************************************************************)

L1 = {0.977227838, 0.978468414, 0.978733, 0.978520949, 0.978369444,
   0.978823949, 0.977641374, 0.97882497, 0.978270253, 0.978055283};
L2 = {0.9784009, 0.97759909, 0.9785063, 0.97845532, 0.97843962,
   0.97811941, 0.97822043, 0.97803142, 0.97763814, 0.97999276};
L3 = {0.97864864, 0.97826469, 0.97825807, 0.97790241, 0.97953766,
   0.97825144, 0.97863748, 0.97825765, 0.97849053, 0.97807963};
L4 = {0.97769911, 0.97869949, 0.97906296, 0.97918648, 0.97904328,
   0.97780733, 0.97857803, 0.97817371, 0.97722217, 0.97765397};
L5 = {0.97953631, 0.97869124, 0.97902058, 0.97815903, 0.97895426,
   0.97792903, 0.97890449, 0.97829445, 0.9799012, 0.97861807};

BoxWhiskerPlot[L3, L4, L1, L2, L5, BoxOrientation -> Vertical,
 FrameStyle -> Directive[Black, 20], AspectRatio -> 0.7,
 FrameTicks -> {{{3, "Maple"}, {4, "Mathematica"}, {1, "Quantis"}, {2,
      "Vienna"}, {5, "\[Pi]"}}, {0.9775, 0.9780, 0.9785, 0.9790,
    0.9795, 0.9800}, None, None},
 BoxLabels -> {"Maple", "Mathematica", "Quantis", "Vienna", "\[Pi]"},
 BoxFillingStyle -> {Hue[0.25], Hue[0.25], Hue[0.5], Hue[0.5],
   Hue[0.15]}, BoxMedianStyle -> {{Red, Thick}}]

Export["/mytex/2010-QvPR-boxLentropy.eps", %, "EPS", ImageSize -> 500]

(******************************************************************)
