The basic motivation behind this work is to raise the question that whether post selection can be considered a valid physical transformation (on probability space) or not. We study the consequences of both answers set in a device (theory) independent framework, based only on observed statistics. We start with taking up post-selection as an assumption and model the same using independent devices governed by Boolean functions. We establish analogy between the post selection functions and the general probabilistic games in a two party binary input-output scenario. As an observation, we categorize all possible post-selection functions based on the effect on a uniform input probability distribution. We find that post-selection can transform simple no signaling probability distributions to signaling. Similarly, solving NP complete problems is easy independent of classical or quantum computation (in particular we prove that Post RP = NP). Finally, we demonstrate an instance of the violation of the pigeon hole principle independent of underlying theory. As result of our theory independent modeling we conclude that post-selection as an assumption adds power to the underlying theory. In particular, quantum mechanics benefits more with the post-selection assumption, only because it admits a more general set of allowed probabilities as compared to the local hidden variable model. Without the assumption we associate a device independent efficiency factor to quantify the cost of post selection. Our study shows that in the real world post-selection is not efficient enough to be of any advantage. But from an adversarial perspective it is still of significance. As an application, we obtain robust bounds on faking the bell violation in terms of minimum efficiency required using post selection.
The basic motivation behind this work is to raise the question that whether post selection can be considered a valid physical transformation (on probability space) or not. We study the consequences of both answers set in a device (theory) independent framework, based only on observed statistics. We start with taking up post-selection as an assumption and model the same using independent devices governed by Boolean functions. We establish analogy between the post selection functions and the general probabilistic games in a two party binary input-output scenario. As an observation, we categorize all possible post-selection functions based on the effect on a uniform input probability distribution. We find that post-selection can transform simple no signaling probability distributions to signaling. Similarly, solving NP complete problems is easy independent of classical or quantum computation (in particular we prove that Post RP = NP). Finally, we demonstrate an instance of the violation of the pigeon hole principle independent of underlying theory. As result of our theory independent modeling we conclude that post-selection as an assumption adds power to the underlying theory. In particular, quantum mechanics benefits more with the post-selection assumption, only because it admits a more general set of allowed probabilities as compared to the local hidden variable model. Without the assumption we associate a device independent efficiency factor to quantify the cost of post selection. Our study shows that in the real world post-selection is not efficient enough to be of any advantage. But from an adversarial perspective it is still of significance. As an application, we obtain robust bounds on faking the bell violation in terms of minimum efficiency required using post selection.
The predictions of quantum mechanics cannot be resolved with a completely classical view of the world. In particular, the statistics of space-like separated \nmeasurements on entangled quantum systems violate a Bell inequality [Bell1964]. \nWe put forward a computational perspective on a broad class of Bell tests that study correlators, or the statistics of joint measurement outcomes. We associate \nparticular maps, or functions to particular theories. The violation of a Bell \ninequality then implies the ability to perform some functions, or computations \nthat classical, or more generally, local hidden variable (LHV) theories cannot. \nWe derive an in�finite class of Bell inequalities that establish a link to so-called "non-local games" [Cleve2004]. We then make the connection between \nRaussendorf and Briegel's formulation of Measurement-based Quantum Computing (MBQC) [Raussendorf2001], and these non-local games. Not only can we show that a quantum violation implies a computational advantage in this model, \nwe show that adaptive measurements are required to perform all quantum computations. \nFinally, we explore post-selection of data in Bell tests from both a practical and \nconceptual point-of-view, with particular consideration to so-called "loopholes". \nLoopholes allow LHV theories to simulate quantum correlations through post-selection. \nWe give a computational description of how loopholes can emerge in diff�erent post-selection scenarios. This motivates us to �find a form of post-selection \nthat does not lead to loopholes. Central again to this discussion is the \ndescription of LHV theories in terms of computations. \nInterestingly, quantum correlators can be made more "non-classical" with this \nloophole-free post-selection. This method of post-selection also can simulate \ninformation processing tasks, such as MBQC, that have time-like separated components. \nThis opens up new avenues for the study of time-like tasks studied \nwithin the space-like separated scenario of the Bell test.
Device-independent certifications employ Bell tests to guarantee the proper functioning of an apparatus from the sole knowledge of observed measurement statistics, i.e. without assumptions on the internal functioning of the devices. When these Bell tests are implemented with devices having too low efficiency, one has to post-select the events that lead to successful detections and thus rely on a fair sampling assumption. The question that we address in this paper is what remains of a device-independent certification under fair sampling. We provide an intuitive description of post-selections in terms of filters and define the fair sampling assumption as a property of these filters, equivalent to the definition introduced in Ref. \cite{Berry10}. When this assumption is fulfilled, the post-selected data is reproduced by an ideal experiment where lossless devices measure a filtered state which can be obtained from the actual state via local probabilistic maps. Trusted conclusions can thus be obtained on the quantum properties of this filtered state and the corresponding measurement statistics can reliably be used, e.g., for randomness generation or quantum key distribution. We also explore a stronger notion of fair sampling leading to the conclusion that the post-selected data is a fair representation of the data that would be obtained with lossless detections. Furthermore, we show that our conclusions hold in cases of small deviations from exact fair sampling. Finally, we describe setups previously or potentially used in Bell-type experiments under fair sampling and identify the underlying device-specific assumptions.
From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that , where is a classical complexity class (known to be included in , hence ). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterized by local measurements), efficient computations are contained in . This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, , is equal to . Given only the assumption of tomographic locality, the inclusion in still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativized complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a 'classical oracle'. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include .
Given a pair of isolated devices that accept random binary inputs and return binary outputs, a user can deduce from the observed data alone if the underlying mechanism can be explained classically. Bell's theorem further states that a classical explanation can be ruled out if the devices perform certain measurements on an entangled quantum state, underpinning the security of cryptographic protocols that are device-independent (DI). For certain protocols, such as those performed in a tight space, it might be difficult to perfectly enforce the non-signaling assumption required in Bell's theorem. This prompts the question: is quantum nonlocality robust to such imperfections? We show that if a binary channel sends a noisy copy of one party's input to the other before any measurements take place, the answer is yes. We completely characterize the vertices and facets of the local polytope in this scenario, and identify Bell inequalities that certify non-signaling quantum correlations. This is possible even when a near perfect copy of the input is sent. We go on to show that the identified inequalities are more robust to depolarizing noise than the Clauser-Horne-Shimony-Holt inequality when certifying DI randomness in this scenario. In addition, we characterize the local polytope when both parties receive a noisy copy of each other's input and make similar conclusions, leaving many new potential Bell inequalities to be explored.
Contrary to counterfactual definiteness quantum theory teaches us that measuring instruments are not passively reading predetermined values of physical observables. Counterfactual definiteness allows proving Bell inequalities. If the contextual character of quantum measurements is correctly taken into account the proofs of these inequalities may not be done. In recent computer simulations of idealized Bell experiment predetermined successive outcomes of measurements for each setting and predetermined time delays of their registrations are calculated. Time windows and time delays are used to select various samples. Correlations, estimated using these selected samples are consistent with the predictions of quantum theory and the time window dependence is similar to the dependence observed in some real experiments. It is an important example how correlations can be explained without evoking quantum non-locality. However by using a suitable post-selection one may prove anything. Since before the post-selection generated samples may not violate Bell inequalities as significantly as finite samples generated using quantum predictions thus one may not conclude that counterfactual definiteness is not able to distinguish classical from quantum physics. Moreover we show that for each choice of a time window there exists a contextual hidden variable probabilistic model consistent with the post-selection procedure used by the authors what explains why they are able to reproduce quantum predictions.
Bell non-local correlations cannot be naturally explained in a fixed causal structure. This serves as a motivation for considering models where no global assumption is made beyond logical consistency. The assumption of a fixed causal order between a set of parties, together with free randomness, implies device-independent inequalities—just as the assumption of locality does. It is known that local validity of quantum theory is consistent with violating such inequalities. Moreover, for three parties or more, even the (stronger) assumption of local classical probability theory plus logical consistency allows for violating causal inequalities. Here, we show that a classical environment (with which the parties interact), possibly containing loops, is logically consistent if and only if whatever the involved parties do, there is exactly one fixed-point, the latter being representable as a mixture of deterministic fixed-points. We further show that the non-causal view allows for a model of computation strictly more powerful than computation in a world of fixed causal orders.