The celebrated Bell's no-go theorem rules out the hidden-variable theories falling in the hypothesis of locality and causality, by requiring the theory to model the quantum correlation-at-a-distance phenomena. Here I develop an independent no-go theorem, by inspecting the ability of a theory to model quantum \emph{circuits}. If a theory is compatible with quantum mechanics, then the problems of solving its mathematical models must be as hard as calculating the output of quantum circuits, i.e., as hard as quantum computing. Rigorously, I provide complexity classes capturing the idea of sampling from sequential (causal) theories and from post-selection-based (retro-causal) theories; I show that these classes fail to cover the computational complexity of sampling from quantum circuits. The result is based on widely accepted conjectures on the superiority of quantum computers over classical ones. The result represents a no-go theorem that rules out a large family of sequential and post-selection-based theories. I discuss the hypothesis of the no-go theorem and the possible ways to circumvent them. In particular, I discuss the Schulman model and its extensions, which is retro-causal and is able to model quantum correlation-at-a-distance phenomena: I provides clues suggesting that it escapes the hypothesis of the no-go theorem.
The celebrated Bell's no-go theorem rules out the hidden-variable theories falling in the hypothesis of locality and causality, by requiring the theory to model the quantum correlation-at-a-distance phenomena. Here I develop an independent no-go theorem, by inspecting the ability of a theory to model quantum \emph{circuits}. If a theory is compatible with quantum mechanics, then the problems of solving its mathematical models must be as hard as calculating the output of quantum circuits, i.e., as hard as quantum computing. Rigorously, I provide complexity classes capturing the idea of sampling from sequential (causal) theories and from post-selection-based (retro-causal) theories; I show that these classes fail to cover the computational complexity of sampling from quantum circuits. The result is based on widely accepted conjectures on the superiority of quantum computers over classical ones. The result represents a no-go theorem that rules out a large family of sequential and post-selection-based theories. I discuss the hypothesis of the no-go theorem and the possible ways to circumvent them. In particular, I discuss the Schulman model and its extensions, which is retro-causal and is able to model quantum correlation-at-a-distance phenomena: I provides clues suggesting that it escapes the hypothesis of the no-go theorem.
We show that families of Instantaneous Quantum Polynomial (IQP) circuits corresponding to nontrivial Bell tests exhibit nonlocality. However, we also prove that this nonlocality can only be demonstrated using post-selection or nonlinear processing of the measurement outcomes. Therefore if the output of a computation is encoded in the parity of the measurement outcomes, then families of IQP circuits whose full output distributions are hard to sample still only provide a computational advantage relative to locally causal theories under post-selection. Consequently, post-selection is a crucial technique for obtaining a computational advantage for IQP circuits (with respect to decision problems) and for demonstrating nonlocality within IQP circuits, suggesting a strong link between these phenomena.
The strongest attack against quantum mechanics came in 1935 in the form of a paper by Einstein, Podolsky and Rosen. It was argued that the theory of quantum mechanics could not be called a complete theory of Nature, for every element of reality is not represented in the formalism as such. The authors then put forth a proposition: we must search for a theory where, upon knowing everything about the system, including possible hidden variables, one could make precise predictions concerning elements of reality. This project was ultimatly doomed in 1964 with the work of Bell Bell, who showed that the most general local hidden variable theory could not reproduce correlations that arise in quantum mechanics. There exist mainly three forms of no-go theorems for local hidden variable theories. Although almost every physicist knows the consequences of these no-go theorems, not every physicist is aware of the distinctions between the three or even their exact definitions. Thus we will discuss here the three principal forms of no-go theorems for local hidden variable theories of Nature. We will define Bell theorems, Bell theorems without inequalities and pseudo-telepathy. A discussion of the similarities and differences will follow. 1
Bell nonlocality is an intriguing property of quantum mechanics with far reaching consequences for information processing, philosophy and our fundamental understanding of nature. However, nonlocality is a statement about static correlations only. It does not take into account dynamics, i.e. time evolution of those correlations. Consider a dynamic situation where the correlations remain local for all times. Then at each moment in time there exists a local hidden-variable (LHV) model reproducing the momentary correlations. Can the time evolution of the correlations then be captured by evolving the hidden variables? In this light, we define dynamical LHV models and motivate and discuss potential additional physical and mathematical assumptions. Based on a simple counter example we conjecture that such LHV dynamics does not always exist. This is further substantiated by a rigorous no-go theorem. Our results suggest a new type of nonlocality that can be deduced from the observed time evolution of measurement statistics and which generically occurs in interacting quantum systems.
The strongest attack against quantum mechanics came in 1935 in the form of a paper by Einstein, Podolsky, and Rosen. It was argued that the theory of quantum mechanics could not be called a complete theory of Nature, for every element of reality is not represented in the formalism as such. The authors then put forth a proposition: we must search for a theory where, upon knowing everything about the system, including possible hidden variables, one could make precise predictions concerning elements of reality. This project was ultimately doomed in 1964 with the work of Bell, who showed that the most general local hidden variable theory could not reproduce correlations that arise in quantum mechanics. There exist mainly three forms of no-go theorems for local hidden variable theories. Although almost every physicist knows the consequences of these no-go theorems, not every physicist is aware of the distinctions between the three or even their exact definitions. Thus, we will discuss here the three principal forms of no-go theorems for local hidden variable theories of Nature. We will define Bell theorems, Bell theorems without inequalities, and pseudo-telepathy. A discussion of the similarities and differences will follow. PACS Nos.: 03.65.–w, 03.65.Ud, 03.65.Ta
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.
Motivated by Popescu's example of hidden nonlocality [Phys. Rev. Lett. 74, 2619 (1995)], we elaborate on the conjecture that quantum states that are intuitively nonlocal, i.e., entangled, do not admit a local causal hidden-variables model. We exhibit quantum states which either (i) are nontrivial counterexamples to this conjecture or (ii) possess a new kind of more deeply hidden irreducible nonlocality. Moreover, we propose a nonlocality complexity classification scheme suggested by the latter possibility. Furthermore, we show that Werner's [Phys. Rev. A 40, 4277 (1989)] (and similar) hidden-variables models can be extended to an important class of generalized observables. Finally, a result of Fine [Phys. Rev. Lett. 48, 291 (1982)] on the equivalence of stochastic and deterministic hidden variables is generalized to causal models.