4 papers
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…