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

• URL: http://arxiv.org/abs/2603.00417v1
• Date: Sat, 28 Feb 2026 02:34:09 GMT
• Title: Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints
• Abstract summary: We introduce physics-aware learnability, which defines the learnability relative to an explicit access model.<n>For finite no-signaling and quantum models, PL feasibility becomes linear or semidefinite.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• A complete classification of the existence of finite-dimensional quantum solutions to inconsistent linear constraint systems [0.0]
  We show that inconsistent LCS can be solved by promoting variables to local Pauli operators.<n>We also establish the existence of LCS with a quantum-classical gap over finite fields if and only if $dgeq 3$ and $pmid d$.
  arXiv  Detail & Related papers  (2026-09-15T01:26:46Z)
• A Mathematical Theory of Interpretation: Rational Entropy, Spectral Readout, and Confusability as a Resource [0.0]
  MTI makes interpretation a method-design problem.<n>A four-condition certificate characterizes sharp, decodable, medium-faithful, and order-independent readout.
  arXiv  Detail & Related papers  (2026-08-24T23:03:06Z)
• Intrinsic Structure: Spectral Identifiability for Mechanistic Interpretability [51.56484100374058]
  We prove the first identifiability theorem for a mechanistic-interpretability primitive.<n>The spectrum is an identifiable, model-intrinsic fingerprint with a stated error bar, not a legible decomposition.
  arXiv  Detail & Related papers  (2026-08-10T19:42:01Z)
• Constrained Learning with Universally Learnable Concept Classes [2.5998827435861633]
  We establish universal PACC learnability of the solutions of the solutions of dual algorithms.<n> Optimality is caught between universality, governed by convexity, and strong Lagrangian duality.
  arXiv  Detail & Related papers  (2026-08-09T02:13:57Z)
• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  Invariant learning can fail even when the structure is statistically identifiable.<n>We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive, there exist emphamplable multi-dimensional environments.<n>Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.
  arXiv  Detail & Related papers  (2026-06-11T05:49:43Z)
• Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning [0.3277163122167433]
  We develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits.<n>With $M$ copies, one can learn up to the best $G$-gate approximation error plus a statistical penalty.<n>Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.
  arXiv  Detail & Related papers  (2026-06-10T15:28:36Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• The Inverse Born Rule Fallacy: On the Informational Limits of Phase-Locked Amplitude Encoding [0.0]
  In Quantum Machine Learning (QML) and Quantum Finance, amplitude encoding is often motivated by its logarithmic storage capacity arXiv:1307.0411.<n>This paradigm typically relies on the mapping $= sqrtP$, treating the quantum state as a derivative of a classical probability distribution $P$.<n>We rigorously establish that while $P$ is a projection of $||2$, the simple square-root mapping fails to recover the non-commutative structure necessary for genuine quantum advantage in classification tasks.
  arXiv  Detail & Related papers  (2026-02-24T20:37:13Z)
• Equivariant Evidential Deep Learning for Interatomic Potentials [55.6997213490859]
  Uncertainty quantification is critical for assessing the reliability of machine learning interatomic potentials in molecular dynamics simulations.<n>Existing UQ approaches for MLIPs are often limited by high computational cost or suboptimal performance.<n>We propose textitEquivariant Evidential Deep Learning for Interatomic Potentials ($texte2$IP), a backbone-agnostic framework that models atomic forces and their uncertainty jointly.
  arXiv  Detail & Related papers  (2026-02-11T02:00:25Z)
• Hierarchy of discriminative power and complexity in learning quantum ensembles [15.100044984577915]
  We introduce a hierarchy of integral probability metrics, termed MMD-$k$, which generalizes the maximum mean discrepancy to quantum ensembles.<n>We show that for pure-state ensembles of size $N$, estimating MMD-$k$ using experimentally feasible SWAP-test-based estimators requires $(N2-2/k)$ samples for constant $k$, and $(N3)$ samples for constant $k$.
  arXiv  Detail & Related papers  (2026-01-29T17:13:48Z)
• Partial Feedback Online Learning [88.27143767009376]
  We study a new learning protocol, termed partial-feedback online learning.<n>Each instance admits a set of acceptable labels, but the learner observes only one acceptable label per round.
  arXiv  Detail & Related papers  (2026-01-29T09:39:11Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States [16.185988658474635]
  We prove that estimation of $mathrmtr(rhok O)$ for a broad class of observables $O$ is exponentially hard for any protocol restricted to $(k-1)$-replica joint measurements.<n>Results establish, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for any integer $k>2$.
  arXiv  Detail & Related papers  (2025-09-28T17:46:43Z)
• Explicit Quantum Circuits for Simulating Linear Differential Equations via Dilation [0.0]
  We present a concrete pipeline that connects the dilation formalism with explicit quantum circuit constructions.<n>On the analytical side, we introduce a discretization of the continuous dilation operator that is tailored for quantum implementation.<n>We prove that the resulting scheme achieves a global error bound of order $O(M-3/2)$, up to exponentially small boundary effects.
  arXiv  Detail & Related papers  (2025-09-20T18:54:49Z)
• Computational Complexity of Non-Hermitian Quantum Systems [0.0]
  conditional time evolutions arise when a quantum system is monitored and one postselects on a measurement record.<n>We establish an approximate equivalence between post-selection and arbitrary non-Hermitian Hamiltonians.<n>Non-Hermitian physics neither guarantees a quantum advantage nor precludes efficient classical simulation.
  arXiv  Detail & Related papers  (2025-06-03T22:35:28Z)
• Conditional Distribution Quantization in Machine Learning [83.54039134248231]
  Conditional expectation mathbbE(Y mid X) often fails to capture the complexity of multimodal conditional distributions mathcalL(Y mid X)<n>We propose using n-point conditional quantizations--functional mappings of X that are learnable via gradient descent--to approximate mathcalL(Y mid X)
  arXiv  Detail & Related papers  (2025-02-11T00:28:24Z)
• Demonstration of magic state power of $\mathbf{D}(\mathbf{S}_{3})$ anyons with two qudits [0.0]
  We present a method for implementing both braiding and fusion evolutions using only the operators that create and measure anyons.<n>We show that the entire scheme can be encoded in just two qudits, offering a compact blueprint that is inherently scalable and readily implementable in current quantum platforms.
  arXiv  Detail & Related papers  (2024-08-06T18:00:59Z)
• Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
  We study what classes of probability distributions RNN LMs can represent. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata. These results present a first step towards characterizing the classes of distributions RNN LMs can represent.
  arXiv  Detail & Related papers  (2023-10-08T13:36:05Z)
• Reconstructing $S$-matrix Phases with Machine Learning [49.1574468325115]
  We apply modern machine learning techniques to studying the unitarity constraint. We find a new phase-ambiguous solution which pushes the known limit on such solutions significantly beyond the previous bound.
  arXiv  Detail & Related papers  (2023-08-18T10:29:26Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.