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\}$?
-
$\begingroup$ 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? $\endgroup$– Adam ZalcmanDec 20, 2020 at 3:55
-
$\begingroup$ @AdamZalcman: For $d>2$, $CNOT(|i\rangle,|j\rangle)=|i\rangle|j+i\rangle$ $\endgroup$– WilliamYangDec 20, 2020 at 4:23
-
$\begingroup$ please try to describe what the question is actually about in the title of the post $\endgroup$– 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.