Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2301.01438 · Leibniz international proceedings in informatics

Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality

Ohad Klein, Joseph Slote, Alexander L'vovich Vol'berg, Haonan Zhang

Published Jan 4, 2023• 3 citations
arXivHTMLPDF

Abstract

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=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}.

DOI
10.4230/lipics.itcs.2024.69

Related papers

Noncommutative Bohnenblust–Hille inequalities

Alexander L'vovich Vol'berg, Haonan Zhang

Bohnenblust-Hille inequalities for Boolean cubes have been proven with dimension-free constants that grow subexponentially in the degree (Defant et al. in Math Ann 374(1):653-680, 2019). Such inequalities have found great applications in learning low-degree Boolean functions (Eskenazis and Ivanisvili in Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pp 203-207, 2022). Motivated by learning quantum observables, a qubit analogue of Bohnenblust-Hille inequality for Boolean cubes was recently conjectured in Rouzé et al. (Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, 2022. arXiv preprint arXiv:2209.07279). The conjecture was resolved in Huang et al. (Learning to predict arbitrary quantum processes, 2022. arXiv preprint arXiv:2210.14894). In this paper, we give a new proof of these Bohnenblust-Hille inequalities for qubit system with constants that are dimension-free and of exponential growth in the degree. As a consequence, we obtain a junta theorem for low-degree polynomials. Using similar ideas, we also study learning problems of low degree quantum observables and Bohr's radius phenomenon on quantum Boolean cubes.

arXiv:2210.14468•Mathematische Annalen•Jul 24, 2023•13 citations

Learning Low-Degree Quantum Objects

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez +1 more

We consider the problem of learning low-degree quantum objects up to $\varepsilon$-error in $\ell_2$-distance. We show the following results: $(i)$ unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and unitaries can be learned using $O(1/\varepsilon^d)$ queries (independent of $n$), $(ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from $d$-query quantum algorithms can be classically learned from $O((1/\varepsilon)^d\cdot \log n)$ many random examples $(x,p(x))$ (which implies learnability even for $d=O(\log n)$), and $(iii)$ degree-$d$ polynomials $p:\{-1,1\}^n\to [-1,1]$ can be learned through $O(1/\varepsilon^d)$ queries to a quantum unitary $U_p$ that block-encodes $p$. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.

arXiv:2405.10933•Leibniz international proceedings in informatics•Jan 1, 2024•4 citations

Three lectures on Fourier analysis and learning theory

H. M. Zhang

Fourier analysis on the discrete hypercubes $\{-1,1\}^n$ has found numerous applications in learning theory. A recent breakthrough involves the use of a classical result from Fourier analysis, the Bohnenblust--Hille inequality, in the context of learning low-degree Boolean functions. In these lecture notes, we explore this line of research and discuss recent progress in discrete quantum systems and classical Fourier analysis.

arXiv:2409.10886•Sep 17, 2024•0 citations

Quantum computing, norms and polynomials

Francisco Escudero Gutiérrez

In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.

•Mar 26, 2026•0 citations

Exponential lower bounds for low-degree strategies in position-based quantum cryptography

Isabel M. Moreno-Cuadrado, David Perez-Garcia, Carlos Palazuelos

Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary $U_{AB}$ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary $U_{AB}$ whose implementation in NLQC requires extra quantum systems with dimensions ${\rm exp}(n^{Ω(1)})$, where $n$ is the dimension of systems $A$ and $B$. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in $n$. In this paper we consider the family of diagonal ${\pm 1}$ valued unitaries $U_{\varepsilon}$, indexed by an element of the Boolean hypercube $\varepsilon \in \{\pm 1\}^{n^2}$, i.e. $U_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_B$. We show that if $U_{\varepsilon}$ can be implemented in NLQC with constant accuracy for all $\varepsilon$, and the dependency on $\varepsilon$ in the first round of the associated strategy is a polynomial of degree $O(n^{\frac{1}{4}-δ})$, then the implementation of at least one $U_{\varepsilon}$ in NLQC requires resources scaling as $\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)$. The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.

quant-pharXiv:2609.35592•Sep 29, 2026•0 citations

Noncommutative Bohnenblust--Hille Inequality for qudit systems

Joseph Slote, Alexander L'vovich Vol'berg, Haonan Zhang

Previous noncommutative Bohnenblust--Hille (BH) inequalities addressed operator decompositions in the tensor-product space $M_2(\mathbb{C})^{\otimes n}$; \emph{i.e.,} for systems of qubits \cite{HCP22,VZ23}. Here we prove noncommutative BH inequalities for operators decomposed in tensor-product spaces of arbitrary local dimension, \emph{i.e.,} $M_K(\mathbb{C})^{\otimes n}$ for any $K\geq2$ or on systems of $K$-level qudits. We treat operator decompositions in both the Gell-Mann and Heisenberg--Weyl basis, reducing to the recently-proved commutative hypercube BH \cite{DMP} and cyclic group BH \cite{SVZ} inequalities respectively. As an application we discuss learning qudit quantum observables.

