{"id":"a1de309a-455c-4996-88c2-3d2904792fe2","arxiv_id":"2507.06225","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Two nonisomorphic rank-3 matroids on 18 elements are shown to be quantum isomorphic via a nonlocal game, and a new quantum automorphism group for matroids is introduced.","lead":"This paper connects matroid theory to quantum information by defining cooperative games where two players prove whether two matroids are isomorphic, then allows quantum strategies that go beyond classical ones. It produces two nonisomorphic matroids that are indistinguishable under quantum strategies, and introduces a new quantum symmetry group for matroids.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.5's non-isomorphism proof has a false case analysis: the exhibited '4th nonbasis' can use an element not in X, and the reduction to π(H3)=258 skips possible cases.","rationale":"The reader identified the cited Mermin-Peres perfect quantum strategy as the weakest assumption. That is not where the paper is vulnerable: the magic square result is standard, the sign pattern s_789=-1 is exactly the well-known quantum-satisfiable instance, and Theorem 4.4's reduction is coherent. The actual load-bearing defect is internal to the proof of Theorem 4.5. The non-isomorphism claim is what makes the pair 'surprising,' and it is proved only by the excluded-restriction argument for N. That proof is not merely terse; it contains a false assertion about an element (3,+) belonging to X and an unsupported 'without loss of generality' reduction. A computational check can determine whether the underlying claim is true. If true, the paper needs a corrected proof, which is consistent with the reader's CONDITIONAL verdict; if false, the headline existence result collapses. Therefore the appropriate verdict remains CONDITIONAL, but the condition should include a repaired non-isomorphism proof, not just the [3]-dependent sketch in Theorem 5.3.","tokens_in":22058,"tokens_out":22349,"duration_ms":226825,"concrete_test":"Run a brute-force search over all C(18,9) = 48620 nine-element subsets X of E(P); for each, compute all P-nonbases contained in X (there are 24 total) and check whether exactly three nonbases occur and they partition X, i.e., P|X is isomorphic to the matroid N with nonbases {123,456,789}. A few lines of Oscar/Sage code settle this immediately. If no such X exists, the conclusion of the minor argument is correct and the proof only needs repair; if such X exists, Theorem 4.5's non-isomorphism claim is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of the paper is that the rank-3 matroids P and Q (18 elements) are NB-quantum isomorphic but not isomorphic. The quantum-isomorphism direction is supported by a standard Mermin-Peres strategy and the construction in Theorem 4.4, which appears sound. The load-bearing weak point is the proof of non-isomorphism in Theorem 4.5, which rests entirely on showing that the matroid N (rank 3, nonbases {123,456,789}) is a restriction of Q but not of P. That exclusion argument contains concrete errors. In the subcase where H1 = {(1,+),(2,-),(3,-)} and π(H2)=147, the paper claims that {(1,-),(2,-),(3,+)} is a fourth nonbasis of P lying in X. But X need not contain (3,+): the only element with label 3 in X may be (3,-) from H1, since H2=147 and the chosen H3=258 do not involve label 3. (A different fourth nonbasis, {(1,-),(2,+),(3,-)}, does exist, so the subcase's conclusion may be salvageable, but the written witness is invalid.) More seriously, the step 'Without loss of generality, suppose 2 ∈ π(H3), so π(H3)=258' is unjustified: π(H3) could be 456, 369, or 789, and the argument as written does not treat these cases. Since P and Q share all the numerical invariants listed in the paper, this minor argument is the only evidence for non-isomorphism; as written, that evidence is incomplete.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines matroid isomorphism games associated with cryptomorphic axiom systems S, proves that perfect classical strategies detect ordinary matroid isomorphism (Theorem A), and introduces S-quantum isomorphism via perfect quantum commuting strategies. The main construction (Theorem B) builds rank-3 matroids P and Q on 18 elements from the Mermin-Peres magic square and claims they are NB-quantum isomorphic but not isomorphic. The paper also defines a *-algebra G•(M,N,S) whose nonvanishing is claimed to characterize quantum isomorphism (Theorem 5.3), derives preservation of ground-set size and other numerical invariants, and introduces a quantum automorphism group Aut•(M,S) with a disjoint automorphism criterion. The authors report that P and Q share many invariants, including Tutte polynomial and automorphism group, so the non-isomorphism claim rests on a minor argument involving a rank-3 restriction.","tokens_in":22378,"tokens_out":20122,"duration_ms":212969,"significance":"If the proof of Theorem 4.5 is repaired, the paper's central example would be an explicit, low-rank pair of nonisomorphic matroids that are quantum isomorphic, a genuinely new phenomenon for matroids and a natural analogue of quantum graph isomorphism. The algebraic characterization and the new quantum automorphism group Aut•(M,S) are potentially useful tools, and Theorem D gives a clean separation from the earlier quantum automorphism groups in [7]. The paper is constructive and several auxiliary results (Theorem A, Theorem 3.10, Proposition 5.5) are supported by detailed arguments. However, the non-isomorphism direction of Theorem 4.5 is not proved as written, and Theorem 5.3 is only sketched, so the advertised central claims are not yet fully established.","major_comments":[{"comment":"The non-isomorphism argument is incomplete and contains false statements. In the case H1={(1,+),(2,-),(3,-)} with π(H2)=147 and π(H3)=258, the displayed fourth nonbasis {(1,-),(2,-),(3,+)} is not contained in X: X contains (3,-) from H1 and no (3,+), since neither H2 nor H3 involves label 3. The valid witness is {(1,-),(2,+),(3,-)}. The step \"Without loss of generality, suppose 2∈π(H3), so π(H3)=258\" skips the possibilities π(H3)∈{369,456,789} and requires a symmetry argument that is not supplied. In the following paragraph, the statement \"{π(H1),π(H2),π(H3)} equals {123,345,789} or {147,258,369}\" contains the invalid line 345, and the immediately following assignment π(H1)=123, π(H2)=258, π(H3)=789 is not a partition of {1,...,9}; the intended row partition is presumably {123,456,789} with π(H2)=456. As written, the proof does not establish that no restriction of P is isomorphic to N.","section":"Section 4.3, proof of Theorem 4.4"},{"comment":"The strategy in Theorem 4.4 is only explained for the case where the input pointed nonbases come from Mhom. The sentence \"since tA and tB are fulfilling assignments in the homogeneous system\" is false when an input belongs to MS; in that case tA satisfies the S-system, not the homogeneous system. The proof should explicitly verify that tA*kA lies in the required output matroid for every combination of inputs from Mhom and MS and that the four relation cases remain valid in the mixed cases. The computation appears to be the same in the missing case, so this is a fixable gap, but as stated the proof of the quantum-isomorphism direction of Theorem 4.5 is incomplete.","section":"Section 5.2, proof of Theorem 5.3"},{"comment":"The converse direction of Theorem 5.3 is only sketched. The bijectivity of the map kl is asserted without verification, and the existence of a faithful tracial state on G•(M,N,S) is delegated to Theorems 3.15 and 3.17 of [3] without checking that the hypotheses of those theorems are satisfied. Since Theorem 5.3 is advertised as a purely algebraic characterization of quantum isomorphism and is used in Section 5.3 and in the definition of Aut•(M,S), the proof should be completed or the theorem should be reformulated as a precise reduction to the cited results with all hypotheses verified.","section":"Section 5.2"}],"minor_comments":[{"comment":"The statement \"if and only if M is not a free extension of a paving matroid or M does not split as a direct sum...\" should logically read \"if and only if M is neither a free extension of a paving matroid nor a direct sum of the form U(1,1)⊕U(r−1,n−1)\"; the current wording is ambiguous.","section":"Proposition 2.3(3)"},{"comment":"The notation is inconsistent: Theorem 4.4 speaks of the \"(Mhom,MS,NB)-isomorphism game\" and an NB-isomorphism, while Theorem 4.5 says \"NB•-quantum isomorphic\". The bullet is not defined for quantum isomorphism of matroids.","section":"Section 4.3"},{"comment":"In the proof of Theorem 3.6, the sentence \"A≠Sy_{k+1}\" should instead compare A with S_{b_{k+1}}; as written the subscript refers to a pointed set in N rather than in M.","section":"Section 3.2"},{"comment":"In the first paragraph of the proof, \"the 3 nonbases of Q|Y\" should be \"the three nonbases of Q|Y\" for grammar; more importantly, the sentence listing them is correct but could explicitly state why no other 3-subsets of Y are nonbases of Q.","section":"Section 4.3"},{"comment":"The sentence \"we get that tA ∗ kA and tB ∗ kB fulfilling assignments\" is missing the verb \"are\".","section":"Section 4.3"}],"recommendation":"major_revision","confidential_remarks":"The errors in the non-isomorphism proof of Theorem 4.5 appear repairable; the intended restriction argument can be completed by a short case table or a computer-assisted check, and the quantum direction is sound modulo a routine clarification in Theorem 4.4. I therefore recommend major revision rather than rejection. The authors should also decide whether Theorem 5.3 should be fully proved or explicitly stated as a consequence of the bigalois-extension results in [3]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuinely interesting paper that likely points to something true, but the proof of the main non-isomorphism claim has a gap that needs to be closed. The stress-test note is correct on both counts, so the referee should ask for a complete proof.\n\nWhat's actually new: the idea of defining matroid isomorphism games for each axiomatic structure S, and the quantum version, is a fresh bridge between matroid theory and quantum information. The classical characterization (Theorem A) is clean. The construction of non-isomorphic matroids that are quantum isomorphic from the Mermin-Peres magic square is a nice application of LBCS games. Theorem 4.4 is a genuinely useful transfer principle. If the example is fixed, it gives the first pair of nonisomorphic quantum isomorphic matroids. The algebraic characterization (Theorem 5.3) and the new quantum automorphism groups Aut•(M,S) are also valuable, and the disjoint automorphism criterion (Theorem 6.6) is a nice tool.\n\nThe soft spots: the non-isomorphism direction of Theorem 4.5. The proof exhibits a 9-element restriction of Q that looks like N, and then tries to show no such restriction exists in P. The first issue: in the subcase where H1 = {(1,+),(2,-),(3,-)} and π(H2)=147, the claimed fourth nonbasis {(1,-),(2,-),(3,+)} uses (3,+), which is not necessarily in X because the only label-3 element in X may be (3,-). There is an alternative witness {(1,-),(2,+),(3,-)}, so the subcase may be salvageable, but the written argument is wrong. More seriously, the step 'Without loss of generality, suppose 2 ∈ π(H3), so π(H3)=258' is not WLOG: π(H3) could also be 456, 369, or 789. The sign pattern with s789 = -1 breaks the symmetry of the 3x3 grid, so a generic permutation of labels is not available. The argument must handle these cases separately. This matters because the non-isomorphism claim is the only thing separating P and Q from being isomorphic. The paper lists many shared invariants, so this minor argument is load-bearing. Theorem 5.3 is only sketched and relies on [3] for the bigalois extension and the faithful tracial state; that is likely fine but needs verification.\n\nWho this is for: matroid theorists and quantum information people. The framework is worth knowing even if the example needs repair. I would send it to peer review, but the referee should ask for a complete proof of Theorem 4.5 before acceptance.","headline":"A promising framework and a likely-true example, but the non-isomorphism proof has a genuine gap that needs to be fixed before the main theorem is solid.","tokens_in":22894,"tokens_out":6354,"would_cite":true,"duration_ms":57800,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B35","05E16","16T30","20B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Nonisomorphic matroids can be quantum isomorphic, and this paper exhibits an explicit 18-element pair.","keywords":["matroids","nonlocal games","quantum commuting strategies","quantum isomorphism","matroid isomorphism structures","quantum automorphism groups","linear binary constraint systems","magic-square game"],"falsifier":"One could settle the quantum claim by computing the isomorphism algebra $G^\\bullet(P,Q,\\mathrm{NB})$; if it is the zero algebra, no perfect quantum commuting strategy exists for the nonbasis game. A more direct check would be to verify whether the magic-square linear binary constraint system with $s_{789} = -1$ has a perfect quantum commuting strategy, since a negative answer would invalidate the cited premise on which the main example depends.","tokens_in":21852,"feed_emoji":"🎲","tokens_out":10212,"duration_ms":93066,"temperature":0.7,"pith_summary":"This paper translates matroid isomorphism into nonlocal games: for any standard axiomatic description of a matroid, such as bases, nonbases, circuits, flats, or hyperplanes, two matroids are isomorphic exactly when the corresponding game has a perfect classical winning strategy. It then allows quantum commuting strategies and defines a notion of quantum isomorphism of matroids. The central result is an explicit pair of rank-3 matroids on 18 elements, $P = M_{\\mathrm{hom}}$ and $Q = M_S$, that are quantum isomorphic under the nonbasis game but are not isomorphic. The paper also gives an algebraic characterization: a certain $*$-algebra $G^\\bullet(M,N,S)$ is nonzero exactly when the two matroids are $S$-quantum isomorphic, and this leads to new quantum automorphism groups of matroids.","feed_headline":"Two nonisomorphic matroids still pass a quantum isomorphism test","feed_subtitle":"An 18-element pair built from the magic-square system cannot be told apart by quantum strategies in the nonbasis game.","key_machinery":"The machinery has three pieces. First, the matroid isomorphism game: for an isomorphism structure $S$, the referee sends pointed $S$-sets $(S,p)$ and the players must answer with pointed $S$-sets of the other matroid while preserving the four-valued relation rel (0 for same set and same point, 1 for different set and same point, 2 for same set and different point, 3 otherwise); this is the colored graph isomorphism game on the relation colored graph $G(M,S)$. Second, the conversion in Theorem 4.4 from a perfect quantum strategy for a linear binary constraint system game, here the magic-square system with the sign pattern $s_{789} = -1$, into a perfect quantum strategy for the nonbasis game between $M_{\\mathrm{hom}}$ and $M_S$. Third, the isomorphism algebra $G^\\bullet(M,N,S)$, a quotient of the quantum permutation algebra by relations enforcing preservation of rel; its nonvanishing characterizes quantum commuting winning strategies, and for $N = M$ it becomes the quantum automorphism group $\\mathrm{Aut}^\\bullet(M,S)$.","core_discovery":"The central claim is Theorem 4.5: the matroids $P = M_{\\mathrm{hom}}$ and $Q = M_S$, where $M$ is the rank-3 matroid on nine points whose nonbases are the three rows and three columns of a $3\\times3$ grid, and where $S$ is the sign choice $s_{789} = -1$ with all other signs $+1$, are not isomorphic but are NB-quantum isomorphic. They have the same rank, ground-set size, numbers of bases, independent sets, circuits, flats, and hyperplanes, the same connectivity, the same Tutte polynomial, and isomorphic automorphism groups, yet no isomorphism exists. The non-isomorphism is certified by a minor argument: $Q$ has a restriction isomorphic to the matroid whose nonbases are $123$, $456$, and $789$, while no restriction of $P$ is. The quantum isomorphism comes from a perfect quantum commuting strategy for the magic-square linear binary constraint system, converted by Theorem 4.4 into a perfect strategy for the nonbasis matroid game.","pith_inferences":["Any linear binary constraint system with a perfect quantum commuting strategy and no perfect classical strategy should similarly generate nonisomorphic but quantum isomorphic matroids by the same doubling construction; the magic-square system is the first example, not the only one.","Because the matroid game is a colored graph isomorphism game, the known wealth of quantum isomorphic but nonisomorphic graphs suggests many more matroid pairs exist, possibly on smaller ground sets than 18.","Flipping different subsets of signs in the magic-square system would produce companion matroids $M_S$; checking which of those are pairwise nonisomorphic but quantum isomorphic would test how robust the construction is.","The paper's automorphism-group criterion detects noncommutativity of the algebra, but a natural next step is to decide when $\\mathrm{Aut}^\\bullet(M,S)$ differs from the classical automorphism group as a quantum group, not merely as an algebra."],"forward_implications":["If two matroids are $S$-quantum isomorphic for a covering structure $S$, then their ground sets have the same size, and for each $r$ the number of $S$-sets of size $r$ is the same.","Quantum isomorphism can occur without isomorphism: the nonbasis game cannot separate $P$ and $Q$ even though a matroid minor argument does.","Existence of a perfect quantum commuting strategy for the matroid game is equivalent to nonvanishing of the explicit $*$-algebra $G^\\bullet(M,N,S)$, connecting matroid isomorphism to the algebraic toolkit of quantum graph isomorphism, including tracial states and bigalois extensions.","The construction produces matroids whose quantum automorphism group $\\mathrm{Aut}^\\bullet(M,\\mathrm{NB})$ is noncommutative even when the earlier bases-based quantum automorphism group is commutative.","Under circuit-quantum isomorphism, the property of being paving is preserved when the ranks agree."],"supporting_citations":[{"why":"Supplies the magic-square linear binary constraint system and the fact that the game with the chosen sign pattern has a perfect quantum strategy, which Theorem 4.4 converts into a quantum winning strategy for the matroid game.","marker":"[10]"},{"why":"Provides the general definition of linear binary constraint system games and the framework used to associate a matroid $M_S$ to a sign pattern.","marker":"[6]"},{"why":"Gives the cyclic-flat lattice characterization of matroids used in Theorem 4.3 to prove that $M_S$ is a matroid.","marker":"[2]"},{"why":"Supplies the bigalois-extension and tracial-state results used in Theorem 5.3 to pass from a nonzero isomorphism algebra to a perfect quantum commuting strategy.","marker":"[3]"},{"why":"Identifies the matroid isomorphism game with the colored graph isomorphism game and provides the quantum automorphism group framework behind the disjoint automorphism criterion.","marker":"[14]"},{"why":"Defines the earlier bases-based quantum automorphism groups of matroids that the new $\\mathrm{Aut}^\\bullet(M,S)$ is shown to go beyond in Example 6.8.","marker":"[7]"},{"why":"Provides the C*-algebraic characterization of perfect quantum commuting strategies for synchronous games used in Lemma 3.9 and throughout the paper.","marker":"[13]"}],"fun_headline_variants":["Quantum test can't tell these matroids apart, but they differ","Nonisomorphic matroids that fool quantum isomorphism","Matroids: same stats, quantum look-alikes, actually distinct","Quantum isomorphism masks a pair of nonisomorphic matroids","Matroid pair: quantum identical, classical distinct"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction rests on the known theorem that the magic-square linear binary constraint system with the sign pattern $s_{789} = -1$ and all other signs $+1$ has a perfect quantum commuting strategy; if that theorem were wrong, the proof that $P$ and $Q$ are NB-quantum isomorphic would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Quantum test can't tell these matroids apart, but they differ","Nonisomorphic matroids that fool quantum isomorphism","Matroids: same stats, quantum look-alikes, actually distinct","Quantum isomorphism masks a pair of nonisomorphic matroids","Matroid pair: quantum identical, classical distinct"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000686,"raw_usage":{"total_tokens":3076,"prompt_tokens":879,"completion_tokens":2197,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":495,"completion_tokens_details":{"reasoning_tokens":2116}},"tokens_in":495,"tokens_out":2197,"duration_ms":20266,"temperature":1.0,"reasoning_tokens":2116,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:08:19.968312+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One could settle the quantum claim by computing the isomorphism algebra $G^\\bullet(P,Q,\\mathrm{NB})$; if it is the zero algebra, no perfect quantum commuting strategy exists for the nonbasis game. A more direct check would be to verify whether the magic-square linear binary constraint system with $s_{789} = -1$ has a perfect quantum commuting strategy, since a negative answer would invalidate the cited premise on which the main example depends.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the magic-square linear binary constraint system and the fact that the game with the chosen sign pattern has a perfect quantum strategy, which Theorem 4.4 converts into a quantum winning strategy for the matroid game."},{"cited_title":"Cleve and R","cited_arxiv_id":null,"evidence_quote":"Provides the general definition of linear binary constraint system games and the framework used to associate a matroid $M_S$ to a sign pattern."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the cyclic-flat lattice characterization of matroids used in Theorem 4.3 to prove that $M_S$ is a matroid."},{"cited_title":"Brannan, A","cited_arxiv_id":null,"evidence_quote":"Supplies the bigalois-extension and tracial-state results used in Theorem 5.3 to pass from a nonzero isomorphism algebra to a perfect quantum commuting strategy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Identifies the matroid isomorphism game with the colored graph isomorphism game and provides the quantum automorphism group framework behind the disjoint automorphism criterion."},{"cited_title":"Corey, M","cited_arxiv_id":null,"evidence_quote":"Defines the earlier bases-based quantum automorphism groups of matroids that the new $\\mathrm{Aut}^\\bullet(M,S)$ is shown to go beyond in Example 6.8."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the C*-algebraic characterization of perfect quantum commuting strategies for synchronous games used in Lemma 3.9 and throughout the paper."}],"review_version":1}