Approximate QFT

Controlled-phase rotations of pi/2^k with large k barely change anything but cost a lot on hardware. The approximate QFT drops them. Build a QFT with a dial for how far apart two qubits can be and still interact.

Objective

build_qft_circuit(num_qubits, max_distance) returns the QFT (|x> -> (1/sqrt(N)) sum_y e^(2 pi i x y / N) |y>, including the final qubit reversal), keeping a controlled phase between qubits j and k only if |j - k| <= max_distance. With max_distance = num_qubits - 1 it must be the exact QFT.

Constraints

• No library QFT / QFTGate.

Entry Point

Checks

• Exports build_qft_circuit(num_qubits, max_distance).
• max_distance = n - 1 equals the exact DFT matrix for 1 to 4 qubits.
• Approximate variants drop exactly the long-range rotations.