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.
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
L2-influence from below by a constant multiple of
Var(T)log(n)/n. The proof heavily depends on upper and lower commutator estimates on the Hilbert space.
We prove here several tightness results for such quantum inequalities as 1) the comparison of operator norm and product norm of
d-local hamiltonians, 2) Bohnenblust--Hille inequality for
d-local hamiltonians, 3) for quantum Fourier entropy-influence conjecture. We give a deterministic prove of the sharpness of Bohnenblust--Hille exponent. We also discuss the quantum Aaronson--Ambainis conjecture in a special case of anti-commuting Pauli strings.
Previous noncommutative Bohnenblust--Hille (BH) inequalities addressed operator decompositions in the tensor-product space
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)⊗n for any
K≥2 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.
We study the one-way communication complexity of the
f-Boolean Hidden Partition problem. Here, Alice is given an
n-bit string and Bob is given
Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of
f on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where
f is the parity function.
We establish classical and quantum communication bounds for
f-Boolean Hidden Partition in terms of the sign degree
d of
f, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when
d≤1 and quantum protocols when
d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every
f of sign degree
d≥2, the randomized classical communication complexity of this problem is
Θ(n1−1/d) while its quantum communication complexity lies between
Ω(n1−2/d) and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions
f admitting polynomial quantum advantage as those for which
d≥2, with a new infinite family of exponential separations given by the case
d=2.
Low-energy estimation and state preparation for general
k-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound
O∗(2n/2) for both problems, with the improvement depending on the relative accuracy
ε and the locality
k. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small
ε/k, our algorithms improve the exponent by a factor of
log(k/ε) over [BGLGST, PRL 2025]. Our main technical result is an entropy-governed lower bound on the dimension of the Hamiltonian's low-energy subspace, obtained by depolarizing its ground state. For fixed
k, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg,
XY, and Ising models on arbitrary interaction graphs.