Reliable computation from contextual correlations

Abstract

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-2. In this setting, it was shown that non-contextual correlations do not provide any extra computational power, while contextual correlations were found to be necessary for the deterministic evaluation of non-linear 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 GHZ non-contextuality inequality also suffices for reliable computation.

5 pages, no figures. v2: corrected argument in section IV, other slight changes for clarity

References in corpus (9)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Contextuality supplies the magic for quantum computation
• The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
• Novel schemes for measurement-based quantum computation
• Contextuality in Measurement-based Quantum Computation
• Computational power of correlations
• Contextuality and Wigner function negativity in qubit quantum computation
• Non-adaptive Measurement-based Quantum Computation and Multi-party Bell Inequalities

Cited by in corpus (7)

• Kochen-Specker Contextuality
• Memory cost of temporal correlations
• Contextuality in spin-orbit laser modes
• Correlations for computation and computation for correlations
• Connecting XOR and XOR* games
• Convexity of noncontextual wirings and how they order the set of correlations
• The Interplay between Quantum Contextuality and Wigner Negativity