54 citations · 84 across the 6 of their papers we have counts for
11 papers
Robustness of Quantum Algorithms for Nonconvex Optimization
Weiyuan Gong, Chenyi Zhang, Tongyang Li
Recent results suggest that quantum computers possess the potential to speed up nonconvex optimization problems. However, a crucial factor for the implementation of quantum optimiz…
Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
Tongyang Li, Ruizhe Zhang
We initiate the study of quantum algorithms for optimizing approximately convex functions. Given a convex set and a function $F\colon\mathbb{R}^{n…
Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets
Zongqi Wan, Zhijie Zhang, Tongyang Li +2
Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horiz…
Quantum query complexity with matrix-vector products
Andrew M. Childs, Shih-Han Hung, Tongyang Li
We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the tr…
Sublinear classical and quantum algorithms for general matrix games
Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti +1
We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix $A\…
On the cut dimension of a graph
Troy Lee, Tongyang Li, Miklos Santha +1
Let be a weighted undirected graph with edges. The cut dimension of is the dimension of the span of the characteristic vectors of the minimum cuts of , viewe…