\documentclass[12pt]{iopart}
%DIF LATEXDIFF DIFFERENCE FILE
%DIF DEL compression_old.tex   Fri Aug 14 15:35:19 2015
%DIF ADD compression.tex       Mon Nov  2 14:29:36 2015
\usepackage{iopams}


\usepackage{graphicx}
% \usepackage{natbib}
\usepackage[breaklinks]{hyperref}
 %\usepackage{amsmath}


\newcommand{\ket}[1]{|{#1}\rangle}
\newcommand{\bra}[1]{\langle{#1}|}
\newcommand{\NID}{\rm{NID}}
\newcommand{\NCD}{\rm{NCD}}
%DIF < 
%DIF PREAMBLE EXTENSION ADDED BY LATEXDIFF
%DIF UNDERLINE PREAMBLE %DIF PREAMBLE
\RequirePackage[normalem]{ulem} %DIF PREAMBLE
\RequirePackage{color}\definecolor{RED}{rgb}{1,0,0}\definecolor{BLUE}{rgb}{0,0,1} %DIF PREAMBLE
\providecommand{\DIFaddtex}[1]{{\protect\color{blue}\uwave{#1}}} %DIF PREAMBLE
\providecommand{\DIFdeltex}[1]{{\protect\color{red}\sout{#1}}}                      %DIF PREAMBLE
%DIF SAFE PREAMBLE %DIF PREAMBLE
\providecommand{\DIFaddbegin}{} %DIF PREAMBLE
\providecommand{\DIFaddend}{} %DIF PREAMBLE
\providecommand{\DIFdelbegin}{} %DIF PREAMBLE
\providecommand{\DIFdelend}{} %DIF PREAMBLE
%DIF FLOATSAFE PREAMBLE %DIF PREAMBLE
\providecommand{\DIFaddFL}[1]{\DIFadd{#1}} %DIF PREAMBLE
\providecommand{\DIFdelFL}[1]{\DIFdel{#1}} %DIF PREAMBLE
\providecommand{\DIFaddbeginFL}{} %DIF PREAMBLE
\providecommand{\DIFaddendFL}{} %DIF PREAMBLE
\providecommand{\DIFdelbeginFL}{} %DIF PREAMBLE
\providecommand{\DIFdelendFL}{} %DIF PREAMBLE
%DIF END PREAMBLE EXTENSION ADDED BY LATEXDIFF
%DIF PREAMBLE EXTENSION ADDED BY LATEXDIFF
%DIF HYPERREF PREAMBLE %DIF PREAMBLE
\providecommand{\DIFadd}[1]{\texorpdfstring{\DIFaddtex{#1}}{#1}} %DIF PREAMBLE
\providecommand{\DIFdel}[1]{\texorpdfstring{\DIFdeltex{#1}}{}} %DIF PREAMBLE
%DIF END PREAMBLE EXTENSION ADDED BY LATEXDIFF

\begin{document}

\title{Probing the quantum-classical boundary with compression software}
\author{Hou Shun Poh$^1$, Marcin Markiewicz\DIFdelbegin \DIFdel{$^{2,3}$}\DIFdelend \DIFaddbegin \DIFadd{$^{2}$}\DIFaddend , Pawe{\l}
  Kurzy\'nski\DIFdelbegin \DIFdel{$^{1,4}$}\DIFdelend \DIFaddbegin \DIFadd{$^{1,3}$}\DIFaddend , Alessandro Cer\`{e}$^1$, Dagomir Kaszlikowski\DIFdelbegin \DIFdel{$^{1,5}$
  }\DIFdelend \DIFaddbegin \DIFadd{$^{1,4}$
  }\DIFaddend and Christian Kurtsiefer\DIFdelbegin \DIFdel{$^{1,5}$}\DIFdelend \DIFaddbegin \DIFadd{$^{1,4}$}\DIFaddend }
%\address{Center~for~Quantum~Technologies, National~University~of~Singapore,
%3 Science Drive 2, Singapore  117543}
%\author{Marcin Markiewicz$^{2,3}$}
%\address{Faculty~of~Physics, University~of~Warsaw,  ul. Pasteura 5, PL-02-093
%Warszawa, Poland}
%\address{Institute~of~Theoretical~Physics~and~Astrophysics, University~of~Gdansk, ul. Wita Stwosza 57, PL-80-952, Gdansk, Poland}
%\author{Pawe{\l} Kurzy\'nski$^{1,4}$}
%\address{Center~for~Quantum~Technologies, National~University~of~Singapore, 3 Science Drive 2, Singapore  117543}
%\address{Faculty~of~Physics, Adam~Mickiewicz~University, Umultowska 85, 61-614 Pozna\'{n}, Poland}
%\author{Alessandro Cer\`{e}$^1$}
%\address{Center~for~Quantum~Technologies, National~University~of~Singapore, 3 Science Drive 2, Singapore  117543}
%\author{Dagomir Kaszlikowski$^{1,5}$}
%\address{Center~for~Quantum~Technologies, National~University~of~Singapore,
%3 Science Drive 2, Singapore  117543}
%\address{Department~of~Physics,
%  National~University~of~Singapore, 2 Science Drive 3, Singapore  117542}
%\author{Christian Kurtsiefer$^{1,5}$}
\address{$^1$Center~for~Quantum~Technologies, National~University~of~Singapore,
3 Science Drive 2, Singapore  117543}
\DIFdelbegin %DIFDELCMD < \address{$^2$Faculty~of~Physics, University~of~Warsaw,  ul. Pasteura 5, PL-02-093
%DIFDELCMD < Warszawa, Poland}
%DIFDELCMD < \address{$^3$Institute~of~Theoretical~Physics~and~Astrophysics,
%DIFDELCMD <   University~of~Gdansk, ul. Wita Stwosza 57, PL-80-952, Gdansk, Poland}
%DIFDELCMD < \address{$^4$Faculty~of~Physics, Adam~Mickiewicz~University, Umultowska 85, 61-614 Pozna\'{n}, Poland}
%DIFDELCMD < \address{$^5$Department~of~Physics,
%DIFDELCMD <   National~University~of~Singapore, 2 Science Drive 3, Singapore  117542}
%DIFDELCMD < 
%%%
\DIFdelend \DIFaddbegin \address{$^2$Institute of Physics, Jagiellonian University, ul. Stanislawa Lojasiewicza 11, 30-348 Krakow, Poland}
%DIF > \address{$^3$Institute~of~Theoretical~Physics~and~Astrophysics,
%DIF >   University~of~Gdansk, ul. Wita Stwosza 57, PL-80-952, Gdansk, Poland}
\address{$^3$Faculty~of~Physics, Adam~Mickiewicz~University, Umultowska 85, 61-614 Pozna\'{n}, Poland}
\address{$^4$Department~of~Physics,
  National~University~of~Singapore, 2 Science Drive 3, Singapore  117542}
\DIFaddend 

\begin{abstract}
We \DIFdelbegin \DIFdel{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, }\DIFdelend \DIFaddbegin \DIFadd{adapt an algorithmic approach to the problem of local-realism in a bipartite scenario. We assume that local outcomes are simulated by spatially separated universal Turing machines. The outcomes are calculated from inputs encoding information about a local measurement setting and a description of the bipartite system sent to both parties. In general, such a description can encode some additional information not available in quantum theory, i.e., local hidden variables. Using the Kolmogorov complexity of local outcomes }\DIFaddend we derive an inequality \DIFdelbegin \DIFdel{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 that does not
  require the assumption of an }\emph{\DIFdel{independent identically distributed}}
  %DIFAUXCMD
\DIFdel{(}\DIFdelend \DIFaddbegin \DIFadd{that must be obeyed by any local realistic theory. Since the Kolmogorov complexity is in general uncomputable, we show that this inequality can be expressed in terms of lossless compression of the data generated in such experiments and that quantum mechanics violates it. Finally, we confirm experimentally our findings using polarisation-entengled photonic pairs and readily available compression software. We argue that our approach relaxes the }\DIFaddend i.i.d. \DIFdelbegin \DIFdel{) realization of photon pairs}\DIFdelend \DIFaddbegin \DIFadd{assumption, namely that individual bits in the outcome bit-strings do not have to be }\emph{\DIFadd{independent and identically distributed}}\DIFaddend .
\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.}
\DIFdelbegin \DIFdel{The idea that physical processes can be considered as computations done on some universal machines traces back to Turing and von
Neumann~\mbox{%DIFAUXCMD
\cite{Coveney:1996tx}}%DIFAUXCMD
. 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~\mbox{%DIFAUXCMD
\cite{Wolfram:1985je}}%DIFAUXCMD
. There are physical phenomena that cannot be traced with analytical tools, which further motivated a computational approach to physics~\mbox{%DIFAUXCMD
\cite{Moore:1990bn}}%DIFAUXCMD
. Moreover, the idea of quantum computation~\mbox{%DIFAUXCMD
\cite{Feynman:82} }%DIFAUXCMD
led to a discovery of a few problems efficiently traceable on quantum computers but not on classical ones~\mbox{%DIFAUXCMD
\cite{Shor:1994tb,Grover:1996}}%DIFAUXCMD
}\DIFdelend \DIFaddbegin 

\DIFadd{In a standard Bell scenario \mbox{%DIFAUXCMD
\cite{Bell} }%DIFAUXCMD
Alice and Bob share a bipartite system and each of them performs a randomly chosen local measurement on their subsystems. Next, Alice and Bob evaluate correlations between their outcomes. A violation of a suitable correlation-based Bell inequality refutes local realism.
}

\DIFadd{In order to calculate correlations one has to estimate probabilities $p(x,y|a,b)$ that Alice outcome is $x$ and Bob's is $y$, given the measurement settings are $a$ and $b$, respectively. This is done under the assumption that Alice and Bob perform their measurements on independent and identically distributed (i.i.d.) pairs of non-classically correlated systems and therefore one has $p(x,y|a,b)=N(x,y|a,b)/N(a,b)$. $N(x,y|a,b)$ is the number of times outcomes $x$ and $y$  detected when the measurements settings are $a$ and $b$, whereas $N(a,b)$ is the total number of measurements with settings $a$ and $b$}\DIFaddend .

\DIFaddbegin \DIFadd{An interesting information theoretic approach to Bell inequalities was proposed in 80's by Braunstein and Caves \mbox{%DIFAUXCMD
\cite{Braunstein:1988en}}%DIFAUXCMD
. Instead of using correlation functions they constructed a test of local realism using conditional Shannon entropies $H(a|b) = H(ab)-H(b)$, where $H(x)=-\sum_i p(x=x_i)\log_2 p(x=x_i)$. Although these inequalities are not tight their immediate advantage is that one does not need to worry about the labelling and they work for any number of outcomes. Instead, one is interested in a more fundamental problem, namely how much information about Alice's outcomes is contained in Bob's ones.
}

\DIFaddend The \DIFdelbegin \DIFdel{question arises if the complexity of the output of }\DIFdelend \DIFaddbegin \DIFadd{simplest information-theoretic Bell inequality is of the following form
}\begin{equation}\DIFadd{\label{BCi}
H(a_1|b_1) \leq H(a_1|b_1) + H(b_1|a_2) + H(a_2|b_1).
}\end{equation}
\DIFadd{It holds for local realism but it is violated by quantum theory.
}

\DIFadd{Although the method of Braunstein and Caves offers a conceptually new approach, it still requires estimation of probabilities $p(x,y|a,b)$. Therefore, actual experimental implementations of such information-theoretic tests are akin to the standard ones because they require an identical statistical analysis of data strings obtained by Alice and Bob. However, Shannon entropy of }\DIFaddend a \DIFdelbegin \DIFdel{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~\mbox{%DIFAUXCMD
\cite{Fuchs:1992vv}}%DIFAUXCMD
. 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~\mbox{%DIFAUXCMD
\cite{Li:2004kz}}%DIFAUXCMD
.Next, we use the fact that Kolmogorov complexity can be approximated by compression algorithms~\mbox{%DIFAUXCMD
\cite{Cilibrasi:2005jna}}%DIFAUXCMD
. We then compress experimental data obtained from polarization measurements on entangled photon pairs and show a violation of the classical bound.
}\DIFdelend
\DIFaddbegin \DIFadd{data string generated by an i.i.d. source has an important operational meaning. It tells us how much such a data string can be losslessly compressed~\mbox{%DIFAUXCMD
\cite{Shannon:1948iy}}%DIFAUXCMD
. Still, Shannon's source coding theorem is based on infinite data strings. In realistic situations data strings are finite and one faces a problem of finding a suitable algorithm for an efficient compression of a given finite data string.}\DIFaddend 

\DIFdelbegin \subsection{\DIFdel{Kolmogorov complexity}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdel{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$'}\DIFdelend \DIFaddbegin \DIFadd{For most data strings it is hard, or impossible, to prove that a compression algorithm we found is the best}\DIFaddend . However, this \DIFdelbegin \DIFdel{is not optimal: in many cases the program can be much shorter than the string itself. }%DIFDELCMD < 

%DIFDELCMD < %%%
\DIFdel{This brings us to the }\DIFdelend \DIFaddbegin \DIFadd{does not stop us from introducing a concept of the best possible compression algorithm for a given data string $x$. This is exactly the idea behind the Kolmogorov complexity. More formally, the }\DIFaddend concept of Kolmogorov complexity \DIFdelbegin \DIFdel{$K(x)$, }\DIFdelend \DIFaddbegin \DIFadd{requires a reference to a universal model of computation, for example a universal Turing machine (UTM). In this case the Kolmogorov complexity $K(x)$ of a data string $x$ is }\DIFaddend the \DIFdelbegin \DIFdel{minimal
length $l(\Lambda)$ of all programs }\DIFdelend \DIFaddbegin \DIFadd{length $l(\Lambda)$ of the shortest program }\DIFaddend $\Lambda$\DIFdelbegin \DIFdel{that reproduce a specific output
}\DIFdelend \DIFaddbegin \DIFadd{, which, when fed into a UTM, produces an output string }\DIFaddend $x$\DIFdelbegin \DIFdel{. 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~\mbox{%DIFAUXCMD
\cite{Li:2009wu}}%DIFAUXCMD
. In most cases }\DIFdelend \DIFaddbegin \DIFadd{. }\DIFaddend $K(x)$ is \DIFdelbegin \DIFdel{uncomputable~\mbox{%DIFAUXCMD
\cite{Cover:2006ub}}%DIFAUXCMD
.To circumvent this issue,  we can estimate $K(x)$ with some efficient lossless
compression }\DIFdelend \DIFaddbegin \DIFadd{in general uncomputable, however realistic compression algorithms }\DIFaddend $C(x)$ \DIFdelbegin \DIFdel{~\mbox{%DIFAUXCMD
\cite{Cilibrasi:2005jna}}%DIFAUXCMD
.}\DIFdelend \DIFaddbegin \DIFadd{bound it from above ~\mbox{%DIFAUXCMD
\cite{Cilibrasi:2005jna}}%DIFAUXCMD
, i.e.,  $K(x)\leq C(x)$. In addition, compression algorithms can be applied to data strings that are generated by non i.i.d. sources.
}\DIFaddend 

\DIFdelbegin \subsection{\DIFdel{Bipartite systems}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdel{We now extend this picture to }\DIFdelend \DIFaddbegin \DIFadd{We show that one can observe violations of local realism by studying compression rates $C(x)$ of realistic compression algorithms applied to outcomes of Bell tests. We derive a compression-based Bell inequality. Next, we experimentally test our inequality using a source of entangled photonic pairs. We observe a violation for properly chosen local measurement settings and a properly chosen compression algorithm. We note that our approach is related to an earlier one by Fuchs~\mbox{%DIFAUXCMD
\cite{Fuchs:1992vv} }%DIFAUXCMD
and that an alternative approach to non i.i.d. sources was discussed by Gill \mbox{%DIFAUXCMD
\cite{Gill}}%DIFAUXCMD
.
}

\section{\DIFadd{Algorithmic approach to Bell scenario}}

\DIFadd{Let us start with the following assumption: }\emph{\DIFadd{If there exists a local-realistic description of Bell measurements  then it can be encoded as a program for UTMs that output bit strings corresponding to measurement outcomes of a realistic experiment.}} \DIFadd{In fact, this assumption says that the physical Church-Turing thesis applies to hypothetical local hidden variables. Such program would contain full information about a physical system that is necessary to compute the outcomes of measurements performed on it, provided a description of a measurement setting is also available to the UTM (see Fig. \ref{fig0} top).
}

\begin{figure}
  \centerline{\includegraphics[width=.7\columnwidth]{figure1.eps}}
  \caption{\DIFaddFL{The figure and the caption has to be changed -- see references to this figure in the text.}}
  \label{fig0}
\end{figure}


\DIFadd{In particular, we consider }\DIFaddend two spatially separated \DIFdelbegin \DIFdel{UTM's  $U_A$ (Alice ) and $U_B$ (Bob ). If these machines cannot
communicate, they generate two output strings that }\DIFdelend \DIFaddbegin \DIFadd{UTMs: UTM$_A$ and UTM$_B$. Each UTM is fed with a program encoding information about a bipartite system shared between Alice and Bob and with an additional program encoding a local measurement setting $a_j$ and $b_k$ ($j,k=0,1$). Without loss of generality we can assume that both programs are concatenated, one after another, on a single bit string which is an input into the machine.
}

\DIFadd{The input programs to both machines }\DIFaddend are \DIFdelbegin \DIFdel{independent, although the programs fed into the machines can be correlated.
Moreover, the input programs are }\DIFdelend classical bit strings \DIFdelbegin \DIFdel{so }\DIFdelend \DIFaddbegin \DIFadd{and }\DIFaddend the correlations between them \DIFdelbegin \DIFdel{must be classical.
}%DIFDELCMD < 

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

%DIFDELCMD < %%%
\DIFdel{We consider a model experiment, similar to the Bell test~\mbox{%DIFAUXCMD
\cite{Bell}}%DIFAUXCMD
: a source emits pairs of photons traveling to two
separate polarization analyzers M}\DIFdelend \DIFaddbegin \DIFadd{result only from the shared information about the preparation ($\Lambda$). In addition, UTM}\DIFaddend $_A$ \DIFdelbegin \DIFdel{(Alice) and  M}\DIFdelend \DIFaddbegin \DIFadd{has no access to a description of a measurement setting  $b_k$ that was fed to UTM}\DIFaddend $_B$ \DIFdelbegin \DIFdel{(Bob). Each analyzer has two outputs labeled 0 }\DIFdelend \DIFaddbegin \DIFadd{and vice versa. Therefore, the output strings $x_j$ }\DIFaddend and \DIFdelbegin \DIFdel{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} ).
}%DIFDELCMD < 

%DIFDELCMD < \begin{figure}
%DIFDELCMD <   \centerline{\includegraphics[width=.7\columnwidth]{figure1.eps}}
%DIFDELCMD <   %%%
%DIFDELCMD < \caption{%
{%DIFAUXCMD
\DIFdelFL{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$.}} 
  %DIFAUXCMD
%DIFDELCMD < \label{fig0}
%DIFDELCMD < \end{figure}
%DIFDELCMD < 
%%%
\DIFdelend \DIFaddbegin \DIFadd{$y_k$, which simulate measurement outcomes, are solely computed from inputs $\Lambda;a_j$ and  $\Lambda;b_k$, respectively. Since both UTMs do not communicate, correlations between $x_j$ and $y_k$ can only originate from $\Lambda$. This implies that any posssible hidden variable must be encoded in $\Lambda$.
}\DIFaddend 

The \DIFdelbegin \DIFdel{output $x$ of each analyzer can be described as the output of a UTM, fed with the settings }\DIFdelend \DIFaddbegin \DIFadd{simulation is done in the following way (see Fig. \ref{fig0} bottom). One copy of a program $\Lambda$ is sent to Alice and another one to Bob. The first copy is concatenated with a description of a measurement setting }\DIFaddend $a_j$ \DIFdelbegin \DIFdel{or }\DIFdelend \DIFaddbegin \DIFadd{and fed into UTM$_A$, whereas the second one is concatenated with }\DIFaddend $b_k$ \DIFdelbegin \DIFdel{, 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. %DIF < 
Next, we describe the output of the experiment as the output of two local
non-communicating UTMs$U_A$ }\DIFdelend and \DIFdelbegin \DIFdel{$U_B$. We feed $\Lambda$ to both of them and obtain two output strings }\DIFdelend \DIFaddbegin \DIFadd{fed into UTM$_B$. At this point both UTMs start to compute and after some time the output strings $x_j$ and $y_k$ are produced. Next, we repeat the whole procedure but with different measurement settings. The goal is to produce all four pairs of bit strings: $\{x_0,y_0\}$}\DIFaddend , \DIFdelbegin \DIFdel{$x$
}\DIFdelend \DIFaddbegin \DIFadd{$\{x_0,y_1\}$, $\{x_1,y_0\}$ }\DIFaddend and \DIFdelbegin \DIFdel{$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. }\DIFdelend \DIFaddbegin \DIFadd{$\{x_1,y_1\}$.
}\DIFaddend 

\DIFdelbegin \DIFdel{The Kolmogorov complexity $K(x,y)$ of two bit stringsis the }\DIFdelend \DIFaddbegin \subsection{\DIFadd{Analysis of the outcome strings}}

\DIFadd{The core of the Bell test is to find a method to acquire some information about possible hidden variables from the measurement outcomes. In our case we have the output strings $\{x_j,y_k\}$ generated either by a computer simulation, or by physical systems. We want to infer from them something about the program capable of generating these strings on two spatially separated UTMs. The general idea is to compare the two bit strings using some mathematical tools. In the standard approach \mbox{%DIFAUXCMD
\cite{Bell} }%DIFAUXCMD
these tools are statistical, namely one estimates a probability that $x_j^{(n)}$ (the n-th bit of $x_j$) has the same value as $x_k^{(n)}$. These probabilities can be later used to calculate correlation functions $\langle a_j b_k\rangle$ or entropies $H(a_j|b_k)$, which can be plugged into relevant Bell inequalities. Here, we propose an algorithmic method of comparing these bit strings.
}

\DIFadd{Let us come back to the concept of the Kolmogorov complexity introduced in the beginning. We defined $K(x)$ as the }\DIFaddend length of the shortest program generating \DIFdelbegin \DIFdel{them simultaneously. $K(x, y)$ can be shorter than $K(x)\,+\,K(y)$ }\DIFdelend \DIFaddbegin \DIFadd{$x$ on a UTM. In the same way we can define $K(x,y)$ as the length of the shortest program generating both strings $x$ and $y$. Note, that }\DIFaddend if $x$ and $y$ are correlated \DIFdelbegin \DIFdel{- the more correlated they are , the simpler it is to compute one string knowing the other. }%DIFDELCMD < 

%DIFDELCMD < %%%
\DIFdel{A distance measure between }\DIFdelend \DIFaddbegin \DIFadd{one may have $K(x,y) < K(x) + K(y)$, i.e., a UTM can generate $y$ using some parts of the program that was designed for }\DIFaddend $x$\DIFaddbegin \DIFadd{. In our case we are interested in $K(x_j,y_k)$, $K(x_j)$ }\DIFaddend and \DIFdelbegin \DIFdel{$y$ called }\DIFdelend \DIFaddbegin \DIFadd{$K(y_k)$. In other words, we seek the shortest hidden variable descriptions of the Bell scenario. Note that if we assume that some hidden variable description exists, then there must exist the shortest such description.
}

\DIFadd{To this end we use the
}\DIFaddend \emph{Normalized Information Distance} (NID) \DIFdelbegin \DIFdel{was introduced in\mbox{%DIFAUXCMD
\cite{Li:2004kz}}%DIFAUXCMD
:
}\DIFdelend \DIFaddbegin \DIFadd{introduced in~\mbox{%DIFAUXCMD
\cite{Li:2004kz}
}%DIFAUXCMD
}\DIFaddend \begin{equation}
  \NID(x, y)\,=\,\frac{K(x,y)\,-\,\min\{K(x), K(y)\}}{\max\{K(x), K(y)\}}\,.
\end{equation}
\DIFdelbegin \DIFdel{The NID }\DIFdelend \DIFaddbegin \DIFadd{This distance }\DIFaddend is a metric \DIFdelbegin \DIFdel{and thus obeys the triangle inequality
}\begin{displaymath}\DIFdel{\label{eq:triangle}
  \NID(x, y)\,+\,\NID(y, z)\,\geq\,\NID(x, z)\,.
}\end{displaymath}
%DIFAUXCMD
\DIFdel{It holds }\DIFdelend up to a correction \DIFdelbegin \DIFdel{of order $\log(l(x))$, which can
be neglected for sufficiently long strings ~\mbox{%DIFAUXCMD
\cite{Li:2004kz}}%DIFAUXCMD
. }%DIFDELCMD < 

%DIFDELCMD < 
%DIFDELCMD < %%%
\subsection{\DIFdel{Information Inequality}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdel{We consider bit strings $x_{a_j}$ and $y_{b_k}$ generated by Alice and Bob
with fixed settings $a_j$ }\DIFdelend \DIFaddbegin \DIFadd{$\frac{\log_2 N}{N}$, where $N$ is the length of strings $x$ }\DIFaddend and \DIFdelbegin \DIFdel{$b_k$. Inequality ~(\ref{eq:triangle}) transforms to }\DIFdelend \DIFaddbegin \DIFadd{$y$. It compares $x$ and $y$ without detailed knowledge about their origin. If the two data strings are identical then $K(x,y)=K(x,x)=K(x)$. The last equality follows from the fact that in order to generate two copies of $x$ we can run the same program twice. In this case $NID(x,y)=0$. However, if $x$ and $y$ are uncorrelated then $K(x,y)=K(x)+K(y)$ and $NID(x,y)=1$. In general $0 \leq NID(x,y) \leq 1$.
}

\subsection{\DIFadd{Algorithmic Bell inequality}}

\DIFadd{We can use the metric properties of NID to construct a Bell inequality. Note, that the metric approach to Bell inequalities was used before in \mbox{%DIFAUXCMD
\cite{Santos,Schumacher,Triangle1,Triangle2}}%DIFAUXCMD
.
The NID obeys the triangle inequality
}\DIFaddend \begin{equation}\DIFdelbegin %DIFDELCMD < \label{eq:NID_a0b1}
%DIFDELCMD <   %%%
\DIFdelend \DIFaddbegin \label{eq:triangle}
  \DIFaddend \NID(x\DIFdelbegin \DIFdel{_{a_0}}\DIFdelend , y\DIFdelbegin \DIFdel{_{b_0}}\DIFdelend )\DIFaddbegin \DIFadd{\,}\DIFaddend +\DIFaddbegin \DIFadd{\,}\DIFaddend \NID(y\DIFdelbegin \DIFdel{_{b_0}}\DIFdelend , \DIFdelbegin \DIFdel{y_{b_1}}\DIFdelend \DIFaddbegin \DIFadd{z}\DIFaddend )\DIFaddbegin \DIFadd{\,}\DIFaddend \geq\DIFaddbegin \DIFadd{\,}\DIFaddend \NID(x\DIFdelbegin \DIFdel{_{a_0}}\DIFdelend , \DIFdelbegin \DIFdel{y_{b_1}}\DIFdelend \DIFaddbegin \DIFadd{z}\DIFaddend )\,.
\DIFdelbegin %DIFDELCMD < 
\end{equation}
%DIFDELCMD < %%%
\DIFdel{However, $\NID(y_{b_0}, y_{b_1})$ }\DIFdelend \DIFaddbegin %}
\DIFadd{In our case we can write the following
}\begin{equation}\DIFadd{\label{eq:NID_a0b1}
  \NID(x_{0}, y_{0})+\NID(y_{0}, y_{1})\geq\NID(x_{0}, y_{1})\,.
}\end{equation}

\DIFadd{However, $\NID(y_{0}, y_{1})$ }\DIFaddend cannot be determined experimentally because the strings \DIFdelbegin \DIFdel{$y_{b_0}$ and $ y_{b_1}$ come from measurements of incompatible observables. }\DIFdelend \DIFaddbegin \DIFadd{$y_{0}$ and $ y_{1}$ cannot be obtained at the same time since they come from incompatible measurements. Thus we follow a standard reasoning used in derivation of all known Bell inequalities (with a possible exception in \mbox{%DIFAUXCMD
\cite{Wolf:2015wc}}%DIFAUXCMD
). This is called }{\em \DIFadd{counterfactual definiteness}} \DIFadd{and it says that it is admissible to consider outcomes of unperformed experiments. We apply it to our case and assume that uncomputed strings have a definite Kolmogorov complexity.
}




\DIFaddend We therefore use the triangle inequality
\DIFdelbegin \DIFdel{$\NID(x_{a_1}, y_{b_0})+\NID(x_{a_1}, y_{b_1})\geq\NID(y_{b_0}, y_{b_1})\,,$
}\DIFdelend \DIFaddbegin \DIFadd{$\NID(x_{1}, y_{0})+\NID(x_{1}, y_{1})\geq\NID(y_{0}, y_{1})\,,$
}\DIFaddend and combine it with ~(\ref{eq:NID_a0b1}) % and (\ref{eq:NID_b0b1})
to get:
\begin{eqnarray}\label{eq:ineq}
  \NID(x\DIFdelbegin \DIFdel{_{a_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend , y\DIFdelbegin \DIFdel{_{b_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend )+\NID(x\DIFdelbegin \DIFdel{_{a_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend , y\DIFdelbegin \DIFdel{_{b_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend ) + &\NID(x\DIFdelbegin \DIFdel{_{a_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend , y\DIFdelbegin \DIFdel{_{b_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend )\geq \DIFdelbegin %DIFDELCMD < \nonumber\\
%DIFDELCMD <   &%%%
\DIFdelend \NID(x\DIFdelbegin \DIFdel{_{a_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend , y\DIFdelbegin \DIFdel{_{b_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend )\,.
\end{eqnarray}
\DIFaddbegin \DIFadd{As mentioned above, NID is only approximately a metric, therefore the above inequality holds up to a term $\frac{\log_2 N}{N}$.
}\DIFaddend 

\DIFdelbegin \DIFdel{We }\DIFdelend \DIFaddbegin \DIFadd{For convenience we }\DIFaddend introduce a parameter
$S'$ quantifying the degree of violation of (\ref{eq:ineq}):
\begin{eqnarray}\label{eq:ineq2}
  S' &=& \NID(x\DIFdelbegin \DIFdel{_{a_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend , y\DIFdelbegin \DIFdel{_{b_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend ) -  \NID(x\DIFdelbegin \DIFdel{_{a_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend ,y\DIFdelbegin \DIFdel{_{b_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend ) \DIFdelbegin %DIFDELCMD < \nonumber \\
%DIFDELCMD <   &%%%
\DIFdelend - \DIFdelbegin %DIFDELCMD < & %%%
\DIFdelend \NID(x\DIFdelbegin \DIFdel{_{a_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend ,y\DIFdelbegin \DIFdel{_{b_0}}\DIFdelend \DIFaddbegin \DIFadd{_{0}}\DIFaddend )\,-\,\NID(x\DIFdelbegin \DIFdel{_{a_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend ,y\DIFdelbegin \DIFdel{_{b_1}}\DIFdelend \DIFaddbegin \DIFadd{_{1}}\DIFaddend ) \leq 0
\end{eqnarray}
\DIFaddbegin \DIFadd{The violation of local realism occurs if $S'$ is positive.
}\DIFaddend 

To test \DIFdelbegin \DIFdel{this inequality, }\DIFdelend \DIFaddbegin \DIFadd{the positivity of $S'$ }\DIFaddend we have to address \DIFdelbegin \DIFdel{the following problem .
We }\DIFdelend \DIFaddbegin \DIFadd{a problem that also appears in standard Bell scenarios (for a suggested resolution see \mbox{%DIFAUXCMD
\cite{Wolf:2015wc}}%DIFAUXCMD
). For example, we }\DIFaddend can set up a source to generate entangled photon pairs in an arbitrary
state\DIFdelbegin \DIFdel{but }\DIFdelend \DIFaddbegin \DIFadd{. However, }\DIFaddend for every experimental run $i$\DIFaddbegin \DIFadd{, }\DIFaddend with the same preparation\DIFdelbegin \DIFdel{the
resulting string $x_{i,a_j}$ }\DIFdelend \DIFaddbegin \DIFadd{, the
generated local string $x_{j_i}$ }\DIFaddend can be different.
Consequently, the corresponding program $\Lambda_i$ \DIFdelbegin \DIFdel{is }\DIFdelend \DIFaddbegin \DIFadd{can be }\DIFaddend different for every
experimental run. \DIFaddbegin \DIFadd{Therefore, we need to argue why $NID(x_{j_i},y_{0_i})$ and $NID(x_{j_{i'}},y_{1_{i'}})$ can be considered simply as $NID(x_{j},y_{0})$ and $NID(x_{j},y_{1})$.
}\DIFaddend 

\DIFdelbegin \DIFdel{It is reasonable to assume }\DIFdelend \DIFaddbegin \DIFadd{To address this issue, we introduce a new assumption }\DIFaddend 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})$ \DIFaddbegin \DIFadd{up to a term $\frac{\log_2 N}{N}$. We call this assumption }{\em \DIFadd{uniform complexity}}\DIFadd{.
}

\DIFadd{Thus our inequality only applies to programs that have this property. It follows that if the inequality (\ref{eq:ineq2}) is violated, either local realism or uniform complexity are invalid. Uniform complexity can in principle be tested experimetnally}\DIFaddend .
\DIFdelbegin \DIFdel{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.
}\DIFdelend 

\DIFdelbegin \section{\DIFdel{Estimation of Kolmogorov complexity}}
%DIFAUXCMD
\addtocounter{section}{-1}%DIFAUXCMD
%DIF < \emph{Statistical vs. Algorithmic.}
  \DIFdel{In }\DIFdelend \DIFaddbegin \DIFadd{Another problem that needs to be resolved is that in }\DIFaddend general the Kolmogorov complexity
cannot be evaluated but it can be estimated. One can adapt two conceptually
different approaches. \DIFaddbegin \DIFadd{The first one, the statistical approach, results in an inequality that is similar to (\ref{BCi}). We will briefly discuss it, however since we aim at algorithmic approach we later focus on the other one.
}\DIFaddend 

\DIFdelbegin \subsection{\DIFdel{Statistical Approach}} 
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdelend \DIFaddbegin \subsubsection{\DIFadd{Statistical approach}}

\DIFaddend The statistical approach uses an ensemble \DIFaddbegin \DIFadd{$X$ }\DIFaddend of all possible \DIFaddbegin \DIFadd{$2^N$ bit strings of length }\DIFaddend $N$ \DIFdelbegin \DIFdel{-bit strings }\DIFdelend 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
figure~\ref{fig:violation_versus_separation}a.
The maximal violation is $S'=0.24$ for
$\theta\,=\,8.6^\circ$.
\DIFdelbegin %DIFDELCMD < \begin{figure}
%DIFDELCMD <   \hfill\includegraphics[width=0.85\columnwidth]{figure2.eps}
%DIFDELCMD <   %%%
%DIFDELCMD < \caption{%
{%DIFAUXCMD
%DIFDELCMD < \label{fig:violation_versus_separation}
%DIFDELCMD <     %%%
\DIFdelFL{Plots of $S$ versus angle of separation $\theta$.
    (a) Result obtained from (\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$.}}
%DIFAUXCMD
%DIFDELCMD < \end{figure}
%DIFDELCMD < %%%
\DIFdel{This statistical approach requires the assumption that output of the systems are }\emph{\DIFdel{independent identically distributed}} %DIFAUXCMD
\DIFdel{(i.i.d.).
}\DIFdelend 

\DIFdelbegin \subsection{\DIFdel{Algorithmic approach}}
%DIFAUXCMD
\addtocounter{subsection}{-1}%DIFAUXCMD
\DIFdelend \DIFaddbegin \subsubsection{\DIFadd{Algorithmic approach}}
\DIFaddend 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 (\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. \DIFaddbegin \DIFadd{Moreover, it was shown in \mbox{%DIFAUXCMD
\cite{Cilibrasi:2005jna} }%DIFAUXCMD
that NCD is a metric up to a term $\frac{\log_2 N}{N}$, therefore (}\label{eq:ineq3}\DIFadd{) holds up to the same term.
}\DIFaddend 


\DIFaddbegin \begin{figure}
  \hfill\includegraphics[width=0.85\columnwidth]{figure2.eps}
  \caption{\label{fig:violation_versus_separation}
    \DIFaddFL{Plots of $S$ versus angle of separation $\theta$.
    (a) Result obtained from (\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}
%DIF > %%%%%%%%%UP TO HERE%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\DIFaddend \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.

In order to evaluate the NCDs of the binary strings, we need to choose a
compression algorithm that performs close to the Shannon
limit~\cite{Shannon:1948iy}. This is
necessary to ensure that it does not introduce any unintended
artifacts that lead to an overestimation of the violation. Preferably we
want to work in the regime where the obtained NCDs
always underestimate the violation. For this purpose, we characterized
four compression algorithms implemented by freely available compression
programs:
LZMA~\cite{ref:lzma}, BZIP2~\cite{ref:bzip2}, GZIP~\cite{ref:gzip}
and LZW~\cite{Welch:84}. To eliminate the overhead associated with the compression of ASCII text files, we save data in a binary format.

For this characterization and a simulation of the experiment, we need to
generate a ``random'' string of bits (1, 0) or pairs of bits (00, 01, 10, and
11) of various length with various probability distributions.
We generate these strings using the \emph{MATLAB}~\cite{ref:matlab} function
\mbox{\emph{randsample()}} that uses the pseudo random number generator
\emph{mt19937ar} with a long period of $2^{19937} - 1$. It is based on the
Mersenne Twister~\cite{matsumoto:98}, with ziggurat~\cite{marsaglia:00} as the
algorithm that generates the required probability distribution. The complexity
of this (deterministic) source of pseudorandom numbers should be high enough
to {\emph not} be captured as algorithmic.


\begin{figure}
  \hfill\includegraphics[width=0.85\columnwidth]{figure3.eps}
  \caption{\label{fig:compression_ratio_singles}
    Comparison of the compression overhead $Q$ obtained using four different compression algorithms on pseudo-random strings of varying lengths. The expected value for an ideal compressor is 0.
    From this characterization we can exclude LZW as a useful compressor for our application.}
\end{figure}

The first part of this characterization involves establishing the minimum string length required for the compression algorithms to perform consistently.
We start by generating binary strings, $x$, with equal probability of 1's and 0's, i.e. random strings, of varying length.
For each $x$, we evaluate the compression overhead $Q$ as
\begin{equation}\label{eq:compression_overhead}
  Q=\frac{C(x)-H(x)} {l(x)}\,.
\end{equation}
For a good compressor, we expect $Q$ to be close to 0.
From Fig.~\ref{fig:compression_ratio_singles}, it can be seen that for all the compressors, $Q$ starts to converge after about $10^5$ bits, setting the minimum string length required for the compressors to work consistently.
The LZW compressor fails this test, converging to a $Q$ of 0.37 for long string, while BZIP2, GZIP and LZMA give a $Q$ below $10^{-1}$.

\begin{figure}
  \hfill\includegraphics[width=0.85\columnwidth]{figure4.eps}
  \caption{
    Compression overhead $Q$ for the string $xy$ as a function of the probability of pairwise correlation $p$ between the bits of the generating strings $x$ and $y$ for three different compressors: BZIP2, GZIP, and LZMA.
    \label{fig:compressibility_versus_correlation}}
\end{figure}

In the second part of this characterization, test the compressors with strings with a known amount of correlation.
We generate a random string $x$ of length $10^7$ using the same technique already described.
We then generate a second string $y$ of equal length and with probability $p$ of being correlated
to $x$.
For $p=0$ the two strings are equal, i.e. perfectly correlated.
For $p=0.5$ they are uncorrelated.

The two strings $x$ and $y$ are then combined to form the string $xy$: to avoid artifacts due to the limited data block size of the compression algorithms, the elements of $x$ and $y$ are interleaved.
We then compress $xy$ and evaluate the compression overhead $Q$ as a function of $p$.
The results for different compressors are shown in Fig.~\ref{fig:compressibility_versus_correlation}.
Although there are ranges of $p$ where BZIP2 and GZIP perform better than LZMA, the latter shows a more uniform performance over the entire interval of $p$.
It is reasonable to assume that the use of LZMA should reduce the possibility of artifacts in the estimation of the NCD also for the data obtained from the experiment.

%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}
  \hfill\includegraphics[width=.75\columnwidth]{figure5.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 (\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$.


\subsection{Symmetrization of detector efficiencies}\label{app:symmetrization}
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.
  The experimental setup (see figure~\ref{fig:setup}) uses four APDs:
  $D_{HA}$, $D_{VA}$ (Alice), and $D_{HB}$, $D_{VB}$ (Bob) to register photon pair events
  in the two spatial modes. By denoting events at $D_{H}$ and $D_{V}$ as 1 and
  0, the four possible output patterns are 00, 01, 10, and 11, where the least
  and most significant bit corresponds to the Alice and Bob mode,
  respectively. Due to differences in the the losses in the transmitted and
  reflected port of the PBS, efficiencies in coupling light into the APDs, and
  the quantum efficiencies of APDs, the detection efficiencies for the four
  output combinations are different.
  The resulting effective pair efficiencies are then given by the product of the
  contributing detection efficiencies $\eta_{VB}$, $\eta_{HB}$, $\eta_{VA}$, and $\eta_{HA}$.

  This asymmetry will skew the statistics of the measurement results.
  We symmetrize the effective pair efficiencies for each  $(\theta_{A}, \theta_{B})$
  measuring also the following settings for the half wave plates:
  $(\theta_{A}+45^\circ,\theta_{B})$,
  $(\theta_{A}, \theta_{B}+45^\circ)$,
  and $(\theta_{A}+45^\circ,\theta_{B}+45^\circ)$.
  This procedure swaps the output ports of the PBS at which each polarization state is detected.
  The resulting outcomes are then interleaved, providing an uniform detection
  probability for the four possible outcomes.
  The effective pair detection efficiency for all four combinations is then
  $(\eta_{VB}\,\eta_{VA}\,+\,\eta_{VB}\,\eta_{HA}\,+\,\eta_{HB}\,\eta_{VA}\,+\,\eta_{HB}\,\eta_{HA})/4$.


\section{Results}
The inequality is experimentally tested by evaluating $S$ in
(\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 (\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
(\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.

\section{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. \DIFdelbegin \DIFdel{We show
that this is not possible if one uses a computation paradigm of a local
UTM. Although this }\DIFdelend \DIFaddbegin \DIFadd{Although this point of view }\DIFaddend has been already extensively
\DIFdelbegin \DIFdel{researched }\DIFdelend \DIFaddbegin \DIFadd{used }\DIFaddend 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 \DIFdelbegin \DIFdel{local }\DIFdelend 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 (\ref{eq:ineq3}), which we
find violated in the specific case of polarization-entangled photon pairs.
Therefore, \DIFdelbegin \DIFdel{at least this physical processes can not }\DIFdelend \DIFaddbegin \DIFadd{no hidden variables can }\DIFaddend be encoded as programs
\DIFdelbegin \DIFdel{on local }\DIFdelend \DIFaddbegin \DIFadd{for spatially seprated }\DIFaddend 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 \DIFaddbegin \DIFadd{assumption that each bit in a data string comes from an }\DIFaddend i.i.d. \DIFdelbegin \DIFdel{assumption}\DIFdelend \DIFaddbegin \DIFadd{source}\DIFaddend . The
compression treats the string of data as a single entity, and does not ignore
correlations between subsequent string elements.
\DIFdelbegin \DIFdel{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.
}\DIFdelend 

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

\ack{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{iopart-num}
%\bibliography{compression}{}
\providecommand{\newblock}{}
\begin{thebibliography}{10}
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\eprint}[2][]{\url{#2}}
% Bibliography created with iopart-num v2.1
% /biblio/bibtex/contrib/iopart-num

\bibitem{Coveney:1996tx}
Coveney P~V and Highfield R 1996 {\em Frontiers of Complexity: The Search for
  Order in a Chaotic World\/} (Fawcett Columbine) ISBN 9780449910818

\bibitem{Wolfram:1985je}
Wolfram S 1985 {\em Phys. Rev. Lett.\/} {\bf 54} 735--738
  \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevLett.54.735}

\bibitem{Moore:1990bn}
Moore C 1990 {\em Phys. Rev. Lett.\/} {\bf 64} 2354--2357
  \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevLett.64.2354}

\bibitem{Feynman:82}
Feynman R~P 1982 {\em Int. J. Theor. Phys.\/} {\bf 21} 467--488
  \urlprefix\url{http://link.springer.com/10.1007/BF02650179}

\bibitem{Shor:1994tb}
Shor P~W 1994 Algorithms for quantum computation: discrete logarithms and
  factoring {\em Proceedings of the 35th Annual Symposium on Foundations of
  Computer Science\/} (Santa Fe, NM: IEEE) pp 124--134 ISBN 0818665807

\bibitem{Grover:1996}
Grover L~K 1996 A fast quantum mechanical algorithm for database search {\em
  Proceedings, 28th Annual ACM Symposium on the Theory of Computing\/} p 212
  \urlprefix\url{http://arxiv.org/abs/quant-ph/9605043}

\bibitem{Fuchs:1992vv}
Fuchs C~A 1992 Algorithmic information theory and the hidden variable question
  {\em Workshop on Squeezed States and Uncertainty Relations\/} NASA Conference
  Publication 3135 ed Han D, Kim Y~S and Zachary W~W (NASA, Washington, DC) pp
  83--85

\DIFaddbegin \bibitem{Gill}
\DIFadd{Gill R D 2003 Time, Finite Statistics, and Bell's Fifth Position
}{\em \DIFadd{Proc. of ``Foundations of Probability and Physics - 2''}}\DIFadd{, Ser. Math. Modelling in Phys., Engin., and Cogn. Sc., vol. 5 2002, V\"axj\"o Univ. Press pp. 179-206
}

\DIFaddend \bibitem{Li:2004kz}
Li M, Chen X, Li X, Ma B and Vit{\'a}nyi P~M~B 2004 {\em Information Theory,
  IEEE Transactions on\/} {\bf 50} 3250--3264

\bibitem{Cilibrasi:2005jna}
Cilibrasi R and Vit{\'a}nyi P~M~B 2005 {\em Information Theory, IEEE
  Transactions on\/} {\bf 51} 1523--1545

\bibitem{Li:2009wu}
Li M and Vitanyi P~M~B 2009 {\em An Introduction to Kolmogorov Complexity and
  Its Applications\/} Texts in Computer Science (Springer New York) ISBN
  9780387498201
\DIFaddbegin 

\bibitem{Santos}
\DIFadd{Santos E 1986 }{\em \DIFadd{Phys. Lett. A }} {\bf \DIFadd{115}} \DIFadd{363
}

\bibitem{Schumacher}
\DIFadd{Schumacher B W 1991 }{\em \DIFadd{Phys. Rev. A}} {\bf \DIFadd{44}} \DIFadd{7047
}

\bibitem{Triangle1}
\DIFadd{Kurzynski P Kaszlikowski D 2014 }{\em \DIFadd{Phys. Rev. A}} {\bf \DIFadd{89}} \DIFadd{012103
}

\bibitem{Triangle2}
\DIFadd{Wajs M, Kurzynski P and Kaszlikowski D 2015 }{\em \DIFadd{Phys. Rev. A}} {\bf \DIFadd{91}} \DIFadd{012114
}\DIFaddend 

\bibitem{Cover:2006ub}
Cover T~M and Thomas J~A 2006 {\em Elements of Information Theory\/} 2nd ed
  (Wiley-Interscience) ISBN 9780471748816

\bibitem{ref:lzma}
Pavlov I http://www.7-zip.org/sdk.html
  \urlprefix\url{http://www.7-zip.org/sdk.html}

\bibitem{Bell}
Bell J~S 1964 {\em Physics\/} {\bf 1} 195--200

\bibitem{Braunstein:1988en}
Braunstein S~L and Caves C~M 1988 {\em Phys. Rev. Lett.\/} {\bf 61} 662--665
  \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevLett.61.662}

\bibitem{Shannon:1948iy}
Shannon C~E 1948 {\em Bell System Technical Journal\/} {\bf 27} 379--423
  \urlprefix\url{http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6773024}

\bibitem{ref:bzip2}
Seward J http://www.bzip.org/ \urlprefix\url{http://www.bzip.org}

\bibitem{ref:gzip}
Gailly J~l and Adler M http://www.gzip.org/
  \urlprefix\url{http://www.gzip.org/}

\bibitem{Welch:84}
Welch T 1984 {\em Computer\/} {\bf 17} 8--19 ISSN 0018-9162

\bibitem{ref:matlab}
MATLAB R2010a, The MathWorks, Inc., Natick, Massachusetts, United States.

\bibitem{matsumoto:98}
Matsumoto M and Nishimura T 1998 {\em ACM Transactions on Modeling and Computer
  Simulation (TOMACS)\/} {\bf 8} 3--30

\bibitem{marsaglia:00}
Marsaglia G and Tsang W~W 2000 {\em Journal of Statistical Software\/} {\bf 5}
  1--7 ISSN 1548-7660 \urlprefix\url{http://www.jstatsoft.org/v05/i08}

\bibitem{kwiat:95}
Kwiat P~G, Mattle K, Weinfurter H, Zeilinger A, Sergienko A~V and Shih Y 1995
  {\em Phys. Rev. Lett.\/} {\bf 75} 4337--4341
  \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevLett.75.4337}

\bibitem{kurtsiefer:01}
Kurtsiefer C, Oberparleiter M and Weinfurter H 2001 {\em Phys. Rev. A\/} {\bf
  64} 023802

\bibitem{clauser:69}
Clauser J~F, Horne M, Shimony A and Holt R 1969 {\em Phys. Rev. Lett.\/} {\bf
  23} 880--884

\bibitem{Wolf:2015wc}
Wolf S 2015 {\em arXiv\/} (\textit{Preprint} \eprint{1505.07037})
  \urlprefix\url{http://arxiv.org/abs/1505.07037}

\end{thebibliography}



\end{document}
