\documentclass[aps,prl,twocolumn,superscriptaddress, showpacs]{revtex4-1}

\usepackage{graphicx}
\usepackage{natbib}
\usepackage[breaklinks]{hyperref}
\newcommand{\ket}[1]{|{#1}\rangle}
\newcommand{\bra}[1]{\langle{#1}|}
\newcommand{\NID}{\text{NID}}
\newcommand{\NCD}{\text{NCD}}

\begin{document}

\title{Probing the quantum-classical boundary with compression software}
\author{Hou Shun Poh}
\affiliation{Center~for~Quantum~Technologies, National~University~of~Singapore,
3 Science Drive 2, Singapore  117543}
\author{Marcin Markiewicz}
\affiliation{Faculty~of~Physics, University~of~Warsaw,  ul. Pasteura 5, PL-02-093
Warszawa, Poland}
\affiliation{Institute~of~Theoretical~Physics~and~Astrophysics, University~of~Gdansk, ul. Wita Stwosza 57, PL-80-952, Gdansk, Poland}
\author{Pawe{\l} Kurzy\'nski}
\affiliation{Center~for~Quantum~Technologies, National~University~of~Singapore, 3 Science Drive 2, Singapore  117543}
\affiliation{Faculty~of~Physics, Adam~Mickiewicz~University, Umultowska 85, 61-614 Pozna\'{n}, Poland}
\author{Alessandro Cer\`{e}}
\affiliation{Center~for~Quantum~Technologies, National~University~of~Singapore, 3 Science Drive 2, Singapore  117543}
\author{Dagomir Kaszlikowski}
\affiliation{Center~for~Quantum~Technologies, National~University~of~Singapore,
3 Science Drive 2, Singapore  117543}
\affiliation{Department~of~Physics,
  National~University~of~Singapore, 2 Science Drive 3, Singapore  117542}
\author{Christian Kurtsiefer}
\affiliation{Center~for~Quantum~Technologies, National~University~of~Singapore,
3 Science Drive 2, Singapore  117543}
\affiliation{Department~of~Physics,
  National~University~of~Singapore, 2 Science Drive 3, Singapore  117542}

\begin{abstract}
  We experimentally demonstrate an impossibility to simulate quantum
  bipartite correlations with a deterministic universal Turing machine.
  We use the Normalized Information Distance (NID) that allows the comparison of two pieces of data without detailed knowledge about their origin.
  Using NID, we derive an inequality for output of two local deterministic universal Turing machines with correlated inputs.
  This inequality is violated by correlations generated by a maximally entangled polarization two-photon state.
  The violation is shown using a freely available lossless compressor. The presented technique may allow to complement the common statistical interpretation of quantum physics by an algorithmic one.
\end{abstract}

% insert suggested PACS numbers in braces on next line
\pacs{
03.67.-a,   % Quantum information
03.65.Ta,   % Foundations of quantum mechanics; measurement theory
42.50.Dv,   % Quantum state engineering and measurements (see also 03.65.Ud Entanglement and quantum nonlocality, e.g., EPR paradox, Bells inequalities, GHZ states, etc.)
89.20.Ff  % Computer science and technology
}
\keywords{Kolmogorov Complexity | Quantum correlations | Description of reality | Turing Machine}

\maketitle
% \section{Introduction}
\emph{Introduction.}  The idea that physical processes can be considered as computations done on some universal machines traces back to Turing and von
  Neumann~\cite{Coveney:1996tx}. The growth of the computational power allowed for further development of these concepts.
  This resulted in a completely new approach to science in which the complexity of observed phenomena is closely related to the complexity of computational resources needed to simulate them~\cite{Wolfram:1985je}.
  There are physical phenomena that cannot be traced with analytical tools,
  which further motivated a computational approach to physics~\cite{Moore:1990bn}.
  Moreover, the idea of quantum computation~\cite{Feynman:82} led to a
  discovery of a few problems efficiently traceable on quantum computers but not on classical ones~\cite{Shor:1994tb,Grover:1996}.

  Classical physics can be simulated on universal Turing machines (UTM), or other
  computationally equivalent models~\cite{Wolfram:2001ue}.  On the other hand,
  efficient simulation of quantum systems requires a replacement of
  deterministic UTM with 
  quantum computers whose states are non-classically correlated. Such machines
  can even simulate any local quantum system efficiently~\cite{Deutsch:1985ba,Lloyd:96}.
  Can we experimentally distinguish between these two descriptions of the universe
  using a logically self-contained computational approach?

  In this paper we show that
  there are processes which cannot be simulated on local UTM at all,
  independently of the available classical resources,
  following a simialr approach by Fuchs~\cite{Fuchs:1992vv}.
  We first introduce Kolmogorov complexity,
  a measure of the classical complexity of a phenomena,
  and later apply it to derive a bound on classical descriptions~\cite{Li:2004kz}. Next, we use the fact that Kolmogorov complexity can be approximated by compression algorithms~\cite{Cilibrasi:2005jna}.
  We then compress
  experimental data obtained from polarisation
  measurements on entangled photon pairs
  and show a violation of the classical bound.

  \emph{Kolmogorov complexity.} Consider the description of a machine, whether classical or quantum, that outputs a string $x$ of 0's and 1's. In the case of a UTM, we can always write a program $\Lambda$ that generates $x$.
  The simplest such program is obviously `PRINT $x$'.
  However, this is not optimal: in many cases the program can be much shorter than the string itself.

  This brings us to the concept of Kolmogorov complexity $K(x)$, the minimal
  length $l(\Lambda)$ of all programs $\Lambda$ that reproduce a specific output
  $x$. If $K(x)$ is comparable to
  the length of the output
  $l(x)$ then our algorithmic description of $x$ is inefficient, and $x$ is called algorithmically random~\cite{Li:2009wu}.
  In most cases $K(x)$ is uncomputable~\cite{Cover:2006ub}.
  To circumvent this issue, we can estimate $K(x)$ with some efficient lossless compression $C(x)$~\cite{Cilibrasi:2005jna}.

  \emph{Bipartite systems.} We now extend this picture to two spatially separated UTM's
  $U_A$ (Alice) and $U_B$ (Bob).
  If these machines cannot communicate,
  they generate two output strings that are independent,
  although the programs fed into the machines can be correlated.
  Moreover, the input programs are classical bit strings so the correlations between them must be classical.

  We determine the complexity of the strings using the
  \emph{Normalized Information Distance} (NID)~\cite{Li:2004kz}.
  This distance compares two data sets without detailed knowledge about their origin.
  In practice, we evaluate an approximation to the NID, the \emph{Normalized Compression Distance} (NCD)~\cite{Cilibrasi:2005jna}, using a lossless compression software, in our case the LZMA Utilities, based on the Lempel-Ziv-Markov chain algorithm~\cite{ref:lzma}.

% \section{Simulation by deterministic universal Turing machines}
  We consider a model experiment, similar to the Bell test~\cite{Bell}: a source emits pairs of photons traveling to two
  separate polarization analyzers M$_A$ (Alice) and M$_B$ (Bob).
  Each analyzer has two outputs labelled 0 and 1,
  and can be
  set along directions $a_0$ or $a_1$ for M$_A$, and $b_0$ or $b_1$ for M$_B$.
  The analyzers' outputs are bit strings (see figure~\ref{fig0}).

\begin{figure}
  \centerline{\includegraphics[width=.8\columnwidth]{figure1.eps}}
  \caption{Measurement: $N$ particles enter a measuring device
    characterized by two polarizer settings $a_0$ and $a_1$ generating $N$-outcome bit strings.
    Simulation: UTM is fed with a
    program $\Lambda_i$ and information about the chosen setting
    $a_0$ or $a_1$. It outputs string of length $N$. Simulation of
    correlated measurements: Local UTMs generate strings $x$ and
  $y$ according to a common program $\Lambda$. }
  \label{fig0}
\end{figure}

The output $x$ of each analyzer can be described as the output of a UTM, fed with the settings $a_j$ or $b_k$, and a program
$\Lambda$, which contains the information about generating the correct
output for every detection event and for every setting.
For a string of finite length $l(x)=N$, $\Lambda$ has to
describe the $4^N$ possible events. 
The length of the shortest $\Lambda$ is the Kolmogorov complexity of
the generated string.

Next, we consider the simulation of the experiment with two local
non-communicating UTMs $U_A$ and $U_B$.
We feed $\Lambda$ to both of them and obtain two output strings, $x$
and $y$, both of length $N$. The program has to describe the
behavior of all $2N$ events for all possible settings $a_j$ and $b_k$, hence
$16^N$ possibilities.

  % \subsection{Normalized Information Distance}
The Kolmogorov complexity $K(x,y)$ of two bit strings is the length of the shortest program generating them simultaneously. $K(x, y)$ can be shorter than $K(x)\,+\,K(y)$ if $x$ and $y$ are correlated - the more correlated they are, the simpler it is to compute one string knowing the other. 

Cilibrasi and Vitanyi~\cite{Cilibrasi:2005jna} constructed a distance measure between $x$ and $y$ called \emph{Normalized Information Distance} (NID),
  \begin{equation}
      \NID(x, y)\,=\,\frac{K(x,y)\,-\,\min\{K(x), K(y)\}}{\max\{K(x), K(y)\}}\,.
  \end{equation}

  The NID is a metric and thus obeys the triangle inequality
  \begin{equation}\label{eq:triangle}
      \NID(x, y)\,+\,\NID(y, z)\,\geq\,\NID(x, z)\,.
  \end{equation}
  It holds up to a correction of order $\log(l(x))$, which can
  be neglected for sufficiently long strings~\cite{Cilibrasi:2005jna}.


  % \subsection{Information Inequality}
  We consider bit strings $x_{a_j}$ and $y_{b_k}$ generated by Alice and Bob
  with fixed settings $a_j$ and $b_k$.
  Inequality ~(\ref{eq:triangle}) transforms to
  \begin{equation}\label{eq:NID_a0b1}
      \NID(x_{a_0}, y_{b_0})+\NID(y_{b_0}, y_{b_1})\geq\NID(x_{a_0}, y_{b_1})\,.
  \end{equation}
  However, $\NID(y_{b_0}, y_{b_1})$ cannot be determined experimentally because the strings $y_{b_0}$ and $ y_{b_1}$ come from measurements of incompatible observables.
  We therefore use the triangle inequality
  $
  % \begin{equation}\label{eq:NID_b0b1}
      \NID(x_{a_1}, y_{b_0})+\NID(x_{a_1}, y_{b_1})\geq\NID(y_{b_0}, y_{b_1})\,,
  % \end{equation}
  $
  and combine it with ~(\ref{eq:NID_a0b1}) % and (\ref{eq:NID_b0b1})
  to get:
  \begin{eqnarray}\label{eq:ineq}
      \NID(x_{a_0}, y_{b_0})+\NID(x_{a_1}, y_{b_0}) + &\NID(x_{a_1}, y_{b_1})\geq \nonumber\\
      &\NID(x_{a_0}, y_{b_1}).
  \end{eqnarray}

  We introduce a parameter
  $S'$ quantifying the degree of violation of Eq.~(\ref{eq:ineq}):
  \begin{eqnarray}\label{eq:ineq2}
     S' &=& \NID(x_{a_0}, y_{b_1}) -  \NID(x_{a_0},y_{b_0}) \nonumber \\
     &-& \NID(x_{a_1},y_{b_0})\,-\,\NID(x_{a_1},y_{b_1}) \leq 0
  \end{eqnarray}

  To test this inequality,
  we have to address the following problem.
  We can set up a source to generate entangled photon pairs in an arbitrary state but 
  for every experimental run $i$ with the same preparation the resulting string $x_{i,a_j}$ can be different.
  Consequently, the corresponding program $\Lambda_i$ is different for every experimental run.

  It is reasonable to assume that for every two experimental runs $i$ and $i'$ the complexity of the generated strings remains the same:
  $K(x_{i,a_j})\,=\,K(x_{i',a_j})$ and $K(x_{i,a_j}, y_{i,b_k})\,=\,K(x_{i',a_j}, y_{i',b_k})$.
  Without these assumptions the same physical preparation of the experiment has different consequences and thus the notion of preparation loses its meaning. More generally, the predictive power of science can be stated as: the same preparation results in the same complexity of observed phenomena.

% \section{Estimation of Kolmogorov complexity}

\emph{Statistical vs. Algorithmic.}  In general the Kolmogorov complexity cannot be evaluated but it can be estimated. One can adapt two conceptually different approaches.

  % \subsection{Statistical Approach} 
  The statistical approach uses an ensemble of all possible $N$-bit strings and looks for their average Kolmogorov complexity. The ensemble  average is the Shannon entropy $H(X)$~\cite{Cover:2006ub} and thus
  \begin{equation}\label{eq:nid_entropy}
      \langle \NID(x, y)\rangle=\frac{H(x, y)-\min\{H(x), H(y)\}}{\max\{H(x), H(y)\}}\,.
  \end{equation}

  Inequality~(\ref{eq:ineq}) becomes an entropic Bell inequality by Braunstein and
  Caves~\cite{Braunstein:1988en} if local entropies are maximal, i.e.,
  $H(x)=H(y)=N$. 
  They showed that for a maximally entangled polarization state of two photons
  and polarizer angles such that
  % \begin{eqnarray}
  %  \vec{a_0}\cdot\vec{b_1}&=&\cos 3\theta\,,\nonumber \\
  %  \vec{a_0}\cdot\vec{b_0}&=&\vec{a_1}\cdot\vec{b_0}=\vec{a_1}\cdot\vec{b_1}=\cos
  %  \theta\,,\label{eq:braunstein}
  % \end{eqnarray}
  $\vec{a_0}\cdot\vec{b_1}=\cos 3\theta\,$,
  $\vec{a_0}\cdot\vec{b_0}=\vec{a_1}\cdot\vec{b_0}=\vec{a_1}\cdot\vec{b_1}=\cos
   \theta$,
  inequality~(\ref{eq:ineq}) is violated for an appropriate range of $\theta$.
 An expected quantum value of $S'$ as a function of $\theta$ is shown in
  Fig.~\ref{fig:violation_versus_separation}a.
  The maximal violation is $S'=0.24$ for 
  $\theta\,=\,8.6^\circ$.

\begin{figure}
  \includegraphics[width=\columnwidth]{figure2.eps}
  \caption{\label{fig:violation_versus_separation}
  Plots of $S$ versus angle of separation $\theta$.
  (a) Result obtained from Eq.~(\ref{eq:nid_entropy})
  (b) result obtained from using the LZMA compressor on a simulated data ensemble,
  (c) measurement of $S$ in the experiment shown in figure~\ref{fig:setup},
  and (d) longer measurement at the optimal angle $\theta=8.6^\circ$.}
\end{figure}

  % \subsection{Algorithmic approach}
    On the other hand, it is possible to avoid a statistical description of our experiment following Ref.~\cite{Cilibrasi:2005jna} where it was shown that the Kolmogorov complexity can be well approximated by compression algorithms. In \cite{Cilibrasi:2005jna} the \emph{Normalized Compression Distance}~(NCD) is introduced
    \begin{equation}\label{eq:NCD}
        \NCD(x,y)=\frac{C(x,y)-\min\{C(x),C(y)\}}{\max\{C(x),C(y)\}}\,,
    \end{equation}
    where $C(x)$ is the length of the compressed string $x$, and $C(x,y)$ is the length of the compressed concatenated strings $x,y$.
    Replacing NID with NCD in Eq.~(\ref{eq:ineq2}) leads to a new inequality:
    \begin{eqnarray}\label{eq:ineq3}
       S'\rightarrow S&=&\NCD(x_{a_0},y_{b_1}) - \NCD(x_{a_0},y_{b_0}) \nonumber
       \\ &-&\NCD(x_{a_1},y_{b_0}) - \NCD(x_{a_1},y_{b_0}) \leq 0\,.
    \end{eqnarray}
    This expression can be tested experimentally because the NCD is operationally
    defined.

% \section{Choice of compressor}
  To conduct an experiment we need to ensure the suitability of the
  compression software we use to evaluate the NCD. For this, we 
  numerically simulate the outcome of an experiment based on a distribution of
  results predicted by quantum physics.
  Among the packages we tested, we found that the LZMA Utility~\cite{ref:lzma}
  approaches the Shannon limit~\cite{Shannon:1948iy} most closely.

Most compression algorithms use some prediction about the data composition. If it matches this prediction, the compression can be done efficiently. Our experimental data fit the specifics of the LZMA Utility (see the Supplementary materials). In general our method can be used for data from any source by finding a suitable compression algorithm~\cite{Cilibrasi:2005jna}. Thus, we are not limited to \emph{independent identically distributed} (i.i.d.) sources, as it is commonly assumed in standard statistical ensemble-based experiments, like, for instance, Bell-type tests.


The simulation also verifies the angle that maximizes the
violation~(\ref{eq:ineq3}).
The results of the simulation are presented in figure~\ref{fig:violation_versus_separation}.
More details on the generation of the simulated data and the choice of the compressor are provided in the Supplementary materials.

% \section{Experiment}

\begin{figure}
  \includegraphics[width=.9\columnwidth]{figure3.eps}
  \caption{Schematic of the experimental set-up. 
  Polarization correlations of entangled-photon pairs are measured by the polarization analyzers
  M$_A$ and M$_B$,
  each consisting of a half wave plate ($\lambda/2$) followed by a polarization beam splitter (PBS).
  All photons are detected by Avalanche photodetectors D$_H$ and D$_V$, and registered in a coincidence unit (CU).}
  \label{fig:setup}
\end{figure}

  \emph{Experiment.} In our experiment (see figure~\ref{fig:setup}), the output of a
  grating-stabilized laser diode (LD, central wavelength 405\,nm) passes
  through a single mode optical fiber (SMF) for spatial mode filtering, and is
  focused to a beam waist of 80\,${\mu}$m into a 2\,mm thick BBO crystal cut
  for type-II phase-matching. There, photon pairs are generated via
  spontaneous parametric down-conversion (SPDC) in a slightly non-collinear
  configuration.  A half-wave plate ($\lambda$/2) and a pair of compensation
  crystals (CC) take care of the temporal and transversal
  walk-off~\cite{kwiat:95}.
  Two spatial modes (A, B) of down-converted light, defined
  by the SMFs for 810\,nm, are matched to the pump mode to optimize
  the collection~\cite{kurtsiefer:01}. In type-II SPDC, each down-converted pair
  consists of an ordinary and extraordinarily polarized photon, corresponding to
  horizontal (H) and vertical (V) in our setup.  A pair of
  polarization controllers (PC) ensures that the SMFs do not affect the
  polarization of the collected photons. To arrive at an approximate singlet
  Bell state, the phase $\phi$ 
  between the two decay possibilities in the polarization state
  $\ket{\psi}=\frac{1}{\sqrt{2}}\left(\ket{H}_A\ket{V}_B+e^{i\phi}\ket{V}_A\ket{H}_B\right)$ is adjusted to $\phi=\pi$ by tilting the CC.

  In the polarization analyzers (figure~\ref{fig:setup}), photons from SPDC
  are projected onto arbitrary linear polarization by $\lambda$/2 plates, set
  to half of the analyzing angles $\theta_{A(B)}$, and
  polarization beam splitter in each analyzer.
  Photons are detected by avalanche photo diodes (APD), and corresponding detection events from the same pair identified by a coincidence unit if they arrive within $\approx\pm$3\,ns of each other.

  The quality of polarization entanglement is tested by probing the polarization
  correlations in a basis complementary to the intrinsic HV basis of the
  crystal.
  With interference filters (IF) of 5\,nm bandwidth (FWHM) centered at 810\,nm,
  in the $45^\circ$ linear polarization basis
  we observe a visibility $V_{45}$ = 99.9$\pm$0.1\%. The visibility in
  the natural H/V basis of the type-II down-conversion process also reaches
  $V_{\rm HV}$ = 99.9$\pm$0.1\%.
  A separate test of a CHSH-type Bell inequality~\cite{clauser:69}
  leads to a value of $S=2.826\pm0.0015$. This indicates a high quality
  of polarization entanglement; the uncertainties in the visibilities are obtained from propagated Poissonian counting statistics.

  % \subsection{Measurement and Data Post-processing}
  We record coincidences of detection events between
  detectors at A and B.
  For each PBS, the transmitted output is associated with 0 and the reflected one with 1.
  The
  resulting binary strings $x$ from A, and $y$ from B are written into two
  individual binary files.
  From these, we calculate the NCD using Eq.~(\ref{eq:NCD}).
  This procedure is repeated for each of the four settings ($a_0,b_0$), ($a_1,b_0$), ($a_1,b_1$), and ($a_0,b_1$) in order to obtain the value for $S$.

  To remove the bias due to differences in the detection efficiency of the APDs
  in the experiment, we also measure for each setting the associated orthogonal
  ones (see Supplementary materials for details).

% \section{Results}
  The inequality is experimentally tested by evaluating $S$ in
  Eq.~(\ref{eq:ineq3}) for a range of $\theta$; the
  results [points (c), (d) in figure~\ref{fig:violation_versus_separation}]
  are consistently lower than the trace (a) calculated via entropy
  using Eq.~(\ref{eq:nid_entropy}),
  and than a simulation with the same compressor (b).
  This is because the LZMA Utility is not working exactly at the Shannon limit,
  and also due to imperfect state generation and detection.

  For $\theta=8.6^\circ$ we collected results from a large number of photon
  pairs. Although we set out in this work to avoid a statistical argument in the
  interpretation of measurement results, we do resort to statistical techniques to
  assess the confidence in an experimental finding of a violation of inequality
  Eq.~(\ref{eq:ineq3}).
  To estimate an uncertainty of the experimentally obtained values for $S$,
  this large data set
  was subdivided
  into files with length greater than $10^5$ bits.
  The results from all these files are then averaged to obtain the
  final result of $S(\theta=8.6^\circ)$=\,0.0494$\,\pm\,$0.0076, with the latter
  indicating a relatively small standard deviation over these different subsets.

\emph{Discussion.} There is a trend to look at physical systems and processes as
  programs run on a computer made of the constituents of our universe. We show
  that this is not possible if one uses a computation paradigm of a local
  UTM. Although this has been already extensively
  researched in quantum information theory, we present a complementary
  algorithmic approach for an explicit, experimentally testable example.
  This algorithmic approach is complementary to the orthodox Bell inequality approach to quantum nonlocality~\cite{Bell} that is statistical in its nature.

  Any process that can be simulated on a local UTM can be encoded as a program that is fed into it. For every such a program there exists its shortest description (Kolmogorov complexity), which in most cases can only be  approximated by compression. Moreover, such a description must obey distance properties as shown in~\cite{Li:2004kz,Cilibrasi:2005jna}.
  By testing Eq.~(\ref{eq:ineq3}), we show that this is unattainable in the
  specific case of polarization-entangled photon pairs. Therefore, there
  exist physical processes that cannot be simulated on local UTMs.

  There are two fundamentally different notions of complexity in computer
  science. On one hand, computational complexity, mainly researched on in quantum information science, studies how much resources are needed to solve a computational problem. These studies focus on complexity classes such as P, NP~\cite{Papadimitriou:1994vk}, and its main concern is,  given an input program, how efficiently it can be computed. On the other hand, algorithmic complexity deals with a problem of what the most efficient encoding of an input program is. This complementary problem to computational complexity has not yet received enough attention 
  in quantum information science,
  and it would require a further work on a quantum version of Kolmogorov complexity~\cite{Mueller:2007wc}.

  We would like to stress that our analysis of the experimental data is purely
  and consistently algorithmic. We do not resort to statistical methods that are alien to the concept of computation. If this approach can be extended to all quantum experiments, it would replace the commonly used statistical interpretation of quantum theory.
 
\emph{Acknowledgments.} We acknowledge the support of this work by the National Research Foundation \&
  Ministry of Education in Singapore, partly through the Academic Research Fund MOE2012-T3-1-009. P.K. and D.K. are also supported by the Foundational Questions Institute (FQXi).
  A.C. also thanks Andrea Baronchelli for the hints on the use of compression software.


\bibliographystyle{apsrev4-1}
% \bibliography{compression.bib}{}


%merlin.mbs apsrev4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked
%Control: key (0)
%Control: author (72) initials jnrlst
%Control: editor formatted (1) identically to author
%Control: production of article title (-1) disabled
%Control: page (0) single
%Control: year (1) truncated
%Control: production of eprint (0) enabled
\begin{thebibliography}{23}%
\makeatletter
\providecommand \@ifxundefined [1]{%
 \@ifx{#1\undefined}
}%
\providecommand \@ifnum [1]{%
 \ifnum #1\expandafter \@firstoftwo
 \else \expandafter \@secondoftwo
 \fi
}%
\providecommand \@ifx [1]{%
 \ifx #1\expandafter \@firstoftwo
 \else \expandafter \@secondoftwo
 \fi
}%
\providecommand \natexlab [1]{#1}%
\providecommand \enquote  [1]{``#1''}%
\providecommand \bibnamefont  [1]{#1}%
\providecommand \bibfnamefont [1]{#1}%
\providecommand \citenamefont [1]{#1}%
\providecommand \href@noop [0]{\@secondoftwo}%
\providecommand \href [0]{\begingroup \@sanitize@url \@href}%
\providecommand \@href[1]{\@@startlink{#1}\@@href}%
\providecommand \@@href[1]{\endgroup#1\@@endlink}%
\providecommand \@sanitize@url [0]{\catcode `\\12\catcode `\$12\catcode
  `\&12\catcode `\#12\catcode `\^12\catcode `\_12\catcode `\%12\relax}%
\providecommand \@@startlink[1]{}%
\providecommand \@@endlink[0]{}%
\providecommand \url  [0]{\begingroup\@sanitize@url \@url }%
\providecommand \@url [1]{\endgroup\@href {#1}{\urlprefix }}%
\providecommand \urlprefix  [0]{URL }%
\providecommand \Eprint [0]{\href }%
\providecommand \doibase [0]{http://dx.doi.org/}%
\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}%
\let\auto@bib@innerbib\@empty
%</preamble>
\bibitem [{\citenamefont {Coveney}\ and\ \citenamefont
  {Highfield}(1996)}]{Coveney:1996tx}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {P.~V.}\ \bibnamefont
  {Coveney}}\ and\ \bibinfo {author} {\bibfnamefont {R.}~\bibnamefont
  {Highfield}},\ }\href@noop {} {\emph {\bibinfo {title} {Frontiers of
  Complexity: The Search for Order in a Chaotic World}}}\ (\bibinfo
  {publisher} {Fawcett Columbine},\ \bibinfo {year} {1996})\BibitemShut
  {NoStop}%
\bibitem [{\citenamefont {Wolfram}(1985)}]{Wolfram:1985je}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {S.}~\bibnamefont
  {Wolfram}},\ }\href {\doibase 10.1103/PhysRevLett.54.735} {\bibfield
  {journal} {\bibinfo  {journal} {Phys. Rev. Lett.}\ }\textbf {\bibinfo
  {volume} {54}},\ \bibinfo {pages} {735} (\bibinfo {year} {1985})}\BibitemShut
  {NoStop}%
\bibitem [{\citenamefont {Moore}(1990)}]{Moore:1990bn}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {C.}~\bibnamefont
  {Moore}},\ }\href {\doibase 10.1103/PhysRevLett.64.2354} {\bibfield
  {journal} {\bibinfo  {journal} {Phys. Rev. Lett.}\ }\textbf {\bibinfo
  {volume} {64}},\ \bibinfo {pages} {2354} (\bibinfo {year}
  {1990})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Feynman}(1982)}]{Feynman:82}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {R.~P.}\ \bibnamefont
  {Feynman}},\ }\href {\doibase 10.1007/BF02650179} {\bibfield  {journal}
  {\bibinfo  {journal} {Int. J. Theor. Phys.}\ }\textbf {\bibinfo {volume}
  {21}},\ \bibinfo {pages} {467} (\bibinfo {year} {1982})}\BibitemShut
  {NoStop}%
\bibitem [{\citenamefont {Shor}(1994)}]{Shor:1994tb}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {P.~W.}\ \bibnamefont
  {Shor}},\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {Proceedings of the
  35th Annual Symposium on Foundations of Computer Science}}}\ (\bibinfo
  {publisher} {IEEE},\ \bibinfo {address} {Santa Fe, NM},\ \bibinfo {year}
  {1994})\ pp.\ \bibinfo {pages} {124--134}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Grover}(1996)}]{Grover:1996}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {L.~K.}\ \bibnamefont
  {Grover}},\ }in\ \href {http://arxiv.org/abs/quant-ph/9605043} {\emph
  {\bibinfo {booktitle} {Proceedings, 28th Annual ACM Symposium on the Theory
  of Computing}}}\ (\bibinfo {year} {1996})\ p.\ \bibinfo {pages}
  {212}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Wolfram}(2001)}]{Wolfram:2001ue}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {S.}~\bibnamefont
  {Wolfram}},\ }\href@noop {} {\emph {\bibinfo {title} {New Kind of
  Science?}}}\ (\bibinfo  {publisher} {Wolfram Media, Inc.},\ \bibinfo {year}
  {2001})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Deutsch}(1985)}]{Deutsch:1985ba}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {D.}~\bibnamefont
  {Deutsch}},\ }\href {\doibase 10.1098/rspa.1985.0070} {\bibfield  {journal}
  {\bibinfo  {journal} {Proceedings of the Royal Society of London A:
  Mathematical, Physical and Engineering Sciences}\ }\textbf {\bibinfo {volume}
  {400}},\ \bibinfo {pages} {97} (\bibinfo {year} {1985})}\BibitemShut
  {NoStop}%
