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

The Quantum KKL Inequality

Yong Jiao, Wenlong Lin, Sijie Luo, Dejian Zhou

quant-phmath.FASubmitted Sep 18, 2026• Announced Sep 21, 2026• 0 citations
arXivHTMLPDF

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.

AI Summary

The paper addresses the Montanaro–Osborne quantum KKL conjecture: must every $n$-qubit quantum Boolean function—a self-adjoint unitary $T$—have a qubit with squared $L_2$-influence of order $\mathrm{Var}(T)\log n/n$? Here $D_j$ removes the component proportional to the identity on qubit $j$, and $\mathrm{Inf}(T)=\sum_j\|D_jT\|_2^2$, using normalized Schatten norms. It claims an affirmative resolution, proving $\log(1/\max_j\|D_jT\|_2^2)\leq 2^{11}\mathrm{Inf}(T)/\mathrm{Var}(T)$ and consequently $\max_j\|D_jT\|_2^2\geq 2^{-12}\mathrm{Var}(T)\log n/n$. This reaches the $p=2$ endpoint not covered by previous quantum influence bounds for $1\leq p<2$. The classical route is obstructed because Boolean observables need not satisfy $\|D_jT\|_1=\|D_jT\|_2^2$. The proof factors each influence operator into normalized local Pauli commutator derivations. These derivatives anticommute with $T$ because $T^2=\mathbf1$, supplying lower commutator bounds. Upper bounds for low-degree observables combine quantum hypercontractivity with partial-transpose products that reverse multiplication order one qubit at a time. Randomized, heat-semigroup-smoothed derivative tests connect the two estimates; a dyadic spectral window and separate degree truncations control approximation errors. The theorem concerns Boolean observables on the qubit tensor-product algebra, not arbitrary observables or general noncommutative probability spaces. The paper notes that the analogous $L_2$-influence KKL inequality fails in the CAR-algebra setting. It does not develop algorithmic or experimental applications.

Little sign of AI-generated text

Error found: Section 5 unjustifiably replaces d ≤ κ(9 + 2 log q) by d ≤ κ(9 + log q), although retaining the missing factor still proves the stated final constant. The exponential-form theorem includes T = −I under its stated nontriviality assumption, even though its ratio Inf(T)/Var(T) is undefined for that operator. Section 5 incorrectly asserts n/Var(T) ≥ 2 for all cases under consideration, since a traceless single-qubit self-adjoint unitary has n/Var(T) = 1.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

The Quantum KKL Inequality — E8 Intelligence Research

Andrew Stewart Caldin

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

•Nov 9, 2026•0 citations

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

Joseph Slote

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

math.FACross-listedarXiv:2608.01424•Aug 4, 2026•4 citations

A note on quantum black-box complexity of almost all Boolean functions

Andris Ambainis

arXiv:quant-ph/9811080•Information Processing Letters•Jul 1, 1999•26 citations

Some Monogamy Inequalities Based on the $$\alpha $$-logarithmic Concurrence Measure for N-qubit States

Yinzhu Wang, Chen Cheng, Lihua Hao +2 more

International Journal of Theoretical Physics•Jan 22, 2025•0 citations

Exponential lower bounds for low-degree strategies in position-based quantum cryptography

Isabel M. Moreno-Cuadrado, David Perez-Garcia, Carlos Palazuelos

Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary $U_{AB}$ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary $U_{AB}$ whose implementation in NLQC requires extra quantum systems with dimensions ${\rm exp}(n^{Ω(1)})$, where $n$ is the dimension of systems $A$ and $B$. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in $n$. In this paper we consider the family of diagonal ${\pm 1}$ valued unitaries $U_{\varepsilon}$, indexed by an element of the Boolean hypercube $\varepsilon \in \{\pm 1\}^{n^2}$, i.e. $U_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_B$. We show that if $U_{\varepsilon}$ can be implemented in NLQC with constant accuracy for all $\varepsilon$, and the dependency on $\varepsilon$ in the first round of the associated strategy is a polynomial of degree $O(n^{\frac{1}{4}-δ})$, then the implementation of at least one $U_{\varepsilon}$ in NLQC requires resources scaling as $\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)$. The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.

