# Quantum Fourier Transform (QFT)¶

## Overview¶

The quantum Fourier transform is the quantum implementation of the discrete Fourier transform over the amplitudes of a wavefunction. Detailed explanations can be found in references [1] and [2]. The QFT forms the basis of many quantum algorithms such as Shor’s factoring algorithm, discrete logarithm, and others to be found in the quantum algorithms zoo [3].

## Source Code Docs¶

Here you can find documentation for the different submodules in qft.

### grove.qft.fourier¶

grove.qft.fourier.bit_reversal(qubits)

Generate a circuit to do bit reversal.

Parameters: qubits – Qubits to do bit reversal with. A program to do bit reversal.
grove.qft.fourier.inverse_qft(qubits)

Generate a program to compute the inverse quantum Fourier transform on a set of qubits.

Parameters: qubits – A list of qubit indexes. A Quil program to compute the inverse Fourier transform of the qubits.
grove.qft.fourier.qft(qubits)

Generate a program to compute the quantum Fourier transform on a set of qubits.

Parameters: qubits – A list of qubit indexes. A Quil program to compute the Fourier transform of the qubits.

References

 [1] Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010.
 [2] Rieffel, E. G., and W. Polak. “A Gentle Introduction to Quantum Computing.” (2011).