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?

$\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$ Commented Jul 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$ Commented Jul 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$ Commented Jul 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$ Commented Jul 2, 2024 at 23:15

1 Answer 1

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

$\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$ Commented Jul 2, 2024 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$ Commented Jul 3, 2024 at 18:33

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.