Faster Quantum-inspired Algorithms for Solving Linear Systems

加速 量子算法 组合数学 算法 数学 量子 二次方程 卡帕 物理 计算机科学 量子力学 几何学 操作系统
作者
Changpeng Shao,Ashley Montanaro
出处
期刊:ACM transactions on quantum computing [Association for Computing Machinery]
卷期号:3 (4): 1-23 被引量:13
标识
DOI:10.1145/3520141
摘要

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system \( A{\bf x}= {\bf b} \) , we show that there is a classical algorithm that outputs a data structure for \( {\bf x} \) allowing sampling and querying to the entries, where \( {\bf x} \) is such that \( \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert \) . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is \( \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) \) , where \( \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert \) and \( \kappa = \Vert A\Vert \Vert A^{+}\Vert \) . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity \( \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) \) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution \( {\bf x} \) in time \( \widetilde{O}(\kappa _F^2) \) , while the best quantum algorithm known returns \( | {\bf x} \rangle \) in time \( \widetilde{O}(\kappa _F) \) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
PDF的下载单位、IP信息已删除 (2025-6-4)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
现代冷松完成签到,获得积分10
1秒前
Chimmy完成签到,获得积分10
6秒前
朴树朋友完成签到,获得积分20
6秒前
wlnhyF完成签到,获得积分10
8秒前
pursuit完成签到,获得积分10
11秒前
Neltharion完成签到,获得积分10
12秒前
沈海完成签到,获得积分10
14秒前
悦耳傥完成签到 ,获得积分10
14秒前
一叶知秋应助大橙子采纳,获得10
14秒前
科研小能手完成签到,获得积分10
15秒前
guoxingliu发布了新的文献求助200
16秒前
Double_N完成签到,获得积分10
19秒前
路路完成签到 ,获得积分10
20秒前
碧蓝的盼夏完成签到,获得积分10
24秒前
AU完成签到 ,获得积分10
25秒前
研友_yLpYkn完成签到,获得积分10
26秒前
兴奋的定帮完成签到 ,获得积分0
27秒前
一叶知秋应助大橙子采纳,获得10
28秒前
29秒前
金蛋蛋完成签到 ,获得积分10
29秒前
马琛尧完成签到 ,获得积分10
31秒前
一行白鹭上青天完成签到 ,获得积分10
35秒前
帅气的宽完成签到 ,获得积分10
36秒前
lixoii完成签到 ,获得积分10
38秒前
萌萌许完成签到,获得积分10
38秒前
sunce1990完成签到 ,获得积分10
41秒前
Bin_Liu完成签到,获得积分20
42秒前
宇老师完成签到,获得积分10
42秒前
研友_VZG7GZ应助马琛尧采纳,获得10
43秒前
安安的小板栗完成签到,获得积分10
46秒前
123_完成签到,获得积分10
48秒前
NexusExplorer应助大橙子采纳,获得10
49秒前
上善若水完成签到 ,获得积分10
51秒前
qiqi发布了新的文献求助10
55秒前
55秒前
英俊的铭应助cm采纳,获得10
56秒前
57秒前
量子星尘发布了新的文献求助10
57秒前
affy210310完成签到,获得积分10
58秒前
名字不好起完成签到,获得积分10
58秒前
高分求助中
【提示信息,请勿应助】关于scihub 10000
Les Mantodea de Guyane: Insecta, Polyneoptera [The Mantids of French Guiana] 3000
徐淮辽南地区新元古代叠层石及生物地层 3000
The Mother of All Tableaux: Order, Equivalence, and Geometry in the Large-scale Structure of Optimality Theory 3000
Handbook of Industrial Diamonds.Vol2 1100
Global Eyelash Assessment scale (GEA) 1000
Picture Books with Same-sex Parented Families: Unintentional Censorship 550
热门求助领域 (近24小时)
化学 材料科学 医学 生物 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 冶金 细胞生物学 免疫学
热门帖子
关注 科研通微信公众号,转发送积分 4038157
求助须知:如何正确求助?哪些是违规求助? 3575869
关于积分的说明 11373842
捐赠科研通 3305650
什么是DOI,文献DOI怎么找? 1819255
邀请新用户注册赠送积分活动 892655
科研通“疑难数据库(出版商)”最低求助积分说明 815022