Bayesian Matroid-Union Bounds for Quantum List Discrimination: Support Congestion, Process Compression, and Exact Adaptive-Parallel Phases
Admitted after checks by named AI models and editor approval. Not peer reviewed. Screening record
In quantum list discrimination a measurement returns at most ell candidate labels and succeeds when the true hypothesis belongs to the returned list. We associate a Rado independent-transversal matroid to the support subspaces of a mixed quantum ensemble and prove that every true-label inclusion vector lies in the independence polytope of the ell-fold matroid union. This yields all-subset Bayesian bounds for arbitrary priors, soft rewards, an integer congestion deficit, equality audits, and canonical compression to quantum-process testers. Exact attainment and insufficiency examples separate support combinatorics from quantum geometry. We then solve two input-dependent process families. For binary laminar dephase-prepare channels with M=2^h, list size ell=2^s, and q uses, arbitrary entangled parallel probes and adaptive quantum memories obey P_parallel=min(1,ell(q+1)/M) and P_adaptive=min(1,ell 2^q/M). For complete unitary-error ensembles we translate the known approximate dense-coding spectrum law into a list cap, derive an exact serial/parallel/Bell multitime trichotomy, and give a fixed-probe example where the coarse list-rank cap is not attained. The matroid theorem is a support obstruction rather than a general POVM feasibility characterization; the laminar separation is a classical feedback tradeoff embedded quantumly, and no indefinite-causal-order advantage is claimed.
Preview PDF on this page v1
Uses your browser's PDF viewer. Open the PDF directly if a preview is unavailable.
Cite this paper
Lluis Eriksson (2026). Bayesian Matroid-Union Bounds for Quantum List Discrimination: Support Congestion, Process Compression, and Exact Adaptive-Parallel Phases. AIRR.SCIENCE, ARR-2026-15SJ1ANHDN8D88Z1, v1. https://airr.science/papers/ARR-2026-15SJ1ANHDN8D88Z1/versions/v1/
Use this version link to cite the manuscript you read. A Working paper label means the version has not completed AIRR screening. AIRR screening is not journal peer review. Import BibTeX, RIS or CSL JSON into your reference manager to apply a citation style.
Version history
The paper identifier remains stable. Each version has its own immutable release, timestamp and version identifier.
- v1 · source snapshot available · viewing
Verification record
- Frontier-model screening
- Not assessed
- Source integrity
- Pass
- Bibliographic integrity
- Partial
- Reproducibility
- Partial
- Lean 4
- Not applicable
Recorded under ARR-VERIFY-1.0. AIRR verification and screening are not peer review.
AI assistance statement
OpenAI Codex assisted with theorem exploration, literature triage, proof stress testing, exact verifier development, manuscript editing, reproducibility checks, machine-readable extraction, and AIRR deposit preparation. The author selected and reviewed the claims, assumptions, proofs, citations, and executable evidence and remains responsible for the final work. AI output is not treated as independent scientific evidence.
Frontier-model screening
Status: not_assessed. Any listed reports correspond to this exact version under ARR-SCREEN-1.0; no absent assessment is represented as a pass.
Model assessments and review context
- Distinct models
- 2
- Range
- 3.70–4.25
- Method
- bounded capability-weighted mean · exact version only
Limited evidence · 1/2 benchmark matches. This is an evidence description, not a probability of correctness.
One provider; shared blind spots possible; Fresh blinded review context not documented for every model; Benchmark match incomplete; Adverse reports or unresolved objections require editorial disposition
OpenAI · gpt-6-astra · High · unknown · review context: unknown3.70
Recommendation: Minor Revision · Material objections: 0
The exact 20-page v1 establishes a sound support-based Bayesian list hierarchy by combining elementary quantum inequalities with classical Rado-Edmonds theory. Its process compression, laminar-channel phase, simplex POVM and qubit exclusion certificate are consistent with their proofs and the executed checks. The work is substantive but primarily a synthesis: dense-coding optimality and the basic exclusion/feedback mechanisms are prior art, and the support cap is not generally attainable. No unresolved main-claim-invalidating objection was found. Minor revision is warranted because the manuscript overstates the exactness and scope of its multitime replay and should sharpen several novelty and resource qualifications. The score credits the all-subset formulation and exact examples without crediting a general solution of quantum list discrimination.
- Correctness confidence
- The closed union-rank substitution and all-subset support inequality are sound. Canonical compression handles singular tester normalizations correctly. The laminar flag reduction and the stated restricted Weyl wirings have matching constructions. Supplied tests and an independent exact matrix certificate support the concrete optima.
- Rigor
- The distinction between a matroid obstruction and physical attainability is maintained, including the exact qubit counterexample. Zero priors, soft rewards, core tails and compression losses are treated explicitly. Computational claims in Sections 11 and 13 exceed what the multitime replay actually checks.
- Novelty
- The all-subset Bayesian union-polytope formulation is a credible incremental synthesis. Rado/Edmonds, exclusion, tester compression, dense coding and adaptive search are established. Primary checks confirm the dense-coding spectrum law and the stronger projector obstruction; the self-cited one-label predecessor was not checked for overlap.
- Significance
- The bound improves total dimension for congested high-prior clusters and gives useful exact attainment examples. It can be vacuous for full-rank mixed states and is not a complete feasibility test. The architecture separations rely on deliberately classical dephasing channels or tightly restricted memory resources.
- Reproducibility
- All four supplied scripts pass, including 240 rank/subset/budget cases and 70 laminar cases. However verify_multitime_ueb.py uses float square roots and formula comparisons, not exact frame spectra or PSD tests. An independent symbolic check here verified the D=4,r=2,list=2 matrix primal/dual certificate. No formal verification was supplied.
Strengths
- Lemma 3.2 and Theorem 4.1, pp.4-5: substituting the Rado rank into Edmonds union and writing B=C disjoint-union F leaves the nonnegative term (ell-1)|F|. Combining rho_i<=P_A with the per-outcome budget and s_i<=1 therefore gives exactly the stated union-rank inequalities, including mixed supports and soft rewards.
- Proposition 4.3, p.6: summation by parts over sorted priors makes each weighted prefix deficit nonnegative. Equality is consequently equivalent to saturation only at strict prior drops; zero priors and ties cause no hidden extra equality conditions.
- Lemma 5.1, Theorem 5.2 and Corollary 5.3, pp.6-8: restricting inverse square roots to supp T correctly produces a POVM and normalized effective states. Common congruence cannot raise any support-sum rank. The positive core argument remains valid for subnormalized cores, and the separate tail suprema are explicitly distinguished.
- Theorems 6.1-6.2, pp.8-10: common input dephasing permits a label-independent flag decomposition, including reference systems. Conditional adaptive memory contains no information beyond the flagged transcript. Laminar cells give q+1 parallel classes and feedback gives at most 2^q leaves; the breadth-first and prefix-following constructions attain both bounds for ell=2^s.
- Theorems 7.1-7.2, pp.10-12: the complete-error-basis twirl gives S=D I tensor rho_R and a constant PGM overlap, with a matching dual. The Weyl fibre sizes and terminal support dimensions correctly give the stated SER0/PAR0/PARBell laws under their explicit restrictions.
- Theorem 9.2 and Proposition 10.1, pp.14-16: the root-frame effects sum to identity and annihilate every omitted simplex vertex. The qubit circumcenter has radius 1/sqrt(3), positive barycentric weights and matching exclusion primal/dual cost. These examples establish both attainment and genuine insufficiency of full union rank.
Weaknesses
- Sections 11 and 13, pp.16-18, describe exact rational/algebraic checks of complete-unitary-basis frame spectra and a fixed-probe certificate. The supplied verify_multitime_ueb.py constructs neither frame matrices nor POVM effects/dual slacks; it uses floating square roots, tolerances and equality of formula values. The successful replay is much weaker evidence than that description.
- Section 11 describes 240 small subspace instances, but verify_list_matroid_union.py uses only three support fixtures and counts their subset/list-budget combinations. The number 240 is correct as a case count, not as the number of independently varied subspace families.
- Section 7 and related work: Feng-Duan-Ji already derive and attain the approximate dense-coding formula (Eq. (17), https://arxiv.org/pdf/quant-ph/0604149). The paper acknowledges this; the process-list translation and restricted wiring consequences should carry the novelty claim, rather than the spectrum formula itself.
- Section 8: the projector obstruction of Stratton-Hsieh-Skrzypczyk can be stronger than the union density threshold, as the paper acknowledges. In the qubit example the largest eigenvalue of sum rho_i is (15+sqrt(153))/10>2, already excluding a perfect two-list POVM. The new value calculation is useful, but the impossibility is not a new feasibility criterion.
- Sections 5 and 13: full-rank perturbations can trivialize support bounds; selecting useful positive cores remains an extra optimization. The 81/100 cap is not shown attainable, and no optimal algorithm for general priors, noise or unrestricted process architectures is proved.
- Priority and packaging: the one-label predecessor [3] was not retrieved, so incremental overlap remains unverified. The supplied batch contains the replay scripts but not the LaTeX/bibliography package advertised on p.18; a manuscript rebuild was therefore not performed. No stored or author-provided report was treated as independent evidence.
Potential errors
- Section 7, p.12: the D=4 rank-two fixture is described as an intermediate entanglement spectrum, although its nonzero Schmidt spectrum is flat (1/2,1/2). It demonstrates nonsaturation of the coarse list cap at intermediate Schmidt rank, not a nonflat-spectrum effect. The numerical value (2+sqrt(2))/4 itself is correct.
- Section 6, p.9: the insertion proof for q+1 laminar cells needs the inclusion-compatible order to put containing sets before contained sets; an arbitrary insertion can meet several existing cells. A parent-first order exists and makes the proof work, so this is a minor clarification, not a counterexample to the phase law.
Strong novelty candidates
- Theorems 4.1-4.3 and Corollary 5.3: inclusion vectors for arbitrary-prior mixed-state soft-list decisions lie in a single exact union-matroid independence polytope, with a prefix equality audit and a positive-core tail extension. The contribution is the operational synthesis, not new matroid theory.
- Theorem 6.2: the exact all-depth list/feedback phase against arbitrary parallel entanglement and adaptive quantum memories is a clear, fully bounded application. It remains a classical-query mechanism embedded in channels, as explicitly stated.
- The juxtaposition of an all-size simplex attainment family, the exact hemisphere optimum and the intermediate-rank list-cap failure gives concrete boundaries between support combinatorics and POVM geometry; priority for the package remains provisional.
Unresolved material objections
None reported.
arr:assessment:2fb0ce9d-161c-4618-a843-c2866e7b1497 · prompt ARR-ASSESS-1.0 · runtime identity: OpenAI gpt-6-astra · reasoning effort: high · basis: operator verified ui · evidence SHA-256 dc26468164614b2b8c940b1f33019642104c11c3fe9b2885cb38a4dcbae5a481 · response SHA-256 7aea31fa028e13a898a71eeef75446a0de6a55075085f06bd007ab45a010a1ae · canonical PDF SHA-256 a955a5e4a05adbef081a8fbb0c8a76f46b2027eca35a0be0dbaf82a607fbb8a2
OpenAI · gpt-5.6-sol · High · unknown · review context: unknown4.25
Recommendation: Minor Revision · Material objections: 0
This exact 20-page manuscript proves a clean and useful matroid-union outer bound for quantum list discrimination and transports it correctly through fixed tester normalizations. The arbitrary-prior formula, soft-list extension, exact laminar adaptive/parallel phase, simplex attainment, and qubit nonsufficiency certificate make the boundary of the theorem unusually clear. I found no unresolved material objection. Minor revision should expand two compressed operational proofs and temper novelty claims to the limits of the literature search.
- Correctness confidence
- The support inequalities, matroid-union rank collapse, process compression, laminar decision-tree reduction, dense-coding SDP, and explicit attainability and insufficiency examples are internally consistent. All four supplied replay programs executed successfully.
- Rigor
- The main theorem is short and complete, and limitations are carefully separated from feasibility. The adaptive quantum-to-classical reduction and the intermediate-spectrum list optimum are convincing but sufficiently compressed that fuller channel-state bookkeeping would improve auditability.
- Novelty
- Rado-Edmonds theory, state exclusion, tester normalization, and the dense-coding spectrum law are established and credited. The union-polytope inclusion theorem and exact architecture applications look like plausible new combinations, but priority was not exhaustively established.
- Significance
- The all-subset Bayes bound retains labeled support congestion and applies to arbitrary priors, mixed states, soft lists, and tester compression. Exact examples sharply distinguish combinatorial obstruction from physical attainability and isolate feedback resources.
- Reproducibility
- All four standard-library programs ran cleanly, covering 240 union-rank cases, exact simplex and qubit certificates, 70 laminar phase cases, UEB fibres, Schmidt caps, and wiring values. The programs appropriately describe themselves as finite checks, not proofs.
Strengths
- Theorem 4.1 correctly combines the operator inequality rho_i <= P_A, the per-outcome reward budget, and singleton bounds to obtain exactly the independence polytope of the ell-fold Rado-matroid union.
- Lemma 5.1 preserves all tester probabilities under Moore-Penrose compression, while Theorem 5.2 correctly uses a common linear map to obtain a tester-independent but explicitly coarser support cap.
- The regular-simplex root-frame POVM and the three-qubit primal-dual exclusion certificate rigorously show both exact attainment and failure of support sufficiency within transparent finite examples.
- The laminar-channel theorem distinguishes parallel cells from adaptive decision-tree leaves and proves matching constructions against the stated entangled-parallel and quantum-memory strategy classes.
Weaknesses
- The adaptive part of Theorem 6.1 relies on a concise genie-flag induction; writing the conditional memory state and its label-independence invariant explicitly would make the reduction robust to instrument and transcript conventions.
- The D=4 rank-two list optimum in Equation (36) is sketched through sector pinching and a covariant dual; the full normalization across four shift sectors is not displayed in the manuscript even though the fixture checks the value.
- Several potentially new components are direct combinations of classical matroid union, support domination, and standard tester compression, so the contribution is substantial synthesis rather than a new foundational discrimination formalism.
Potential errors
- Corollary 8.1 refers to Theorem 4.2, although the relevant arbitrary-prior statement is Corollary 4.2; this appears to be a cross-reference error rather than a mathematical flaw.
- The phrase 'complete input-dependent family' in the abstract could be read broadly, while Theorem 6.2 concerns one specially constructed laminar family with uniform priors and power-of-two list sizes.
Strong novelty candidates
- Embedding the entire inclusion-probability vector into the ell-fold Rado-matroid independence polytope, with arbitrary priors and soft reward budgets, is the clearest general candidate contribution.
- The exact all-depth laminar channel phase against arbitrary entangled parallel inputs and adaptive quantum memories is a concrete architecture-sensitive novelty candidate.
- The paired simplex-attainment and hemisphere-obstruction examples give a sharp, reusable account of where the support obstruction is exact and where quantum geometry remains decisive.
Unresolved material objections
None reported.
arr:assessment:261af4ac-3b1b-49e2-9a71-14fbe1280b50 · prompt ARR-ASSESS-1.0 · runtime identity: OpenAI gpt-5.6-sol · reasoning effort: high · basis: operator verified ui · evidence SHA-256 6e94b601904a67ab4be78f3a90c852db7bebc85a9a14f13d6bf29e97c282e9a7 · response SHA-256 2640961c7670707b69bdc94616cb145dcd19911414a6633845be32be9163826a · canonical PDF SHA-256 a955a5e4a05adbef081a8fbb0c8a76f46b2027eca35a0be0dbaf82a607fbb8a2
A model assessment is not peer review or a correctness certificate. AIRR preserves disagreement, exact-version provenance and later reassessments.
Editorial disclosure
Founder-owned pilot record: Lluis Eriksson is both the author and AIRR's current founder-editor. No independent editorial review, peer review, frontier-model screening, or scientific certification is claimed. Acceptance records a technically valid deposit, not a finding that the paper is correct.