Master’s degree awarded: André Oestereich (UFF)Posted: March 8, 2016
Last Monday, March 7th, André Oestereich’s successfully passed his dissertation examination at the Infoptics group at UFF. His dissertation, “Computational expressiveness of correlations”, discusses an operational approach to the study of how correlations help in computation, with a view to better understanding the measurement-based model of quantum computation. He was supervised by Ernesto Galvão, who was joined in the examination committee by Fernando de Melo (CBPF) and Thiago de Oliveira (UFF). André will remain at UFF to pursue his PhD under Ernesto’s supervision. Congratulations, André! Please find his dissertation’s abstract below.
André Luis Oestereich
Title: Computational Expressiveness of Correlations
This dissertation explores some differences between quantum 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 contextuality.
Then it proceeds to an introduction of 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  and studied by Raussendorf , that aims to make the computational power of correlations. We procceed to see that non-contextual resources do not provide a computational ehancement and that quantum resources do provide it even without adaptivity.
We continue by reviewing a scheme for reliable computation using faulty components, first proposed by Von Neumann and later studied by Hajek and Weller  and Evans and Schulman . This scheme is then used to show how a range of bipartite quantum correlations suffice 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.