Quantum advantage from sequential transformation contextuality

Shane Mansfield, Elham Kashefi

Published 2018-01-24Version 1

We introduce a notion of contextuality for transformations in sequential contexts, distinct from the Bell-Kochen-Specker and Spekkens notions of contextuality, which can arise even in a single qubit system. Within a transformation-based model for quantum computation we show that strong sequential transformation contextuality is necessary for deterministic computation of non-linear functions. For probabilistic computation, sequential transformation contextuality is necessary for obtaining advantage over classical implementations and the degree of advantage quantifiably relates to the degree of contextuality.