In papers, one of them being An Experimental Study of Shor's Factoring Algorithm on IBM Q is stated that replacing QFT with the semiclassical QFT (Kitaev's approach) reduces the needed number of qubits to solve a given problem with Shor's algorithm. Other than using a different approach - measuring one qubit of the period register each time contrary to the approach where multiple qubits are used is there a mathematical difference between sc-QFT and QFT?

More precisely, my question is: if QFT is mathematically described as

$$| x \rangle \rightarrow \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \exp\left(\frac{2\pi ixy}{N}\right) | y\rangle,$$

how does the equation for sc-QFT look like?


1 Answer 1


The semi-classical QFT only behaves the same as the QFT if you are immediately measuring the QFT's output. A mathematical description of the unitary effect of the QFT isn't going to work, because the semi-classical QFT isn't a unitary operation. It's a frequency space measurement operation.

You need to describe the semi-classical QFT in terms of the probability distribution of measurement results (as a function in the input state). You can also describe QFT+measure in this way, and confirm that their descriptions in terms of probability distribution are equal.


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.