Quantum Fourier Transform#

The Quantum Fourier Transform (QFT) is the MPS equivalent of the Fast Fourier Transform (FFT). It transforms vectors in a space of dimension \(2^n\) according to:

\[\mathbf{e}_{i} \xrightarrow{\mathcal{F}} \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} e^{-i 2 \pi ij / 2^n} \mathbf{e}_j\]

In SeeMPS, the Fourier transform is implemented as a sequence of unitary transformations \(\mathcal{F} = F_n F_{n-1} \cdots F_1\) that mimic layers of a quantum Fourier transform circuit acting on \(n\) qubits, up to the final qubit swap.

Implementation#

The algorithm assumes that the Fourier transform acts on an MPS composed of \(n\) two-dimensional objects (qubits). The total algorithm is encoded as an MPOList with \(n\) MPOs implementing Hadamard gates and conditional rotations, with exact tensors of small bond dimension.

Specifically, for the \(i\)-th layer:

  • Sites \(n < i\) have identity tensors

  • Site \(i\) has a Hadamard gate with control output

  • Sites \(j > i\) have conditional rotation gates \(\exp(i 2\pi / 2^{j-i})\)

Bond dimension preservation#

An important property of the QFT in the MPS formalism is that it does not significantly increase the bond dimension of the state. This was first reported for discrete encodings of bandwidth-limited functions and later confirmed in more general scenarios. This property enables efficient use of Fourier-based techniques for:

Qubit reversal#

The QFT circuit produces output qubits in reversed order compared to the standard FFT convention. The function qft_flip() implements the qubit reversal that makes qft_flip(qft(f)) equivalent to the FFT of the vector version of f. However, this operation can be costly in the MPS representation, so it is often avoided when possible.

Negative frequencies in the output are placed in the upper part of the quantum register, following the two’s complement notation.

Multidimensional transforms#

For multidimensional functions encoded as MPS, SeeMPS provides partial transforms that act on subsets of qubits. The functions qft_nd_mpo() and iqft_nd_mpo() create transforms for specified qubit indices, enabling efficient multidimensional Fourier analysis.

qft(-> MPS)

Apply the quantum Fourier transform onto a quantum register of qubits encoded in the matrix-product 'state'.

iqft(-> MPS)

Apply the inverse quantum Fourier transform onto a quantum register of qubits encoded in the matrix-product 'state'.

qft_mpo(N[, sign, strategy])

Create an MPOList object representing a Quantum Fourier Transform for a quantum register with N qubits.

iqft_mpo(N[, strategy])

MPOList implementing the inverse quantum Fourier transform.

qft_nd_mpo(sites[, N, sign, strategy])

Create an MPOList object representing a Quantum Fourier Transform for subset of qubits in a quantum register with N qubits.

iqft_nd_mpo(sites[, N, strategy])

Create an MPOList object representing the inverse Quantum Fourier Transform for subset of qubits in a quantum register with N qubits.

qft_flip(state)

Swap the qubits in the quantum register, to fix the reversal suffered during the quantum Fourier transform.

See also#