Performs fast fermionic Fourier transform.
View aliases
Main aliases
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 ˆa†n, n∈1,2,…,N according to:
FFFT†˜a†kFFFT=1√NN−1∑n=0e−i2πNnkˆa†n,
where ˜a†k 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|0..⟩=|1..⟩, a†1|0..⟩=|01..⟩, a†2|0..⟩=|001..⟩, ….
The gate count of generated circuit is θ(N2), generated circuit depth is θ(N) and distinct gates count is θ(N21+N22+⋯+N2n), where N=N1N2…Nn is prime decomposition of N. In a case where N is some power of 2, it reduces to θ(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(N2) 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.
Returns | |
---|---|
Circuit that performs FFFT on given qubits. |