238 citations · 627 across the 10 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018★ 58 cited
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…
cs.DS2018★ 143 cited
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…
cs.IR2018★ 238 cited
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…