Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions

DOI10.1007/s00220-024-04981-0arXiv2209.07279MaRDI QIDQ6125778

Cambyse Rouzé, Melchior Wirth, Haonan Zhang

Publication date: 11 April 2024

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2209.07279

Mathematics Subject Classification ID

Theory of computing (68Qxx) Selfadjoint operator algebras ((C^*)-algebras, von Neumann ((W^*)-) algebras, etc.) (46Lxx) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)

Cites Work

• On the failure of concentration for the \(\ell_\infty\)-ball
• The average sensitivity of bounded-depth circuits
• Geometric influences
• Improving the Lieb-Robinson bound for long-range interactions
• Entanglement rates and the stability of the area law for the entanglement entropy
• Sharpness of KKL on Schreier graphs
• Relating relative entropy, optimal transport and Fisher information: a quantum HWI inequality
• On the hardness of approximating minimum vertex cover
• Modified logarithmic Sobolev inequalities in discrete settings
• Isoperimetric and concentration inequalities: equivalence under curvature lower bound
• On the role of convexity in isoperimetry, spectral gap and concentration
• Applications of the complex interpolation method to a von Neumann algebra: non-commutative \(L^ p\)-spaces
• A note on the edges of the n-cube
• Boolean functions with low average sensitivity depend on few coordinates
• Hypercontractivity in noncommutative \(L_1\) spaces
• On the degree of Boolean functions as real polynomials
• First passage percolation has sublinear distance variance.
• Poincaré, modified logarithmic Sobolev and isoperimetric inequalities for Markov chains with non-negative Ricci curvature
• Graph products, Fourier analysis and spectral techniques
• Theory of operator algebras. II
• On the distribution of the Fourier spectrum of Boolean functions
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Lévy-Gromov's isoperimetric inequality for an infinite dimensional diffusion generator
• A quantitative Arrow theorem
• A converse Gaussian Poincaré-type inequality for convex functions
• Spectral analysis and Feller property for quantum Ornstein-Uhlenbeck semigroups
• Talagrand inequality at second order and application to Boolean analysis
• Quantum reverse hypercontractivity: its tensorization and application to strong converses
• Complete gradient estimates of quantum Markov semigroups
• Noncommutative martingale deviation and Poincaré type inequalities with applications
• Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance
• On the Fourier spectrum of functions on Boolean cubes
• Quantum algorithms for learning and testing juntas
• Hypercontractivity for a quantum Ornstein-Uhlenbeck semigroup
• Nonembeddability theorems via Fourier analysis
• Schwartz operators
• Superconcentration and Related Topics
• Hypercontractivity of quasi-free quantum semigroups
• On the fourier tails of bounded functions over the discrete cube
• Quantum Computation as Geometry
• 50 Years of First-Passage Percolation
• Constant depth circuits, Fourier transform, and learnability
• Hypercontractivity for free products
• Learning Monotone Decision Trees in Polynomial Time
• Quantum flows associated to master equations in quantum optics
• On the Fourier spectrum of monotone functions
• Assignment of Numbers to Vertices
• Every monotone graph property has a sharp threshold
• Hypercontractive Measures, Talagrand’s Inequality, and Influences
• Analysis and Geometry of Markov Diffusion Operators
• Improved quantum hypercontractivity inequality for the qubit depolarizing channel
• Analysis of Boolean Functions
• Noise Sensitivity of Boolean Functions and Percolation
• Hypercontractivity in finite-dimensional matrix algebras
• Fluctuations in first-passage percolation
• The $\chi ^2$χ2-divergence and mixing times of quantum Markov processes
• Quantum logarithmic Sobolev inequalities and rapid mixing
• KKL, Kruskal--Katona, and Monotone Nets
• Some optimal inapproximability results
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices
• The geometry of Markov diffusion generators
• Noise sensitivity of Boolean functions and applications to percolation
• Talagrand's inequality for interacting particle systems satisfying a log-Sobolev inequality
• Learning low-degree functions from a logarithmic number of random queries
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item