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 $\mathbb{Z}_2$ -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.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 $\mathbb{Z}_2$-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.

quant-pharXiv:2607.26157Jul 30, 20260 citations

Decision-making in cognitive paradoxes with contextuality and quantum formalism

Ishwarya M.S., Aswani Kumar Cherukuri

Applied Soft ComputingJul 3, 202016 citations

The Role of Classical Computation in Measurement-Based Quantum Computation

Dan E. Browne, Janet Anders

Springer eBooksJun 10, 20080 citations

Measurement-Based Interference in Quantum Computation

XUYou-Yang

理论物理通讯：英文版Jan 1, 20130 citations

Logical pre- and post-selection paradoxes are proofs of contextuality

Matthew F. Pusey, Matthew Leifer

If a quantum system is prepared and later post-selected in certain states, "paradoxical" predictions for intermediate measurements can be obtained. This is the case both when the intermediate measurement is strong, i.e. a projective measurement with Luders-von Neumann update rule, or with weak measurements where they show up in anomalous weak values. Leifer and Spekkens [quant-ph/0412178] identified a striking class of such paradoxes, known as logical pre- and post-selection paradoxes, and showed that they are indirectly connected with contextuality. By analysing the measurement-disturbance required in models of these phenomena, we find that the strong measurement version of logical pre- and post-selection paradoxes actually constitute a direct manifestation of quantum contextuality. The proof hinges on under-appreciated features of the paradoxes. In particular, we show by example that it is not possible to prove contextuality without Luders-von Neumann updates for the intermediate measurements, nonorthogonal pre- and post-selection, and 0/1 probabilities for the intermediate measurements. Since one of us has recently shown that anomalous weak values are also a direct manifestation of contextuality [arXiv:1409.1535], we now know that this is true for both realizations of logical pre- and post-selection paradoxes.If a quantum system is prepared and later post-selected in certain states, "paradoxical" predictions for intermediate measurements can be obtained. This is the case both when the intermediate measurement is strong, i.e. a projective measurement with Luders-von Neumann update rule, or with weak measurements where they show up in anomalous weak values. Leifer and Spekkens [quant-ph/0412178] identified a striking class of such paradoxes, known as logical pre- and post-selection paradoxes, and showed that they are indirectly connected with contextuality. By analysing the measurement-disturbance required in models of these phenomena, we find that the strong measurement version of logical pre- and post-selection paradoxes actually constitute a direct manifestation of quantum contextuality. The proof hinges on under-appreciated features of the paradoxes. In particular, we show by example that it is not possible to prove contextuality without Luders-von Neumann updates for the intermediate measurements, nonorthogonal pre- and post-selection, and 0/1 probabilities for the intermediate measurements. Since one of us has recently shown that anomalous weak values are also a direct manifestation of contextuality [arXiv:1409.1535], we now know that this is true for both realizations of logical pre- and post-selection paradoxes.

arXiv:1506.07850Electronic Proceedings in Theoretical Computer ScienceNov 4, 201525 citations

\mathbb{Z}_2

-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.