COPING WITH DECOHERENCE: PARALLELIZING THE QUANTUM FOURIER TRANSFORM
Abstract
Rank-varying computational complexity describes those computations in which the complexity of executing each step is not a constant, but evolves throughout the computation as a function of the order of execution of each step [2]. This paper identifies practical instances of this computational paradigm in the procedures for computing the quantum Fourier transform and its inverse. It is shown herein that under the constraints imposed by quantum decoherence, only a parallel approach can guarantee a reliable solution or, alternatively, improve scalability.
This research was supported by the Natural Sciences and Engineering Research Council of Canada.
References
- International Journal of High Performance Computing and Networking 4(1/2), 85 (2006). Crossref, Google Scholar
- , Parallel Computing: Models, Algorithms, and Applications , eds.
Sanguthevar Rajasekaran and John H. Reif ( CRC Press , 2006 ) . Google Scholar - International Journal of Parallel, Emergent and Distributed Systems 20(2), 147 (2005), DOI: 10.1080/17445760500033432. Crossref, ISI, Google Scholar
- , Complexity Theory Retrospective II, eds.
Lane A. Hemaspaandra and Alan L. Selman (Springer-Verlag, New York, 1997) pp. 23–51. Crossref, Google Scholar -
C. Cohen-Tannoudji , B. Diu and F. Laloe , Quantum Mechanics 1 and 2 ( Wiley , New York , 1977 ) . Google Scholar -
T. H. Cormen , Introduction to Algorithms ( MIT Press , Cambridge, Massachusetts , 2001 ) . Google Scholar - Physical Review Letters 76, 3228 (1996), DOI: 10.1103/PhysRevLett.76.3228. Crossref, ISI, Google Scholar
-
M. Hirvensalo , Quantum Computing ( Springer-Verlag , 2001 ) . Crossref, Google Scholar -
S. J. Lomonaco Jr. (ed.) , Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium ,Proceedings of Symposia in Applied Mathematics 58 ( American Mathematical Society , Washington, DC , 2000 ) . Google Scholar - International Journal of Security and Its Applications 3(4), 45 (2009). ISI, Google Scholar
- International Journal of Unconventional Computing 2(1), 73 (2006). ISI, Google Scholar
-
M. A. Nielsen and I. L. Chuang , Quantum Computation and Quantum Information ( Cambridge University Press , 2000 ) . Google Scholar - ACM Computing Surveys 32(3), 300 (2000), DOI: 10.1145/367701.367709. Crossref, ISI, Google Scholar
- Special issue on Quantum Computation of the SIAM Journal on Computing 26(5), 1484 (1997). Crossref, ISI, Google Scholar


