Algebraic paradoxes in adaptive quantum computation
arXiv:2607.26157
The paper shows that any adaptive Z₂‑linear measurement‑based quantum computation that deterministically computes a non‑affine Boolean function must involve a quantum resource that violates a set of linear equations, providing an algebraic, cohomological witness of strong contextuality for adaptive protocols.
Abstract
Measurement-based quantum computation (MBQC) is a universal model of quantum computation whose full power requires adaptivity. Contextuality is known to power quantum advantage in MBQC, yet it has resisted algebraic analysis in the adaptive setting. We show that if an adaptive -linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin's All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a larger scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.
39 pages