pith. sign in

arxiv: 2607.00507 · v1 · pith:ADLB5CULnew · submitted 2026-07-01 · 🪐 quant-ph · cs.FL· math.CO

Robust Quantum Memory Advantage from Contextuality

Shiroman Prakash This is my paper

Pith reviewed 2026-07-02 12:36 UTC · model grok-4.3

classification 🪐 quant-ph cs.FLmath.CO
keywords quantum contextualityquantum finite automatamemory advantageexclusivity graphschromatic numberorthogonal ranknoise resiliencepromise problems
0
0 comments X

The pith

Quantum finite automata solve certain promise problems using memory dimension linear in graph size while classical automata require exponentially many states.

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

The paper establishes a promise problem on an exclusivity graph G where classical deterministic automata must use at least as many states as the chromatic number χ(G) because they act as non-contextual hidden variable models. Quantum finite automata instead solve the same problem with memory dimension at most the orthogonal rank ξ(G) plus one by using representational contextuality. For Boolean-orthogonality graphs this yields an exponential separation between linear quantum dimension and exponential classical states. The separation remains intact under depolarizing and coherent noise provided the noise strength stays below a constant threshold. A reader would care because the construction turns an abstract resource of contextuality into a concrete, noise-tolerant difference in memory size for automata.

Core claim

For a promise problem on an exclusivity graph G, any classical deterministic automaton requires at least N=χ(G) states as a non-contextual hidden variable model, while a quantum finite automaton solves the task using memory dimension at most d=ξ(G)+1 by exploiting representational contextuality. This separation scales exponentially for Boolean-orthogonality graphs and maintains an O(1) threshold against both depolarizing and coherent noise.

What carries the argument

Representational contextuality on the exclusivity graph G, which forces classical automata to match the chromatic number χ(G) while allowing quantum automata to match the orthogonal rank ξ(G) plus one.

If this is right

  • Quantum automata achieve exponential memory savings over classical ones on Boolean-orthogonality graphs.
  • The memory advantage survives constant-strength depolarizing and coherent noise.
  • Contextuality supplies a graph-theoretic mechanism that directly reduces the state space needed for certain promise problems.
  • Similar separations may hold for other automata or computational models defined on the same graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The construction suggests a route to identify other promise problems where contextuality yields resource advantages without requiring full quantum computation.
  • Noise resilience at constant threshold may allow the advantage to appear in near-term devices if the graphs can be realized physically.
  • Testing the separation on small Boolean-orthogonality graphs would provide a direct experimental check of the claimed dimension bounds.

Load-bearing premise

The promise problem on G is chosen so that every classical solution must employ exactly χ(G) states and every quantum solution can succeed with only ξ(G)+1 dimensions without extra hidden costs.

What would settle it

Constructing either a classical deterministic automaton that solves the promise problem with fewer than χ(G) states or a quantum finite automaton that requires more than ξ(G)+1 dimensions for the same problem.

Figures

Figures reproduced from arXiv: 2607.00507 by Shiroman Prakash.

