> ## Documentation Index
> Fetch the complete documentation index at: https://b01t.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Quantum Fourier Transform: QFT and Inverse QFT

> Use b01t's QFT and inverse QFT as certified @parametric building blocks for phase estimation, Shor's algorithm, and any frequency-domain quantum routine.

The Quantum Fourier Transform (QFT) is the quantum analogue of the discrete Fourier transform. It maps computational basis states to the Fourier basis: `QFT|j⟩ = (1/√2^n) Σ_k exp(2πijk/2^n)|k⟩`. In practice you use the QFT — almost always its inverse — to read out a phase from a quantum register. It is the final step in Quantum Phase Estimation, and it appears in Shor's order-finding circuit and in any algorithm that encodes information in the eigenvalue of a unitary.

## Imports

```python theme={null}
from b01t.zoo.qft import qft, inverse_qft
```

Both functions are `@parametric` because they use continuous rotation gates (`CRZ`, `Rz`). This means you can call them from inside other `@parametric` or `@adaptive` functions, but not from `@coherent` bodies (which require exact/permutation gates only).

## `qft`

```python theme={null}
qft(reg: QReg)
```

Applies the Quantum Fourier Transform to the register `reg` in-place. Processes qubits from LSB to MSB without a final bit-reversal swap. This ordering matches the QPE convention, where `counting[k]` controls `U^{2^k}`, so the inverse QFT can decode the phase directly without additional permutations.

**Gate decomposition:** For each qubit `j`, applies `H(reg[j])` followed by controlled-phase gates `CP(π/2^(k−j))` from qubit `k` to qubit `j`, for all `k > j`. Each `CP(θ)` is decomposed as `CRZ(θ, ctrl, tgt)` followed by `Rz(θ/2, ctrl)`.

## `inverse_qft`

```python theme={null}
inverse_qft(reg: QReg)
```

Applies the inverse QFT — the adjoint of `qft` — to the register `reg` in-place. Use this at the end of a QPE circuit to convert phase information in the counting register into a readable binary value.

## Building a circuit with QFT

<Steps>
  <Step title="Import and define a register">
    ```python theme={null}
    from b01t import QReg, parametric, h
    from b01t.zoo.qft import qft, inverse_qft
    ```
  </Step>

  <Step title="Apply the QFT inside a @parametric function">
    ```python theme={null}
    @parametric
    def prepare_fourier_basis(reg: QReg):
        """Put each qubit in superposition then apply QFT."""
        for q in reg:
            h(q)
        qft(reg)
    ```
  </Step>

  <Step title="Build and compile to Qiskit">
    ```python theme={null}
    from b01t import QiskitBackend

    prog = prepare_fourier_basis.build(("reg", 4))
    qc = QiskitBackend().emit(prog)
    print(qc.draw())
    ```
  </Step>
</Steps>

## Using inverse\_qft in a QPE circuit

The most common use of `inverse_qft` is as the final step of Quantum Phase Estimation. b01t's `zoo.qpe` module wraps this pattern for you, but you can also build it directly:

```python theme={null}
from b01t import QReg, parametric, h
from b01t.zoo.qft import inverse_qft


def my_controlled_unitary(counting: QReg, work: QReg):
    """Apply controlled-U^(2^k) for each counting bit k."""
    ...


@parametric
def qpe(counting: QReg, work: QReg):
    # Step 1: uniform superposition on counting register
    for i in range(len(counting)):
        h(counting[i])

    # Step 2: controlled unitaries (your implementation)
    my_controlled_unitary(counting, work)

    # Step 3: inverse QFT decodes the phase into the counting register
    inverse_qft(counting)
```

Or use `make_qpe` from `zoo.qpe` directly:

```python theme={null}
from b01t.zoo.qpe import make_qpe

qpe = make_qpe(my_controlled_unitary)
# qpe(counting, work) does all three steps automatically
```

## Round-trip example

You can verify that `inverse_qft(qft(reg))` is the identity by building the round-trip circuit and checking the qubit count:

```python theme={null}
from b01t import QReg, parametric
from b01t.zoo.qft import qft, inverse_qft
from b01t import QiskitBackend

@parametric
def roundtrip(reg: QReg):
    qft(reg)
    inverse_qft(reg)

prog = roundtrip.build(("reg", 3))
qc = QiskitBackend().emit(prog)
print(f"Qubits: {qc.num_qubits}, Gates: {qc.size()}")
```

<Note>
  The b01t QFT does not include bit-reversal swaps. This is deliberate: it matches the QPE convention where `counting[k]` controls `U^{2^k}`. If you need the standard DFT bit ordering for a different application, you will need to add the swap layer manually.
</Note>

<Tip>
  Gate count for the QFT on `n` qubits is `n + n*(n-1)/2` two-qubit gates, which grows as O(n²). For large registers this can be significant — consider approximate QFT (truncating small rotation angles) if circuit depth is a constraint.
</Tip>