"""
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`).
"""
import numpy as np

__all__ = ['qft']


def _invert_op(op):
    """H and SWAP are self-inverse; CP(theta)^-1 = CP(-theta)."""
    if op[0] == 'cp':
        gate, ctrl, tgt, angle = op
        return (gate, ctrl, tgt, -angle)
    return op


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