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

The Quantum KKL Inequality — E8 Intelligence Research

Andrew Stewart Caldin

Published Nov 9, 2026• 0 citations
Publisher

Abstract

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. Source: http://arxiv.org/abs/2609.21900v1 (arXiv:2609.21900v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

DOI
10.5281/zenodo.24075471

Related papers

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 Entropy Contraction and Factorization from Hypercontractivity — E8 Intelligence Research

Andrew Stewart Caldin

We prove that hypercontractivity implies entropy contraction for a single quantum channel, without a detailed balance condition. For primitive quantum Markov semigroups that are KMS-symmetric with respect to a faithful invariant state \(σ\), we obtain the modified Log-Sobolev bound $α_1\geq \fracλ{(2+\log\|σ^{-1}\|_\infty)}$ where $λ$ is the spectral gap. This removes the assumption of \(L_p\)-regularity for the comparison through the log-Sobolev constant. As an application, we show that the hypercontractivity of an average of two conditional expectations implies the approximate tensorization of relative entropy. Source: http://arxiv.org/abs/2609.20753v1 (arXiv:2609.20753v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 7, 2026•0 citations

Optimal spectrum estimation — E8 Intelligence Research

Andrew Stewart Caldin

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound. Source: http://arxiv.org/abs/2609.30171v1 (arXiv:2609.30171v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 13, 2026•0 citations

A General Composition Theorem for Approximate Degree — E8 Intelligence Research

Andrew Stewart Caldin

A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree. Source: http://arxiv.org/abs/2609.30139v1 (arXiv:2609.30139v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 13, 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•22 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
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. Source: http://arxiv.org/abs/2609.21900v1 (arXiv:2609.21900v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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 that hypercontractivity implies entropy contraction for a single quantum channel, without a detailed balance condition. For primitive quantum Markov semigroups that are KMS-symmetric with respect to a faithful invariant state σσσ, we obtain the modified Log-Sobolev bound α1≥λ(2+log⁡∥σ−1∥∞)α_1\geq \fracλ{(2+\log\|σ^{-1}\|_\infty)}α1​≥(2+log∥σ−1∥∞​)λ​ where λλλ is the spectral gap. This removes the assumption of LpL_pLp​-regularity for the comparison through the log-Sobolev constant. As an application, we show that the hypercontractivity of an average of two conditional expectations implies the approximate tensorization of relative entropy. Source: http://arxiv.org/abs/2609.20753v1 (arXiv:2609.20753v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
We prove that the spectrum of an unknown ddd-dimensional quantum state can be estimated to error ε\varepsilonε in total variation distance using O ⁣(d2min⁡{1(εlog⁡d)4,  1(εlog⁡d)2}) O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) O(d2min{(εlogd)41​,(εlogd)21​}) copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of ddd in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound. Source: http://arxiv.org/abs/2609.30171v1 (arXiv:2609.30171v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} and g:{0,1}m→{0,1}g:\{0,1\}^m\to\{0,1\}g:{0,1}m→{0,1}, deg~(f∘g)=Θ ⁣(deg~(f) deg~(g)), \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), deg​(f∘g)=Θ(deg​(f)deg​(g)), where deg~\widetilde{deg}deg​ denotes constant-error approximate degree. Source: http://arxiv.org/abs/2609.30139v1 (arXiv:2609.30139v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.
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.