Quantum QR decomposition in the computational basis

doi:10.1007/s11128-020-02777-4

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 系统科学研究所

	Quantum QR decomposition in the computational basis
	Ma, Guangsheng 1; Li, Hongbo 2; Zhao, Jiman 1
刊名	QUANTUM INFORMATION PROCESSING
	2020-07-29
卷号	19 期号:8 页码:16
关键词	Quantum algorithms Computational basis Quantum QR decomposition
ISSN号	1570-0755
DOI	10.1007/s11128-020-02777-4
英文摘要	In this paper, we propose a quantum algorithm for approximating the QR decomposition of any N x N matrix with a running time O(1/epsilon(2) N(2.5)polylog( N)), where epsilon is the desired precision. This quantum algorithm provides a polynomial speedup over the best classical algorithm, which has a running time O(N-3). Our quantum algorithm utilizes the quantum computation in the computational basis (QCCB) and a setting of updatable quantum memory. We further present a systematic approach to applying the QCCB to simulate any quantum algorithm. By this approach, the simulation time does not exceed O(N(2)polylog( N)) times the running time of the quantum algorithm originally designed with the amplitude encoding method, where N is the size of the problem.
资助项目	NSFC[11671388] ; National Key Research Program[2018YFA0704705] ; National Natural Science Foundation of China[11471040] ; National Natural Science Foundation of China[11761131002]
WOS研究方向	Physics
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000557536200002
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/51943]
专题	系统科学研究所
通讯作者	Zhao, Jiman
作者单位	1.Beijing Normal Univ, Key Lab Math & Complex Syst, Minist Educ, Sch Math Sci, Beijing 100875, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Ma, Guangsheng,Li, Hongbo,Zhao, Jiman. Quantum QR decomposition in the computational basis[J]. QUANTUM INFORMATION PROCESSING,2020,19(8):16.
APA	Ma, Guangsheng,Li, Hongbo,&Zhao, Jiman.(2020).Quantum QR decomposition in the computational basis.QUANTUM INFORMATION PROCESSING,19(8),16.
MLA	Ma, Guangsheng,et al."Quantum QR decomposition in the computational basis".QUANTUM INFORMATION PROCESSING 19.8(2020):16.