Reply to referee

Dear Editor,

first of all, we would like to thank both referees for their constructive comments, and the depth of analysis they did with this manuscript. As the changes in he updated manuscript are quite extensive, we would like to go through the issues raised point by point:

Referee 1:

We are happy that the Referee appreciate the relevance of our work. We have corrected the typos indicated (and quite some more..). 

We also have added the following sentence to the second paragraph of Section 3 to further clarify the connection between compressor choice, NCD, and NID:  

"This is necessary to ensure that the $\NCD$ is a good approximation of the $\NID$, and that it does not introduce any unintended artifacts that lead to an overestimation of the violation." We hope to have made it sufficiently clear that the transition from NID to NCD is a critical step that warrants some attention.


Referee 2:

First of all we thank the Referee for the detailed critique presented. While we do not agree with all the points, we feel that it helped us make the message in this draft of the manuscript clearer. Specifically, we re-wrote the first part of section 2, and split off the second part of the old section in a separate section 3 ("Estimation of the Kolmogorov complexity...").

C1 & 5 & 9) [because they are related]:
We think that the classification proposed by the referee, (parties, settings, outcomes), misses an important point of every Bell test: the statistics necessary to evaluate the correlations.
 If we were to follow the line of argument of the referee, experimentally, all inequalities are then (parties, settings, outcomes^N), with N representing the number of repetitions of the test - because this is the only way how a correlation between polarizations (or other degrees of freedom) can be experimentally established. We point this out right at the beginning of our re-written section 2.

We are also not sure why FSSO would be "The natural way to test such a Bell inequality". If we were applying this same statement to the standard Bell inequality we would fall into the "freedom of choice" loophole.
Then, following along in this line of reasoning, including the basis switching, all Bell test the referee defined as (2,2,2) are in fact (2, 2^N, 2^N) experimentally, to be then reduced to the terms of the inequality by replacing probabilities with frequencies.

We claim that our approach includes the realization part already in its definition, avoiding to resort to statistics to move from a (2, 2^N, 2^N) experiment to a (2,2,2) theory. When it comes to inequality (9), we do not compute the probability of all possible 2^N outcomes. We instead measure, with the necessary computational approximations, a property of the generated strings, i.e., distances between strings pairs. Although this is similar to standard Bell inequalities in spirit, we do not think it can be classified based on the possible number of N-bit strings outputs.

We are then puzzled by this statement: "[...]You would never do this with the output of a Turing machine".
The output of a UTM is a string of bits and, as such, it can be manipulated - it is just classical information. This is exactly what we do to extract the four pairs of strings we use in the inequality. After a closer inspection, it is easy to realize that this operation is technically identical to what happens for every standard Bell inequality: the measurement outputs of every run are collected based on the measurement
setting on A and B side in order to obtain correlations between a given setting.

We are confused by the reason to ask for the removal of figure 1. The figure depicts in its upper part how the the output of a standard quantum measurement can be described in terms of the output of a UTM. We feel this illustrates the connection we are trying to make between a physical system and a corresponding generation of results through a UTM, supplied with a program and information on measurement bases.  In its lower part, it represents the computational system that given the same inputs of a standard Bell test (the sequence of basis settings) reproduce its output: a sequence of bits.  Under the same assumption used for the derivation of the standard Bell inequality. i.e. spacial separation and non communication of the two parties, we derive inequality (9).
The sequences of bits used in the figure are purely representative, not a numerical example. As such, we think it is useful to understand the concept, certainly not as a concrete example of inequality test that, as explained later in the article, requires much longer strings. We did remove a few spurious graphical elements in the figure, though (an additional 1, and an index for the program Lambda).

We also do not understand why the Referee ask us to analyze the strings only after sorting them by the basis choice of a single side. As in the case of a standard Bell test, the sorting is based on the basis choice on BOTH sides.
Similarly, the argument that the UTM in the experiment only output noise, is in agreement with what we expect from standard interpretation of Bell inequality: the sequence of outputs from any of the parties, if not correlated with the other party, is a sequence of random numbers. Obtaining a different result from our computational approach would be surprising, and a possible indication of a wrong approach.

Then, as a reply to the comment that: "But now the Turing machine model in Figure 1 is completely uninteresting because the Turing machine can only output noise": that is why we consider two UTMs sharing a program. What is interesting is the maximum correlation detectable in the two output strings according to a local-realistic model of computation compared to the one detectable for a quantum system.
We make explicit reference to the work of Braunstein and Caves. We indicate how through statistics, i.e., the estimation of probabilities from the observed frequencies, their entropic inequality is an estimation of inequality (9) thanks to the connection between Shannon entropy and Kolmogorov complexity.

After stating our point of view, we do not believe that restricting the inequality to FSSO cases, as suggested by the referee, is justified.
The derivation of inequality (9) does not make use of any FSSO assumption, separated from the uniformity of complexity we introduced to clarify our working assumptions.