arXiv:2406.08509•Jun 3, 2024•0 citations
Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice ([n]k)\binom{[n]}{k}(k[n]​), the hypergrid [K]n[K]^n[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 fff over products of the cyclic group {exp⁡(2πik/K)}k=1K\{\exp(2πi k/K)\}_{k=1}^K{exp(2πik/K)}k=1K​ controls the supremum of fff over the entire polytorus ({z∈C:∣z∣=1}n)(\{z\in\mathbf{C}:|z|=1\}^n)({z∈C:∣z∣=1}n), with multiplicative constant CCC depending on KKK and deg(f)\text{deg}(f)deg(f) only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., CCC does not depend on nnn). This dimension-free Remez-type inequality removes the main technical barrier to giving O(log⁡n)\mathcal{O}(\log n)O(logn) sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-KKK 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}.
Bohnenblust-Hille inequalities for Boolean cubes have been proven with dimension-free constants that grow subexponentially in the degree (Defant et al. in Math Ann 374(1):653-680, 2019). Such inequalities have found great applications in learning low-degree Boolean functions (Eskenazis and Ivanisvili in Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pp 203-207, 2022). Motivated by learning quantum observables, a qubit analogue of Bohnenblust-Hille inequality for Boolean cubes was recently conjectured in Rouzé et al. (Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, 2022. arXiv preprint arXiv:2209.07279). The conjecture was resolved in Huang et al. (Learning to predict arbitrary quantum processes, 2022. arXiv preprint arXiv:2210.14894). In this paper, we give a new proof of these Bohnenblust-Hille inequalities for qubit system with constants that are dimension-free and of exponential growth in the degree. As a consequence, we obtain a junta theorem for low-degree polynomials. Using similar ideas, we also study learning problems of low degree quantum observables and Bohr's radius phenomenon on quantum Boolean cubes.
We consider the problem of learning low-degree quantum objects up to ε\varepsilonε-error in ℓ2\ell_2ℓ2​-distance. We show the following results: (i)(i)(i) unknown nnn-qubit degree-ddd (in the Pauli basis) quantum channels and unitaries can be learned using O(1/εd)O(1/\varepsilon^d)O(1/εd) queries (independent of nnn), (ii)(ii)(ii) polynomials p:{−1,1}n→[−1,1]p:\{-1,1\}^n\rightarrow [-1,1]p:{−1,1}n→[−1,1] arising from ddd-query quantum algorithms can be classically learned from O((1/ε)d⋅log⁡n)O((1/\varepsilon)^d\cdot \log n)O((1/ε)d⋅logn) many random examples (x,p(x))(x,p(x))(x,p(x)) (which implies learnability even for d=O(log⁡n)d=O(\log n)d=O(logn)), and (iii)(iii)(iii) degree-ddd polynomials p:{−1,1}n→[−1,1]p:\{-1,1\}^n\to [-1,1]p:{−1,1}n→[−1,1] can be learned through O(1/εd)O(1/\varepsilon^d)O(1/εd) queries to a quantum unitary UpU_pUp​ that block-encodes ppp. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.
Fourier analysis on the discrete hypercubes {−1,1}n\{-1,1\}^n{−1,1}n has found numerous applications in learning theory. A recent breakthrough involves the use of a classical result from Fourier analysis, the Bohnenblust--Hille inequality, in the context of learning low-degree Boolean functions. In these lecture notes, we explore this line of research and discuss recent progress in discrete quantum systems and classical Fourier analysis.
In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary UABU_{AB}UAB​ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary UABU_{AB}UAB​ whose implementation in NLQC requires extra quantum systems with dimensions exp(nΩ(1)){\rm exp}(n^{Ω(1)})exp(nΩ(1)), where nnn is the dimension of systems AAA and BBB. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in nnn. In this paper we consider the family of diagonal ±1{\pm 1}±1 valued unitaries UεU_{\varepsilon}Uε​, indexed by an element of the Boolean hypercube ε∈{±1}n2\varepsilon \in \{\pm 1\}^{n^2}ε∈{±1}n2, i.e. Uε∣i⟩A∣j⟩B=εij∣i⟩A∣j⟩BU_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_BUε​∣i⟩A​∣j⟩B​=εij​∣i⟩A​∣j⟩B​. We show that if UεU_{\varepsilon}Uε​ can be implemented in NLQC with constant accuracy for all ε\varepsilonε, and the dependency on ε\varepsilonε in the first round of the associated strategy is a polynomial of degree O(n14−δ)O(n^{\frac{1}{4}-δ})O(n41​−δ), then the implementation of at least one UεU_{\varepsilon}Uε​ in NLQC requires resources scaling as exp⁡(Ω(n2δ(log⁡n)2))\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)exp(Ω((logn)2n2δ​)). The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
Previous noncommutative Bohnenblust--Hille (BH) inequalities addressed operator decompositions in the tensor-product space M2(C)⊗nM_2(\mathbb{C})^{\otimes n}M2​(C)⊗n; \emph{i.e.,} for systems of qubits \cite{HCP22,VZ23}. Here we prove noncommutative BH inequalities for operators decomposed in tensor-product spaces of arbitrary local dimension, \emph{i.e.,} MK(C)⊗nM_K(\mathbb{C})^{\otimes n}MK​(C)⊗n for any K≥2K\geq2K≥2 or on systems of KKK-level qudits. We treat operator decompositions in both the Gell-Mann and Heisenberg--Weyl basis, reducing to the recently-proved commutative hypercube BH \cite{DMP} and cyclic group BH \cite{SVZ} inequalities respectively. As an application we discuss learning qudit quantum observables.