\documentclass[aps,prl,twocolumn,superscriptaddress]{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\\Supplementary material}
\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}
\maketitle
\section{Symmetrization of detector efficiencies}\label{app:symmetrization}
  The experimental setup (Fig.~3 in main article) 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{Choice of compressor}\label{app:choice_compression}
  In order to evaluate the NCDs of the binary strings, we need to choose a
  compression algorithm that performs close to the Shannon limit. 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:
  \textit{lzma}~\cite{ref:lzma}, \textit{bzip2}~\cite{ref:bzip2}, \textit{gzip}~\cite{ref:gzip},
  and \textit{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}
    \centerline{\includegraphics[width = .5\textwidth]{figure_supp1.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 \textit{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 \textit{lzw} compressor fails this test, converging to a $Q$ of 0.37 for long string, while \textit{bzip2}, \textit{gzip}, and \textit{lzma} give a $Q$ 
  below $10^{-1}$.

  \begin{figure}
    \centerline{\includegraphics[width = .5\textwidth]{figure_supp2.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: \textit{bzip}, \textit{gzip}, and \textit{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 \textit{bzip} and \textit{gzip} perform better than \textit{lzma}, the latter shows a more uniform performance over the entire interval of $p$.
  It is reasonable to assume that the use of \textit{lzma} should reduce the possibility of artifacts in the estimation of the NCD also for the data obtained from the experiment.

\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}{7}%
\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 {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 {Seward}()}]{ref:bzip2}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {J.}~\bibnamefont
  {Seward}},\ }\href {http://www.bzip.org} {}\bibinfo {howpublished}
  {http://www.bzip.org/}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gailly}\ and\ \citenamefont {Adler}()}]{ref:gzip}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {J.-l.}\ \bibnamefont
  {Gailly}}\ and\ \bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Adler}},\
  }\href {http://www.gzip.org/} {}\bibinfo {howpublished}
  {http://www.gzip.org/}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Welch}(1984)}]{Welch:84}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {T.}~\bibnamefont
  {Welch}},\ }\href {\doibase 10.1109/MC.1984.1659158} {\bibfield  {journal}
  {\bibinfo  {journal} {Computer}\ }\textbf {\bibinfo {volume} {17}},\ \bibinfo
  {pages} {8} (\bibinfo {year} {1984})}\BibitemShut {NoStop}%
\bibitem [{ref()}]{ref:matlab}%
  \BibitemOpen
  \href@noop {} {}\bibinfo {howpublished} {MATLAB R2010a, The MathWorks, Inc.,
  Natick, Massachusetts, United States.}\BibitemShut {Stop}%
\bibitem [{\citenamefont {Matsumoto}\ and\ \citenamefont
  {Nishimura}(1998)}]{matsumoto:98}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont
  {Matsumoto}}\ and\ \bibinfo {author} {\bibfnamefont {T.}~\bibnamefont
  {Nishimura}},\ }\href {\doibase 10.1145/272991.272995} {\bibfield  {journal}
  {\bibinfo  {journal} {ACM Transactions on Modeling and Computer Simulation
  (TOMACS)}\ }\textbf {\bibinfo {volume} {8}},\ \bibinfo {pages} {3} (\bibinfo
  {year} {1998})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Marsaglia}\ and\ \citenamefont
  {Tsang}(2000)}]{marsaglia:00}%
  \BibitemOpen
  \bibfield  {author} {\bibinfo {author} {\bibfnamefont {G.}~\bibnamefont
  {Marsaglia}}\ and\ \bibinfo {author} {\bibfnamefont {W.~W.}\ \bibnamefont
  {Tsang}},\ }\href {http://www.jstatsoft.org/v05/i08} {\bibfield  {journal}
  {\bibinfo  {journal} {Journal of Statistical Software}\ }\textbf {\bibinfo
  {volume} {5}},\ \bibinfo {pages} {1} (\bibinfo {year} {2000})}\BibitemShut
  {NoStop}%
\end{thebibliography}%


\end{document}

