© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2210.14468 · Mathematische Annalen

Noncommutative Bohnenblust–Hille inequalities

Alexander L'vovich Vol'berg, Haonan Zhang

Published Jul 24, 2023• 13 citations

Abstract

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.

DOI: 10.1007/s00208-023-02680-0

Related papers

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

Ohad Klein, Joseph Slote, Alexander L'vovich Vol'berg +1 more

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

arXiv:2301.01438•Leibniz international proceedings in informatics•Jan 4, 2023•3 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

Dense Hamiltonians at the Parseval Limit: The Noncommutative BH Constant is Exponential and the Quantum FEI Conjecture is False

Joseph Slote

For each $d\geq 1$ we construct a norm-1 Hermitian operator whose Pauli expansion contains $N(d)=\exp(Ω(d^2))$ terms, each of degree $d$ and magnitude $1/\sqrt{N(d)}$ - the largest magnitude permitted by Parseval's identity. For comparison, if a bounded diagonal operator (or equivalently, a bounded degree-$d$ function on the Boolean cube) has $N(d)$ Pauli coefficients, all of magnitude $Ω(1/\sqrt{N(d)})$, then $N(d)\leq \exp(\widetilde{O}(d^{1.5}))$. This construction implies the noncommutative Bohnenblust--Hille (BH) constant satisfies $\mathrm{BH}_{M_2}(d)\geq\exp(Ω(d))$. Together with the upper bounds proved in prior work, this settles the asymptotic growth of $\mathrm{BH}_{M_2}(d)$ as exponential. Our lower bound also asymptotically separates $\mathrm{BH}_{M_2}(d)$ from the (classical) hypercube BH constant $\mathrm{BH}_{\{\pm 1\}}(d)$, which in turn is known to be subexponential: $\mathrm{BH}_{\{\pm 1\}}(d)\leq C^{\sqrt{d \log d}}$. Our Hamiltonians are also unitary and thus quantum Boolean functions in the sense of Montanaro and Osborne (2010). As such they refute the quantum Fourier Entropy-Influence conjecture of Bu et al. (2024), a natural generalization of the classical Fourier Entropy-Influence conjecture due to Friedgut and Kalai (1996).

math.FACross-listedarXiv:2608.01424•Aug 4, 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

The Quantum KKL Inequality

Yong Jiao, Wenlong Lin, Sijie Luo +1 more

In this paper, we resolve the quantum KKL conjecture of Montanaro and Osborne \cite{MO2010} for quantum Boolean functions on the $n$-qubit hypercube. More precisely, for every self-adjoint unitary $T$, we bound the largest $L_2$-influence from below by a constant multiple of $\mathrm{Var}(T)\log(n)/n$. The proof heavily depends on upper and lower commutator estimates on the Hilbert space.

quant-pharXiv:2609.21900•Sep 21, 2026•0 citations

Quantum Talagrand, KKL and Friedgut’s Theorems and the Learnability of Quantum Boolean Functions

Cambyse Rouzé, Melchior Wirth, Haonan Zhang

We extend three related results from the analysis of influences of Boolean functions to the quantum setting, namely the KKL theorem, Friedgut's Junta theorem and Talagrand's variance inequality for geometric influences. Our results are derived by a joint use of recently studied hypercontractivity and gradient estimates. These generic tools also allow us to derive generalizations of these results in a general von Neumann algebraic setting beyond the case of the quantum hypercube, including examples in infinite dimensions relevant to quantum information theory such as continuous variables quantum systems. Finally, we comment on the implications of our results as regards to noncommutative extensions of isoperimetric type inequalities, quantum circuit complexity lower bounds and the learnability of quantum observables.

arXiv:2209.07279•Communications in Mathematical Physics•Apr 1, 2024•12 citations

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.

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

Fourier analysis on the discrete hypercubes

\mathcal{O}(\log 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.

For each

d\geq 1

we construct a norm-1 Hermitian operator whose Pauli expansion contains

N(d)=\exp(Ω(d^2))

terms, each of degree

d

and magnitude

1/\sqrt{N(d)}

- the largest magnitude permitted by Parseval's identity. For comparison, if a bounded diagonal operator (or equivalently, a bounded degree-

d

function on the Boolean cube) has

N(d)

Pauli coefficients, all of magnitude

Ω(1/\sqrt{N(d)})

, then

N(d)\leq \exp(\widetilde{O}(d^{1.5}))

. This construction implies the noncommutative Bohnenblust--Hille (BH) constant satisfies

\mathrm{BH}_{M_2}(d)\geq\exp(Ω(d))

. Together with the upper bounds proved in prior work, this settles the asymptotic growth of

\mathrm{BH}_{M_2}(d)

as exponential. Our lower bound also asymptotically separates

\mathrm{BH}_{M_2}(d)

from the (classical) hypercube BH constant

\mathrm{BH}_{\{\pm 1\}}(d)

, which in turn is known to be subexponential:

\mathrm{BH}_{\{\pm 1\}}(d)\leq C^{\sqrt{d \log d}}

. Our Hamiltonians are also unitary and thus quantum Boolean functions in the sense of Montanaro and Osborne (2010). As such they refute the quantum Fourier Entropy-Influence conjecture of Bu et al. (2024), a natural generalization of the classical Fourier Entropy-Influence conjecture due to Friedgut and Kalai (1996).

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.

In this paper, we resolve the quantum KKL conjecture of Montanaro and Osborne \cite{MO2010} for quantum Boolean functions on the

n

-qubit hypercube. More precisely, for every self-adjoint unitary

T

, we bound the largest

L_2

-influence from below by a constant multiple of

\mathrm{Var}(T)\log(n)/n

. The proof heavily depends on upper and lower commutator estimates on the Hilbert space.

We extend three related results from the analysis of influences of Boolean functions to the quantum setting, namely the KKL theorem, Friedgut's Junta theorem and Talagrand's variance inequality for geometric influences. Our results are derived by a joint use of recently studied hypercontractivity and gradient estimates. These generic tools also allow us to derive generalizations of these results in a general von Neumann algebraic setting beyond the case of the quantum hypercube, including examples in infinite dimensions relevant to quantum information theory such as continuous variables quantum systems. Finally, we comment on the implications of our results as regards to noncommutative extensions of isoperimetric type inequalities, quantum circuit complexity lower bounds and the learnability of quantum observables.