Quantum algorithms: entanglement-enhanced information processing

We discuss the fundamental role of entanglement as the essential non-classical feature providing the computational speed-up in the known quantum algorithms. We review the construction of the Fourier transform on an Abelian group and the principles underlying the fast Fourier transform (FFT) algorith...