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:2608.01424

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

Joseph Slote

math.FAmath-phquant-phSubmitted Aug 2, 2026• Announced Aug 4, 2026• 4 citations
arXivHTMLPDF

Abstract

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

Comments
8 pages

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•19 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

Tightness of and counterexamples to several quantum estimates

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

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.

arXiv:2608.04411•Aug 5, 2026•2 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•6 citations

Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem

Mark Bun, Joao F. Doriguello, John Kallaugher +1 more

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 \le 1$ and quantum protocols when $d \le 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 \ge 2$, the randomized classical communication complexity of this problem is $Θ(n^{1-1/d})$ while its quantum communication complexity lies between $Ω(n^{1-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 \ge 2$, with a new infinite family of exponential separations given by the case $d = 2$.

quant-pharXiv:2610.06789•Oct 6, 2026•0 citations

Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms

Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi +1 more

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^\ast(2^{n/2})$ for both problems, with the improvement depending on the relative accuracy $\varepsilon$ 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 $\varepsilon/k$, our algorithms improve the exponent by a factor of $\log(k/\varepsilon)$ 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.

quant-pharXiv:2609.34532•Sep 29, 2026•0 citations
For each d≥1d\geq 1d≥1 we construct a norm-1 Hermitian operator whose Pauli expansion contains N(d)=exp⁡(Ω(d2))N(d)=\exp(Ω(d^2))N(d)=exp(Ω(d2)) terms, each of degree ddd and magnitude 1/N(d)1/\sqrt{N(d)}1/N(d)​ - the largest magnitude permitted by Parseval's identity. For comparison, if a bounded diagonal operator (or equivalently, a bounded degree-ddd function on the Boolean cube) has N(d)N(d)N(d) Pauli coefficients, all of magnitude Ω(1/N(d))Ω(1/\sqrt{N(d)})Ω(1/N(d)​), then N(d)≤exp⁡(O~(d1.5))N(d)\leq \exp(\widetilde{O}(d^{1.5}))N(d)≤exp(O(d1.5)).
This construction implies the noncommutative Bohnenblust--Hille (BH) constant satisfies BHM2(d)≥exp⁡(Ω(d))\mathrm{BH}_{M_2}(d)\geq\exp(Ω(d))BHM2​​(d)≥exp(Ω(d)). Together with the upper bounds proved in prior work, this settles the asymptotic growth of BHM2(d)\mathrm{BH}_{M_2}(d)BHM2​​(d) as exponential. Our lower bound also asymptotically separates BHM2(d)\mathrm{BH}_{M_2}(d)BHM2​​(d) from the (classical) hypercube BH constant BH{±1}(d)\mathrm{BH}_{\{\pm 1\}}(d)BH{±1}​(d), which in turn is known to be subexponential: BH{±1}(d)≤Cdlog⁡d\mathrm{BH}_{\{\pm 1\}}(d)\leq C^{\sqrt{d \log d}}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).
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 nnn-qubit hypercube. More precisely, for every self-adjoint unitary TTT, we bound the largest L2L_2L2​-influence from below by a constant multiple of Var(T)log⁡(n)/n\mathrm{Var}(T)\log(n)/nVar(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 ddd-local hamiltonians, 2) Bohnenblust--Hille inequality for ddd-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)⊗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.
We study the one-way communication complexity of the fff-Boolean Hidden Partition problem. Here, Alice is given an nnn-bit string and Bob is given Ω(n)Ω(n)Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of fff 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 fff is the parity function. We establish classical and quantum communication bounds for fff-Boolean Hidden Partition in terms of the sign degree ddd of fff, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1d \le 1d≤1 and quantum protocols when d≤2d \le 2d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every fff of sign degree d≥2d \ge 2d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d)Θ(n^{1-1/d})Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d)Ω(n^{1-2/d})Ω(n1−2/d) and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions fff admitting polynomial quantum advantage as those for which d≥2d \ge 2d≥2, with a new infinite family of exponential separations given by the case d=2d = 2d=2.
Near-Optimal Bounds on the Density of Low-Energy States of kkk-Local Hamiltonians and Faster Quantum Algorithms
Low-energy estimation and state preparation for general kkk-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound O∗(2n/2)O^\ast(2^{n/2})O∗(2n/2) for both problems, with the improvement depending on the relative accuracy ε\varepsilonε and the locality kkk. 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\varepsilon/kε/k, our algorithms improve the exponent by a factor of log⁡(k/ε)\log(k/\varepsilon)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 kkk, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, XYXYXY, and Ising models on arbitrary interaction graphs.