Endpoint quantum KKL inequality for Boolean observables

Problem

Does the Montanaro–Osborne \(L^2\) quantum KKL inequality hold for every Boolean quantum observable?

Let \(A=A^\dagger\) act on \(n\geq2\) qubits and satisfy \(A^2=I\). Write \(\tau(A)=2^{-n}\operatorname{Tr}A\), let \(\mathcal E_i\) completely depolarize qubit \(i\), and define

\begin{equation} \mathcal E_i(A)=\frac{I_i}{2}\otimes\operatorname{Tr}_iA, \qquad D_iA=A-\mathcal E_i(A), \qquad \operatorname{Inf}^{(2)}_i(A)=\tau[(D_iA)^\dagger D_iA]. \tag{1} \end{equation}

Does a universal constant \(c>0\) exist such that every such \(A\) satisfies

\begin{equation} \max_i\operatorname{Inf}^{(2)}_i(A) \geq c\bigl(1-\tau(A)^2\bigr)\frac{\log n}{n}? \tag{2} \end{equation}

Equation (2) uses the squared influences defined in Eq. (1); the balanced case has \(\tau(A)=0\).

Source

The question is explicitly posed or retained as open in the cited primary literature [Montanaro08][Jiao24]. The statement is rewritten here to make its hypotheses and success criterion self-contained.

Progress

Reports do not certify correctness or automatically change the problem's status. Progress policy.

For diagonal observables \(A=\sum_x f(x)|x\rangle\langle x|\), the influence in Eq. (1) reduces to the classical bit-flip influence, and Eq. (2) becomes the classical KKL bound. The tensor-product quantum extension was proposed by Montanaro and Osborne [Montanaro08].
Rouzé, Wirth, and Zhang proved important quantum Talagrand, KKL-type, and Friedgut results using geometric or \(L^p\) influences with \(p<2\). Those results do not resolve the displayed endpoint. Jiao, Lin, Luo, and Zhou explicitly preserve this distinction and state that the Montanaro–Osborne conjecture remains open. [Rouz24], [Jiao24]
The February 17, 2026 revision by Chang and Li develops further variance-decay and higher-order inequalities. Its relevant influence results remain sub-\(L^2\); their constants do not give the required endpoint by simply taking \(p\to2\). [Chang26]
An August 6, 2026 paper by Slote, Volberg, and Zhang provides another useful comparison. Its Hermitian-dilation family has small influences on the data qubits but an ancilla of influence one. Section 7 explicitly explains why this is not a counterexample to standard quantum KKL, which counts every qubit. [Slote26]

Comment

Retained as unresolved, with 2026 partial-progress and counterexample checks. A counterexample in a canonical anticommutation-relation algebra uses a different coordinate structure and must not be substituted for a counterexample on the tensor-product qubit cube. [Jiao24]

References

[Montanaro08]: A. Montanaro and T. J. Osborne, Quantum boolean functions, arXiv:0810.2435 (2008); Chicago Journal of Theoretical Computer Science (2010). Paper.arXiv
[Jiao24]: Y. Jiao, W. Lin, S. Luo, and D. Zhou, Quantum KKL-type inequalities revisited, arXiv:2411.12399, November 2024, Introduction, including the explicit distinction between the CAR counterexample and the Montanaro–Osborne conjecture. Full text. See Conjecture 1.4 for the displayed variance-weighted formulation.link
[Rouz24]: C. Rouzé, M. Wirth, and H. Zhang, Quantum Talagrand, KKL and Friedgut’s theorems and the learnability of quantum Boolean functions, arXiv:2209.07279; Communications in Mathematical Physics (2024). Paper.arXiv
[Chang26]: F. Chang and P. Li, Quantum Talagrand-type Inequalities via Variance Decay, arXiv:2601.01900v2, February 17, 2026, Introduction and Section 4. Full text.link
[Slote26]: J. Slote, A. Volberg, and H. Zhang, Tightness of and counterexamples to several quantum estimates, arXiv:2608.04411v2, August 6, 2026, Section 7, on the influential ancilla. Full text.link

Endpoint quantum KKL inequality for Boolean observables

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems