Discrete Analysis Seminar

The Solovay--Kitaev theorem, which has important ramifications in quantum computing, gives guarantees on approximations of an arbitrary element of \(SU(2)\) using a fixed finite set, so long as that set generates a dense subgroup. Given element \(g\) and precision \(\varepsilon\), it was known how to compute in \(\textnormal{poly}\log(1/\varepsilon)\) time a \(\varepsilon\)-approximation which uses \(O(\log^{3.001}(1/\varepsilon))\)-many gates from the set. Kuperberg recently improved this count to \(O(\log^{1.45}(1/\varepsilon))\). We will discuss the proof of this new development.

Log-concave distributions over \(\mathbb{R}^n\) are distributions with density functions of the form \(e^V\) where \(V\) is a concave function over \(\mathbb{R}^n\). Such distributions demonstrate strong concentration properties and yet are broad enough to include distribution such as the Gaussian distribution, the Laplace distribution, and uniform measures on convex sets. In search of an analogous notion over the Boolean cube, Eldan and Shamir study \(\beta\)-semi-log-concave measures over the Booleaan cube, which are measures \(\nu\) over \(\{-1, 1\}^n\) whose multilinear extension \(f\) satisfies \(\nabla^2 \log f(x) \le \beta I_n\) for some \(\beta \ge 0\). They prove that any Hamming Lipschitz test function \(\varphi\) over \(\{-1, 1\}^n\) satisfies \(\mathrm{Var}_{\nu}[\varphi] \le n^{2 - C_\beta}\) for some \(C_\beta > 0\), which demonstrates a concentration of measure of \(\mu\). In this talk, we will present the proof of their result via stochastic localization.

Last week, we presented the martingale method for the uniform measure (more generally, product measures) over \(C_n \triangleq \{-1, 1\}^n\) that showed that \(\textnormal{Var}_{\nu}(\varphi) \le O(n)\) for any \(1\)-Hamming-Lipschitz function \(\varphi : C_n \to \mathbb{R}\). Then we realized that the martingale method holds for any localization process on \(\nu\). We ended with motivating stochastic localization as a continuous-time version of the martingale method. This week, we will show that stochastic localization on \(\nu\) is in fact a localization process, making it feasible to apply the martingale method over continuous-time. We will then reduce the problem down to showing that the rate of change of exponential tilts on \(\nu\) with respect to the Wasserstein distance is at most \(O(\beta n^{1 - c_\beta})\) for some \(c_\beta > 0\), which is the heart of the analysis and the part that crucially uses the \(\beta\)-semi-log-concavity of our measure \(\nu\).