Pith. sign in

REVIEW 2 major objections 2 minor 1 cited by

Quantum Memory Advantage from Contextuality

T0 review · 2 major / 2 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read For any exclusivity graph G, the paper claims a two-symbol promise problem that any sound classical finite automaton solves with at least χ(G) memory states is solved by a measure-once quantum finite automaton with only ξ(G) dimensions; on

desk verdict The zero-error χ vs ξ memory separation is defensible, but the advertised 'sharp phase transition' is not proven — the paper overclaims in the abstract and conclusion. read the letter →

arxiv 2607.00507 v2 pith:ADLB5CUL submitted 2026-07-01 quant-ph cs.FLmath.CO

Shiroman Prakash This is my paper
classification quant-phcs.FLmath.CO
keywords contextualityexclusivitygraphschromaticnumberorthogonalrankquantumfiniteautomatastatecomplexitypromiseproblemsmemoryadvantage
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 tries to establish that quantum contextuality—specifically the impossibility of coloring an exclusivity graph with few colors—can be turned into an unconditional memory advantage for a very simple language task. It defines a promise problem whose inputs are pairs of measurement outcomes: either the same outcome or two mutually exclusive outcomes. Any classical finite automaton that never mistakes a mutually exclusive pair for a valid pair must use at least as many internal states as the graph's chromatic number, whereas a quantum finite automaton needs only the dimension of the graph's simplest orthogonal representation. For a family of n-bit Boolean orthogonality graphs this becomes 2^{Ω(n)} classical states versus O(n) quantum dimensions. The paper also shows that if the classical machine is allowed a small probability of confusing exclusive events, the exponential penalty disappears above a sharp threshold, and it interprets the χ>ξ gap as a distinct resource it calls representational contextuality.

What carries the argument

The load-bearing objects are the exclusivity graph G (vertices are outcomes, edges are mutually exclusive pairs), its chromatic number χ(G) (the minimum independent-set cover, hence the minimum number of ontic states a sound classical model needs), and its orthogonal rank ξ(G) (the minimum dimension of a quantum representation with orthogonal projectors on edges). The promise problem converts these into automata: zero soundness error is exactly physical exclusivity, classical machines are analyzed through the identity P(accept uv)=Σ_λ μ_u(λ)ξ_v(λ), and the QFA solution uses Householder reflections U_v that map the initial state to |v⟩, so that adjacent vertices become orthogonal.

What would settle it

Exhibit a classical probabilistic finite automaton that solves the paper's promise problem on a graph with χ(G)>ξ(G) using fewer than χ(G) states while keeping soundness error zero and completeness error below one—for example, fewer than 7 states on the 18-vertex graph join described in the paper, or o(2^{Ω(n)}) states on the Boolean orthogonality graphs. Alternatively, show that the same promise language is solved by a quantum automaton in dimension less than ξ(G), which would break the claimed tightness of the upper bound.

Watch

Extended reading notes

Core claim

The central claim is a computational translation of the gap between chromatic number and orthogonal rank. For an exclusivity graph G=(V,E), the paper's promise problem asks an automaton to accept strings vv and reject strings uv where (u,v)∈E. A classical probabilistic finite automaton with zero soundness error must have at least χ(G) states: rejecting every adjacent pair forces the support of each preparation to be an independent set, and covering all vertices by such sets is exactly a coloring. A measure-once quantum finite automaton encodes each vertex as a unit vector in an orthogonal representation and uses Householder reflections to route the initial state, requiring only ξ(G) dimensio

Load-bearing premise

The load-bearing premise is that a classical automaton's internal states can be treated as ontic states in an ontological model, so that 'never accepts adjacent outcomes' forces the support of every outcome to be an independent set; if a classical machine were allowed a non-ontological encoding that exploits temporal correlations or external memory, the N≥χ(G) bound would not follow.

Editorial extensions

