Skip to content

QFT (Quantum Fourier Transform)

The standard H + controlled-phase cascade plus trailing qubit-order swap, returned as a gate-tuple list. Verified against the brute-force analytic DFT matrix (max error 1.4e-15 across 1-4 qubits) and a QFT-then-inverse-QFT round trip.

qft

Quantum Fourier Transform circuit builder -- the textbook cascade of H and controlled-phase gates, plus the trailing qubit-order swap, returned as a gate-tuple list ready for run_circuit. A standard building block (phase estimation, Shor's algorithm, arithmetic circuits) that every general- purpose SDK ships (Qiskit's QFT, Cirq's cirq.QuantumFourierTransformGate).

qft 

qft(n_qubits, inverse=False, do_swaps=True)

Build the Quantum Fourier Transform circuit on n_qubits.

Parameters

n_qubits : int Number of qubits, must be >= 1. inverse : bool Build the inverse QFT instead (same gate set, reversed order, negated phase angles). do_swaps : bool Include the trailing qubit-reversal swaps that put the output in the same qubit order as the input. The H/CP cascade alone produces the Fourier-transformed amplitudes in bit-reversed qubit order; set this to False only if the caller will account for that reversal itself (e.g. chaining straight into another subroutine that expects it).

Returns

list[tuple]

Examples

import dense_evolution as de sim = de.DenseSVSimulator(3) sim.run_circuit(de.qft(3)) sim.get_probabilities() # uniform: QFT|000> = equal superposition

Source code in dense_evolution/qft.py 
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
57
58
59
60
61
62
63
64
65
66
def qft(n_qubits, inverse=False, do_swaps=True):
    """
    Build the Quantum Fourier Transform circuit on n_qubits.

    Parameters
    ----------
    n_qubits : int
        Number of qubits, must be >= 1.
    inverse : bool
        Build the inverse QFT instead (same gate set, reversed order,
        negated phase angles).
    do_swaps : bool
        Include the trailing qubit-reversal swaps that put the output in
        the same qubit order as the input. The H/CP cascade alone
        produces the Fourier-transformed amplitudes in bit-reversed
        qubit order; set this to False only if the caller will account
        for that reversal itself (e.g. chaining straight into another
        subroutine that expects it).

    Returns
    -------
    list[tuple]

    Examples
    --------
    >>> import dense_evolution as de
    >>> sim = de.DenseSVSimulator(3)
    >>> sim.run_circuit(de.qft(3))
    >>> sim.get_probabilities()  # uniform: QFT|000> = equal superposition
    """
    if n_qubits < 1:
        raise ValueError(f"qft needs at least 1 qubit, got {n_qubits}")

    ops = []
    for j in range(n_qubits):
        ops.append(('h', j))
        for k in range(j + 1, n_qubits):
            angle = np.pi / (2 ** (k - j))
            ops.append(('cp', k, j, angle))
    if do_swaps:
        for i in range(n_qubits // 2):
            ops.append(('swap', i, n_qubits - 1 - i))

    if inverse:
        ops = [_invert_op(op) for op in reversed(ops)]
    return ops