Marton's conjecture in polynomial time

arXiv:2609.20771 · cs.CC, math.CO, quant-ph · Submitted 2026-09-17 · Read on arXiv

cs.CC, math.CO, quant-ph

Submitted: 2026-09-17

Updated: 2026-09-17

Comments: 63 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Stabilizer States — 16× in this paper · explained in 2 episodes
• Query Complexity — 10× in this paper · explained in 2 episodes
• Verification — 10× in this paper · explained in 2 episodes
• Fidelity — 8× in this paper · explained in 2 episodes
• Agnostic Learning — 4× in this paper · explained in 1 episode
• Sample Complexity — 4× in this paper · explained in 15 episodes
• Accuracy — 2× in this paper · explained in 1 episode
• Annual ACM-SIAM Symposium on Discrete Algorithms — 2× in this paper
• Trace — 2× in this paper · explained in 2 episodes
• Alignment — 1× in this paper · explained in 1 episode
• Ambient Dimension — 1× in this paper · explained in 1 episode
• Core — 1× in this paper · explained in 2 episodes
• Geometric Distribution — 1× in this paper · explained in 2 episodes
• Quantum Circuits — 1× in this paper · explained in 2 episodes
• Regularization — 1× in this paper · explained in 3 episodes
• Trace Distance — 1× in this paper · explained in 3 episodes

Sources

• Tomography of quantum states with bounded extent
• An algorithmic Polynomial Freiman-Ruzsa theorem
• Learning Clifford-structured quantum unitaries and Hamiltonians
• Distribution-Specific Agnostic Boosting
• Marton's Conjecture in abelian groups with bounded torsion

Related papers

• Parameterized Hardness of Zonotope Containment and Neural Network Verification
• Hardware-Algorithm Co-Optimization of Early-Exit Neural Networks for Multi-Core Edge Accelerators
• Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
• Strassen's support functionals coincide with the quantum functionals
• Exponential Quantum Advantage in Numbers-on-Forehead Communication
• Rational degree is polynomially related to degree