4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented Jul 1 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
    Commented Jul 1 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
    Commented Jul 2 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
    Commented Jul 2 at 23:15

1 Answer 1

Reset to default
2
+50
$\begingroup$

I would think so. The canonical one in the Galois-qudit Clifford group is for phi being the field trace.

enter image description here

https://errorcorrectionzoo.org/c/galois_into_galois#citation-1

https://arxiv.org/pdf/quant-ph/0211014

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jackson Walters
    Commented Jul 2 at 23:09
  • 2
    $\begingroup$ I'm not aware of anything for S_n other than the special case of the non-Abelian FT over finite groups. $\endgroup$
    – Victor V Albert
    Commented Jul 3 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.