If this is right

  • The advantage is structural, not an artifact of long inputs: the input length is exactly two symbols, so no accumulation of unitary rotations contributes.
  • On Boolean orthogonality graphs the separation is exponential: 2^{Ω(n)} classical states vs O(n) quantum dimensions, and the exponential alphabet size does not force a classical controller overhead because transition unitaries are synthesized by O(n)-sized circuits.
  • Representational contextuality sits strictly between state-independent and state-dependent contextuality; it is present in graphs with χ>ξ even when statistical state-independent violations are impossible, and it suffices for state-dependent contextuality.
  • Permitting classical soundness error above the threshold (1−ϵ_c)^2/(4χ(G)) makes the exponential gap vanish—a random-walk fingerprinting automaton on an expander graph solves the same promise problem with O(n) states—while erasure-dominated noise, which only raises completeness error, leaves the exponential advantage intact.
  • A 60-vertex Kochen-Specker graph already realizes the gap χ−ξ=2 at ξ=4, so the advantage can be probed with a single 4-level qudit; depolarizing and coherent noise thresholds are O(1) and independent of graph size.

Reading between the lines

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

  • If the automaton-to-ontological-model mapping is sound, representational contextuality gives a direct operational reading of the chromatic-number/orthogonal-rank gap as the extra number of distinct classical states a simulator must keep, independent of any inequality violation; one could search for other graph parameters, such as vector or quantum chromatic numbers, that yield analogous single-sho
  • The two-symbol restriction suggests the same graph-theoretic gap may appear in communication-complexity or zero-error signalling tasks where the message is a single outcome pair; testing the 60-vertex graph on a two-qubit platform would be a direct experimental check of the predicted d=4 vs N=6 separation.
  • The threshold phenomenon echoes the fragility of logical contextuality under unsharp measurements, giving a quantitative algorithmic counterpart that could be extended to sequential or temporal contextuality, where memory bounds may grow with input length rather than saturating at length two.
  • A natural extension is to replace rank-1 orthogonal representations with higher-rank projectors or nonexact representations, which would interpolate between the χ and ξ bounds and might yield partial quantum advantages at intermediate soundness errors.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper defines a promise problem (KSP) on an exclusivity graph G: the input is a length-2 string over the vertex alphabet, promised to be either two identical symbols or two adjacent (mutually exclusive) symbols. The main formal claims are: (i) any probabilistic finite automaton solving KSP with zero soundness error needs N ≥ χ(G) states (Theorem 1); (ii) there exists a measure-once QFA solving KSP with dimension d = ξ(G) via Householder reflections (Theorem 2); (iii) for Boolean orthogonality graphs this gives an exponential classical-vs-quantum memory gap (2^{Ω(n)} vs O(n)); and (iv) there is a "sharp algorithmic phase transition": once soundness error exceeds about 1/(4χ), the classical state complexity collapses to O(n) using expander-based fingerprinting. The zero-error separation is mathematically sound, but the phase-transition claim is not supported by the provided proofs.

Significance. If appropriately revised, this is a valuable contribution. The zero-error lower bound for PFAs is rigorous and self-contained (Supplement Eqs. S1–S6), the Householder QFA construction is explicit and correct, and the exponential gap for Boolean orthogonality graphs is a strong, unconditional separation. The bounds are derived independently, with no parameter fitting, and the main proofs are reproducible. However, the advertised sharp phase transition and the "requires d=ξ(G)" language both go beyond what is proved. These overstatements are load-bearing for the abstract and conclusions, but they are fixable without changing the core zero-error result.

major comments (2)
  1. [§5, Eq. (4); Supplement, Eqs. (S25)–(S27)] The paper claims a 'sharp phase transition' at ε_s > 1/(4χ): classical memory collapses from 2^{Ω(n)} to O(n). This is not established. The expander protocol has N = m d^k 2^{k+1} and error ≤ (ρ+λ_2)^k; N = O(n) requires k and d to be constants, making the soundness error a fixed constant independent of n. To drive ε_s down to the subconstant threshold 1/(4χ) ≈ 2^{-Ω(n)}, k must grow as Ω(n), giving N = 2^{Ω(n)}. Moreover, Theorem 3 itself gives N ≥ (1−ε_c)^2/(4ε_s) in this regime, which is also exponential for ε_s just above 1/(4χ). The paper therefore proves a constant-error upper bound and a small-error lower bound, but not a phase transition at the stated threshold. This claim appears in the abstract and conclusion and must be substantially weakened or removed.
  2. [Abstract; Theorem 2] The abstract states that a QFA 'requires' a memory of dimension d = ξ(G), but Theorem 2 proves only that there exists a QFA solving KSP in dimension ξ(G). A general measure-once QFA is not restricted to Hermitian Householder reflections. If U_v is not Hermitian, the zero-error condition |⟨ψ0|U_v U_u|ψ0⟩|² = 0 is not equivalent to orthogonality of |u_u⟩ = U_u|ψ0⟩ and |v_v⟩ = U_v|ψ0⟩. Thus the exact quantum memory requirement ξ(G) is not proved. The statement should be changed to 'can be solved with d = ξ(G)', and the abstract should not claim that the QFA requires this dimension unless a matching lower bound is supplied.
