Precise relationship between classical and quantum Fourier transform for a finite abelian group $\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ket}[1]{|#1\rangle}
\newcommand{\bra}[1]{\langle#1|}$
I asked this question on the quantum computing SE site a few weeks ago, but got no responses, so I thought I might try posting it here.
I am trying to figure out the precise relationship (if any) between the quantum Fourier transform for finite abelian groups and the classical Fourier transform for those groups. Here is my attempt so far…
Suppose $G$ is a finite abelian group. We know $G\cong\Z/n_1\Z\times\dots\times\Z/n_r\Z$ For some positive integers $n_1,\dots,n_r$, so I write the irreducible characters of $G$ as
$$
\chi_x(g) = \prod_{j=1}^r\exp(2\pi i x_j g_j/n_j)
$$
where $x=(x_1,\dots,x_r)\in G$ with each $x_i\in \Z/n_i\Z$, and likewise for $g\in G$.
The text I am using defines the Fourier transform of a function $f:G\to \C$ as the function $\widehat f:\widehat G \to \C$ such that
$$
\widehat f(\chi) = \langle f,\chi\rangle = \frac{1}{|G|}\sum_{g\in G}f(g)\overline{\chi(g)}.
$$
Meanwhile I see the QFT for a finite abelian group defined as the linear transformation $F_G$ such that
$$
F_G\ket g = \frac{1}{\sqrt{|G|}}\sum_{x\in G}\chi_x(g)\ket x.
$$
Now, the classical Fourier transform is not applied to group elements but rather to maps $G\to\C$. It makes sense to think of a state like $\ket g$ (to which the QFT may be applied) as encoding the function on $G$ that is $1$ at $g$ and $0$ elsewhere. To draw a parallel between these two transforms, I thus considered applying the classical transform to the function $\delta_g:G\to \C$ that is $1$ at $g$ and $0$ elsewhere. As far as I can tell, then, the relationship between the classical and QFT for $G$ is
\begin{align*}
\bra x F_G\ket g &= \frac{1}{\sqrt{|G|}}\chi_x(g)\\ 
&= \sqrt{|G|}\overline{\left(\frac{1}{|G|}\overline{\chi_x(g)}\right)} \\
&= \sqrt{|G|} \left(\overline{\widehat\delta_g(\chi_x)}\right).
\end{align*}
So the equation I got above is very nearly what I'd expect: ignoring the normalization factor, it almost says that the $\ket x$th entry of $F_G\ket g$ is equal to $\widehat \delta_g(\chi_x)$, except there is a conjugate there.
The fact that we get this conjugate seemed a little odd to me, and I was wondering whether this is an indication that there is some error or inconsistency in my reasoning (or incompatibility between my definitions), or if it is just “the way things work.” Alternatively, is there any more direct way of relating the QFT to the ordinary Fourier transform for a finite abelian group?
 A: The original motivation for Fourier analysis is decomposing functions into combinations of pure harmonics, waves, characters, irreps, or whatever you want to call the constituent pieces. So for a function $f:G\to\mathbb{C}$ (where $G$ is abelian), we expect we can write $f$ as a linear combination $\sum \hat{f}(\chi)\chi$, where each character $\chi$ has a coefficient $\widehat{f}(\chi)$. In other words, $f(g)=\sum_{\chi\in\widehat{G}}\widehat{f}(\chi)\chi(g)$ for all $g\in G$, and we can think of the coefficients $\hat{f}$ as a function $\widehat{f}:\widehat{G}\to\mathbb{C}$.
At this point, let's say we choose an identification $G\cong\mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_k}$ and use it to also create an identification with $\widehat{G}\cong\mathbb{Z}_{n_1}\times\cdots\times\mathbb{Z}_{n_k}$ where we have the formula $\chi_x(g)=\exp(2\pi i \sum x_jg_j/n_j)$, as you've mentioned. This yields $\chi_x(g)=\chi_g(x)$ for any $x,g\in G$.
If we write $f$ as a linear combination of $\chi$s as in the aforementioned way, we have
$$ f(g)=\sum_{x\in G}\widehat{f}(x)\chi_x(g), \quad \widehat{f}(x)=\frac{1}{|G|}\sum_{g\in G}f(g)\overline{\chi_x(g)}. $$
However, if we use a different normalization to define the $\widehat{f}(\chi)$s, we can say
$$ f(g)=\frac{1}{\sqrt{|G|}}\sum_{x\in G}\widehat{f}(x)\chi_x(g), \quad \widehat{f}(x)=\frac{1}{\sqrt{|G|}}\sum_{g\in G}f(g)\overline{\chi_x(g)}. $$
We will use this normalization. It's useful because then the act of taking the Fourier transform is a unitary transformation on the inner product space of functions $G\to\mathbb{C}$, and then as a linear operator it has order four. As you've defined it, we have a linear operator $F$ given by
$$ F=\frac{1}{\sqrt{|G|}}\sum_{x,g}\chi_x(g)|x\rangle\langle g|. $$
If we write a function as $|f\rangle=\sum_{g\in G}f(g)|g\rangle$, we may compute $F|\widehat{f}\rangle$ as
$$ \begin{array}{lll}
F|\widehat{f}\rangle & = & \displaystyle
 \frac{1}{\sqrt{|G|}}\left(\sum_{x,g,}\chi_x(g)|x\rangle\langle g|\right)\left(\sum_{h\in G}\widehat{f}(h)|h\rangle\right) \\
& = & \displaystyle
 \frac{1}{\sqrt{|G|}}\sum_{x,g}\chi_x(g)\widehat{f}(g)|x\rangle \\
& = & \displaystyle
 \frac{1}{\sqrt{|G|}}\sum_x\left(\sum_g\widehat{f}(g)\chi_g(x)\right)|x\rangle \\
& = & \displaystyle
 \frac{1}{\sqrt{|G|}}\sum_x f(x)|x\rangle \\
& = & \displaystyle = |f\rangle.
\end{array} $$
Interpret $F|\widehat{f}\rangle=|f\rangle$ as saying $F$ is the inverse Fourier transform. As the Wikipedia page for the QFT puts it: "the quantum Fourier transform has the same effect as the inverse discrete Fourier transform" (under this convention).
