English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give a classical algorithm for linear regression analogous to the quantummatrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical ReviewLetters'09, arXiv:0811.3171] for low-rank matrices [Wossnig, Zhao, and Prakash,Physical Review Letters'18, arXiv:1704.06174], when the input matrix $A$ isstored in a data structure applicable for QRAM-based state preparation.  Namely, suppose we are given an $A \in \mathbb{C}^{m\times n}$ with minimumnon-zero singular value $\sigma$ which supports certain efficient $\ell_2$-normimportance sampling queries, along with a $b \in \mathbb{C}^m$. Then, for some$x \in \mathbb{C}^n$ satisfying $\|x - A^+b\| \leq \varepsilon\|A^+b\|$, we canoutput a measurement of $|x\rangle$ in the computational basis and output anentry of $x$ with classical algorithms that run in$\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^6}{\sigma^{12}\varepsilon^4}\big)$and$\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^2}{\sigma^8\varepsilon^4}\big)$time, respectively. This improves on previous "quantum-inspired" algorithms inthis line of research by at least a factor of$\frac{\|A\|^{16}}{\sigma^{16}\varepsilon^2}$ [Chia, Gily\'en, Li, Lin, Tang,and Wang, STOC'20, arXiv:1910.06151]. As a consequence, we show that quantumcomputers can achieve at most a factor-of-12 speedup for linear regression inthis QRAM data structure setting and related settings. Our work appliestechniques from sketching algorithms and optimization to the quantum-inspiredliterature. Unlike earlier works, this is a promising avenue that could lead tofeasible implementations of classical regression in a quantum-inspiredsettings, for comparison against future quantum computers.

An improved quantum-inspired algorithm for linear regression