238 citations · 627 across the 10 of their papers we have counts for
10 papers
Do you know what q-means?
Arjan Cornelissen, Joao F. Doriguello, Alessandro Luongo +1
Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's algorithm for -means. This algorithm t…
An Improved Classical Singular Value Transformation for Quantum Machine Learning
Ainesh Bakshi, Ewin Tang
We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. QSVT, introduced by [GSLW, STOC'19, arXiv:1806.…
A CS guide to the quantum singular value transformation
Ewin Tang, Kevin Tian
We present a simplified exposition of some pieces of [Gilyén, Su, Low, and Wiebe, STOC'19, arXiv:1806.01838], which introduced a quantum singular value transformation (QSVT) framew…
Query-optimal estimation of unitary channels in diamond distance
Jeongwan Haah, Robin Kothari, Ryan O'Donnell +1
We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a -dimensional qudit, we aim to output a classical des…
An improved quantum-inspired algorithm for linear regression
András Gilyén, Zhao Song, Ewin Tang
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09, arXiv:0811.3171] f…
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-inspired low-rank stochastic regression with logarithmic dependence on the dimension
András Gilyén, Seth Lloyd, Ewin Tang
We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices. Inspired by recent work of Tang, assuming length-square sampling…
Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
Ewin Tang
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Ta…
A quantum-inspired classical algorithm for recommendation systems
Ewin Tang
We give a classical analogue to Kerenidis and Prakash's quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups i…
Factorizations of -Nonnegative Matrices
Sunita Chepuri, Neeraja Kulkarni, Joe Suk +1
A matrix is -nonnegative if all its minors of size or less are nonnegative. We give a parametrized set of generators and relations for the semigroup of -nonnegative $n\ti…