openfermion.circuits.ffft

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.

qubits Sequence of qubits that the FFFT circuit will be generated for. This sequence represents a sequence of consecutive creation operators under big-endian encoded JWT representation. The indices assignment is significant since it used to define the FFFT operation itself. The input sequence is assumed to have nearest neighbourhood connectivity.

Circuit that performs FFFT on given qubits.

ValueError When length of the input array is not a power of 2.