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$. enter image description here

And what does this result mean?

enter image description here


1 Answer 1


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.

What Does this Result Mean?

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.

Can I Show a Compiled Circuit for $11^x \, (\text{mod} \, 15)$?

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.

  • $\begingroup$ wow!! You are so kind and very smart!!:) so thank you!! I learn a lot of quantum knowledge because of you. Thank you!! $\endgroup$
    – 유도경
    Feb 7, 2020 at 14:22
  • 1
    $\begingroup$ Thank you for the kind words. My pleasure. $\endgroup$ Feb 7, 2020 at 14:30

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.