As for the FSSO nature of the experimental demonstrations, we explicitly indicate that it is an operative assumption to allow us to carry on a proof of principle demonstration.

Nonetheless, we agree that some part of the manuscript could generate some confusion on the analysis of the output strings. A substantial re-organization and rewriting of section 2 (which now is split in two
sections) makes it difficult to indicate a detailed difference to the previous manuscript version, but we start with the hopefully clearer comparison of this work with previous Bell tests:

"The core of any test for local realism is to acquire some information about possible hidden variables from measurement outcomes. The standard approach for Bell tests is based on the statistical inference of correlations between measurements. This implies repeating an experiment many times, sorting the results according to the measurement basis, and estimating the probability of each possible outcome from the observed frequencies.
The algorithmic approach we present, instead, considers the output of a long sequence of  measurements, the strings $x$ and $y$, as primitives. The analysis of these strings, combined with the sequence of measurement bases, relies on their complexity, not  on the statistics of the individual measurements outcomes.

This algorithmic model of a Bell test can be designed, in its most general form, in terms of input programs, UTMs,  and their corresponding outputs. We can describe the sequence of measurement results of each party,..."

We hope that the re-organization of this section removed much of the confusion we seem to have generated.


C2) Comment about "labeling"
We have clarified the paragraph.  We replaced: 
"[...] one does not need to worry about labeling, and they work for any number of outcomes."

with:

"[...]they can be applied to experiments with more than two outcomes without any modifications."


C3) - Discussion of Shannon's coding. We have modified the text, specifying that Shannon's theorem is non-constructive. We replaced:

"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."

with:

"However, Shannon's source coding theorem does not give a prescription for how to achieve this maximum compression."

C4) We have removed the following sentence and citation from page 5:
"(with a possible exception in [12])."
We believe that the remaining two citations of Ref. [12] are pertinent to the subject of the specific paragraph and the overall structure of the paper.

C5) - uniform complexity. We tried to clean up the introduction of this concept a bit more at the new end of section 2.

C6) We have added a new paragraph to section 5:

"The data collected in this last measurement allow us to check the uniformity of the measured complexity across the 8 measurements for each basis setting. The NCD values corresponding to each trial are shown in figure 6. It is evident how the complexity of the generated strings do not vary significantly between trials, with a maximum variation of the order of 2%, supporting the uniform complexity assumption."

Additionally, we added the new figure 6 to show that over a few sets, the complexity appears indeed uniform. The caption to this new figure reads:

"Measured value of the NCD for 8 trials for the four bases (a0,b0), (a1,b0), (a1,b1), and (a0,b1), and fixed angle θ = 8.6\degree. The evident stability of the values supports the uniform complexity assumption."

Related to this, we have also corrected a typo from the original manuscript: the total number of measurement runs used to estimate the error on the value of S was 8, and not 10.

C7) We hope to have addressed this confusion  with the re-written section 2.

C8) We have made clearer that the optimal value is obtained by the analytical solution of inequality 5 by modifying two sentences at the end of section 2.2.1 from:

"[...]inequality (5) is violated for an appropriate range of \theta. An expected quantum value of S' as a function of \theta is shown in figure 2a. The maximal violation is S' = 0.24 for \theta = 8.6\degree."

to:

"[...]inequality (5) is violated for an appropriate range of \theta. We can directly calculate the expected value of S' as a function of \theta for the case of maximally polarization entangled photon pairs.
We plot S' in figure 2(a) as a benchmark for the experimental values. We find a maximal violation of S'=0.24 for \theta = 8.6\degree."

The values are indeed an analytical results, but they are a reasonably messy mathematica result, and we feel that quoting them they would not add any particularly insight to the concept.

C9) - see our replies to C1. We feel to have addressed this in some sense. Perhaps this idea could be expanded to more scenarios, but this would not be the scope of the manuscript at hand.

M1) Thanks for the suggestion - we fixed this.

M2) We replaced "[...]we found is the best" with "[...] is optimal".

M3) We appreciate the suggestion but we have decided to keep it.

M4) Clarify fair sampling: In the first paragraph of section 4.1 we replaced:
"[...] we assume a fair sampling."
 with 

"[...] we assume that the fraction of the photon we detected is a fair
representation of the entire ensemble (fair sampling assumption)."

M5) We agree that the concatenation is closer to the original intuition at the origin of the paper. But it is impractical for the number of measurements we record: every real compressor is always limited by the total amount of memory available. Even with a moderately long string, concatenation would place the correlated part of the strings too far apart for the software to find them, even in the case of programs like bzip2 that uses a transform to reorder the data before compressing (https://en.wikipedia.org/wiki/Burrows–Wheeler_transform).

M6) The sentence has been removed from then summary - we feel that the reorganized section 2 expresses what we think is important now much better.

We also tried to clean up the introduction to make it perhaps more accessible. 


With this, we hope to have addressed the concerns by the referees, and look forward for your consideration.

With Best Regards on behalf of all authors,

Christian Kurtsiefer