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.
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.
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 computational complexity of approximating the 2-to-q norm of linear operators (defined as |A|2->q = maxv≠ 0|Av|q/|v|2) for q > 2, as well as connections between this question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture (UGC). We show the following: For any constant even integer q ≥ 4, a graph G is a small-set expander if and only if the projector into the span of the top eigenvectors of G's adjacency matrix has bounded 2->q norm. As a corollary, a good approximation to the 2->q norm will refute the Small-Set Expansion Conjecture --- a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n2/q) time, thus obtaining a different proof of the known subexponential algorithm for Small-Set-Expansion. Constant rounds of the "Sum of Squares" semidefinite programing hierarchy certify an upper bound on the 2->4 norm of the projector to low degree polynomials over the Boolean cube, as well certify the unsatisfiability of the "noisy cube" and "short code" based instances of Unique-Games considered by prior works. This improves on the previous upper bound of exp(logO(1) n) rounds (for the "short code"), as well as separates the "Sum of Squares"/"Lasserre" hierarchy from weaker hierarchies that were known to require ω(1) rounds. We show reductions between computing the 2->4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2->4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2->4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2->4 norm.