Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computational expressiveness of correlations

André L. Oestereich

Published Jan 1, 2016• 0 citations
OpenAlex

Abstract

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

Related papers

Correlations in Measurement-Based Quantum Computing and Bell Inequalities

Dan E. Browne

Measurement-based quantum computation (or the one-way quantum computation) is a model in which a series of adaptive single qubit measurements upon an entangled resource state can produce classical output data equivalent to an arbitrary quantum logic circuit. Loosely speaking, the correlations in these measurements can be considered the resource which allows the computation to be performed. Bell inequalities demonstrate that quantum mechanics permits the outcomes of sets of measurements to be correlated in ways incompatible with the predictions of any local hidden variable theory, including classical physics. In the Bell inequality, and multi-party generalisations, a set of single-qubit measurements are performed, on spatially separated systems. Correlations in these measurements can act as a signature that no local hidden variable description of the experiment is possible. At first sight, we see superficial similarities between these settings. In both cases, non-classical correlations play a central role. However, there are also some key differences. Most importantly, measurement-based quantum computing requires adaptive measurements, at odds with the spatial-separated nature of Bell inequality experiments. Nevertheless some striking connections have been reported [1], [2] particularly between GHZ-type paradoxes and deterministic MBQC computations, and between CHSH-type Bell inequalities and non-deterministic MBQC correlations [1], [3]. In my talk I will survey these works and some recent results [3], [4] from my group at UCL, in which a number of connections between multi-party Bell inequalities and MBQC are explored. [1] J. Anders and D.E. Browne, "The Computational Power of Correlations", Physical Review Letters 102, 050502 (2009) [2] R. Raussendorf, "Quantum computation, discreteness, and contextuality", arxiv:0907.5449 [3] M. J. Hoban, E.T. Campbell, K. Loukopolous, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalties", in preparation. [4] M. J. Hoban and D.E. Browne, in preparation.

•Jan 1, 2016•0 citations

Reliable computation from contextual correlations

André L. Oestereich, Ernesto F. Galvão

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.

arXiv:1706.09757•Physical Review A•Dec 4, 2017•13 citations

Connecting Quantum Contextuality and Nonlocality

Jianqi Sheng, Dongkai Zhang, Lixiang Chen

Quantum theory departs from classical physics in its treatment of correlations, most prominently through the phenomena of contextuality and nonlocality. Once regarded primarily as foundational curiosities, these effects are now understood as key operational resources for quantum computation, communication, and simulation. Although traditionally investigated in distinct settings, recent theoretical and experimental advances have revealed deep conceptual, mathematical, and operational connections between them. This review presents a unified perspective on these developments based on sheaf-theoretic and graph-theoretic frameworks, which provide theory-independent characterizations of statistical correlations. These approaches clarify the structural relationship between contextuality and nonlocality, facilitate the formulation of experimentally testable inequalities, and guide implementations in realistic physical platforms, with particular emphasis on photonic systems. By bridging abstract theoretical structures and concrete experimental realizations, this review sheds light on the nonclassical foundations of quantum correlations and their emerging role in quantum technologies.

quant-pharXiv:2602.23221•Feb 27, 2026•0 citations

Quantifying quantum nonlocality

Ben Toner

Quantum mechanics is nonlocal, meaning it cannot be described by any classical local hidden variable model. In this thesis we study two aspects of quantum nonlocality. Part I addresses the question of what classical resources are required to simulate nonlocal quantum correlations. We start by constructing new local models for noisy entangled quantum states. These constructions exploit the connection between nonlocality and Grothendieck's inequality, first noticed by Tsirelson. Next, we consider local models augmented by a limited amount of classical communication. After generalizing Bell inequalities to this setting, we show that (i) one bit of communication is sufficient to simulate the correlations of projective measurements on a maximally entangled state of two qubits, and (ii) five bits of communication are sufficient to simulate the joint correlation of two-outcome measurements on any bipartite quantum state. The latter result can be interpreted as a stronger (constrained) version of Grothendieck's inequality. In part II, we investigate the monogamy of nonlocal correlations. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, obtaining an intriguing generalization of Tsirelson's bound, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities. We study not only correlations that arise within quantum theory, but also arbitrary correlations that do not allow signaling between separate groups of parties. These results are based on new techniques for obtaining Tsirelson bounds, or bounds on the quantum value of a Bell inequality, and have applications to interactive proof systems and cryptography.

•Aug 12, 2013•3 citations

Parts and Wholes. An Inquiry into Quantum and Classical Correlations

M. P. Seevinck

