6
$\begingroup$

I am currently reading Shor's algorithm on my own and I come across a paper via this link. It shows the circuit for implementing Shor's alogrithm. Here it depicts that taking a QFT circuit on the number a on the qubits b that are already in fourier space would result in the addition of a and b in Fourier space.

enter image description here

The addition is quite intuitive. However, when it comes the subtraction, I am stuck.Why taking an inverse QFT circuit would result in the $b-a$ or $2^{n+1} - (a-b)$? Wouldn't it return $a+b$ as the second stage output is $\Phi(a+b)$?

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

In the paper they mention that a thick bar drawn on the left of a gate is their notation for its inverse. So in the second circuit they have drawn the inverse of $\phi ADD(a)$, i.e. $\phi ADD(-a)$.

$QFT^{-1}$ is there to un-Fourier transform the result, not to actually perform the substraction.

Improve this answer
$\endgroup$

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.