Open Access

ARTICLE

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

Xuwei Tang¹, Juan Xu^1,2,3,*, Bojia Duan¹

1 College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China.
2 Institute for Quantum Computing, University of Waterloo, Canada.
3 Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, China.

* Corresponding Author: Juan Xu. Email: .

Computers, Materials & Continua 2018, 57(2), 307-319. https://doi.org/10.32604/cmc.2018.03693

Abstract

Grover's search algorithm is one of the most significant quantum algorithms, which can obtain quadratic speedup of the extensive search problems. Since 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 performance. When simulating the Grover's algorithm, the storage space required is exponential, which makes it difficult to simulate the high-qubit Grover's algorithm. To this end, we deeply study the storage problem of probability amplitude, which is the core of the Grover simulation algorithm. We propose a novel memory-efficient method via amplitudes compression, and validate the effectiveness of the method by theoretical analysis and simulation experimentation. The results demonstrate that our compressed simulation search algorithm can help to save nearly 87.5% of the storage space than the uncompressed one. Thus 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 one. Particularly, our memory-efficient simulation method can also be used to simulate other quantum algorithms to effectively reduce the storage costs required in simulation.

---

Keywords

---