# What is this equation for coin operator is trying to do in this quantum walk for Non-regular graph? This coin operator is called Fourier coin

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?

• Does anyone have any idea, I really need to know this quickly? – Binshumesh sachan Nov 21 '20 at 13:16

## 1 Answer

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 • So, In the equation which I have given above what it is actually trying to do? – Binshumesh sachan Nov 21 '20 at 17:26
• @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. – KAJ226 Nov 21 '20 at 17:43
• No problem. Thanks for providing me atleast that much information. – Binshumesh sachan Nov 21 '20 at 18:24