Contextuality as a computational resource

Contextuality means that measurement outcomes cannot be modeled consistently by values independent of their compatible context. Whether it enables a computational advantage depends on the computational model and task, not its mere presence in a finite experiment.

Howard–Wallman–Veitch–Emerson establish contextuality requirements for magic-state-based computation in an odd-prime-dimensional stabilizer setting. Measurement-based computation has other model-specific results, including Raussendorf's contextuality links and Anders–Browne's promotion of restricted classical control. Sheaf-theoretic descriptions quantify contextuality but do not supply a universal speedup theorem.

For a concrete benchmark, fix the resource-state or measurement family, allowed stabilizer or measurement-based operations, circuit-size scaling, and whether classical simulation means exact sampling, approximate total-variation sampling or a decision task. Then seek simulation algorithms or resource-conversion lower bounds as the contextuality parameter changes.

Necessity in one model is not sufficiency in another, and contextuality of a constant-size gadget alone is not an asymptotic computational separation. This is a scoped programme related to A16, not one necessary-and-sufficient criterion for all quantum advantage.

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.