\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 reproduce 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}. 
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}.

The question arises if the complexity of the output of a system can be used as
a signature of its non-classicality. 
In this paper we show that there are processes which cannot be 
reproduced on local universal Turing machines (UTM) at all,
independently of the available classical resources,
following a similar approach by Fuchs~\cite{Fuchs:1992vv}.
We first revisit the concept of Kolmogorov complexity,
a measure of the classical complexity of a phenomenon,
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 polarization 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}.

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 labeled 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. A Universal Turing machine (UTM) fed with a
    program $\Lambda_i$ and information about the settings
    $a_0$ or $a_1$ can reproduce the string of length $N$. The bottom part
    shows a model to reproduce correlated strings $x$ and $y$ generated from
    measurements on a bipartite system with local UTMs and 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 describe the output of the experiment as the output of 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.

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. 

A distance measure between $x$ and $y$ called \emph{Normalized Information
  Distance} (NID) was introduced in \cite{Li:2004kz}:
\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{Li:2004kz}.


% \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
$\NID(x_{a_1}, y_{b_0})+\NID(x_{a_1}, y_{b_1})\geq\NID(y_{b_0}, y_{b_1})\,,$
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
$\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 numerically generated
    data, 
    (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}
This statistical approach requires the assumption that output of the systems are \emph{independent identically distributed} (i.i.d.).

% \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}
Most compression algorithms use some prediction about the data composition. If
it matches this prediction, the compression can be done efficiently. 
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 (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 numerical simulation also verifies the angle that maximizes the
violation of (\ref{eq:ineq3}). The results of this 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}=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.

The Kolmogorov complexity of the output of local UTM must obey distance
properties  as  shown in~\cite{Li:2004kz,Cilibrasi:2005jna}, and can be
approximated by compression.
The distance properties lead to inequality Eq.~(\ref{eq:ineq3}), which we
find violated in the specific case of polarization-entangled photon pairs.
Therefore, at least this physical processes can not be encoded as programs
on local UTMs.

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. In addition, the algorithmic approach
does not use the notion of an ensemble and the i.i.d. assumption. The
compression treats the string of data as a single entity, and does not ignore
correlations between subsequent string elements. Our approach allows us
therefore to omit the notion of probability, at least for the case at hand. If
it can be extended to other quantum experiments, it would offer an alternative
with less assumptions to the commonly used statistical interpretation of
quantum theory.

We have become aware of a recent work by Wolf~\cite{Wolf:2015wc}
inspired by the ideas presented in this work, where this algorithmic approach
is used to  provide a different viewpoint on nonlocality that does not require
counterfactual reasoning.

\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}{}
\begin{thebibliography}{19}%
\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 {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 {Wolf}(2015)}]{Wolf:2015wc}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {S.}~\bibnamefont
  {Wolf}},\ }\href {http://arxiv.org/abs/1505.07037} {\bibfield  {journal}
  {\bibinfo  {journal} {arXiv}\ } (\bibinfo {year} {2015})},\ \Eprint
  {http://arxiv.org/abs/1505.07037} {1505.07037} \BibitemShut {NoStop}%
\end{thebibliography}%


\end{document}
