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$ Dec 20, 2020 at 3:55
  • $\begingroup$ @AdamZalcman: For $d>2$, $CNOT(|i\rangle,|j\rangle)=|i\rangle|j+i\rangle$ $\endgroup$ Dec 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 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.


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.