Pith. sign in

REVIEW 4 major objections 5 minor 63 references

Algebraic paradoxes in adaptive quantum computation

T0 review · 4 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adaptive MBQC that deterministically computes a non-affine Boolean function must yield an AvN contextuality paradox.

desk verdict A genuinely new flattening of adaptive MBQC into an AvN scenario, with a plausible but not yet rigorous induction — send to strong referees. read the letter →

arxiv 2607.26157 v1 pith:GVPHW3IE submitted 2026-07-28 quant-ph cs.LO

Samson Abramsky , Rui Soares Barbosa , Carmen Constantin , Martti Karvonen This is my paper · ORCID
classification quant-phcs.LO MSC 81P1381P68 PACS 03.65.Ta03.67.Lx
keywords measurement-basedquantumcomputationadaptivitycontextualityall-versus-nothingargumentZ2-linearMBQCcohomologicalstrongempiricalmodels
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that any adaptive measurement-based quantum computation (MBQC) with Z2-linear classical control that deterministically computes a non-affine Boolean function must exploit a quantum resource containing an all-versus-nothing (AvN) paradox: a family of linear equations over Z2 that hold in every run but are jointly inconsistent. This is an algebraic, linear-algebraically checkable form of strong contextuality, strengthening an earlier result that only demonstrated strong contextuality in a non-algebraic sense. The proof is constructive: adaptive protocols are flattened into ordinary measurements on a larger scenario of tree-like protocols, and the inconsistent equations are built inductively from the protocol tree. A corollary resolves a longstanding open question by showing that cohomological witnesses of contextuality extend to adaptive protocols, in both the sheaf-theoretic and group-cohomological frameworks. If correct, the result means the computational advantage of adaptive MBQC is always backed by an explicit linear contradiction.

What carries the argument

The central object is the scenario MP(BI,Z2) of Z2-valued measurement protocols on a Bell scenario BI — a multi-site scenario where each context picks at most one measurement per site — whose 'measurements' are adaptive protocol trees with branching nodes (outcome-dependent continuations) and multiplicative nodes (halt-if-outcome-mismatch), including higher-arity parity nodes that measure a set of variables and return only their total parity. The key identity is equation (4): for any empirical model e and any protocol p with post-processing Z and linear encoding Q, the sum over all inputs w of the measurement Q(w).p;Z is 0 in the Z2-linear theory of MP(e,Z2) whenever the input dimension is a

What would settle it

Enumerate all unary-node protocols with up to four sites and all linear encodings Q with input dimension l = m(p)+2, and directly evaluate the sum in equation (4) over every global assignment of outcomes to the underlying measurements; if any assignment yields a sum of 1 rather than 0, then Theorem 5.11 (and hence Theorem 3.6) is false. More specifically, search for a pair (p, v.p) where the splicing construction of Lemma 6.4 produces a protocol violating the admissibility condition of Definition 5.1 (for example, a node re-measuring a site with a different setting), or find two orders of elim

Watch

Extended reading notes

Core claim

The central claim (Theorem 3.6) is: if an MBQC on a Bell-type scenario, described by an empirical model e, a base protocol p, and linear pre- and post-processing maps Q and Z, deterministically computes a non-affine function f: Z2^l → Z2^o, then the induced empirical model MP(e,Z2) on the scenario of measurement protocols MP(BI,Z2) has an inconsistent Z2-linear theory — its linear equations entail the contradiction 0 = 1. The proof reduces to the single-output, two-input case of odd-weight Boolean functions, where the sum over all inputs of f(w) equals 1 while the key identity (equation (4)) says that the corresponding sum of protocol measurements Q(w).p;Z vanishes in the Z2-linear theory fo

Load-bearing premise

The proof of the main theorem relies on two combinatorial constructions that the paper itself describes as informal or 'not fully rigorous': the splicing lemma (Lemma 6.4) and the conventions for repeated measurement variables in Section 6.4; if either fails in an edge case — for example with overlapping measurement sets, multiplicative nodes, or output-bit interactions — the key identity (4) that drives the contradiction would not be established.

Editorial extensions

