Quantum multirow iteration algorithm for linear systems with nonsquare coefficient matrices

doi:10.1103/PhysRevA.110.022438

	Quantum multirow iteration algorithm for linear systems with nonsquare coefficient matrices
	Lin, Weitao 1; Tian, Guojing 1; Sun, Xiaoming 1
	2024-08-27
发表期刊	PHYSICAL REVIEW A
ISSN	2469-9926
卷号	110 期号:2 页码:14
摘要	In the field of quantum linear system algorithms, quantum computing has realized exponential computational advantages over classical computing. However, the focus has been on square coefficient matrices, with few quantum algorithms addressing nonsquare matrices. Towards this kind of problems defined by Ax = b where A E Rm`n, we propose a quantum algorithm inspired by the classical multirow iteration method and provide an explicit quantum circuit based on the quantum comparator and quantum random access memory. The time complexity of our quantum multirow iteration algorithm is O(K log2 m), with K representing the number of iteration steps, which demonstrates an exponential speedup compared to the classical version.. Based on the convergence of the classical multirow iteration algorithm, we prove that our quantum algorithm converges faster than the quantum one-row iteration algorithm presented by Shao and Xiang [C. Shao and H. Xiang, Phys. Rev. A 101, 022322 (2020)]. Moreover, our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems and quadratic optimization problems.
DOI	10.1103/PhysRevA.110.022438
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[62325210] ; National Natural Science Foundation of China[62272441] ; National Natural Science Foundation of China[12204489] ; National Natural Science Foundation of China[62301531] ; Strategic Priority Research Program of Chinese Academy of Sciences[XDB28000000]
WOS研究方向	Optics ; Physics
WOS类目	Optics ; Physics, Atomic, Molecular & Chemical
WOS记录号	WOS:001302457900004
出版者	AMER PHYSICAL SOC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/39494
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Lin, Weitao
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Lin, Weitao,Tian, Guojing,Sun, Xiaoming. Quantum multirow iteration algorithm for linear systems with nonsquare coefficient matrices[J]. PHYSICAL REVIEW A,2024,110(2):14.
APA	Lin, Weitao,Tian, Guojing,&Sun, Xiaoming.(2024).Quantum multirow iteration algorithm for linear systems with nonsquare coefficient matrices.PHYSICAL REVIEW A,110(2),14.
MLA	Lin, Weitao,et al."Quantum multirow iteration algorithm for linear systems with nonsquare coefficient matrices".PHYSICAL REVIEW A 110.2(2024):14.