quant-pharXiv:2609.35592•Sep 29, 2026•1 citation

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
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.
The paper addresses the Montanaro–Osborne quantum KKL conjecture: must every nnn-qubit quantum Boolean function—a self-adjoint unitary TTT—have a qubit with squared L2L_2L2​-influence of order Var(T)log⁡n/n\mathrm{Var}(T)\log n/nVar(T)logn/n? Here DjD_jDj​ removes the component proportional to the identity on qubit jjj, and Inf(T)=∑j∥DjT∥22\mathrm{Inf}(T)=\sum_j\|D_jT\|_2^2Inf(T)=∑j​∥Dj​T∥22​, using normalized Schatten norms.
It claims an affirmative resolution, proving log⁡(1/max⁡j∥DjT∥22)≤211Inf(T)/Var(T)\log(1/\max_j\|D_jT\|_2^2)\leq 2^{11}\mathrm{Inf}(T)/\mathrm{Var}(T)log(1/maxj​∥Dj​T∥22​)≤211Inf(T)/Var(T) and consequently max⁡j∥DjT∥22≥2−12Var(T)log⁡n/n\max_j\|D_jT\|_2^2\geq 2^{-12}\mathrm{Var}(T)\log n/nmaxj​∥Dj​T∥22​≥2−12Var(T)logn/n. This reaches the p=2p=2p=2 endpoint not covered by previous quantum influence bounds for 1≤p<21\leq p<21≤p<2. The classical route is obstructed because Boolean observables need not satisfy ∥DjT∥1=∥DjT∥22\|D_jT\|_1=\|D_jT\|_2^2∥Dj​T∥1​=∥Dj​T∥22​.
The proof factors each influence operator into normalized local Pauli commutator derivations. These derivatives anticommute with TTT because T2=1T^2=\mathbf1T2=1, supplying lower commutator bounds. Upper bounds for low-degree observables combine quantum hypercontractivity with partial-transpose products that reverse multiplication order one qubit at a time. Randomized, heat-semigroup-smoothed derivative tests connect the two estimates; a dyadic spectral window and separate degree truncations control approximation errors.
The theorem concerns Boolean observables on the qubit tensor-product algebra, not arbitrary observables or general noncommutative probability spaces. The paper notes that the analogous L2L_2L2​-influence KKL inequality fails in the CAR-algebra setting. It does not develop algorithmic or experimental applications.
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
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).
Some Monogamy Inequalities Based on the α\alpha α-logarithmic Concurrence Measure for N-qubit States
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary UABU_{AB}UAB​ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary UABU_{AB}UAB​ whose implementation in NLQC requires extra quantum systems with dimensions exp(nΩ(1)){\rm exp}(n^{Ω(1)})exp(nΩ(1)), where nnn is the dimension of systems AAA and BBB. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in nnn. In this paper we consider the family of diagonal ±1{\pm 1}±1 valued unitaries UεU_{\varepsilon}Uε​, indexed by an element of the Boolean hypercube ε∈{±1}n2\varepsilon \in \{\pm 1\}^{n^2}ε∈{±1}n2, i.e. Uε∣i⟩A∣j⟩B=εij∣i⟩A∣j⟩BU_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_BUε​∣i⟩A​∣j⟩B​=εij​∣i⟩A​∣j⟩B​. We show that if UεU_{\varepsilon}Uε​ can be implemented in NLQC with constant accuracy for all ε\varepsilonε, and the dependency on ε\varepsilonε in the first round of the associated strategy is a polynomial of degree O(n14−δ)O(n^{\frac{1}{4}-δ})O(n41​−δ), then the implementation of at least one UεU_{\varepsilon}Uε​ in NLQC requires resources scaling as exp⁡(Ω(n2δ(log⁡n)2))\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)exp(Ω((logn)2n2δ​)). The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
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.