If this is right

  • If the theorem is correct, every deterministic adaptive Z2-linear MBQC computing a non-affine function carries an explicit AvN paradox, so contextuality in the adaptive setting is always witnessed by linear algebra rather than only topological invariants.
  • A corollary settles an open question about cohomological contextuality: non-vanishing cohomological witnesses exist for adaptive protocols, both in the sheaf-cohomological and group-cohomology frameworks, with the sheaf-theoretic witness propagating back to the original scenario.
  • The constructive proof gives an algorithm to extract the inconsistent linear system directly from the protocol tree, potentially enabling automated paradox generation for adaptive quantum circuits.
  • The flattening construction establishes that adaptive AvN arguments are strictly more informative than non-adaptive ones: the paper exhibits cases where the underlying scenario has a consistent linear theory even though the protocol scenario is AvN-contextual.
  • The same flattening technique offers a general bridge for lifting other non-adaptive contextuality tools (for example, measures of contextuality or simulation relations) to adaptive MBQC.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A quantitative refinement of the main theorem is a plausible next step: relating the success probability of a noisy adaptive MBQC to the nonlinearity of the computed function and a contextual-fraction-like measure on the flattened scenario would extend the known non-adaptive inequality to feed-forward protocols.
  • The explicit AvN witnesses may be usable for self-testing adaptive quantum hardware: certifying not only the resource state but also the feed-forward mechanism, since the paradox constrains the entire conditional measurement structure.
  • The flattening/co-Kleisli perspective likely generalises beyond Z2 and Bell scenarios to qudit MBQC and arbitrary algebraic contextuality scenarios, potentially producing a comonadic resource theory of adaptive protocols.
  • Because adaptive AvN arguments can detect contextuality that flat arguments miss, they could provide sharper, hardware-relevant constraints for error detection in adaptive quantum devices, going beyond standard randomised benchmarking.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper presents a constructive proof that any deterministic adaptive Z2-linear MBQC protocol computing a non-affine Boolean function must exhibit an All-versus-Nothing (AvN) algebraic contextuality witness in a flattened scenario of measurement protocols (Theorem 3.6). The proof reduces to establishing equation (4), formalized as Theorem 5.11, via an induction on branching depth that uses three tree transformations: splicing (Lemma 6.4), condensing (Lemma 6.6), and removal of higher-arity nodes (§6.4). The paper further claims cohomological consequences, including a resolution of Raussendorf's open question on extending cohomological witnesses to adaptive protocols (Theorem 7.1 and §7.2).

Significance. If the main theorem holds, it is a substantial advance: it extends the algebraic AvN paradigm from non-adaptive to adaptive MBQC, gives an explicit inductive construction of inconsistent linear equations from any non-linear deterministic Z2-linear computation, and supplies cohomological witnesses in both Čech and group-cohomology frameworks, answering a question raised by Raussendorf. The paper also contains a genuinely useful flattening construction (MP(BI,Z2)) and a worked adaptive example in Section 4 that makes the intended mechanism concrete. The proof is largely machine-checkable in principle, and the authors are commendably explicit about the two places where the current exposition is informal. However, those two gaps are load-bearing, and the cohomological consequence is only sketched.

major comments (4)
  1. [§6.2, Lemma 6.4 (footnote 10)] Lemma 6.4 is the first load-bearing step in the induction for Theorem 5.11, yet it is not proved. The proof is replaced by the statement 'we believe that the slightly less formal exposition here is more illuminating'. The informal splicing construction decomposes a protocol as 'p1, then x, then ...', but Definition 5.1 only allows prepending a node to a continuation; there is no formal operation of 'initial subprotocol followed by node'. Consequently, the existence of q, the preservation of p+v.p = q+v.q, and the asserted rank reduction via Tq(u*) = Tp(u*) + Q(w*) are not established. Since Lemma 6.5 and hence Step 1 of Theorem 5.11 rely directly on Lemma 6.4, equation (7) is not yet proven.
  2. [§6.4, repeated-occurrence conventions (pp. 28–29)] The elimination of higher-arity nodes (Lemma 6.9 and Lemma 6.10) depends on a convention for protocols in which the same measurement variable occurs twice. The paper admits: 'Formally, this is not fully rigorous without defining these protocols with repeated measurements and proving a version of Theorem 6.3 decomposing them into branches.' The asserted 'first occurrence' convention is claimed to be confluent, but no proof is given. This is not a cosmetic issue: the reduction to smaller n(p) in Step 3 fails if the convention is not well defined on arbitrary families of overlapping measurement sets arising from repeated applications of Lemma 6.8. Thus the induction in Theorem 5.11 is incomplete.
  3. [§6.3, Lemma 6.6] The proof of the condensing lemma is presented as an informal 'in a bit more detail' construction, not a full verification. In particular, the claim that 'q behaves similarly to p in that, barring them aborting early, the vector giving the measurement settings and the final output bit of both p and q is given by w+Tb' is asserted without a formal induction, and the compatibility argument showing that p and q return the same outcome for every global assignment is sketched rather than proved. Lemma 6.7 and Step 2 of Theorem 5.11 depend on this result, so the gap must be closed.
  4. [§7.1, Theorem 7.1 and §7.3] The paper claims to resolve Raussendorf's open question, but Theorem 7.1 is only given a proof sketch, with the explicit caveat that 'the part of this argument requiring significant elaboration is the verification of the functoriality and naturality properties'. The same is true of the group-cohomological consequences in §7.2. If the open-question resolution is a headline contribution, the cohomological transfer needs either a full proof or an explicit statement that it is a conjecture/outline for future work. As written, the claimed resolution is not fully established in this manuscript.
