Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I'm studying Shor's algorithm.
This diagram shows a calculation of $4^x\mod21$.
I don't understand how this expresses $4^x \mod21$.
Could you explain this? For example, by showing another calculation such as $11^x\mod15$.
And what does this result mean?
It seems that you are trying to make sense of compiled circuits from this paper. All Sections, Tables and Figures noted below are in reference to this paper. The short answers are in bold in case you are not looking for explanation.
The circuit in your question is a "compiled" quantum circuit, which uses known information about the solution to a specified problem to create a simplified implementation of Shor's algorithm. The motivation for doing this is discussed in Section III(A).
Using the notation convention $f_{a,N}(x)=a^x \, (\text{mod} \, N)$, the authors create a truth table (Table V) that implements the modular exponentiation of $f_{4,21}(x)$: $$\vert x \rangle \vert 0 \rangle \rightarrow \vert x \rangle \vert \; 4^x \, (\text{mod} \, 21) \rangle.$$
The input value, $x$, corresponds to the left side of both Table V and Table VI, which in turn corresponds to the value over the three input qubits ($q1_0$ through $q1_2$ in your circuit).
The value of the function $f_{4,21}(x)$ corresponds the right side of Table V, which in turn corresponds to the five output qubits of the circuit in Figure 5.
The two output qubits in your circuit ($q1_3$ and $q1_4$) correspond to $\text{log}_4 (f_{4,21}(x))$, where $x$ is the input value over $q1_0$, $q1_1$, and $q1_2$.
These values are tabulated in the right side of Table VI. This is a second level of compilation, again made possible by a priori knowledge of the solution.
In the context of this compiled circuit we are not interested in measuring the output qubits because the circuit was specifically constructed so that the output qubits will match Table VI. It's an easy exercise to modify your circuit and verify that they do.
Instead, the state of the three input qubits after the QFT is the interesting measurement. These values are interesting because despite the layers of synthetic compilation, they match the values predicted by theory.
This is explained in detail in Section V. The end result is Table XI, which tabulates the probability of measuring state $\vert k \rangle$ (over your $q1_0$, $q1_1$, and $q1_2$) in the columns relative to a postulated period of $f_{4,21}(x)$ in the rows. Note that the authors do not use binary in the column headers, so, e.g. $\vert 5 \rangle \equiv \vert 101 \rangle$.
From Table III we know a priori that the period of $f_{4,21}(x)$ is 3. So as expected
Your histogram corresponds to row 3 of Table XI.
If you increase your shots the numbers should align even more closely.
The cited paper has examples of composite circuits constructed for several other problems. These are much more detailed and reliable than I could hope to provide here, so I would refer you there instead.
