import cmath
import math


def qft(mem):
    """Apply quantum Fourier transform to the first t qubits."""
    new_amplitudes = []
    N = 2**mem.t

    # Calculate root of unity in two steps, as complex exponentiation is
    # expensive.
    w__ = cmath.exp(2 * math.pi * 1j / N)

    for k, _ in enumerate(mem):
        s = 0
        for j in range(N):
            wjk = w__**(j * k)
            s += wjk * mem.amplitudes[j]
        new_amplitudes.append(s / math.sqrt(N))
    mem.amplitudes = new_amplitudes
    return mem