Distillation protocols for Fourier states in quantum computing

Fourier states are multi-qubit registers that facilitate phase rotations in fault-tolerant quantum computing. We propose distillation protocols for constructing the fundamental, n-qubit Fourier state with error O(2⁻ⁿ) at a cost of O(n log n) Toffoli gates and Clifford gates, or any arbitrary Fourier state using O(n²) gates. We analyze these protocols with methods from digital signal processing. These results suggest that phase kickback, which uses Fourier states, could be the current lowest-overhead method for generating arbitrary phase rotations.