QUANTUM ALGORITHMS - ENTANGLEMENT-ENHANCED INFORMATION-PROCESSING

We discuss the fundamental role of entanglement as the essential non-c lassical feature providing the computational speed-up in the known qua ntum algorithms. We review the construction of the Fourier transform o n an Abelian group and the principles underlying the fast Fourier tran sform (FFT) algorithm. We describe the implementation of the FFT algor ithm for the group of integers module 2(n) in the quantum context, sho wing how the group-theoretic formalism leads to the standard quantum n etwork, and identify the property of entanglement that gives rise to t he exponential speed-up (compared to the classical FFT). Finally, we o utline the use of the Fourier transform in extracting periodicities, w hich underlies its utility in the known quantum algorithms.