\bibitem [{\citenamefont {Lloyd}(1996)}]{Lloyd:96}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {S.}~\bibnamefont
  {Lloyd}},\ }\href {\doibase 10.1126/science.273.5278.1073} {\bibfield
  {journal} {\bibinfo  {journal} {Science}\ }\textbf {\bibinfo {volume}
  {273}},\ \bibinfo {pages} {1073} (\bibinfo {year} {1996})}\BibitemShut
  {NoStop}%
\bibitem [{\citenamefont {Fuchs}(1992)}]{Fuchs:1992vv}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {C.~A.}\ \bibnamefont
  {Fuchs}},\ }in\ \href@noop {} {\emph {\bibinfo {booktitle} {Workshop on
  Squeezed States and Uncertainty Relations}}},\ \bibinfo {series and number}
  {NASA Conference Publication 3135},\ \bibinfo {editor} {edited by\ \bibinfo
  {editor} {\bibfnamefont {D.}~\bibnamefont {Han}}, \bibinfo {editor}
  {\bibfnamefont {Y.~S.}\ \bibnamefont {Kim}}, \ and\ \bibinfo {editor}
  {\bibfnamefont {W.~W.}\ \bibnamefont {Zachary}}}\ (\bibinfo {address} {NASA,
  Washington, DC},\ \bibinfo {year} {1992})\ pp.\ \bibinfo {pages}
  {83--85}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Li}\ \emph {et~al.}(2004)\citenamefont {Li},
  \citenamefont {Chen}, \citenamefont {Li}, \citenamefont {Ma},\ and\
  \citenamefont {Vit{\'a}nyi}}]{Li:2004kz}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont
  {Li}}, \bibinfo {author} {\bibfnamefont {X.}~\bibnamefont {Chen}}, \bibinfo
  {author} {\bibfnamefont {X.}~\bibnamefont {Li}}, \bibinfo {author}
  {\bibfnamefont {B.}~\bibnamefont {Ma}}, \ and\ \bibinfo {author}
  {\bibfnamefont {P.~M.~B.}\ \bibnamefont {Vit{\'a}nyi}},\ }\href {\doibase
  10.1109/TIT.2004.838101} {\bibfield  {journal} {\bibinfo  {journal}
  {Information Theory, IEEE Transactions on}\ }\textbf {\bibinfo {volume}
  {50}},\ \bibinfo {pages} {3250} (\bibinfo {year} {2004})}\BibitemShut
  {NoStop}%
\bibitem [{\citenamefont {Cilibrasi}\ and\ \citenamefont
  {Vit{\'a}nyi}(2005)}]{Cilibrasi:2005jna}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {R.}~\bibnamefont
  {Cilibrasi}}\ and\ \bibinfo {author} {\bibfnamefont {P.~M.~B.}\ \bibnamefont
  {Vit{\'a}nyi}},\ }\href {\doibase 10.1109/TIT.2005.844059} {\bibfield
  {journal} {\bibinfo  {journal} {Information Theory, IEEE Transactions on}\
  }\textbf {\bibinfo {volume} {51}},\ \bibinfo {pages} {1523} (\bibinfo {year}
  {2005})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Li}\ and\ \citenamefont {Vitanyi}(2009)}]{Li:2009wu}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont
  {Li}}\ and\ \bibinfo {author} {\bibfnamefont {P.~M.~B.}\ \bibnamefont
  {Vitanyi}},\ }\href@noop {} {\emph {\bibinfo {title} {An Introduction to
  Kolmogorov Complexity and Its Applications}}},\ Texts in Computer Science\
  (\bibinfo  {publisher} {Springer New York},\ \bibinfo {year}
  {2009})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cover}\ and\ \citenamefont
  {Thomas}(2006)}]{Cover:2006ub}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {T.~M.}\ \bibnamefont
  {Cover}}\ and\ \bibinfo {author} {\bibfnamefont {J.~A.}\ \bibnamefont
  {Thomas}},\ }\href@noop {} {\emph {\bibinfo {title} {Elements of Information
  Theory}}},\ \bibinfo {edition} {2nd}\ ed.\ (\bibinfo  {publisher}
  {Wiley-Interscience},\ \bibinfo {year} {2006})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Pavlov}()}]{ref:lzma}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {I.}~\bibnamefont
  {Pavlov}},\ }\href {http://www.7-zip.org/sdk.html} {}\bibinfo {howpublished}
  {http://www.7-zip.org/sdk.html}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Bell}(1964)}]{Bell}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {J.~S.}\ \bibnamefont
  {Bell}},\ }\href@noop {} {\bibfield  {journal} {\bibinfo  {journal}
  {Physics}\ }\textbf {\bibinfo {volume} {1}},\ \bibinfo {pages} {195}
  (\bibinfo {year} {1964})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Braunstein}\ and\ \citenamefont
  {Caves}(1988)}]{Braunstein:1988en}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {S.~L.}\ \bibnamefont
  {Braunstein}}\ and\ \bibinfo {author} {\bibfnamefont {C.~M.}\ \bibnamefont
  {Caves}},\ }\href {\doibase 10.1103/PhysRevLett.61.662} {\bibfield  {journal}
  {\bibinfo  {journal} {Phys. Rev. Lett.}\ }\textbf {\bibinfo {volume} {61}},\
  \bibinfo {pages} {662} (\bibinfo {year} {1988})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Shannon}(1948)}]{Shannon:1948iy}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {C.~E.}\ \bibnamefont
  {Shannon}},\ }\href {\doibase 10.1002/j.1538-7305.1948.tb01338.x} {\bibfield
  {journal} {\bibinfo  {journal} {Bell System Technical Journal}\ }\textbf
  {\bibinfo {volume} {27}},\ \bibinfo {pages} {379} (\bibinfo {year}
  {1948})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Kwiat}\ \emph {et~al.}(1995)\citenamefont {Kwiat},
  \citenamefont {Mattle}, \citenamefont {Weinfurter}, \citenamefont
  {Zeilinger}, \citenamefont {Sergienko},\ and\ \citenamefont
  {Shih}}]{kwiat:95}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {P.~G.}\ \bibnamefont
  {Kwiat}}, \bibinfo {author} {\bibfnamefont {K.}~\bibnamefont {Mattle}},
  \bibinfo {author} {\bibfnamefont {H.}~\bibnamefont {Weinfurter}}, \bibinfo
  {author} {\bibfnamefont {A.}~\bibnamefont {Zeilinger}}, \bibinfo {author}
  {\bibfnamefont {A.~V.}\ \bibnamefont {Sergienko}}, \ and\ \bibinfo {author}
  {\bibfnamefont {Y.}~\bibnamefont {Shih}},\ }\href
  {http://link.aps.org/doi/10.1103/PhysRevLett.75.4337} {\bibfield  {journal}
  {\bibinfo  {journal} {Phys. Rev. Lett.}\ }\textbf {\bibinfo {volume} {75}},\
  \bibinfo {pages} {4337} (\bibinfo {year} {1995})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Kurtsiefer}\ \emph {et~al.}(2001)\citenamefont
  {Kurtsiefer}, \citenamefont {Oberparleiter},\ and\ \citenamefont
  {Weinfurter}}]{kurtsiefer:01}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {C.}~\bibnamefont
  {Kurtsiefer}}, \bibinfo {author} {\bibfnamefont {M.}~\bibnamefont
  {Oberparleiter}}, \ and\ \bibinfo {author} {\bibfnamefont {H.}~\bibnamefont
  {Weinfurter}},\ }\href {\doibase 10.1103/PhysRevA.64.023802} {\bibfield
  {journal} {\bibinfo  {journal} {Phys. Rev. A}\ }\textbf {\bibinfo {volume}
  {64}},\ \bibinfo {pages} {023802} (\bibinfo {year} {2001})}\BibitemShut
  {NoStop}%
