Parallel Simulation of Quantum Search

Authors

  • Simona Caraiman “Gheorghe Asachi” Technical University of Iasi Romania, 700050 Iasi, 27 Dimitrie Mangeron
  • Vasile Manta “Gheorghe Asachi” Technical University of Iasi Romania, 700050 Iasi, 27 Dimitrie Mangeron

Keywords:

quantum computer simulation, parallel computing, quantum search.

Abstract

Simulation of quantum computers using classical computers is a computationally hard problem, requiring a huge amount of operations and storage. Parallelization can alleviate this problem, allowing the simulation of more qubits at the same time or the same number of qubits to be simulated in less time. A promising approach is represented by executing these simulators in Grid systems that can provide access to high performance resources. In this paper we present a parallel implementation of the QC-lib quantum computer simulator deployed as a Grid service. Using a specific scheme for partitioning the terms describing quantum states and efficient parallelization of the general singe qubit operator and of the controlled operators, very good speed-ups were obtained for the simulation of the quantum search problem.

References

S. Caraiman, A. Archip, and V. Manta. A grid enabled quantum computer simulator. In Proc. of SYNASC'09. IEEE Computer Society, 2009. http://dx.doi.org/10.1109/synasc.2009.57

S. Caraiman and V. Manta. New applications of quantum algorithms to computer graphics: the Quantum Random Sample Consensus algorithm. In Proc. of ACM CF '09, pages 81-88, New York, NY, USA, 2009. ACM. http://dx.doi.org/10.1145/1531743.1531757

R. Feynman. Simulating physics with computers. Int. J. Theor. Phys., 21(6):467-488, 1982. http://dx.doi.org/10.1007/BF02650179

I. Foster, C. Kesselman, and S. Tuecke. The anatomy of the grid: Enabling scalable virtual organizations. Int. J. High Perform. Comput. Appl., 15(3):200-222, 2001. http://dx.doi.org/10.1177/109434200101500302

I. Glendinning and B. Omer. Parallelization of the QC-lib quantum computer simulator library. In Proc. of PPAM 2003, volume 3019 of LNCS, pages 461-468. Springer, 2004. http://dx.doi.org/10.1007/978-3-540-24669-5_60

L. Grover. A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM Annual STOC, pages 212-219, 1996. http://dx.doi.org/10.1145/237814.237866

J. Niwa, K. Matsumoto, and H. Imai. General-purpose parallel simulator for quantum computing. In Proc. of UMC '02, pages 230-251, London, UK, 2002. Springer-Verlag. http://dx.doi.org/10.1007/3-540-45833-6_20

B. Ömer. Simulation of quantum computers, 1996. http://tph.tuwien.ac.at/ oemer/doc/qcsim. ps.

B. Ömer. Structured Quantum Programming. PhD thesis, TU Vienna, 2003.

K. D. Raedt, K. Michielsen, H. D. Raedt, B. Trieuc, G. Arnoldc, M. Richterc, T. Lippertc, H. Watanabed, and N. Itoe. Massively parallel quantum computer simulator. Computer Physics Communications, 176(2):121-136, 2007. http://dx.doi.org/10.1016/j.cpc.2006.08.007

P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proc. of SFCS '94, pages 124-134. IEEE Computer Society, 1994. http://dx.doi.org/10.1109/sfcs.1994.365700

B. Sotomayor. The Globus Toolkit 4 programmer's tutorial, 2005. http://gdp.globus.org/gt4-tutorial/multiplehtml/index.html.

F. Tabakin and B. Juliá-Díaz. QcMpi: A parallel environment for quantum computing. Computer Physics Communications, 180(6):948-964, 2009. http://dx.doi.org/10.1016/j.cpc.2008.11.021

Published

2010-12-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.