171 citations · 480 across the 25 of their papers we have counts for
29 papers
Unleashing the Potential of LLMs for Quantum Computing: A Study in Quantum Architecture Design
Zhiding Liang, Jinglei Cheng, Rui Yang +6
Large Language Models (LLMs) contribute significantly to the development of conversational AI and has great potentials to assist the scientific research in various areas. This pape…
Exponential speedups for quantum walks in random hierarchical graphs
Shankar Balasubramanian, Tongyang Li, Aram Harrow
There are few known exponential speedups for quantum algorithms and these tend to fall into even fewer families. One speedup that has mostly resisted generalization is the use of q…
Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems
Qian Zuo, Tongyang Li
We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A\in\mathbb{R}^{m\times n…
Near-Optimal Quantum Coreset Construction Algorithms for Clustering
Yecheng Xue, Xiaoyu Chen, Tongyang Li +1
-Clustering in (e.g., -median and -means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the class…
Fidelity estimator, randomized benchmarking and ZNE for quantum pulses
Jinglei Cheng, Zhiding Liang, Rui Yang +4
Most previous research focused on designing pulse programs without considering the performance of individual elements or the final fidelity. To evaluate the performance of quantum…
Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
Minbo Gao, Zhengfeng Ji, Tongyang Li +1
We propose the first online quantum algorithm for solving zero-sum games with regret under the game setting. Moreover, our quantum algorithm computes an $\varepsi…
Towards Advantages of Parameterized Quantum Pulses
Zhiding Liang, Jinglei Cheng, Zhixin Song +7
The advantages of quantum pulses over quantum gates have attracted increasing attention from researchers. Quantum pulses offer benefits such as flexibility, high fidelity, scalabil…
Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret
Han Zhong, Jiachen Hu, Yecheng Xue +2
While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design pro…
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 Lower Bounds for Finding Stationary Points of Nonconvex Functions
Chenyi Zhang, Tongyang Li
Quantum algorithms for optimization problems are of general interest. Despite recent progress in classical lower bounds for nonconvex optimization under different settings and quan…
A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
Xinzhao Wang, Shengyu Zhang, Tongyang Li
Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of di…
Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
Andrew M. Childs, Tongyang Li, Jin-Peng Liu +2
Given a convex function , the problem of sampling from a distribution is called log-concave sampling. This task has wide app…
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…
On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
Yizhou Liu, Weijie J. Su, Tongyang Li
Classical algorithms are often not effective for solving nonconvex optimization problems where local minima are separated by high barriers. In this paper, we explore possible quant…
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 State Preparation with Optimal Circuit Depth: Implementations and Applications
Xiao-Ming Zhang, Tongyang Li, Xiao Yuan
Quantum state preparation is an important subroutine for quantum computing. We show that any -qubit quantum state can be prepared with a -depth circuit using only single-…
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…
Quantum algorithms for escaping from saddle points
Chenyi Zhang, Jiaqi Leng, Tongyang Li
We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function , our quantum algorithm ou…
Quantum exploration algorithms for multi-armed bandits
Daochen Wang, Xuchen You, Tongyang Li +1
Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access t…
Quantum Wasserstein Generative Adversarial Networks
Shouvanik Chakrabarti, Yiming Huang, Tongyang Li +2
The study of quantum generative models is well-motivated, not only because of its importance in quantum machine learning and quantum chemistry but also because of the perspective o…
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, Tongyang Li +3
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quant…
Quantum algorithm for estimating volumes of convex bodies
Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung +3
Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates…