# A simple question about QFT and CNOT

Given two $$d$$-dimensional states $$QFT|i\rangle(i\in\{0,1,2,...,d-1\})$$ and $$|\varphi\rangle=|0\rangle$$. If I perform $$CNOT(QFT|i\rangle,|\varphi\rangle)$$, and then perform $$QFT^{-1}|\varphi\rangle$$, can I get $$i$$ with measurement on$$|\varphi\rangle$$ in base $$\{|0\rangle,|1\rangle,\ldots,|d-1\rangle\}$$?

• What does CNOT do when $d > 2$? Do you perhaps assume that $d=2^n$ and CNOT stands for $n$ CNOTs applied pairwise between two $n$-qubit registers? Dec 20, 2020 at 3:55
• @AdamZalcman: For $d>2$, $CNOT(|i\rangle,|j\rangle)=|i\rangle|j+i\rangle$ Dec 20, 2020 at 4:23
• please try to describe what the question is actually about in the title of the post
– glS
Dec 21, 2020 at 23:48

## 1 Answer

Yes, with probability $$\frac{1}{d}$$.

Begin by computing the output state

\begin{align} |\psi\rangle &= (I\otimes QFT^{-1} \circ CNOT \circ QFT \otimes I)|i\rangle|0\rangle \\ &= (I\otimes QFT^{-1} \circ CNOT)\frac{1}{\sqrt{d}}\sum_{j=0}^{d-1}\omega^{ij}|j\rangle|0\rangle \\ &= \frac{1}{\sqrt{d}}\sum_{j=0}^{d-1}\omega^{ij} (I\otimes QFT^{-1} \circ CNOT)|j\rangle|0\rangle \\ &= \frac{1}{\sqrt{d}}\sum_{j=0}^{d-1}\omega^{ij} I\otimes QFT^{-1}|j\rangle|j\rangle \\ &= \frac{1}{\sqrt{d}}\sum_{j=0}^{d-1}\omega^{ij} |j\rangle \frac{1}{\sqrt{d}}\sum_{k=0}^{d-1}\omega^{-jk}|k\rangle \\ &= \frac{1}{d}\sum_{j,k=0}^{d-1}\omega^{(i-k)j} |j\rangle|k\rangle \end{align}

where $$\omega = e^{2\pi i/d}$$. The probability of obtaining result $$|l\rangle$$ when measuring the second register in the computational basis is

\begin{align} P_l &= \langle\psi|l\rangle\langle l|\psi\rangle \\ &= \frac{1}{d^2}\sum_{j',k'=0}^{d-1}\sum_{j,k=0}^{d-1}\omega^{(k'-i)j'}\omega^{(i-k)j} \langle j'|j\rangle\langle k'|l\rangle \langle l|k\rangle \\ &= \frac{1}{d^2}\sum_{j',k'=0}^{d-1}\sum_{j,k=0}^{d-1}\omega^{(k'-i)j'}\omega^{(i-k)j} \delta_{jj'}\delta_{k'l}\delta_{lk} \\ &= \frac{1}{d^2}\sum_{j=0}^{d-1}\omega^{(l-i)j}\omega^{(i-l)j} \\ &= \frac{1}{d}. \end{align}

I suppose it may be interesting to consider why we did not obtain $$|i\rangle$$ with probability 1 as we would have if we had applied $$QFT$$ and $$QFT^{-1}$$ on the same register. In the latter case (without $$CNOT$$), we recover $$|i\rangle$$ because of interference (constructive on $$|i\rangle$$ and destructive on $$|j\rangle$$ for $$j \ne i$$). However, interference is prevented in the present case (with $$CNOT$$) by entanglement. Specifically, as the calculation shows, entanglement introduced by the $$CNOT$$ gate causes different phase factors to land on different kets and therefore prevents their interference.