I am reading the following paper: Discrete-time quantum walk on complex networks for community detection by Kanae Mukai
We define the Coin operator $C$ by: $C=C_1\otimes C_2....C_n$ , We define coin operator for Node $i, C_i:H_i\to H_i$ is given by:

$C_i^F|i\to j_1\rangle|i\to j_2\rangle.......|i\to j_k\rangle=(|i\to j_1\rangle|i\to j_2\rangle.......|i \to j_k\rangle)1/\sqrt(k_i) \begin{pmatrix} 1 & 1 & 1 & ... & 1\\ 1 & e^{\iota\theta/k_i} & e^{2\iota\theta/k_i} & ... & e^{(k_i-1)\iota\theta/k_i}\\ 1 & e^{2\iota\theta/k_i} & e^{4\iota\theta/k_i} & ... & e^{2(k_i-1)\iota\theta/k_i}\\ . & . & . & . & .\\. & . & . & . & .\\. & . & . & . & .\\ 1 & e^{(k_i-1)\iota\theta/k_i} & e^{2(k_i-1)\iota\theta/k_i} & ... & e^{(k_i-1)(k_i-1)\iota\theta/k_i}\end{pmatrix}$
Here $k_i$ is the degree of $i^{th}$ node and $\theta=2\pi$. The author called this coin as Fourier Coin. And this $i\to j$ implies that Node $i$ is going to hope to adjacent Node $j$. Now, What is going on with this equation?

  • $\begingroup$ Does anyone have any idea, I really need to know this quickly? $\endgroup$ Nov 21, 2020 at 13:16

1 Answer 1


The operator Fourier Coin is $k$-point Discrete Fourier Transform (DFT) of node $i$. The matrix representation of a general $N$-point DFT can be found here.

The implementation of DFT on the quantum computer is what we know as QFT, and it can be found in Mike and Ike on pg.219. More specifically, an eight-point DFT can be implemented on the quantum computer as

enter image description here

  • $\begingroup$ So, In the equation which I have given above what it is actually trying to do? $\endgroup$ Nov 21, 2020 at 17:26
  • $\begingroup$ @Binshumeshsachan I don't know about the concept of Fourier coin, unfortunately. I just recognized that the operator that you are trying to implement is a DFT, and I know DFT is used to convert between time and frequency domain hence it can be used to calculate the frequency spectrum. For instance, in shor's algorithm, it is used to pick up the periodicity of the modulus exponential function... Wish I can provide you what it does in the context you are asking for. sorry. $\endgroup$
    – KAJ226
    Nov 21, 2020 at 17:43
  • $\begingroup$ No problem. Thanks for providing me atleast that much information. $\endgroup$ Nov 21, 2020 at 18:24

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.