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 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.
Consider a Hermitian operator A acting on a complex Hilbert space of dimension 2n. We show that when A has small degree in the Pauli expansion, or in other words, A is a local n-qubit Hamiltonian, its operator norm can be approximated independently of n by maximizing ∣⟨ψ∣A∣ψ⟩∣ over a small collection Xn of product states ∣ψ⟩∈(C2)⊗n. More precisely, we show that whenever A is d-local, \textit{i.e.,} °(A)≤d, we have the following discretization-type inequality: ∥A∥≤C(d)maxψ∈Xn∣⟨ψ∣A∣ψ⟩∣. The constant C(d) depends only on d. This collection Xn of ψ's, termed a \emph{quantum norm design}, is independent of A, and consists of product states, and can have cardinality as small as $(1+\eps)^n$, which is essentially tight. Previously, norm designs were known only for homogeneous d-localHamiltonians A \cite{L,BGKT,ACKK}, and for non-homogeneous 2-local traceless A \cite{BGKT}. Several other results, such as boundedness of Rademacher projections for all levels and estimates of operator norms of random Hamiltonians, are also given.
We suggest a tight inequality for norms in d-dimensional space $l_p $ which has simple formulation but appears hard to prove. We give a proof for d=3 and provide a detailed numerical check for d≤200 confirming the conjecture. We conclude with a brief survey of solutions for kin problems which anyhow concern minimization of the output entropy of certain quantum channel and rely upon the symmetry properties of the problem.
Key words and phrases: $l_p $-norm, Rényi entropy, tight inequality, maximization of a convex function.
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 consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works.
1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials p of degree t satisfy a root-influence bound, ∥p∥cb≥∑iInfi[p]/t2, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: ∥p∥cb≥∑iInfi[p]/t. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as t-fold forrelation- are block-multilinear polynomials with ∥p∥cb≤1, our inequality shows that they satisfy t≥∑iInfi[p]. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive.
2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial p defined on {−1,1}n of degree 2t, the Fourier Growth at the level 2t, namely ∥p2t∥ℓ1, satisfies ∥p2t∥ℓ1≤(en/(2t−1))22t−1∥p∥cb. This is optimal up to the factor e, as witnessed by 2t-fold forrelation. As quantum query algorithms that make t queries (to the whole input) satisfy ∥p∥cb≤1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
For each d≥1 we construct a norm-1 Hermitian operator whose Pauli expansion contains N(d)=exp(Ω(d2)) terms, each of degree d and magnitude 1/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/N(d)), then N(d)≤exp(O(d1.5)).
This construction implies the noncommutative Bohnenblust--Hille (BH) constant satisfies BHM2(d)≥exp(Ω(d)). Together with the upper bounds proved in prior work, this settles the asymptotic growth of BHM2(d) as exponential. Our lower bound also asymptotically separates BHM2(d) from the (classical) hypercube BH constant BH{±1}(d), which in turn is known to be subexponential: BH{±1}(d)≤Cdlogd.
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).