\bibitem [{\citenamefont {Clauser}\ \emph {et~al.}(1969)\citenamefont
  {Clauser}, \citenamefont {Horne}, \citenamefont {Shimony},\ and\
  \citenamefont {Holt}}]{clauser:69}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {J.~F.}\ \bibnamefont
  {Clauser}}, \bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Horne}},
  \bibinfo {author} {\bibfnamefont {A.}~\bibnamefont {Shimony}}, \ and\
  \bibinfo {author} {\bibfnamefont {R.}~\bibnamefont {Holt}},\ }\href@noop {}
  {\bibfield  {journal} {\bibinfo  {journal} {Phys. Rev. Lett.}\ }\textbf
  {\bibinfo {volume} {23}},\ \bibinfo {pages} {880} (\bibinfo {year}
  {1969})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Papadimitriou}(1994)}]{Papadimitriou:1994vk}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {C.~H.}\ \bibnamefont
  {Papadimitriou}},\ }\href@noop {} {\emph {\bibinfo {title} {Computational
  Complexity}}},\ Theoretical computer science\ (\bibinfo  {publisher}
  {Addison-Wesley},\ \bibinfo {year} {1994})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Mueller}()}]{Mueller:2007wc}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont
  {Mueller}},\ }\href {http://arxiv.org/abs/0712.4377} {Ph.D. thesis},\
  \bibinfo  {school} {Technical University of Berlin}, \bibinfo {address}
  {Berlin}\BibitemShut {NoStop}%
\end{thebibliography}%


\end{document}
