A Memory-efficient Simulation Method of Grover’s Search Algorithm

作     者：Xuwei Tang Juan Xu Bojia Duan 

作者机构：College of Computer Science and TechnologyNanjing University of Aeronautics and AstronauticsNanjingChina Institute for Quantum ComputingUniversity of WaterlooCanada Key Laboratory of Computer Network and Information Integration(Southeast University)Ministry of EducationChina 

出 版 物：《Computers, Materials & Continua》 (计算机、材料和连续体（英文）)

年 卷 期：2018年第57卷第11期

页      面：307-319页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work was supported by Funding of National Natural Science Foundation of China(Grant No.61571226 Grant No.61701229) 

主　　题：Grover’s search algorithm probability amplitude quantum simulation memory compression 

摘      要：Grover’s search algorithm is one of the most significant quantum algorithms,which can obtain quadratic speedup of the extensive search *** Grover s search algorithm cannot be implemented on a real quantum computer at present,its quantum simulation is regarded as an effective method to study the search *** simulating the Grover s algorithm,the storage space required is exponential,which makes it difficult to simulate the high-qubit Grover’s *** this end,we deeply study the storage problem of probability amplitude,which is the core of the Grover simulation *** propose a novel memory-efficient method via amplitudes compression,and validate the effectiveness of the method by theoretical analysis and simulation *** results demonstrate that our compressed simulation search algorithm can help to save nearly 87.5%of the storage space than the uncompressed *** under the same hardware conditions,our method can dramatically reduce the required computing nodes,and at the same time,it can simulate at least 3 qubits more than the uncompressed ***,our memory-efficient simulation method can also be used to simulate other quantum algorithms to effectively reduce the storage costs required in simulation.