# Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints

arXiv: https://arxiv.org/abs/2603.00417 · HTML: https://mlsanity.com/paper/2603.00417/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 28 Feb 2026.

## Builds on (most cited first, 5 of 5)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Learning quantum states and unitaries of bounded gate complexity](https://mlsanity.com/paper/2310.19882/) (2023)

## Abstract (arXiv)

Beyond binary classification, learnability can become a logically fragile notion: in EMX, even the class of all finite subsets of [0,1] is learnable in some models of ZFC and not in others. We argue the paradox is operational. The standard definitions quantify over arbitrary set-theoretic learners that implicitly assume non-operational resources (infinite precision, unphysical data access, and non-representable outputs). We introduce physics-aware learnability (PL), which defines the learnability relative to an explicit access model -- a family of admissible physical protocols. Finite-precision coarse-graining reduces continuum EMX to a countable problem, via an exact pushforward/pullback reduction that preserves the EMX objective, making the independence example provably learnable with explicit (ε,δ) sample complexity. For quantum data, admissible learners are exactly POVMs on d copies, turning sample size into copy complexity and yielding Helstrom(-type) lower bounds. For finite no-signaling and quantum models, PL feasibility becomes linear or semidefinite and is therefore decidable.