minor comments (5)
  1. [§3.2, Lemma 3.5] In the text after Lemma 3.5, 'by Theorem 3.5' should read 'by Lemma 3.5' (the statement is numbered as a Lemma). Also, the reduction from l to 2 input bits silently assumes the inclusion of a two-dimensional subspace is composed with Q correctly; this is likely fine but deserves a short remark.
  2. [§5.2, Definition 5.7] The definition of MP(BI,Z2) uses 'Theorem 5.1' and 'Theorem 5.9' where the manuscript's own cross-references sometimes call definitions 'Theorems'. This is a consistency issue with the numbering style (Definitions 5.1, 5.2, etc. are referenced as 'Theorem 5.1' in several places).
  3. [§6.1, Lemma 6.2] The proof of Lemma 6.2 says 'This follows from Theorem 5.9 by a straightforward case split, for each global assignment g, on whether ...'. This is acceptable but the case split should be written out, since this lemma is used repeatedly in Lemma 6.3 and later in the paper.
  4. [§6.4, Lemma 6.8] The notation in the displayed equation (10) is ambiguous: the branch 's' appears both as a subprotocol and as a variable in the tree, and the reader must infer that 's' is a branch of the prefix. A brief clarification of the notation would help.
  5. [§7.2] The phrase 'along the action of Q' and the use of 'πs(q)+1' in Lemma 6.7 are slightly confusing because q may have a different set of sites than p; the projection should be explained more explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the AvN equations are constructed inductively from protocol trees, not fitted; self-citations are background bridges and the flagged rigor gaps are proof-completeness issues, not definitional reductions.

full rationale

Walking the derivation chain, I find no circular step. The main identity (7) is proved by induction on n(p), with the three tree transformations (splicing Lemma 6.4, condensation Lemma 6.6, arity reduction Lemma 6.8/6.10) each stated as general combinatorial lemmas and justified operationally through Proposition 5.9; none of them assumes the conclusion. In particular, Theorem 3.6 is derived by adding the four equations (3) for an odd-weight function and separately proving the protocol-side sum (4) vanishes for every e:BI, so the inconsistency is constructed rather than fitted. The repeated use of the authors' own framework — [9] for the flattening analogy, [10, Theorem 21] in Theorem 7.1's first implication — is modular: [10] is a published flat-scenario theorem applied to the newly defined scenario MPZ2(e), not an assumption of the adaptive target, and the rest of Theorem 7.1 is sketched, not reduced to it. The paper itself flags two proof-completeness gaps (footnote in §6.2: "we believe that the slightly less formal exposition here is more illuminating"; §6.4: "Formally, this is not fully rigorous without defining these protocols with repeated measurements"). These are omitted formalizations, not circularity: the repeated-occurrence conventions are asserted as definitions of shorthand, not as the desired equation, and a failure there would break the induction rather than make the theorem true by construction. Hence no equation reduces to its input by definition; score 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 4 invented entities

No free parameters are fitted; the results are theorems. The new objects are proof devices (protocol classes, flattened scenario) and translation gadgets (G(S,e)); none have independent empirical evidence.

assumptions (5)
  • domain assumption Sheaf-theoretic framework of empirical models and contextuality ([12]) — local distributions on contexts, no-disturbance, global sections.
    The paper's definitions of scenario, empirical model, and (strong/AVN) contextuality all presuppose this framework; the main theorem is stated within it.
  • domain assumption Definitions and properties of Z2-linear theory and AvN contextuality ([10]) — an inconsistent linear theory witnesses AvN contextuality.
    Used to identify the target: 'the model MP(e,Z2) has an inconsistent Z2-linear theory'.
  • standard math Lemma 3.5: a Boolean function f : Z2^l -> Z2 is affine iff all restrictions to two-dimensional subspaces have even weight.
    Stated without proof; used to reduce the main theorem to a 2-input odd-weight function.
  • ad hoc to paper Repeated-occurrence conventions for measurement variables (Section 6.4): duplicate measurements resolve to first occurrence or kill the branch.
    Introduced to make Lemmas 6.8–6.9 expansion well-defined; the paper admits this is 'not fully rigorous' without extra definitions.
  • domain assumption Cohomological background: [10, Theorem 21] AvN implies Čech-CSC; maps of scenarios behave functorially; [2] group-cohomology obstruction equivalence.
    Theorem 7.1 proof sketch relies on these previous results; details of functoriality are deferred.
