Computational expressiveness of correlations

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