ALGEBRAIC PARADOXES IN ADAPTIVE QUANTUM COMPUTATION

Measurement-based quantum computation (MBQC) is a universal model of quantum computation where adaptivity—the ability to choose measurement settings based on prior outcomes—is essential for full computational power. While contextuality is known to be the source of quantum advantage in this model, existing algebraic and cohomological tools for detecting it have been limited to non-adaptive, "flat" scenarios. This paper addresses the open question of whether these tools can be extended to the adaptive setting, specifically asking if the contextuality required for adaptive MBQC can always be witnessed by an explicit algebraic contradiction known as an All-versus-Nothing (AvN) argument.

The authors employ a constructive approach to bridge the gap between non-adaptive and adaptive protocols. They model adaptive measurement protocols as non-adaptive measurements on an enlarged, tree-like scenario. This "flattening" construction allows the researchers to apply the existing arsenal of algebraic and cohomological tools—originally designed for static scenarios—to the adaptive case. By building the inconsistent systems of linear equations inductively from the structure of the computation tree, they demonstrate that any adaptive Z2-linear protocol computing a non-affine function must satisfy an inconsistent set of linear equations.

The study confirms that the strong contextuality required for adaptive Z2-linear MBQC is fundamentally algebraic. The authors prove that such protocols can always be witnessed via an AvN argument, resolving a long-standing open question posed by Raussendorf. Furthermore, they show that this algebraic contextuality is cohomologically nontrivial, establishing that cohomological witnesses for contextuality extend to the adaptive setting in both Čech and group-cohomological frameworks. This provides a rigorous, theory-independent foundation for understanding the source of computational power in adaptive quantum systems.