invented entities (4)
  • Multiplicative measurement nodes (⟨D,r,q⟩)
    purpose: Protocols that abort (return 0) unless the parity of D equals r; introduced to make the induction hypothesis of Theorem 5.11 strong enough.
    Purely mathematical construct with no empirical referent outside the paper; it has a handle only via the formal output o(p,g).
  • Higher-arity parity nodes (measuring sum x1+...+xd at once)
    purpose: Allow condensing non-maximal-rank adaptivity matrices into fewer levels.
    Defined as a shorthand for jointly measuring and returning parity; no new physics.
  • Flattened scenario MP(BI,Z2) of measurement protocols
    purpose: Represents adaptive protocols as ordinary measurements so non-adaptive AvN and cohomological tools apply.
    A mathematical scenario, not a physical system; its empirical content is inherited from e via MP(e,Z2).
  • Free partial pointed Boolean group G(S,e)
    purpose: Translate inconsistent Z2-linear theory into absence of a splitting, i.e. a group-cohomological obstruction (Section 7.2).
    A quotient construction used to phrase AvN in group-cohomological language; no independent observable predictions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algebraic paradoxes in adaptive quantum computation." pith.science (2026). https://pith.science/paper/GVPHW3IE

@misc{pith2026260726157,
  author       = {Pith},
  title        = {Pith review of: Algebraic paradoxes in adaptive quantum computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GVPHW3IE}},
  note         = {Machine review of arXiv:2607.26157}
}
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 $\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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

63 extracted references · 17 canonical work pages

  1. [1]

    Cohomology and the algebraic structure of contextuality in measurement based quantum computation

    Sivert Aasnæss. Cohomology and the algebraic structure of contextuality in measurement based quantum computation. In Bob Coecke and Matthew Leifer, editors,16th International Conference on Quantum Physics and Logic (QPL 2019), volume 318 ofElectronic Proceedings in Theoretical Computer Science, pages 242–253. Open Publishing Association, May 2020. doi:10....

    work page doi:10.4204/eptcs.318.15 2019

  2. [2]

    DPhil thesis, University of Oxford, 2021

    Sivert Aasnæss.Comparing two cohomological obstructions for contextuality, and a generalised construction of quantum advantage with shallow circuits. DPhil thesis, University of Oxford, 2021. URL: https://ora.ox.ac.uk/objects/uuid: a31ce72c-3d5e-4ca2-afa3-a38afbb93833/, arXiv:2212.09382 [quant-ph]

    arXiv 2021

  3. [3]

    Contextuality: At the borders of paradox

    Samson Abramsky. Contextuality: At the borders of paradox. In Elaine Landry, editor, Categories for the Working Philosopher, chapter 11, pages 262–285. Oxford University Press, November 2017.doi:10.1093/oso/9780198748991.003.0011

    arXiv 2017

  4. [4]

    Contextuality, algebraic structure, and state-independence

    Samson Abramsky. Contextuality, algebraic structure, and state-independence. In Luca Reggio, Sam van Gool, and Wesley Fussner, editors,Mai Gehrke on Logic, Algebra and Duality, Outstanding Contributions to Logic. Springer, 2026. To appear

    2026

  5. [5]

    The logic of contextuality

    Samson Abramsky and Rui Soares Barbosa. The logic of contextuality. In Christel Baier and Jean Goubault-Larrecq, editors,29th EACSL Annual Conference on Computer Science Logic (CSL 2021), volume 183 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, January 2021. doi: 10.4230/LIP...

    doi:10.4230/lipics.csl.2021.5 2021

  6. [6]

    Contextuality in logical form: Duality for transitive partial CABAs

    Samson Abramsky and Rui Soares Barbosa. Contextuality in logical form: Duality for transitive partial CABAs. Talk presented at 10th Conference on Topology, Algebra, and Categories in Logic (TACL 2022), June 2022. URL:https://www.mat.uc.pt/~tacl2022/pdfs/TACL_2022_ paper_19.pdf

    2022

  7. [7]

    Minimum quantum resources for strong non-locality

    Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, Nadish de Silva, Kohei Kishida, and Shane Mansfield. Minimum quantum resources for strong non-locality. In Mark M Wilde, editor,12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), volume 73 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 9:1...

    doi:10.4230/lipics.tqc.2017.9 2017

  8. [8]

    Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, and Simon Perdrix. A complete char- acterization of all-versus-nothing arguments for stabilizer states.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 375(2106):20160385, November 2017.doi:10.1098/rsta.2016.0385

    arXiv 2017

