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

There is aDFT 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 wemust 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 isde 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?

• 1
  $\begingroup$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).$\endgroup$

  user2533488

  – user2533488

  2024-07-01 22:44:35 +00:00

  CommentedJul 1, 2024 at 22:44
• 1
  $\begingroup$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.$\endgroup$

  user2533488

  – user2533488

  2024-07-01 22:53:57 +00:00

  CommentedJul 1, 2024 at 22:53
• $\begingroup$@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.$\endgroup$

  Jackson Walters

  – Jackson Walters

  2024-07-02 23:05:51 +00:00

  CommentedJul 2, 2024 at 23:05
• $\begingroup$@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.$\endgroup$

  Jackson Walters

  – Jackson Walters

  2024-07-02 23:15:30 +00:00

  CommentedJul 2, 2024 at 23:15

1 Answer1

Start asking to get answers

Find the answer to your question by asking.

Explore related questions

See similar questions with these tags.