minor comments (2)
  1. [Supplement, Boolean-orthogonality graphs] The n-dimensional construction shows ξ(Ω_n) ≤ n, but the equality ξ(Ω_n) = n is asserted without a lower-bound proof or reference. Since the exponential separation only needs the upper bound d = O(n), the authors should either cite a proof of the orthogonal rank or state the result as an upper bound.
  2. [Supplement, Entropic Memory Cost] The statement that the worst-case entropic quantum state complexity is log ξ(G) is asserted without derivation, and the subsequent CPTP-map expectation is explicitly speculative. These should be marked as conjectures, not as proved results.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the classical lower bound and QFA upper bound are independent constructions; the phase-transition concern is a correctness overclaim, not a circular step.

full rationale

The paper's central derivation is self-contained. The classical lower bound N≥χ(G) follows from a direct combinatorial argument on any sound PFA: with ϵ_s=0, Eq. (S4) forces μ_u(λ)ξ_v(λ)=0 for every adjacent pair, so each active joint support J_λ is an independent set and completeness forces these sets to cover V, giving N≥χ(G) (Supplement, Section 4). This uses only the PFA's linear acceptance probabilities, not an imported conclusion. The QFA upper bound d=ξ(G) is an explicit Householder-reflection construction (Theorem 2), and the Boolean-orthogonality exponential gap is quoted from independent Frankl–Rödl/Cameron–Montanaro–Newman–Severini–Winter results. There are no fitted parameters renamed as predictions and no self-citation chains carrying the argument. 'Representational contextuality' is introduced as a definitional label for the χ>ξ gap, but the labeled gap is independently computed, and the hierarchy relative to state-dependent/state-independent contextuality is argued from external graph-theoretic theorems. The skeptical concern about the claimed sharp phase transition at ϵ_s>1/(4χ) is a quantitative correctness question about whether the expander-fingerprinting construction reaches subconstant soundness errors with O(n) states; it does not identify any equation that reduces to its input by construction, so it is outside the circularity rubric.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The central claims rest on known graph-theoretic theorems (Frankl–Rödl, GLS, expander walks), on the ontological-model identification of classical automata, and on the promise-problem modeling of exclusivity. No new physical entity is introduced. The explicit fingerprinting protocol does rely on hand-chosen constants (expander degree and walk length), but these are not fitted to data.

free parameters (3)
  • Ramanujan expander degree d = unspecified constant; chosen large enough so λ_2 < δ
    Fingerprinting protocol: the O(n) state complexity and soundness bound require a constant-degree Ramanujan graph with spectral gap exceeding the code distance δ; d is chosen by hand but not fitted to data.
  • random-walk length k = unspecified constant; chosen so (ρ+λ_2)^k ≤ ε_s
    Same protocol; k is a fixed constant independent of n, selected to push soundness error below the desired constant threshold.
  • code rate c and relative distance δ of the asymptotically good linear code = unspecified constants (c>1, δ>0)
    The fingerprinting construction uses an asymptotically good code; existence is cited, values are not specified.
assumptions (6)
  • domain assumption PFA memory states can be treated as ontic states Λ in Spekkens' ontological model, with μ_u(λ) and ξ_v(λ) nonnegative response functions.
    Section 'Representational Contextuality' and Supplement §3 identify the internal states of a probabilistic automaton with an ontological state space; the KSP lower bounds are derived inside this mapping.
  • domain assumption Absolute soundness (ε_s=0) for adjacent inputs is the computational analogue of physical exclusivity.
    Definition of KSP and Eq. (S3); the entire classical penalty is conditional on this identification.
  • standard math Frankl–Rödl bound α(Ω_n) ≤ (2−δ)^n with δ≈0.05, giving χ(Ω_n)≥2^{Ω(n)}.
    Supplement 'Boolean-orthogonality graphs', Eq. (S24); cited to Refs [38,61]; load-bearing for the exponential classical lower bound.
  • standard math ξ(Ω_n)=n via the ±1/√n coordinate representation.
    Supplement; the upper bound d=O(n) rests on this representation; a lower bound on ξ is not proved here but is not needed for the separation.
  • standard math GLS theorem: ϑ(G,w)=α(G,w) for all w iff G is perfect, used to derive G_RC ⊆ G_SDC.
    Section II, cited Refs [31–33].
  • standard math Expander walk sampling theorem and existence of Ramanujan graphs and asymptotically good codes.
    Fingerprinting protocol in Supplement; cited Refs [46–49,62]; needed for the O(n)-state bounded-error construction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Memory Advantage from Contextuality." pith.science (2026). https://pith.science/paper/ADLB5CUL

