Thread by @fgrosshans

Now at #QuPa (at @InHenriPoincare), Anup Prakash from @IRIF_Paris
on “Quantum Linear Systems with QRAM data structure”
#LTQI

@InHenriPoincare @IRIF_Paris Anupam Prakash uses the HHL algroithm ( @quantum_aram Hassidim Lloyd). Its running time (with improvement) is O(sκ poly(1/ε)):
κ: condition number
s: sparsity
#LTQI #QuPa

@InHenriPoincare @IRIF_Paris @quantum_aram Anupam Prakash: presents an algorithm with improved dependence on sparsity. (quatuified thorugh a µ(A) which I didn’t understand. Check his recent papers with Iordanis Kerenidis for details)
#LTQI #QuPa

@InHenriPoincare @IRIF_Paris @quantum_aram Anupam Prakesh: Quantum algorithm often assume an oracle preforming |i,0⟩→|i,x_i⟩ . It is reasonable if x_i=f(i) with f done by a circuit. For quantum machine learning (QML), f is unknown and it is unreasonable, unless one has a QRAM
#LTQI #QuPa

@InHenriPoincare @IRIF_Paris @quantum_aram Anupam Prakash: Defi,ition: a dataset (N entries) is efficiently loaded in QRAM if it is stored in volume O(N), but it is accessible in time O(polylog(N)).
It allows to have sublinear QML computation (+ date preparation cost, which is not taken into account)
#LTQI #QuPa

@InHenriPoincare @IRIF_Paris @quantum_aram Anupam Prakash loks at singular value estimation (SVE) problem.
A has singular vectors (ui,vi) and values σi
∑βi |vi⟩|0⟩ –SVE→ ∑βi |vi⟩|σi⟩

It allows to solve linear systems
#LTQI #QuPa

@InHenriPoincare @IRIF_Paris @quantum_aram Anupam Prakash‘s SVE algorithm is based on quantum walks and efficient data structures in QRAM.
It is described in arXiv:1603.08675 arxiv.org/abs/1603.08675 and arxiv:1704.04992 arxiv.org/abs/1704.04992
#LTQI #QuPa

@InHenriPoincare @IRIF_Paris @quantum_aram Anupam Prakash’s algorithm in dense case: quadratic speedup over HHL (exponential fro matrices with polylogarithmic rank)
Sparse case: (I was too busy tweeting to get the result here ;-) )
#LTQI #QuPa

@InHenriPoincare @IRIF_Paris @quantum_aram Anupam Prakash: Further improvements: After this work, two groups improved it to have a log(1/ε) dependence.
#LTQI #QuPa