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. [ABSTRACT FROM AUTHOR]