Implementing QFT for Shor's Algorithm

Question

I’m trying to get a Quantum Fourier Transform working with the rest of a compiled version of Shor’s algorithm, attempting to factor $N=21$. In the following image, there’s an initialization phase (before the first vertical line), then a compiled version of modular exponentiation with base 4 up to the second vertical line (based on 1, figure 5), followed by QFT. The output of modular exponentiation seems correct (the output of that module matches the truth table in 1 (table V), which gives $f(4, 21, x) = 4^x \bmod 21)$.

However, the output of QFT gives a pretty much flat distribution over [q3…q7]. This is slightly involved, but I’d appreciate any tips over where I may be going wrong. Happy to provide my code, etc. 

1 Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies, Gamel & James, 2013, https://arxiv.org/abs/1310.6446v2 (edited)

Answer 1

The comment made by arriopolis is correct. The output registers of these compiled circuits are important for synthesizing the circuit, but not particularly interesting to measure. As you saw already, those measurements just match the truth tables they were designed to match.

The QFT and measurements intended for this circuit are

which gives the probability distributions

(If the code implementing any of this would be helpful to anyone, just let me know in the comments.)

The significance of these probability distributions is that they match the expectations of theory for analogous registers of a general implementation of Shor's algorithm. The authors show how this works in detail in Section V, along with proposed uses including quantifying entanglement capacity and noise.

The punchline is that these distributions match the diagonal elements of a reduced density matrix, tracing over the output register to get

$$\rho_p \equiv \text{tr}_o(\vert \phi_p \rangle \langle \phi_p \vert).$$

These are tabulated for this particular case in Table XI (it's clear a priori that $p=3$). Note that the authors' intent to represent binary numbers in the registers by integers was made clear earlier in the section.

However, the circuit above is only an intermediate step towards the authors' aim of substantial simplification of a complex circuit. For example, the composite density matrix for this circuit, which is a necessary step in getting to Table XI, has dimension $2^8 \times 2^8$.

Noting that 5 qubits are used to represent three values (1, 4, and 16) on the output register, the authors use a $\text{log}_4$ map to synthesize the much improved circuit

which remarkably has the same probability distribution on the input register (i.e. matches the same row in Table XI) and maintains the $\text{log}_4$ map between output registers.