** The primary topic of this dissertation is the study of the relationships between parts and wholes as described by particular physical theories, namely generalized probability theories in a quasi-classical physics framework and non-relativistic quantum theory. ** A large part of this dissertation is devoted to understanding different aspects of four different kinds of correlations: local, partially-local, no-signaling and quantum mechanical correlations. Novel characteristics of these correlations have been used to study how they are related and how they can be discerned via Bell-type inequalities that give non-trivial bounds on the strength of the correlations. ** The study of quantum correlations has also prompted us to study a) the multi-partite qubit state space with respect to its entanglement and separability characteristics, and b) the differing strength of the correlations in separable and entangled qubit states. Results include a novel classification of multipartite (partial) separability and entanglement, strong constraints on the monogamy of entanglement and of non-local correlations, and many new entanglement detection criteria that are directly experimentally accessible. ** Because of the generality of the investigation these results also have strong foundational as well as philosophical repercussions for the different sorts of physical theories as a whole; notably for the viability of hidden variable theories for quantum mechanics, for the possibility of doing experimental metaphysics, for the question of holism in physical theories, and for the classical vs. quantum dichotomy.

arXiv:0811.1027•Nov 6, 2008•32 citations

Possibilistic (and other) notions of contextuality

Andrew W. Simmons

Since Bell, Kochen and Specker formulated the first notions of contextuality, a number of frameworks have been created to help make philosophical and mathematical sense of the concept. Two of the most common are the Equivalence-based approach due to Spekkens, and the Sheaf-theoretic framework of Abramsky and Brandenburger. Each of these can support a hierarchy of strengths of contextuality, which can include possibilistic concepts. This thesis will explore the differences between the two approaches, and explore what can be demonstrated by using weaker notions of noncontextuality. Notions of noncontextuality are important for proving no-go theorems which highlight that many properties that are true of classical mechanics fail to be compatible with quantum predictions. Often, the notions of noncontextuality used are very strong assumptions, and even weaker flavours of noncontextuality can be used to draw the same, or similar conclusions. An important class of such notions are, possibilistic assumptions that only care about whether or not events are possible or impossible, rather than the exact Born rule probabilities that are applied to events. Even these weaker notions are often impossible to resolve with the logical structure and predictions of quantum theory. Contextuality has been demonstrated to be a resource for many quantum computational operations, and the contextual fraction has been shown to be an important resource. We introduce a metric that can differentiate between different quantum mechanical scenarios with contextual fraction 1, and demonstrate analogues of CHSH and Tsirelson bounds for this quantity. We also investigate the computational complexity of calculating the values of some metrics for nonlocality and contextuality, completing the classification of possibilistic nonlocality scenarios, as well as other metrics of nonlocality analogous to our metric of maximal contextuality.