Show all 63 references
  1. [9]

    A comonadic view of simulation and quantum resources

    Samson Abramsky, Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield. A comonadic view of simulation and quantum resources. In34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019), pages 23:1–23:12. IEEE, August 2019. doi:10.1109/LICS. 2019.8785677

    2019

  2. [10]

    Contextuality, cohomology and paradox

    Samson Abramsky, Rui Soares Barbosa, Kohei Kishida, Raymond Lal, and Shane Mansfield. Contextuality, cohomology and paradox. In Stephan Kreutzer, editor,24th EACSL Annual Conference on Computer Science Logic (CSL 2015), volume 41 ofLeibniz International Proceedings in Informat...

    2015 doi

  3. [11]

    Contextual fraction as a measure of contextuality.Physical Review Letters, 119(5):050504, August 2017.doi:10.1103/ PhysRevLett.119.050504

    Samson Abramsky, Rui Soares Barbosa, and Shane Mansfield. Contextual fraction as a measure of contextuality.Physical Review Letters, 119(5):050504, August 2017.doi:10.1103/ PhysRevLett.119.050504. ALGEBRAIC PARADOXES IN ADAPTIVE QUANTUM COMPUTATION 37

    2017

  4. [12]

    The sheaf-theoretic structure of non-locality and contextuality.New Journal of Physics, 13(11):113036, November 2011

    Samson Abramsky and Adam Brandenburger. The sheaf-theoretic structure of non-locality and contextuality.New Journal of Physics, 13(11):113036, November 2011. doi:10.1088/ 1367-2630/13/11/113036

    2011

  5. [13]

    The cohomology of non-locality and contextuality

    Samson Abramsky, Shane Mansfield, and Rui Soares Barbosa. The cohomology of non-locality and contextuality. In Bart Jacobs, Peter Selinger, and Bas Spitters, editors,8th International Workshop on Quantum Physics and Logic (QPL 2011), volume 95 ofElectronic Proceedings in Theor...

    2011 doi

  6. [14]

    Janet Anders and Dan E. Browne. Computational power of correlations.Physical Review Letters, 102(5):050502, February 2009.doi:10.1103/PhysRevLett.102.050502

    2009 doi

  7. [15]

    Extending and characterizing quantum magic games, September 2012

    Alex Arkhipov. Extending and characterizing quantum magic games, September 2012. arXiv:1209.3819 [quant-ph]

    2012 arXiv

  8. [16]

    Scalable Bell inequalities for qubit graph states and robust self-testing.Physical Review Letters, 124(2):020402, January 2020.doi:10.1103/PhysRevLett.124.020402

    Flavio Baccari, Remigiusz Augusiak, Ivan Šupić, Jordi Tura, and Antonio Acín. Scalable Bell inequalities for qubit graph states and robust self-testing.Physical Review Letters, 124(2):020402, January 2020.doi:10.1103/PhysRevLett.124.020402

    2020 doi

  9. [17]

    DPhil thesis, University of Oxford, 2015

    Rui Soares Barbosa.Contextuality in quantum mechanics and beyond. DPhil thesis, University of Oxford, 2015

    2015

  10. [18]

    Closing Bell: Boxing black box simulations in the resource theory of contextuality

    Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield. Closing Bell: Boxing black box simulations in the resource theory of contextuality. In Alessandra Palmigiano and Mehrnoosh Sadrzadeh, editors,Samson Abramsky on Logic and Structure in Computer Science and Beyond, volume...

    2023 doi

  11. [19]

    On the Einstein Podolsky Rosen paradox.Physics Physique Fizika, 1(3):195–200, November 1964.doi:10.1103/PhysicsPhysiqueFizika.1.195

    John S Bell. On the Einstein Podolsky Rosen paradox.Physics Physique Fizika, 1(3):195–200, November 1964.doi:10.1103/PhysicsPhysiqueFizika.1.195

    1964 doi

  12. [20]

    On the problem of hidden variables in quantum mechanics.Reviews of Modern Physics, 38(3):447–452, July 1966.doi:10.1103/RevModPhys.38.447

    John S Bell. On the problem of hidden variables in quantum mechanics.Reviews of Modern Physics, 38(3):447–452, July 1966.doi:10.1103/RevModPhys.38.447

    1966 doi

  13. [21]

    Double color codes, September 2015

    Sergey Bravyi and Andrew Cross. Double color codes, September 2015. arXiv:1509.03239 [quant-ph]

    2015 arXiv

  14. [22]

    Quantum advantage with shallow circuits

    Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308–311, October 2018.doi:10.1126/science.aar3106

    2018 doi

  15. [23]

    Briegel, Dan E

    Hans J. Briegel, Dan E. Browne, Wolfgang Dür, Robert Raussendorf, and Maarten van den Nest. Measurement-based quantum computation.Nature Physics, 5(1):19–26, January 2009. doi:10.1038/nphys1157

    2009 doi

  16. [24]

    On the cohomology of contextuality

    Giovanni Carù. On the cohomology of contextuality. In Ross Duncan and Chris Heunen, editors,13th International Conference on Quantum Physics and Logic (QPL 2016), volume 236 ofElectronic Proceedings in Theoretical Computer Science, pages 21–39. Open Publishing Association, Jan...

    2016 doi

  17. [25]

    Towards a complete cohomology invariant for non-locality and contextuality, July 2018

    Giovanni Carù. Towards a complete cohomology invariant for non-locality and contextuality, July 2018. arXiv:1807.04203 [quant-ph]

    2018 arXiv

  18. [26]

    Characterization of binary constraint system games

    Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors,41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), volume 8572 ofLecture No...

    2014

  19. [27]

    Robust self-testing for linear constraint system games, September 2017

    Andrea Coladangelo and Jalex Stark. Robust self-testing for linear constraint system games, September 2017. arXiv:1709.09267 [quant-ph]

    2017 arXiv

  20. [28]

    No quantum solutions to linear constraint systems from monomial measurement-based quantum computation in odd prime dimension, January 2026

    Markus Frembs, Cihan Okay, and Ho Yiu Chung. No quantum solutions to linear constraint systems from monomial measurement-based quantum computation in odd prime dimension, January 2026. arXiv:2601.11367 [quant-ph]

    2026

  21. [29]

    Contextuality as a resource for measurement-based quantum computation beyond qubits.New Journal of Physics, 20(10):103011, October 2018.doi:10.1088/1367-2630/aae3ad

    Markus Frembs, Sam Roberts, and Stephen D Bartlett. Contextuality as a resource for measurement-based quantum computation beyond qubits.New Journal of Physics, 20(10):103011, October 2018.doi:10.1088/1367-2630/aae3ad

    2018 doi

  22. [30]

    Generalised Mermin-type non-locality arguments.Logical Methods in Computer Science, 15(2):3:1–3:51, April 2019.doi:10.23638/lmcs-15(2:3)2019

    Stefano Gogioso and William Zeng. Generalised Mermin-type non-locality arguments.Logical Methods in Computer Science, 15(2):3:1–3:51, April 2019.doi:10.23638/lmcs-15(2:3)2019

    2019 doi

  23. [31]

    Quantum-classical separation in bounded-resource tasks arising from measurement contextuality, December 2025

    Google Quantum AI (Shashwat Kumar, Eliott Rosenberg, Alejandro Grajales Dau, Ro- drigo Cortiñas, et al.). Quantum-classical separation in bounded-resource tasks arising from measurement contextuality, December 2025. arXiv:2512.02284 [quant-ph]

    2025

  24. [32]

    Going beyond Bell’s theorem

    Daniel M Greenberger, Michael A Horne, and Anton Zeilinger. Going beyond Bell’s theorem. In Menas Kafatos, editor,Bell’s Theorem, Quantum Theory and Conceptions of the Universe, volume 37 ofFundamental Theories of Physics, pages 69–72. Springer, October 1989.doi: 10.1007/978-9...

    1989 doi

  25. [33]

    Nonlocality for two particles without inequalities for almost all entangled states

    Lucien Hardy. Nonlocality for two particles without inequalities for almost all entangled states. Physical Review Letters, 71(11):1665–1668, September 1993.doi:10.1103/PhysRevLett.71. 1665

    1993 doi

  26. [34]

    Many-body contex- tuality and self-testing quantum matter via nonlocal games, December 2025

    Oliver Hart, David T Stephen, Evan Wickenden, and Rahul Nandkishore. Many-body contex- tuality and self-testing quantum matter via nonlocal games, December 2025. arXiv:2512.16886 [quant-ph]

    2025

  27. [35]

    Contextuality supplies the ‘magic’ for quantum computation.Nature, 510(7505):351–355, June 2014.doi:10.1038/ nature13460

    Mark Howard, Joel Wallman, Victor Veitch, and Joseph Emerson. Contextuality supplies the ‘magic’ for quantum computation.Nature, 510(7505):351–355, June 2014.doi:10.1038/ nature13460

    2014

  28. [36]

    Analytic and nearly optimal self-testing bounds for the Clauser-Horne- Shimony-Holt and Mermin inequalities.Physical Review Letters, 117(7):070402, August 2016

    Jędrzej Kaniewski. Analytic and nearly optimal self-testing bounds for the Clauser-Horne- Shimony-Holt and Mermin inequalities.Physical Review Letters, 117(7):070402, August 2016. doi:10.1103/PhysRevLett.117.070402

    2016 doi

  29. [37]

    Categories of empirical models

    Martti Karvonen. Categories of empirical models. In Peter Selinger and Giulio Chiribella, editors,15th International Conference on Quantum Physics and Logic (QPL 2018), volume287 ofElectronic Proceedings in Theoretical Computer Science, pages 239–252. Open Publishing Associati...

    2018 doi

  30. [38]

    Contextuality of quantum error-correcting codes.PRX Quantum, 7(1):010319, January 2026.doi:10.1103/7zb5-vs4x

    Derek Khu, Andrew Tanggara, Chao Jin, and Kishor Bharti. Contextuality of quantum error-correcting codes.PRX Quantum, 7(1):010319, January 2026.doi:10.1103/7zb5-vs4x

    2026 doi

  31. [39]

    Kirby and Peter J

    William M. Kirby and Peter J. Love. Contextuality test of the nonclassicality of variational quantum eigensolvers.Physical Review Letters, 123(20):200501, November 2019.doi:10.1103/ PhysRevLett.123.200501

    2019

  32. [40]

    Classical simulation of noncontextual Pauli Hamiltonians

    William M Kirby and Peter J Love. Classical simulation of noncontextual Pauli Hamiltonians. Physical Review A, 102(3):032418, September 2020.doi:10.1103/PhysRevA.102.032418

    2020 doi

  33. [41]

    The problem of hidden variables in quantum mechanics

    Simon Kochen and Ernst P Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17(1):59–87, July 1967. doi:10.1512/iumj.1968.17. 17004

    1967 doi

  34. [42]

    Measurement-based quantum computation with trapped ions.Physical Review Letters, 111(21):210501, November 2013.doi:10.1103/PhysRevLett.111.210501

    Benjamin P Lanyon, Petar Jurcevic, Michael Zwerger, Cornelius Hempel, Esteban A Martinez, Wolfgang Dür, Hans J Briegel, Rainer Blatt, and Christian F Roos. Measurement-based quantum computation with trapped ions.Physical Review Letters, 111(21):210501, November 2013.doi:10.110...

    2013 doi

  35. [43]

    Circuit-based vs

    Harashta Tatimma Larasati and Byung-Soo Choi. Circuit-based vs. measurement-based quantum computing: a comparative analysis, layered metrics, and decision flow for ap- proach selection.EPJ Quantum Technology, 13(1):39, February 2026.doi:10.1140/epjqt/ s40507-026-00483-1

    2026 doi

  36. [44]

    Quantum advantage from sequential-transformation contextuality.Physical Review Letters, 121(23):230401, December 2018

    Shane Mansfield and Elham Kashefi. Quantum advantage from sequential-transformation contextuality.Physical Review Letters, 121(23):230401, December 2018. doi:10.1103/ PhysRevLett.121.230401

    2018

  37. [45]

    Self testing quantum apparatus.Quantum Information and Computation, 4(4):273–286, July 2004.doi:10.26421/QIC4.4-3

    Dominic Mayers and Andrew Yao. Self testing quantum apparatus.Quantum Information and Computation, 4(4):273–286, July 2004.doi:10.26421/QIC4.4-3

    2004 doi

  38. [46]

    doi:10.1103/PhysRevLett

    NDavidMermin.Extremequantumentanglementinasuperpositionofmacroscopicallydistinct states.Physical Review Letters, 65(15):1838–1840, October 1990. doi:10.1103/PhysRevLett. 65.1838

    1990 doi

  39. [47]

    Simple unified form for the major no-hidden-variables theorems.Physical Review Letters, 65(27):3373–3376, December 1990.doi:10.1103/PhysRevLett.65.3373

    N David Mermin. Simple unified form for the major no-hidden-variables theorems.Physical Review Letters, 65(27):3373–3376, December 1990.doi:10.1103/PhysRevLett.65.3373

    1990 doi

  40. [48]

    Bartlett, and Robert Raussendorf

    Cihan Okay, Sam Roberts, Stephen D. Bartlett, and Robert Raussendorf. Topological proofs of contextuality in quantum mechanics.Quantum Information and Computation, 17(13 & 14):1135–1166, November 2017.doi:10.26421/QIC17.13-14-5

    2017 doi

  41. [49]

    Incompatible results of quantum measurements.Physics Letters A, 151(3):107– 108, December 1990.doi:10.1016/0375-9601(90)90172-K

    Asher Peres. Incompatible results of quantum measurements.Physics Letters A, 151(3):107– 108, December 1990.doi:10.1016/0375-9601(90)90172-K

    1990 doi

  42. [50]

    Quantum nonlocality as an axiom.Foundations of Physics, 24(3):379–385, March 1994.doi:10.1007/BF02058098

    Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom.Foundations of Physics, 24(3):379–385, March 1994.doi:10.1007/BF02058098

    1994 doi

  43. [51]

    High-speed linear optics quantum computing using active feed-forward.Nature, 445(7123):65–69, January 2007.doi:10.1038/nature05346

    Robert Prevedel, Philip Walther, Felix Tiefenbacher, Pascal Böhi, Rainer Kaltenbaek, Thomas Jennewein, and Anton Zeilinger. High-speed linear optics quantum computing using active feed-forward.Nature, 445(7123):65–69, January 2007.doi:10.1038/nature05346

    2007 doi

  44. [52]

    Contextuality in measurement-based quantum computation.Physical Review A, 88(2):022322, August 2013.doi:10.1103/PhysRevA.88.022322

    Robert Raussendorf. Contextuality in measurement-based quantum computation.Physical Review A, 88(2):022322, August 2013.doi:10.1103/PhysRevA.88.022322

    2013 doi

  45. [53]

    Cohomological framework for contextual quantum computations.Quan- tum Information and Computation, 19(13 & 14):1141–1170, November 2019.doi:10.26421/ qic19.13-14-4

    Robert Raussendorf. Cohomological framework for contextual quantum computations.Quan- tum Information and Computation, 19(13 & 14):1141–1170, November 2019.doi:10.26421/ qic19.13-14-4

    2019

  46. [54]

    Putting paradoxes to work: Contextuality in measurement-based quan- tum computation

    Robert Raussendorf. Putting paradoxes to work: Contextuality in measurement-based quan- tum computation. In Alessandra Palmigiano and Mehrnoosh Sadrzadeh, editors,Sam- son Abramsky on Logic and Structure in Computer Science and Beyond, volume 25 of ALGEBRAIC PARADOXES IN ADAPT...

    2023 doi

  47. [55]

    A one-way quantum computer.Physical Review Letters, 86(22):5188–5191, May 2001.doi:10.1103/PhysRevLett.86.5188

    Robert Raussendorf and Hans J Briegel. A one-way quantum computer.Physical Review Letters, 86(22):5188–5191, May 2001.doi:10.1103/PhysRevLett.86.5188

    2001 doi

  48. [56]

    The role of cohomology in quantum computation with magic states.Quantum, 7:979, April 2023

    Robert Raussendorf, Cihan Okay, Michael Zurel, and Polina Feldmann. The role of cohomology in quantum computation with magic states.Quantum, 7:979, April 2023. doi:10.22331/ q-2023-04-13-979

    2023

  49. [57]

    DPhil thesis, University of Oxford, 2024

    Amy J Searle.Correlation and combinatorics: causal contextuality and spin systems. DPhil thesis, University of Oxford, 2024. URL: https://ora.ox.ac.uk/objects/uuid: 7f3e70f3-5136-4a64-89e8-858034004181

    2024

  50. [58]

    Mapping temporal correlations to contextuality correlations

    Amy J Searle, Rui Soares Barbosa, and Samson Abramsky. Mapping temporal correlations to contextuality correlations. Talk presented at 21st International Conference on Quantum Physics and Logic (QPL 2024), July 2024. URL:https://qpl2024.dc.uba.ar/abstracts/100.pdf

    2024

  51. [59]

    Operator solutions of linear systems and small cancella- tion, December 2024

    William Slofstra and Lu-Ming Zhang. Operator solutions of linear systems and small cancella- tion, December 2024. arXiv:2412.10305 [quant-ph]

    2024 arXiv

  52. [60]

    Self-testing of quantum systems: a review.Quantum, 4:337, September 2020.doi:10.22331/q-2020-09-30-337

    Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review.Quantum, 4:337, September 2020.doi:10.22331/q-2020-09-30-337

    2020 doi

  53. [61]

    Experimental one-way quantum computing

    Philip Walther, Kevin J Resch, Terry Rudolph, Emmanuel Schenck, Harald Weinfurter, Vlatko Vedral, Markus Aspelmeyer, and Anton Zeilinger. Experimental one-way quantum computing. Nature, 434(7030):169–176, March 2005.doi:10.1038/nature03347

    2005 doi

  54. [62]

    Scalable tests of quantum contextuality from stabilizer-testing nonlocal games, December

    Wanbing Zhao, H W Shawn Liew, Wen Wei Ho, Chunxiao Liu, and Vir B Bulchandani. Scalable tests of quantum contextuality from stabilizer-testing nonlocal games, December

  55. [2025]

    arXiv:2512.16654 [quant-ph]. Samson Abramsky Department of Computer Science, University College London London, United Kingdom Email address:s.abramsky@ucl.ac.uk Rui Soares Barbosa International Iberian Nanotechnology Laboratory Braga, Portugal Email address:rui.soaresbarbosa@i...

    2026

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.