I am reading Regev's proof of existence of quantum algorithm to sample from a discrete Gaussian distribution given a CVP oracle and I am confused about his calculation of the Quantum Fourier transform of a state $| s\rangle$, where $s\in\mathbb{Z}_R^n$. What he did was the QFT of $|s\rangle$ is proportional to $\displaystyle\sum_{t\in\mathbb{Z}_R^n}\exp(2\pi i\langle s,t\rangle / R)|t\rangle$. My question is why divide the exponential just by $R$ instead of dividing by the size of $\mathbb{Z}_R^n$, which is $R^n$? Also can anyone point me to a reference for the Quantum Fourier transform if our states are not typically represented in terms of the usual basis states, or any reference that Regev based his definition of QFT. Thanks!


1 Answer 1


In short, both would be possible, but this leads to very different Fourier transforms. Here, the Fourier transform is first defined on the ring $\mathbb Z_R$ as $$ \hat x(s) = \sum_{t\in\mathbb Z_R} \omega_R^{st}\, x(t), \quad s\in\mathbb Z_R, $$ for a complex function $x$ on $\mathbb Z_R$. For the Fourier transform, it is important, that $t\mapsto \omega_R^{st}$ defines a character of the additive group $\mathbb Z_R$. In turn, this implies that $\omega_R$ is a primitive $R$-th root of unity, w.l.o.g. $\omega_R = \exp(2\pi i/R)$. The mentioned Fourier transform on $\mathbb Z_R^n$ is then obtained by letting the above mapping act component-wise: $$ \hat X(s_1,\dots,s_n) := \sum_{t_1,\dots,t_N\in\mathbb Z_R} \omega_R^{s_1t_1}\cdots\omega_R^{s_nt_n} X(t_1,\dots,t_n) = \sum_{\mathbf{t}\in\mathbb Z_R^n} \omega_R^{\langle \mathbf s, \mathbf t\rangle} X(\mathbf t). $$

Alternatively, one can consider the ring $\mathbb Z_{R^n}$ which has the same cardinality as $\mathbb Z_R^n$, but is not isomorphic to it. With this choice, we can again define a Fourier transform using a $R^n$-th root of unity $\exp(2\pi i/R^n)$. This one is very different from the above defined Fourier transform.

Why do we have such a freedom of choice? Given a Hilbert space of dimension $d$, say $\mathbb C^d$, there are a bunch of different ways to look at it. For instance, if $d=R^n$, we can see $\mathbb C^{R^n}$ as the vector space of functions on $\mathbb Z_{R^n}\simeq\{0,1,\dots,R^n-1\}$ by identifying the standard basis $e_i\equiv|i\rangle$ with the element $i\in\mathbb Z_{R^n}$. The mapping would then be: $$ f \mapsto \sum_{i=0}^{R^n-1} f(i) \,|i\rangle. $$ The Fourier transform becomes a unitary operator on $\mathbb C[\mathbb Z_{R^n}] \simeq \mathbb C^{R^n}$ in this way.

Likewise, we can (non-canonically) enumerate the elements in $\mathbb Z_R^n$ as $\{0,1,\dots,R^n-1\}$ and define a similar identification of $ \mathbb C^{R^n}$ with the functions on $\mathbb Z_R^n$ and obtain a different Fourier transform on $ \mathbb C^{R^n}$ in this way.

Consider as an example the multi-qubit case $d=2^n$. The identification $\mathbb C[\mathbb Z_{2^n}] \simeq \mathbb C^{2^n} \simeq (\mathbb C^2)^{\otimes n}$ is done by mapping the local computational basis $|x_1,\dots,x_n\rangle$ to an integer $x\in\{0,\dots,2^n-1\}$ with binary expansion $x = \sum_{j=1}^n x_j 2^{n-j}$. Then, the Fourier transform on $\mathbb Z_{2^n}$ induces a unitary operator on $(\mathbb C^2)^{\otimes n}$, commonly known as Quantum Fourier Transform. In contrast, the Fourier transform on $\mathbb Z_2$ is the Hadamard gate $H$ and hence, the global Fourier transform induced from $\mathbb Z_2^n$ is simply $H^{\otimes n}$.

  • $\begingroup$ Wow this is a very detailed explanation. Just to make sure I understood what you said, so the QFT on $\mathbb{Z}_q^n$ is just the $n$-fold tensor product of the QFT on $\mathbb{Z}_q$? $\endgroup$
    – schayes
    Apr 7, 2022 at 21:59
  • $\begingroup$ @schayes The definition in your question (of Regev) is indeed a $n$-fold tensor product. $\endgroup$ Apr 8, 2022 at 7: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.