Quantum and classical low-degree learning via a dimension-free Remez inequality

Abstract

Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$, 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\pi ik/K){\}}_{k=1}^K$ controls the supremum of $f$ over the entire polytorus $(\{z\in \mathbf{C}:|z|=1{\}}^n)$, with multiplicative constant $C$ depending on $K$ and $\text{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 $\mathcal{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 \cite{EI22, 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 \cite{CHP}.

arXiv comment35 pages. This version summarizes the main results of several articles and is an extended version of the paper accepted by ITCS 2024. The old version concentrated on the qudit learning will be posted elsewhere