2023/01/04 by Klein, Ohad, Slote, Joseph, Volberg, Alexander +1
#46B07 #46B09 #46B10 #60E15 #Analysis of PDEs (math.AP) #F.2.2 #FOS: Mathematics #FOS: Physical sciences #Functional Analysis (math.FA) #Mathematical Physics (math-ph) #Probability (math.PR) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2301.01438
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]n, 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=1K controls the supremum of f over the entire polytorus (\z\inC:|z|=1\n), 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 O(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 \citeEI22, CHP, VZ22 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 \citeCHP.