World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

COPING WITH DECOHERENCE: PARALLELIZING THE QUANTUM FOURIER TRANSFORM

    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

    • S. G. Akl, International Journal of High Performance Computing and Networking 4(1/2), 85 (2006). CrossrefGoogle Scholar
    • S. G.   Akl , Parallel Computing: Models, Algorithms, and Applications , eds. Sanguthevar   Rajasekaran and John H.   Reif ( CRC Press , 2006 ) . Google Scholar
    • S. G. Akl, B. Cordy and W. Yao, International Journal of Parallel, Emergent and Distributed Systems 20(2), 147 (2005), DOI: 10.1080/17445760500033432. Crossref, ISIGoogle Scholar
    • A. Berthiaume, Complexity Theory Retrospective II, eds. Lane A. Hemaspaandra and Alan L. Selman (Springer-Verlag, New York, 1997) pp. 23–51. CrossrefGoogle Scholar
    • C.   Cohen-Tannoudji , B.   Diu and F.   Laloe , Quantum Mechanics   1 and 2 ( Wiley , New York , 1977 ) . Google Scholar
    • T. H.   Cormen et al. , Introduction to Algorithms ( MIT Press , Cambridge, Massachusetts , 2001 ) . Google Scholar
    • R. Griffiths and C.-S. Niu, Physical Review Letters 76, 3228 (1996), DOI: 10.1103/PhysRevLett.76.3228. Crossref, ISIGoogle Scholar
    • M.   Hirvensalo , Quantum Computing ( Springer-Verlag , 2001 ) . CrossrefGoogle 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
    • M. Nagy, S. G. Akl and S. Kershaw, International Journal of Security and Its Applications 3(4), 45 (2009). ISIGoogle Scholar
    • M. Nagy and S. G. Akl, International Journal of Unconventional Computing 2(1), 73 (2006). ISIGoogle Scholar
    • M. A.   Nielsen and I. L.   Chuang , Quantum Computation and Quantum Information ( Cambridge University Press , 2000 ) . Google Scholar
    • E. Rieffel and W. Polak, ACM Computing Surveys 32(3), 300 (2000), DOI: 10.1145/367701.367709. Crossref, ISIGoogle Scholar
    • P. W. Shor, Special issue on Quantum Computation of the SIAM Journal on Computing 26(5), 1484 (1997). Crossref, ISIGoogle Scholar