2026-08-05T21:18:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19597 2024-03-06T11:04:26Z ddc:004 open_access

Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality Klein, Ohad Slote, Joseph Volberg, Alexander Zhang, Haonan Analysis of Boolean Functions Remez Inequality Bohnenblust-Hille Inequality Statistical Learning Theory Qudits Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice binom([n],k), the hypergrid [K]ⁿ, and noncommutative spaces (matrix algebras). We present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function f over products of the cyclic group {exp(2π i k/K)}_{k = 1}^K controls the supremum of f over the entire polytorus ({z ∈ ℂ:|z| = 1}ⁿ), with multiplicative constant C depending on K and deg(f) only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., C does not depend on n). This dimension-free Remez-type inequality removes the main technical barrier to giving 𝒪(log n) sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-K qudit systems. In particular, our dimension-free Remez inequality implies new Bohnenblust-Hille-type estimates which are central to the learning algorithms and appear unobtainable via standard techniques. Thus we extend to new spaces a recent line of work [Eskenazis and Ivanisvili, 2022; Huang et al., 2022; Volberg and Zhang, 2023] that gave similarly efficient methods for learning low-degree polynomials on the hypercube and observables on qubits. An additional product of these efforts is a new class of distributions over which arbitrary quantum observables are well-approximated by their low-degree truncations - a phenomenon that greatly extends the reach of low-degree learning in quantum science [Huang et al., 2022]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ohad Klein and Joseph Slote and Alexander Volberg and Haonan Zhang 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.69 urn:nbn:de:0030-drops-195977 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.69 eng https://creativecommons.org/licenses/by/4.0/legalcode