On the quantum KKL theorem and related inequalities | BIMSA-Tsinghua Quantum Symmetry Seminar

Abstract

The KKL theorem is a fundamental result in Boolean analysis, stating that any Boolean functionhas an influential variable. Montanaro and Osbomne proposed a quantum extension of Booleanfunctions. In this context, some classical results have been extended to the guantum setting, suchas Talagrand's I-_I’ ineguality. However, a quantum version of the KKL theorem seems to bemissing, as conjectured by Montanaro and Osborne. In this talk, l will present an alternative answerto this question, saying that every balanced quantum Boolean function has a geometricallyinfluential variable. This is based on joint work with Cambyse Rouz (lnria) and Melchior Wirth (lSTAustria).