6 papers
A Tale of Two Walks: From Kac to KMP and Back
Qian Chen, Jingcheng Liu, Minglong Qin +5
We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue o…
Rapid Mixing of Parallel Kac's Walk: From Spheres to Stiefel Manifolds
Qian Chen, Minglong Qin, Fang Song +2
Kac's walk is a classical local random walk whose action on a single real unit vector in dimension mixes in total variation in sequential steps~\cite{PS17}. Lu, Qi…
On the complexity of proximal gradient and proximal gradient-Newton-CG methods for -regularized Optimization
Hong Zhu
In this paper, we propose two second-order methods for solving the \(\ell_1\)-regularized composite optimization problem, which are developed based on two distinct definitions of a…
Quantum State Learning Implies Circuit Lower Bounds
Nai-Hui Chia, Daniel Liang, Fang Song
We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let be a family of non-uniform…
A Cryptographic Perspective on the Verifiability of Quantum Advantage
Nai-Hui Chia, Honghao Fu, Fang Song +1
In recent years, achieving verifiable quantum advantage on a NISQ device has emerged as an important open problem in quantum information. The sampling-based quantum advantages are…
Quantum Pseudorandom Scramblers
Chuhan Lu, Minglong Qin, Fang Song +2
Quantum pseudorandom state generators (PRSGs) have stimulated exciting developments in recent years. A PRSG, on a fixed initial (e.g., all-zero) state, produces an output state tha…