openfermion.circuits.ffft

View source on GitHub

Performs fast fermionic Fourier transform.

openfermion.circuits.ffft(
    qubits: Sequence[cirq.Qid]
) -> cirq.OP_TREE

Generates a circuit that performs fast fermionic Fourier transform (FFFT) which transforms a set of fermionic creation operators \(\hat{a}_n^\dagger\), \(n \in 1, 2, \dots, N\) according to:

\[ \mathit{FFFT}^\dagger \tilde{a}_k^\dagger \mathit{FFFT} = {1 \over \sqrt{N} } \sum_{n=0}^{N-1} e^{-i {2\pi \over N} n k} \hat{a}^\dagger_n \, , \]

where \(\tilde{a}_k^\dagger\) are transformed operators and \(N\) is size of the input qubits sequence.

This function assumes JWT representation of fermionic modes which are big-endian encoded on consecutive qubits: \(a_0^\dagger \lvert 0.. \rangle = \lvert 1.. \rangle\), \(a_1^\dagger \lvert 0.. \rangle = \vert 01.. \rangle\), \(a_2^\dagger \lvert 0.. \rangle = \vert 001.. \rangle\), \(\dots\).

The gate count of generated circuit is \(\theta(N^2)\), generated circuit depth is \(\theta(N)\) and distinct gates count is \(\theta(N_1^2 + N_2^2 + \dots + N_n^2)\), where \(N = N_1 N_2 \dots N_n\) is prime decomposition of \(N\). In a case where \(N\) is some power of 2, it reduces to \(\theta(\log(N))\).

An equivalent circuit can be generated using the openfermion.bogoliubov_transform function with appropriately prepared transformation_matrix argument:

.. testcode::

import openfermion
import numpy as np

def ffft(qubits):
    def fourier_transform_matrix(size):
        root_of_unity = np.exp(-2j * np.pi / size)
        return np.array([[root_of_unity ** (k * n) for n in range(size)]
                         for k in range(size)]) / np.sqrt(size)

    return openfermion.bogoliubov_transform(
        qubits, fourier_transform_matrix(len(qubits)))

The advantage of circuit generated by the FFFT algorithm over the one created with the bogoliubov_transform is that a smaller variety of gates is created, which is \(O(N^2)\) in case of pure bogoliubov_transform. This implementation of FFFT fall-backs to the bogoliubov_transform for the inputs where qubits length is prime.

This implementation of FFFT is based on a generalized, composite size Cooley-Tukey algorithm and adapted to nearest neighbourhood connectivity.