Skip to content

fourier

Generates a Fourier matrix.

fourier 

fourier(dim: int) -> ndarray

Generate the Fourier transform matrix 1.

Generates the dim-by-dim unitary matrix that implements the quantum Fourier transform.

The Fourier matrix is defined as:

\[ W_N = \frac{1}{\sqrt{N}} \begin{pmatrix} 1 & 1 & 1 & 1 & \ldots & 1 \\ 1 & \omega & \omega^2 & \omega^3 & \ldots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \omega^6 & \ldots & \omega^{2(N-1)} \\ 1 & \omega^3 & \omega^6 & \omega^9 & \ldots & \omega^{3(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \omega^{3(N-1)} & \ldots & \omega^{(N-1)(N-1)} \end{pmatrix} \]

Examples:

The Fourier matrix generated from \(d = 3\) yields the following matrix:

\[ W_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega^4 \end{pmatrix} \]
from toqito.matrices import fourier

print(fourier(3))

[[ 0.57735027+0.j 0.57735027+0.j 0.57735027+0.j ] [ 0.57735027+0.j -0.28867513+0.5j -0.28867513-0.5j] [ 0.57735027+0.j -0.28867513-0.5j -0.28867513+0.5j]]

Parameters:

  • dim (int) –

    The size of the Fourier matrix.

Returns:

  • ndarray –

    The Fourier matrix of dimension dim.

References

1 Wikipedia. {DFT} matrix. link.

Source code in toqito/matrices/fourier.py 
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def fourier(dim: int) -> np.ndarray:
    r"""Generate the Fourier transform matrix [@WikiDFT].

    Generates the `dim`-by-`dim` unitary matrix that implements the
    quantum Fourier transform.

    The Fourier matrix is defined as:

    \[
        W_N = \frac{1}{\sqrt{N}}
        \begin{pmatrix}
            1 & 1 & 1 & 1 & \ldots & 1 \\
            1 & \omega & \omega^2 & \omega^3 & \ldots & \omega^{N-1} \\
            1 & \omega^2 & \omega^4 & \omega^6 & \ldots & \omega^{2(N-1)} \\
            1 & \omega^3 & \omega^6 & \omega^9 & \ldots & \omega^{3(N-1)} \\
            \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
            1 & \omega^{N-1} & \omega^{2(N-1)} & \omega^{3(N-1)} &
            \ldots & \omega^{(N-1)(N-1)}
        \end{pmatrix}
    \]

    Examples:
        The Fourier matrix generated from \(d = 3\) yields the following matrix:

        \[
            W_3 = \frac{1}{\sqrt{3}}
            \begin{pmatrix}
                1 & 1 & 1 \\
                1 & \omega & \omega^2 \\
                1 & \omega^2 & \omega^4
            \end{pmatrix}
        \]

        ```python exec="1" source="above"
        from toqito.matrices import fourier

        print(fourier(3))
        ```

    Args:
        dim: The size of the Fourier matrix.

    Returns:
        The Fourier matrix of dimension `dim`.

    """
    # Primitive root of unity.
    root_unity = np.exp(2 * 1j * np.pi / dim)
    entry_1 = np.arange(0, dim)[:, None]
    entry_2 = np.arange(0, dim)
    return np.power(root_unity, entry_1 * entry_2) / np.sqrt(dim)