@misc{pith2026260700507,
  author       = {Pith},
  title        = {Pith review of: Quantum Memory Advantage from Contextuality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ADLB5CUL}},
  note         = {Machine review of arXiv:2607.00507}
}
abstract

Quantum contextuality is a vital non-classical resource, yet illuminating the precise mechanisms through which it enables unconditional computational advantages remains a challenge. We translate graph-theoretic formulations of contextuality into an unconditional quantum memory advantage for formal language recognition. We define a promise problem on an exclusivity graph $G$ where any classical finite automaton respecting exclusivity requires $N \ge \chi(G)$ memory states, whereas a QFA requires a memory of dimension $d = \xi(G)$. The gap between these bounds isolates a structural, information-theoretic incompatibility between classical and quantum descriptions that we term \textit{representational contextuality}. For Boolean orthogonality graphs, this exacts an exponential classical memory penalty ($d=\mathcal{O}(n)$ vs $N=2^{\Omega(n)}$). Finally, we demonstrate a sharp algorithmic phase transition: allowing the classical machine a finite confusability of mutually exclusive events reduces this exponential classical memory cost to $\mathcal{O}(n)$.

Figures

Figures reproduced from arXiv: 2607.00507 by the authors.

Figure 1
Figure 1. The complete Boolean-orthogonality graph Ω [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 1
Figure 1. The 18-vertex graph join of the Yu-Oh graph (outer [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
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 ↗
Figures from the paper (2 more)
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],…
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]

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Perfect Games in Dimension-Bounded Communication

    quant-ph 2026-08 conditional novelty 7.0 of 10

    Every perfect binary-output communication game reduces to graph coloring and orthogonal representation problems, and perfect qubit strategies never beat a classical bit.

Reference graph

Works this paper leans on

69 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [50]

    Kleinmann, O

    M. Kleinmann, O. G¨ uhne, J. R. Portillo, J.-A. Larsson, and A. Cabello, Memory cost of quantum contextuality, New Journal of Physics13, 113011 (2011)

    2011

  2. [51]

    Trandafir, C

    S. Trandafir, C. Kelleher, and A. Cabello, Memory cost of quantum contextuality with pauli observables (2025), arXiv:2506.06869 [quant-ph]

    arXiv 2025

  3. [1]

    J. S. Bell, On the problem of hidden variables in quantum mechanics, Rev. Mod. Phys.38, 447 (1966)

    1966

  4. [2]

    Kochen and E

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

    1967

  5. [3]

    Ac ´ ın, N

    A. Ac ´ ın, N. Brunner, N. Gisin, S. Massar, and S. Piro- nio, Device-independent security of quantum cryptogra- phy against collective attacks, Physical Review Letters 98, 230501 (2007)

    2007

  6. [4]

    Anders and D

    J. Anders and D. E. Browne, Computational power of correlations, Physical Review Letters102, 10.1103/phys- revlett.102.050502 (2009)

    doi:10.1103/phys- 2009

  7. [5]

    Raussendorf, Contextuality in measurement-based quantum computation, Phys

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

    2013

  8. [6]

    Ac ´ ın, T

    A. Ac ´ ın, T. Fritz, A. Leverrier, and A. B. Sainz, A combi- natorial approach to nonlocality and contextuality, Com- munications in Mathematical Physics334, 533 (2015)

    2015

Show all 69 references
  1. [7]

    Howard, J

    M. Howard, J. Wallman, V. Veitch, and J. Emerson, Con- textuality supplies the ‘magic’ for quantum computation, Nature510, 351–355 (2014)

    2014

  2. [8]

    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, 414 (2017)

    2017

  3. [9]

    Bermejo-Vega, N

    J. Bermejo-Vega, N. Delfosse, D. E. Browne, C. Okay, and R. Raussendorf, Contextuality as a resource for mod- els of quantum computation with qubits, Phys. Rev. Lett. 119, 120505 (2017)

    2017

  4. [10]

    Emeriau, M

    P.-E. Emeriau, M. Howard, and S. Mansfield, Quantum advantage in information retrieval, PRX Quantum3, 020307 (2022)

    2022

  5. [11]

    D. C. Kozen,Automata and Computability, Undergrad- uate Texts in Computer Science (Springer-Verlag, 1997)

    1997

  6. [12]

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

    2007

  7. [13]

    Sipser,Introduction to the Theory of Computation, 3rd ed

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

    2013

  8. [14]

    Kondacs and J

    A. Kondacs and J. Watrous, On the power of quantum finite state automata, inProceedings of the 38th An- nual Symposium on Foundations of Computer Science (FOCS)(IEEE Computer Society, 1997) pp. 66–75

    1997

  9. [15]

    Ambainis and R

    A. Ambainis and R. Freivalds, 1-way quantum finite au- tomata: strengths, weaknesses and generalizations, in Proceedings of the 39th Annual Symposium on Founda- tions of Computer Science (FOCS)(IEEE Computer So- ciety, 1998) pp. 332–341

    1998

  10. [16]

    Moore and J

    C. Moore and J. P. Crutchfield, Quantum automata and quantum grammars, Theoretical Computer Science237, 275 (2000)

    2000

  11. [17]

    Brodsky and N

    A. Brodsky and N. Pippenger, Characterizations of 1-way quantum finite automata, SIAM Journal on Computing 31, 1456 (2002)

    2002

  12. [18]

    Ambainis and A

    A. Ambainis and A. Yakaryılmaz, Automata and quan- tum computing, inHandbook of Automata Theory, Vol. 1, edited by J.-E. Pin (European Mathematical Society Publishing House, 2021) pp. 1457–1493

    2021

  13. [19]

    P. J. Cameron, A. Montanaro, M. W. Newman, S. Sev- erini, and A. Winter, On the quantum chromatic number of a graph (2006), arXiv:quant-ph/0608016 [quant-ph]

    2006 arXiv

  14. [20]

    Cabello, Experimentally testable state-independent quantum contextuality, Physical Review Letters101, 10.1103/physrevlett.101.210401 (2008)

    A. Cabello, Experimentally testable state-independent quantum contextuality, Physical Review Letters101, 10.1103/physrevlett.101.210401 (2008)

    2008 doi

  15. [21]

    Cabello, S

    A. Cabello, S. Severini, and A. Winter, Graph-theoretic approach to quantum correlations, Physical Review Let- ters112, 040401 (2014)

    2014

  16. [22]

    Ramanathan and P

    R. Ramanathan and P. Horodecki, Necessary and sufficient condition for state-independent contextual measurement scenarios, Physical Review Letters112, 10.1103/physrevlett.112.040404 (2014)

    2014 doi

  17. [23]

    Cabello, M

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

    2015

  18. [24]

    S. Even, A. L. Selman, and Y. Yacobi, The complexity of promise problems with applications to public-key cryp- tography, Information and Control61, 159 (1984)

    1984

  19. [25]

    Goldreich, On promise problems: A survey, inThe- oretical Computer Science: Essays in Memory of Shi- mon Even, Lecture Notes in Computer Science, Vol

    O. Goldreich, On promise problems: A survey, inThe- oretical Computer Science: Essays in Memory of Shi- mon Even, Lecture Notes in Computer Science, Vol. 3895 (Springer, 2006) pp. 254–290

    2006

  20. [26]

    D. A. Meyer, Finite precision measurement nullifies the Kochen-Specker theorem, Physical Review Letters83, 3751 (1999), quant-ph/9905080

    1999 arXiv

  21. [27]

    Kunjwal and R

    R. Kunjwal and R. W. Spekkens, From the Kochen- Specker theorem to noncontextuality inequalities with- out assuming determinism, Physical Review Letters115, 110403 (2015), arXiv:1506.04150 [quant-ph]

    2015 arXiv

  22. [28]

    A. A. Klyachko, M. A. Can, S. Binicio˘ glu, and A. S. Shu- movsky, Simple test for hidden variables in spin-1 sys- tems, Phys. Rev. Lett.101, 020403 (2008)

    2008

  23. [29]

    R. W. Spekkens, Contextuality for preparations, trans- formations, and unsharp measurements, Physical Review A71, 10.1103/physreva.71.052108 (2005)

    2005 doi

  24. [30]

    Yu and C

    S. Yu and C. H. Oh, State-independent proof of kochen- specker theorem with 13 rays, Physical Review Letters 108, 030402 (2012)

    2012

  25. [31]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimiza- tion, Combinatorica1, 169 (1981)

    1981

  26. [32]

    D. E. Knuth, The sandwich theorem (1993), arXiv:math/9312214 [math.CO]

    1993 arXiv

  27. [33]

    C. Berge, F¨ arbung von graphen, deren s¨ amtliche reg- ulateuren imbrizierte kreise sind, Wissenschaftliche Zeitschrift der Martin-Luther-Universit¨ at Halle- Wittenberg, Mathematisch-Naturwissenschaftliche Reihe10, 114 (1961)

    1961

  28. [34]

    Bravyi, D

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

    2018

  29. [35]

    J. K¨ orner, Coding of an information source having am- biguous alphabet and the entropy of graphs, inTrans- actions of the Sixth Prague Conference on Information Theory, Statistical Decision Functions, Random Pro- cesses(Academia, Prague, 1973) pp. 411–425

    1973

  30. [36]

    Csiszˆ ar, J

    I. Csiszˆ ar, J. K¨ orner, L. Lov´ asz, K. Marton, and G. Si- monyi, Entropy splitting for antiblocking corners and perfect graphs, Combinatorica10, 27 (1990)

    1990

  31. [37]

    Simonyi, Graph entropy: a survey, inCombinatorial Optimization, DIMACS Series in Discrete Mathematics 6 and Theoretical Computer Science, Vol

    G. Simonyi, Graph entropy: a survey, inCombinatorial Optimization, DIMACS Series in Discrete Mathematics 6 and Theoretical Computer Science, Vol. 20, edited by W. Cook, L. Lov´ asz, and P. Seymour (American Mathe- matical Society, 1995) pp. 399–441

    1995

  32. [38]

    Frankl and V

    P. Frankl and V. R¨ odl, Forbidden intersections, Trans- actions of the American Mathematical Society300, 259 (1987)

    1987

  33. [39]

    Buhrman, R

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

    1998

  34. [40]

    Kent, Noncontextual hidden variables and finite pre- cision measurement, Physical Review Letters83, 3755 (1999), quant-ph/9906006

    A. Kent, Noncontextual hidden variables and finite pre- cision measurement, Physical Review Letters83, 3755 (1999), quant-ph/9906006

    1999 arXiv

  35. [41]

    Finite Precision

    N. D. Mermin, A note on Meyer’s “Finite Precision” paper, arXiv preprint quant-ph/9907045 (1999), quant- ph/9907045

    1999 arXiv

  36. [42]

    Clifton and A

    R. Clifton and A. Kent, Simulating quantum mechanics as a classical theory, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineer- ing Sciences456, 2101 (2000), quant-ph/9908031

    2000 arXiv

  37. [43]

    D. M. Appleby, Existential contextuality and the mod- els of Meyer, Kent, and Clifton, Physical Review A65, 022105 (2002), quant-ph/0005056

    2002 arXiv

  38. [44]

    A. Kent, Non-contextuality, finite precision measurement and the Clifton–Kent models, Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics35, 429 (2004), quant- ph/0401019

    2004

  39. [45]

    Garola and C

    C. Garola and C. Sozzo, The Meyer–Kent–Clifton dis- pute: A resolution from a semantic perspective, Foun- dations of Physics Letters17, 465 (2004), quant- ph/0402179

    2004

  40. [46]

    Alon, Eigenvalues and expander graphs, Combinator- ica6, 83 (1986)

    N. Alon, Eigenvalues and expander graphs, Combinator- ica6, 83 (1986)

    1986

  41. [47]

    Lubotzky, R

    A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica8, 261 (1988)

    1988

  42. [48]

    G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the de- sign of expanders and concentrators, Problems of Infor- mation Transmission24, 39 (1988)

    1988

  43. [49]

    Hoory, N

    S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathe- matical Society43, 439 (2006)

    2006

  44. [52]

    Kirchmair, F

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

    2009

  45. [53]

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

    2019

  46. [54]

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

    2021 arXiv

  47. [55]

    Cardosoet al., Implementing a quantum finite au- tomaton in ibmq using custom control pulses, arXiv preprint arXiv:2412.06977 (2024)

    G. Cardosoet al., Implementing a quantum finite au- tomaton in ibmq using custom control pulses, arXiv preprint arXiv:2412.06977 (2024)

    2024 arXiv

  48. [56]

    Waegell and P

    M. Waegell and P. K. Aravind, Critical noncolorings of the 600-cell proving the bell–kochen–specker theorem, Journal of Physics A: Mathematical and Theoretical43, 105304 (2010)

    2010

  49. [57]

    M. O. Rabin, Probabilistic automata, Information and Control6, 230 (1963)

    1963

  50. [58]

    R. Duan, S. Severini, and A. Winter, Zero-error commu- nication via quantum channels, noncommutative graphs, and a quantum lov´ asz number, IEEE Trans. Inf. Theor. 59, 1164–1174 (2013)

    2013

  51. [59]

    Boreland, I

    G. Boreland, I. Todorov, and A. Winter, Sandwich theo- rems and capacity bounds for non-commutative graphs, Journal of Combinatorial Theory, Series A177, 105302 (2021)

    2021

  52. [60]

    Boreland, I

    G. Boreland, I. G. Todorov, and A. Winter, Informa- tion theoretic parameters of noncommutative graphs and convex corners, Illinois Journal of Mathematics66, 10.1215/00192082-9799163 (2022)

    2022 doi

  53. [61]

    Godsil and M

    C. Godsil and M. W. Newman, Coloring an orthogonality graph, European Journal of Combinatorics29, 13 (2008)

    2008

  54. [62]

    Ajtai, J

    M. Ajtai, J. Komlos, and E. Szemeredi, Determinis- tic simulation in logspace, inProceedings of the Nine- teenth Annual ACM Symposium on Theory of Comput- ing, STOC ’87 (Association for Computing Machinery, New York, NY, USA, 1987) p. 132–140. 1 Supplemental Material: Quantum ...

    1987

  55. [63]

    Review of finite automata Deterministic finite automata (DF A).A DF A models sequential computation under memory con- straints, and must accept or reject an input string based on whether it belongs to a specified formal language. For- mally, a DF A is defined by the 5-tuple Mc...

  56. [64]

    Theorem S1.Any classical DF A that correctly solves the KSP for an exclusivity graphG= (V, E)must possess at leastχ(G)internal states, whereχ(G)is the chromatic number ofG

    State complexity of DF A solution to KSP We first establish that any classical DF A that solves the KSP induces a valid vertex coloring on the exclusivity graphG. Theorem S1.Any classical DF A that correctly solves the KSP for an exclusivity graphG= (V, E)must possess at least...

  57. [65]

    LetS={s 1, s2,

    PF As and Ontological Models We formalize the operational mechanics of a classi- cal probabilistic finite automaton (PF A) by mapping it onto the framework of classical ontological models [29]. LetS={s 1, s2, . . . , sN }be the internal state space of the PF A, which we regard...

  58. [66]

    The rejection constraint Eq

    Sound PF A Complexity (Proof of Theorem 1) We first consider a PF A that is permitted an imperfect completeness (1> ϵc ≥0) but is perfectly sound (ϵ s = 0), and provide a proof of Theorem 1 in the main text. The rejection constraint Eq. (S3) requires that for any pair of adjac...

  59. [67]

    W eakly Unsound PF As (Proof of Theorem 3) We now relax the soundness constraint and analyze a weakly unsound PF A whereϵ s >0. We introduce a continuous splitting parameterα∈(0,1] and define a subset of verticesI λ(α) for each stateλ: Iλ(α) = u∈V(G) :µ u(λ)> ϵα s andξ u(λ)> ϵ...

  60. [68]

    , which yields Theorem 3 of the main text

  61. [69]

    Entropic Memory Cost and the F ractional Chromatic Number We now prove that when a classical automaton utilizes shared randomness, its memory overhead for sound solu- tion to the KSP, under an adversarial input distribution, is bounded by the fractional chromatic numberχ f (G)...

    2000

Pith tools

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