arXiv:2609.21900
The Quantum KKL Inequality
Yong Jiao, Wenlong Lin, Sijie Luo, Dejian Zhou
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.
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.