4 papers
Finding Stationary Points by Comparisons
Helin Wang, Chenyi Zhang, Xiwen Tao +2
We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs…
Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
Tongyang Li, Xinzhao Wang, Yexin Zhang
Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computin…
Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs
Yexin Zhang, Shuo Zhou, Xinzhao Wang +5
Gaussian Boson Sampling (GBS) is a promising candidate for demonstrating quantum computational advantage and can be applied to solving graph-related problems. In this work, we prop…
Quantum Algorithms and Lower Bounds for Finite-Sum Optimization
Yexin Zhang, Chenyi Zhang, Cong Fang +2
Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the stud…