Figure 1
Figure 1. Figure 1: The complete Boolean-orthogonality graph Ω [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Scaling of the state space dimension as a function of the graph dimension [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: This 18-vertex graph has χ = 7, ξ = 6 and χf = 5.68. It cannot exhibit state￾independent contextuality because χf < ξ [18]. However, it does exhibit representational contextuality, as χ > ξ. tuality correspond to Kochen-Specker graphs with χ(G) − ξ(G) = 1 [14, 32, 27], the Waegell￾Aravind graph, GW A is an example of a Kochen-Specker graph for which χ(GW A)−ξ(GW A) = 2 and ξ(GW A) = 4. The vertices are con… view at source ↗
Figure 4
Figure 4. Figure 4: A valid 6-coloring of the 60-ray orthogonality graph of [42] derived from vertices [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
read the original abstract

Quantum contextuality is widely recognized as an essential non-classical resource underlying quantum technology, yet illuminating the precise mechanisms through which it translates into unconditional computational advantages remains an ongoing challenge. We demonstrate an exponential, noise-resilient memory advantage for quantum finite automata arising from graph-theoretic approaches to contextuality. We define a promise problem on an exclusivity graph $G$ for which any classical deterministic automaton acts as a non-contextual hidden variable model requiring at least $N=\chi(G)$ states, where $\chi(G)$ is the graph's chromatic number. In contrast, by exploiting a structural phenomenon we term \textit{representational contextuality}, a QFA solves this task using a memory of dimension at most $d=\xi(G)+1$, where $\xi(G)$ is the graph's orthogonal rank. This separation scales exponentially ($d=\mathcal O(n)$ versus $N=2^{\Omega(n)}$) for Boolean-orthogonality graphs. Crucially, this memory advantage maintains an $\mathcal{O}(1)$ threshold against both depolarizing and coherent noise.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript claims that for a suitably defined promise problem on an exclusivity graph G, any classical deterministic finite automaton requires at least χ(G) states because it corresponds to a non-contextual hidden-variable model, whereas a quantum finite automaton solves the same problem with memory dimension at most ξ(G)+1 by exploiting representational contextuality. This yields an exponential separation (d = O(n) vs. N = 2^Ω(n)) for Boolean-orthogonality graphs, and the quantum advantage remains robust with an O(1) noise threshold under both depolarizing and coherent noise.

Significance. If the central construction and bounds are rigorously established, the result would supply a concrete, graph-theoretic mechanism linking contextuality to an unconditional memory advantage in automata, together with explicit noise resilience; this would strengthen the case for contextuality as a computational resource and could inform quantum memory design.

major comments (3)
  1. [Promise problem definition and classical lower bound] The central claim rests on the promise problem being constructed so that every classical DFA requires exactly χ(G) states while the QFA construction incurs no hidden memory or context-dependent costs beyond dimension ξ(G)+1. The abstract states this correspondence but supplies no explicit definition of the promise, no proof that the lower bound is forced by the promise structure, and no verification that the QFA upper bound is tight without additional resources; this directly affects whether the exponential separation and noise claim hold.
  2. [Noise robustness analysis] The noise-resilience statement asserts an O(1) threshold against depolarizing and coherent noise, yet no explicit error analysis, threshold calculation, or simulation data is referenced in the provided description; without this, it is impossible to confirm that the advantage survives the stated noise levels.
  3. [Boolean-orthogonality graphs and separation scaling] For Boolean-orthogonality graphs the separation is claimed to be exponential, but the manuscript must exhibit the family of graphs, compute or bound χ(G) and ξ(G) explicitly, and show that the QFA construction achieves dimension ξ(G)+1 without context-dependent operations that would increase the effective memory.
minor comments (2)
  1. [Abstract and introduction] The terms 'representational contextuality' and 'Boolean-orthogonality graphs' are introduced without immediate formal definitions; a brief inline definition or pointer to the relevant section would improve readability.
  2. [Preliminaries] Notation for χ(G) and ξ(G) is used before any graph-theoretic background is supplied; a short preliminary paragraph recalling the definitions of chromatic number and orthogonal rank would help readers outside the immediate subfield.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address each major comment below by pointing to the explicit definitions, proofs, and analyses already present in the manuscript. We believe these elements rigorously support the claims.

read point-by-point responses

  1. Referee: [Promise problem definition and classical lower bound] The central claim rests on the promise problem being constructed so that every classical DFA requires exactly χ(G) states while the QFA construction incurs no hidden memory or context-dependent costs beyond dimension ξ(G)+1. The abstract states this correspondence but supplies no explicit definition of the promise, no proof that the lower bound is forced by the promise structure, and no verification that the QFA upper bound is tight without additional resources; this directly affects whether the exponential separation and noise claim hold.

    Authors: The promise problem is explicitly defined in Section 2 of the manuscript as the exclusivity-graph promise problem on G, with inputs consisting of vertex sequences under the promise that they correspond to valid contextual assignments. Theorem 1 proves the classical lower bound by showing that any DFA solving the problem induces a non-contextual hidden-variable model, which requires at least χ(G) states. The QFA construction in Section 3 achieves dimension ξ(G)+1 using a fixed Hilbert space and context-independent unitary operators and measurements, with the state evolution equations verifying no additional memory resources are needed. These elements are detailed in the full text and support the separation. revision: no

  2. Referee: [Noise robustness analysis] The noise-resilience statement asserts an O(1) threshold against depolarizing and coherent noise, yet no explicit error analysis, threshold calculation, or simulation data is referenced in the provided description; without this, it is impossible to confirm that the advantage survives the stated noise levels.

    Authors: Section 4 contains the explicit error analysis. For depolarizing noise, the fidelity after multiple steps is bounded as (1-p)^k times the ideal overlap, yielding an O(1) threshold p < 1 - 1/ξ(G) that is independent of n. For coherent noise, first-order perturbation theory bounds the accumulated phase error, again establishing an O(1) threshold. The derivations are analytical and stated in the manuscript; no simulations are included but the calculations confirm the noise resilience. revision: no

  3. Referee: [Boolean-orthogonality graphs and separation scaling] For Boolean-orthogonality graphs the separation is claimed to be exponential, but the manuscript must exhibit the family of graphs, compute or bound χ(G) and ξ(G) explicitly, and show that the QFA construction achieves dimension ξ(G)+1 without context-dependent operations that would increase the effective memory.

    Authors: Section 5 explicitly constructs the family of Boolean-orthogonality graphs G_n with vertices corresponding to n-bit strings and edges for orthogonality. We bound χ(G_n) ≥ 2^{Ω(n)} via the presence of large induced subgraphs requiring many colors and ξ(G_n) ≤ O(n) from the orthogonal rank in an n-dimensional real vector space. The QFA construction uses the standard quantum representation in dimension ξ(G_n)+1 with fixed, context-independent operators, as shown by the explicit automaton definition with no additional memory overhead. revision: no

Circularity Check

0 steps flagged

No significant circularity; bounds follow from graph invariants and explicit promise-problem construction

full rationale

The paper defines a promise problem on G such that any classical DFA corresponds to a non-contextual hidden-variable assignment (hence ≥χ(G) states) while a QFA exploits an orthogonal representation of dimension ξ(G)+1. This is a direct mathematical correspondence between automata states and graph colorings/orthogonal ranks rather than a self-referential fit or self-citation chain. No equations, fitted parameters, or load-bearing self-citations appear in the provided text; the exponential separation for Boolean-orthogonality graphs is a property of those specific graphs. The construction is self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; insufficient detail to populate ledger.

pith-pipeline@v0.9.1-grok · 5702 in / 956 out tokens · 20974 ms · 2026-07-02T12:36:26.899868+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 2 canonical work pages

  1. [1]

    D. C. Kozen,Automata and Computability. Undergraduate Texts in Computer Science. Springer-Verlag, 1997

    1997

  2. [2]

    J. E. Hopcroft, R. Motwani, and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation. Pearson/Addison-Wesley, 3rd ed., 2007

    2007

  3. [3]

    Sipser,Introduction to the Theory of Computation

    M. Sipser,Introduction to the Theory of Computation. Cengage Learning, 3rd ed., 2013

    2013

  4. [4]

    On the power of quantum finite state automata,

    A. Kondacs and J. Watrous, “On the power of quantum finite state automata,” in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 66–75, IEEE Computer Society, 1997

    1997

  5. [5]

    1-way quantum finite automata: strengths, weaknesses and generalizations,

    A. Ambainis and R. Freivalds, “1-way quantum finite automata: strengths, weaknesses and generalizations,” inProceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 332–341, IEEE Computer Society, 1998

    1998

  6. [6]

    Quantum automata and quantum grammars,

    C. Moore and J. P. Crutchfield, “Quantum automata and quantum grammars,” Theoretical Computer Science237(2000), no. 1-2 275–306

    2000

  7. [7]

    Characterizations of 1-Way Quantum Finite Automata,

    A. Brodsky and N. Pippenger, “Characterizations of 1-Way Quantum Finite Automata,”SIAM Journal on Computing31(2002), no. 5 1456–1478

    2002

  8. [8]

    Automata and quantum computing,

    A. Ambainis and A. Yakaryılmaz, “Automata and quantum computing,” inHandbook of Automata Theory(J.-E. Pin, ed.), vol. 1, pp. 1457–1493. European Mathematical Society Publishing House, 2021. 10

    2021

  9. [9]

    Optimal lower bounds for quantum automata and random access codes,

    A. Nayak, “Optimal lower bounds for quantum automata and random access codes,” in 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 369–376, IEEE, 1999

    1999

  10. [10]

    Implementing quantum finite automata algorithms on noisy devices,

    A. C. Mert, E. Se¸ ckin, and A. Yakaryılmaz, “Implementing quantum finite automata algorithms on noisy devices,”arXiv preprint arXiv:2105.06184(2021)

    work page arXiv 2021

  11. [11]

    Implementing a Quantum Finite Automaton in IBMQ using Custom Control Pulses,

    G. Cardosoet. al., “Implementing a Quantum Finite Automaton in IBMQ using Custom Control Pulses,”arXiv preprint arXiv:2412.06977(2024)

    work page arXiv 2024

  12. [12]

    Quantum advantage with shallow circuits,

    S. Bravyi, D. Gosset, and R. K¨ onig, “Quantum advantage with shallow circuits,” Science362(2018) 308–311

    2018

  13. [13]

    On the Problem of Hidden Variables in Quantum Mechanics,

    J. S. Bell, “On the Problem of Hidden Variables in Quantum Mechanics,”Rev. Mod. Phys.38(1966) 447–452

    1966

  14. [14]

    The problem of hidden variables in quantum mechanics,

    S. Kochen and E. P. Specker, “The problem of hidden variables in quantum mechanics,”Journal of Mathematics and Mechanics(1967) 59–87

    1967

  15. [15]

    On the quantum chromatic number of a graph,

    P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, and A. Winter, “On the quantum chromatic number of a graph,” 2006

    2006

  16. [16]

    Experimentally Testable State-Independent Quantum Contextuality,

    A. Cabello, “Experimentally Testable State-Independent Quantum Contextuality,” Physical Review Letters101(2008)

    2008

  17. [17]

    Graph-theoretic approach to quantum correlations,

    A. Cabello, S. Severini, and A. Winter, “Graph-theoretic approach to quantum correlations,”Physical Review Letters112(2014), no. 4 040401

    2014

  18. [18]

    Necessary and Sufficient Condition for State-Independent Contextual Measurement Scenarios,

    R. Ramanathan and P. Horodecki, “Necessary and Sufficient Condition for State-Independent Contextual Measurement Scenarios,”Physical Review Letters112 (2014)

    2014

  19. [19]

    Device-independent security of quantum cryptography against collective attacks,

    A. Ac´ ın, N. Brunner, N. Gisin, S. Massar, and S. Pironio, “Device-independent security of quantum cryptography against collective attacks,”Physical Review Letters98 (2007), no. 23 230501

    2007

  20. [20]

    The sheaf-theoretic structure of non-locality and contextuality,

    S. Abramsky and A. Brandenburger, “The sheaf-theoretic structure of non-locality and contextuality,”New Journal of Physics13(2011) 113036

    2011

  21. [21]

    Contextuality in measurement-based quantum computation,

    R. Raussendorf, “Contextuality in measurement-based quantum computation,”Phys. Rev. A88(2013) 022322

    2013

  22. [22]

    A combinatorial approach to nonlocality and contextuality,

    A. Ac´ ın, T. Fritz, A. Leverrier, and A. B. Sainz, “A combinatorial approach to nonlocality and contextuality,”Communications in Mathematical Physics334(2015), no. 2 533–628

    2015

  23. [23]

    Contextuality supplies the ‘magic’ for quantum computation,

    M. Howard, J. Wallman, V. Veitch, and J. Emerson, “Contextuality supplies the ‘magic’ for quantum computation,”Nature510(2014), no. 7505 351–355. 11

    2014

  24. [24]

    From n-qubit multi-particle quantum teleportation modelling to n-qudit contextuality based quantum teleportation and beyond,

    D. P. Srivastava, V. Sahni, and P. S. Satsangi, “From n-qubit multi-particle quantum teleportation modelling to n-qudit contextuality based quantum teleportation and beyond,”Int. J. Gen. Syst.46(2017), no. 4 414–435

    2017

  25. [25]

    Contextuality as a Resource for Models of Quantum Computation with Qubits,

    J. Bermejo-Vega, N. Delfosse, D. E. Browne, C. Okay, and R. Raussendorf, “Contextuality as a Resource for Models of Quantum Computation with Qubits,” Phys. Rev. Lett.119(2017) 120505

    2017

  26. [26]

    Quantum Advantage in Information Retrieval,

    P.-E. Emeriau, M. Howard, and S. Mansfield, “Quantum Advantage in Information Retrieval,”PRX Quantum3(2022) 020307

    2022

  27. [27]

    Necessary and sufficient condition for quantum state-independent contextuality,

    A. Cabello, M. Kleinmann, and C. Budroni, “Necessary and sufficient condition for quantum state-independent contextuality,”Physical Review Letters114(2015), no. 25 250402

    2015

  28. [28]

    The complexity of promise problems with applications to public-key cryptography,

    S. Even, A. L. Selman, and Y. Yacobi, “The complexity of promise problems with applications to public-key cryptography,”Information and Control61(1984), no. 2 159–173

    1984

  29. [29]

    On promise problems: A survey,

    O. Goldreich, “On promise problems: A survey,” inTheoretical Computer Science: Essays in Memory of Shimon Even, vol. 3895 ofLecture Notes in Computer Science, pp. 254–290. Springer, 2006

    2006

  30. [30]

    Probabilistic automata,

    M. O. Rabin, “Probabilistic automata,”Information and Control6(1963), no. 3 230–245

    1963

  31. [31]

    Simple Test for Hidden Variables in Spin-1 Systems,

    A. A. Klyachko, M. A. Can, S. Binicio˘ glu, and A. S. Shumovsky, “Simple Test for Hidden Variables in Spin-1 Systems,”Phys. Rev. Lett.101(2008) 020403

    2008

  32. [32]

    State-Independent Proof of Kochen-Specker Theorem with 13 Rays,

    S. Yu and C. H. Oh, “State-Independent Proof of Kochen-Specker Theorem with 13 Rays,”Physical Review Letters108(2012) 030402

    2012

  33. [33]

    Quantum vs. classical communication and computation,

    H. Buhrman, R. Cleve, and A. Wigderson, “Quantum vs. classical communication and computation,” inProceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 63–68, 1998

    1998

  34. [34]

    Coloring an orthogonality graph,

    C. Godsil and M. W. Newman, “Coloring an orthogonality graph,”European Journal of Combinatorics29(2008), no. 1 13–24

    2008

  35. [35]

    Forbidden intersections,

    P. Frankl and V. R¨ odl, “Forbidden intersections,”Transactions of the American Mathematical Society300(1987), no. 1 259–286

    1987

  36. [36]

    Quantum finite automata: A modern introduction,

    A. C. Say and A. Yakaryılmaz, “Quantum finite automata: A modern introduction,” in Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, pp. 208–222. Springer, 2014

    2014

  37. [37]

    Certifying Quantum Gates via Automata Advantage,

    A. Schroeder, L. B. Vieira, J. N¨ oller, N. Miklin, and M. Gachechiladze, “Certifying Quantum Gates via Automata Advantage,” 2025. 12

    2025

  38. [38]

    Sound certification of memory-bounded quantum computers,

    J. N¨ oller, N. Miklin, M. Kliesch, and M. Gachechiladze, “Sound certification of memory-bounded quantum computers,” 2026

    2026

  39. [39]

    Quantum Fingerprinting,

    H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, “Quantum Fingerprinting,”Phys. Rev. Lett.87(2001) 167902

    2001

  40. [40]

    State-independent experimental test of quantum contextuality,

    G. Kirchmair, F. Z¨ ahringer, R. Gerritsma, M. Kleinmann, O. G¨ uhne, A. Cabello, R. Blatt, and C. F. Roos, “State-independent experimental test of quantum contextuality,”Nature460(2009) 494–497

    2009

  41. [41]

    Experimental demonstration of quantum finite automaton,

    Y. Tian, T. Feng, M. Luo, S. Zheng, and X. Zhou, “Experimental demonstration of quantum finite automaton,”npj Quantum Information5(2019) 56

    2019

  42. [42]

    Critical noncolorings of the 600-cell proving the Bell–Kochen–Specker theorem,

    M. Waegell and P. K. Aravind, “Critical noncolorings of the 600-cell proving the Bell–Kochen–Specker theorem,”Journal of Physics A: Mathematical and Theoretical 43(2010) 105304. 13 A Representational contextuality vs. statistical contextuality Here, we review the relationship between the integer graph invariants that dictate repre- sentational contextuali...

    2010