A simple question about QFT and CNOT

Question

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\}$?

Answer 1

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.