An operational approach to the study of computation based on correlations considers black boxes with one-bit inputs and outputs, controlled by a limited classical computer capable only of performing sums modulo-two. In this setting, it was shown that noncontextual correlations do not provide any extra computational power, while contextual correlations were found to be necessary for the deterministic evaluation of nonlinear Boolean functions. Here we investigate the requirements for reliable computation in this setting; that is, the evaluation of any Boolean function with success probability bounded away from $1/2$. We show that bipartite CHSH quantum correlations suffice for reliable computation. We also prove that an arbitrarily small violation of a multipartite Greenberger--Horne--Zeilinger noncontextuality inequality also suffices for reliable computation.
An operational approach to the study of computation based on correlations considers black boxes with one-bit inputs and outputs, controlled by a limited classical computer capable only of performing sums modulo-two. In this setting, it was shown that noncontextual correlations do not provide any extra computational power, while contextual correlations were found to be necessary for the deterministic evaluation of nonlinear Boolean functions. Here we investigate the requirements for reliable computation in this setting; that is, the evaluation of any Boolean function with success probability bounded away from 1/2. We show that bipartite CHSH quantum correlations suffice for reliable computation. We also prove that an arbitrarily small violation of a multipartite Greenberger--Horne--Zeilinger noncontextuality inequality also suffices for reliable computation.
Abstract Quantum correlations are central to the foundations of quantum physics and form the basis of quantum technologies. Here, our goal is to connect quantum correlations and computation: using quantum correlations as a resource for computation—and vice versa, using computation to test quantum correlations. We derive Bell-type inequalities that test the capacity of quantum states for computing Boolean functions within a specific model of computation and experimentally investigate them using 4-photon Greenberger–Horne–Zeilinger (GHZ) states. Furthermore, we show how the resource states can be used to specifically compute Boolean functions—which can be used to test and verify the non-classicality of the underlying quantum states. The connection between quantum correlation and computability shown here has applications in quantum technologies, and is important for networked computing being performed by measurements on distributed multipartite quantum states.
This dissertation explores some diferences between quantum mechanics and other theories from a computational perspective, in particular with respect to the kind of correlations they allow, and their computational consequences. It starts with an operational characterization of locality, no-signaling and noncontextuality. Then it proceeds to an introduction to measurement-based quantum computation, a model in which quantum correlations are used to perform computation. Such a model is then generalized in a framework, proposed by Anders and Browne [1] and studied by Raussendorf [2], that aims to make the computational power of correlations more evident. We proceed to see that noncontextual resources do not provide a computational enhancement and that quantum resources do provide it even without adaptivity. We continue by reviewing a scheme for reliable computation using faulty components, rst proposed by von Neumann and later studied by Hajek and Weller [3] and Evans and Schulman [4]. This scheme is then used to show how a range of bipartite quantum correlations su ce for reliable computation. We conclude by showing that quantum correlations that violate non-contextuality bounds by an arbitrarily small amount can be used to enable reliable computation
By combining the assumptions of Bell locality with those of generalized noncontextuality, we define classes of noncontextuality inequalities for correlations arising in a bipartite Bell circuit. These classes are distinguished by which subsets of the full set of operational identities are taken as input to the principle of noncontextuality; certain natural subsets form a hierarchy that provides a way of understanding and classifying different forms of quantum correlations, including entanglement, steering, and nonlocality. Each level of this hierarchy gives rise to a corresponding class of noncontextuality inequalities whose violation witnesses one of these forms of bipartite quantum resourcefulness, thereby yielding different sufficient conditions for entanglement. The resulting entanglement certification paradigm requires no prior characterization of the measurements, delivers a verdict independent of tomographic gauge freedom, and can certify any entangled state without auxiliary entangled sources. To illustrate the power of this paradigm, we show that noncontextuality inequalities can certify entanglement for families of two-qubit isotropic states for which certification by Bell or steering inequalities is known to be impossible. We also show that, compared with the Bell test, this approach certifies a much larger fraction of entangled states, while the associated membership problem is computationally more tractable. On the experimental side, we describe techniques to ensure nontrivial operational identities in the presence of noisy and imperfect implementations. We also identify the sufficient condition under which these techniques are valid, namely, a particular notion of of the implemented Bell circuit, which ensures that the operational identities are independent of tomographic gauge. Finally, we provide an experimental demonstration of the superior performance of this entanglement certification technique using polarization-entangled photons.
Nonlocality can be witnessed either through Bell-inequality violations or through logical contradictions such as Hardy's paradox. In the bipartite two input two outcome scenario, these two routes have distinct geometric behavior: CHSH-maximal correlations are exposed points of the quantum set, whereas known Hardy-type self-testing correlations on the no-signaling boundary are non-exposed. Here we show that this bipartite intuition fails in the tripartite two input two outcome scenario. We study the tripartite instance of a multipartite Hardy-type paradox and prove that the correlation attaining the maximal Hardy success probability self-tests the Greenberger--Horne--Zeilinger state and the associated measurements. Although this correlation lies on the no-signaling boundary, we show that it is an extremal and exposed point of the quantum correlation set. Moreover, it coincides with the correlation attaining the maximal violation of the Mermin inequality. Thus, in the tripartite GHZ scenario, the logical-paradox and Bell-inequality routes to nonlocality select the same exposed quantum boundary point. We also establish a robust version of the self-test, showing that small deviations from the ideal Hardy constraints imply quantitative closeness to the target state and measurements. Our results reveal a qualitative geometric difference between bipartite and tripartite Hardy-type nonlocality and suggest a broader investigation of exposedness for multipartite Hardy correlations in the multiparty setting.
The main objective of this paper is to provide illustrative examples of distributed computing problems for which it is possible to design tight lower bounds for quantum algorithms without having to manipulate concepts from quantum mechanics, at all. As a case study, we address the following class of 2-player problems. Alice (resp., Bob) receives a boolean x (resp., y) as input, and must return a boolean a (resp., b) as output. A game between Alice and Bob is defined by a pair (?, f) of boolean functions. The objective of Alice and Bob playing game (?, f) is, for every pair (x, y) of inputs, to output values a and b, respectively, satisfying ?(a, b) = f(x, y), in absence of any communication between the two players, but in presence of shared resources. The ability of the two players to solve the game then depends on the type of resources they share. It is known that, for the so-called CHSH game, i.e., for the game a ? b = x ? y, the ability for the players to use entangled quantum bits (qubits) helps. We show that, apart from the CHSH game, quantum correlations do not help, in the sense that, for every game not equivalent to the CHSH game, there exists a classical protocol (using shared randomness) whose probability of success is at least as large as the one of any protocol using quantum resources. This result holds for both worst case and average case analysis. It is achieved by considering a model stronger than quantum correlations, the non-signaling model, which subsumes quantum mechanics, but is far easier to handle.
Quantum correlations exhibit behaviour that cannot be resolved with a local hidden variable picture of the world. In quantum information, they are also used as resources for information processing tasks, such as measurement-based quantum computation (MQC). In MQC, universal quantum computation can be achieved via adaptive measurements on a suitable entangled resource state. In this paper, we look at a version of MQC in which we remove the adaptivity of measurements and aim to understand what computational abilities remain in the resource. We show that there are explicit connections between this model of computation and the question of non-classicality in quantum correlations. We demonstrate this by focusing on deterministic computation of Boolean functions, in which natural generalizations of the Greenberger-Horne-Zeilinger paradox emerge; we then explore probabilistic computation via, which multipartite Bell inequalities can be defined. We use this correspondence to define families of multi-party Bell inequalities, which we show to have a number of interesting contrasting properties.