•Sep 1, 2018•2 citations
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
Measurement-based quantum computation (or the one-way quantum computation) is a model in which a series of adaptive single qubit measurements upon an entangled resource state can produce classical output data equivalent to an arbitrary quantum logic circuit. Loosely speaking, the correlations in these measurements can be considered the resource which allows the computation to be performed. Bell inequalities demonstrate that quantum mechanics permits the outcomes of sets of measurements to be correlated in ways incompatible with the predictions of any local hidden variable theory, including classical physics. In the Bell inequality, and multi-party generalisations, a set of single-qubit measurements are performed, on spatially separated systems. Correlations in these measurements can act as a signature that no local hidden variable description of the experiment is possible. At first sight, we see superficial similarities between these settings. In both cases, non-classical correlations play a central role. However, there are also some key differences. Most importantly, measurement-based quantum computing requires adaptive measurements, at odds with the spatial-separated nature of Bell inequality experiments. Nevertheless some striking connections have been reported [1], [2] particularly between GHZ-type paradoxes and deterministic MBQC computations, and between CHSH-type Bell inequalities and non-deterministic MBQC correlations [1], [3]. In my talk I will survey these works and some recent results [3], [4] from my group at UCL, in which a number of connections between multi-party Bell inequalities and MBQC are explored. [1] J. Anders and D.E. Browne, "The Computational Power of Correlations", Physical Review Letters 102, 050502 (2009) [2] R. Raussendorf, "Quantum computation, discreteness, and contextuality", arxiv:0907.5449 [3] M. J. Hoban, E.T. Campbell, K. Loukopolous, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalties", in preparation. [4] M. J. Hoban and D.E. Browne, in preparation.
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/21/21/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.
Quantum theory departs from classical physics in its treatment of correlations, most prominently through the phenomena of contextuality and nonlocality. Once regarded primarily as foundational curiosities, these effects are now understood as key operational resources for quantum computation, communication, and simulation. Although traditionally investigated in distinct settings, recent theoretical and experimental advances have revealed deep conceptual, mathematical, and operational connections between them. This review presents a unified perspective on these developments based on sheaf-theoretic and graph-theoretic frameworks, which provide theory-independent characterizations of statistical correlations. These approaches clarify the structural relationship between contextuality and nonlocality, facilitate the formulation of experimentally testable inequalities, and guide implementations in realistic physical platforms, with particular emphasis on photonic systems. By bridging abstract theoretical structures and concrete experimental realizations, this review sheds light on the nonclassical foundations of quantum correlations and their emerging role in quantum technologies.
Quantum mechanics is nonlocal, meaning it cannot be described by any classical local hidden variable model. In this thesis we study two aspects of quantum nonlocality. Part I addresses the question of what classical resources are required to simulate nonlocal quantum correlations. We start by constructing new local models for noisy entangled quantum states. These constructions exploit the connection between nonlocality and Grothendieck's inequality, first noticed by Tsirelson. Next, we consider local models augmented by a limited amount of classical communication. After generalizing Bell inequalities to this setting, we show that (i) one bit of communication is sufficient to simulate the correlations of projective measurements on a maximally entangled state of two qubits, and (ii) five bits of communication are sufficient to simulate the joint correlation of two-outcome measurements on any bipartite quantum state. The latter result can be interpreted as a stronger (constrained) version of Grothendieck's inequality. In part II, we investigate the monogamy of nonlocal correlations. In a setting where three parties, A, B, and C, share an entangled quantum state of arbitrary dimension, we: (i) bound the trade-off between AB's and AC's violation of the CHSH inequality, obtaining an intriguing generalization of Tsirelson's bound, and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities. We study not only correlations that arise within quantum theory, but also arbitrary correlations that do not allow signaling between separate groups of parties. These results are based on new techniques for obtaining Tsirelson bounds, or bounds on the quantum value of a Bell inequality, and have applications to interactive proof systems and cryptography.
** The primary topic of this dissertation is the study of the relationships between parts and wholes as described by particular physical theories, namely generalized probability theories in a quasi-classical physics framework and non-relativistic quantum theory. ** A large part of this dissertation is devoted to understanding different aspects of four different kinds of correlations: local, partially-local, no-signaling and quantum mechanical correlations. Novel characteristics of these correlations have been used to study how they are related and how they can be discerned via Bell-type inequalities that give non-trivial bounds on the strength of the correlations. ** The study of quantum correlations has also prompted us to study a) the multi-partite qubit state space with respect to its entanglement and separability characteristics, and b) the differing strength of the correlations in separable and entangled qubit states. Results include a novel classification of multipartite (partial) separability and entanglement, strong constraints on the monogamy of entanglement and of non-local correlations, and many new entanglement detection criteria that are directly experimentally accessible. ** Because of the generality of the investigation these results also have strong foundational as well as philosophical repercussions for the different sorts of physical theories as a whole; notably for the viability of hidden variable theories for quantum mechanics, for the possibility of doing experimental metaphysics, for the question of holism in physical theories, and for the classical vs. quantum dichotomy.
Since Bell, Kochen and Specker formulated the first notions of contextuality, a number of frameworks have been created to help make philosophical and mathematical sense of the concept. Two of the most common are the Equivalence-based approach due to Spekkens, and the Sheaf-theoretic framework of Abramsky and Brandenburger. Each of these can support a hierarchy of strengths of contextuality, which can include possibilistic concepts. This thesis will explore the differences between the two approaches, and explore what can be demonstrated by using weaker notions of noncontextuality. Notions of noncontextuality are important for proving no-go theorems which highlight that many properties that are true of classical mechanics fail to be compatible with quantum predictions. Often, the notions of noncontextuality used are very strong assumptions, and even weaker flavours of noncontextuality can be used to draw the same, or similar conclusions. An important class of such notions are, possibilistic assumptions that only care about whether or not events are possible or impossible, rather than the exact Born rule probabilities that are applied to events. Even these weaker notions are often impossible to resolve with the logical structure and predictions of quantum theory. Contextuality has been demonstrated to be a resource for many quantum computational operations, and the contextual fraction has been shown to be an important resource. We introduce a metric that can differentiate between different quantum mechanical scenarios with contextual fraction 1, and demonstrate analogues of CHSH and Tsirelson bounds for this quantity. We also investigate the computational complexity of calculating the values of some metrics for nonlocality and contextuality, completing the classification of possibilistic nonlocality scenarios, as well as other metrics of nonlocality analogous to our metric of maximal contextuality.