# Defining the QFT over finite fields

The DFT is well-developed over $$\mathbb{C}$$ with fast quantum algorithms.

There is a DFT defined classically over $$F_q$$ which mirrors the complex case when we have an $$N^{th}$$ root of unity in $$F_q$$, i.e. $$N|q-1$$.

In a sense, I suppose we must work over $$\mathbb{C}$$ on quantum computers, since the amplitudes are naturally complex. Nevertheless, we can write $$x \in F_q$$ as $$|x\rangle \in \mathcal{H}$$ where we use $$\lfloor \log_2 q \rfloor + 1$$ qubits.

The only definition I could find is de Beaudrap, Cleve, and Watrous, $$\S 2.1$$:

Let $$\phi : GF(q) \rightarrow GF(p)$$ be any nonzero linear mapping. The QFT with respect to $$\phi$$ is

$$F_{q,\phi}: |x \rangle \mapsto \frac{1}{\sqrt{q}} \sum_{y \in GF(q)} \omega^{\phi(xy)}|y \rangle$$

for $$\omega = e^{2 \pi i / p}$$ and extend $$F_{q,\phi}$$ by linearity.

Is this the only definition of a QFT over a finite field?

• I think this is a sort of the point you make in the 3rd paragraph, but if you are interested in a QFT, I don't think a FT over Fq is what you are interested in (i.e. considering Fq-valued functions on some group). But rather, a FT on Fq (i.e. C-valued functions on Fq). Here are sources: sites.math.rutgers.edu/~sk1233/courses/finitefields-F13/… (pp. 5) people.cs.uchicago.edu/~laci/reu02/fourier.pdf (pp. 16). Basically, the additive and multiplicative groups of Fq are considered in tandem. The QFT in question seems to only consider the additive part (see 1st source). Commented Jul 1 at 22:44
• I guess what I said about FT over Fq/FT on Fq can be nitpicking because the terms seem to be interchanged in the literature, but my point was that studying a "QFT over Fq" should be concerned with replacing groups with a finite field, rather than replacing the field C with a different ring. Basically, the Wikipedia article is a different concept. Commented Jul 1 at 22:53
• @user2533488 I really am interested in $F_q$-valued functions on discrete groups, namely the cyclic and symmetric group. The thing is, there are well-defined notions of the DFT over $F_q$ (so, expressing an $F_q$-valued function on $C_n$ or $S_n$ in a frequency basis or basis of matrix coefficients of representations). One can even consider the case where $p|n$ or $p|n!$ (the modular rep'n theory case), so we're looking at the module decomposition of $F_q[C_n]$ or $F_q[S_n]$. That's what I'm aiming to bring to the quantum setting. Commented Jul 2 at 23:05
• @user2533488 To your point, it's a little concerning that the basis vectors are $|y \rangle$ where $y \in F_q$. In the usual DFT the basis vectors are $|x \rangle$ where $x \in \mathbb{Z}/N\mathbb{Z}$, i.e. they are indexed by the group. Commented Jul 2 at 23:15

• Right, this is the canonical one for the cyclic group. In the linked paper in the question they do point out the trace is a reasonable choice for the linear map. I guess there are also things like coordinate projections if you choose a basis for $F_q$ over $F_p$. It'd be cool if there was one for the symmetric group. Commented Jul 2 at 23:09