Experimental study of Shor's factoring algorithm using the IBM Q Experience

We study the results of a compiled version of Shor's factoring algorithm on the ibmqx5 superconducting chip, for the particular case of $N=15$, 21, and 35. The semiclassical quantum Fourier transform is used to implement the algorithm with only a small number of physical qubits, and the circuits are designed to reduce the number of gates to the minimum. We use the square of the statistical overlap to give a quantitative measure of the similarity between the experimentally obtained distribution of phases and the predicted theoretical distribution of phases for different values of the period. This allows us to assign a period to the experimental data without the use of the continued fraction algorithm. A quantitative estimate of the error in our assignment of the period is then given by the overlap coefficient.

Figure 1

Coupling map between the 16 qubits of the ibmqx5 device. The arrows indicate the possible cnot gates between pairs of qubits. In particular, the arrow starts from the control qubit and points to the target qubit.

Figure 2

Circuit for factoring $N=15$, 21, and 35 implemented using the scheme shown in [3]. The first register (top), the period register, stores the estimation of the period, which can be done by using only one qubit through the sc-QFT. The second register (bottom), the computational register, stores the outcomes of the modular exponentiation function $a^x\text{mod}N$ computed through the controlled-$U_{a^x}$ gate. The specific circuits for $U_{a^x}$ used in factoring $N=15,21$, and 35 for a specific base $a$ are shown in the Appendix.

Figure 3

Circuits used in the experimental implementation of Shor's algorithm on ibmqx5. The circuit of Fig. 2 is divided in three separate parts. Each circuit contains a stage of modular exponentiation and a measurement of the period register. The different circuits are joined using a classical algorithm which computes the quantum state of the computational register at the end of the previous circuit and feeds it as input to the next circuit. The classical algorithm also adds the right rotation gates on the period qubit in each successive circuit, based on the results of previous measurements.

Figure 4

(a) Probability of finding a given phase for $N=15$ with base $a=2$ and (b) probability plot of the theoretical distribution and the experimental distribution for $r=4$. The experimental distribution is depicted through the collection of data and a fit of the data. (c) SSO of the experimental data with the theoretical probability distribution corresponding to all possible values of the period $r$.

Figure 5

(a) Probability of finding a given phase for $N=15$ with base $a=11$ and (b) probability plot of the theoretical distribution and the experimental distribution. (c) SSO of the experimental data with the theoretical probability distributions corresponding to all possible periods.

Figure 6

(a) Probability of finding a given phase for $N=21$ with base $a=2$ and (b) probability plot of the theoretical distribution and the experimental distribution. (c) SSO of the experimental data with the theoretical probability distributions corresponding to different periods.

Figure 7

(a) Probability of finding a given phase for $N=35$ with base $a=4$ and (b) probability plot of the theoretical distribution and the experimental distribution. (c) Plot of the SSO between the experimental data and all the possible theoretical distributions for the different values of $r$.

Figure 8

Modular exponentiation circuits for $N=15$. (a) $a^4\text{mod}15$ for any $a$ and $a^2\text{mod}15$ for $a=11$, (b) $a^2\text{mod}15$ for $a=\left\{2,7,8,13\right\}$, (c) $2^1\text{mod}15$ for $a=2$, and (d) ${11}^1\text{mod}15$ for $a=11$.

Figure 9

Modular exponentiation circuits for $N=21$ with base $a=2$. (a) $2^4\text{mod}21$. (b) $2^2\text{mod}21$. Depending on the results of the measurement of the period register in the previous circuits we have (c) $2^1\text{mod}21$ for ${\text{bit}}^{\left(0\right)}=0$ and ${\text{bit}}^{\left(1\right)}=0$, (d) $2^1\text{mod}21$ for ${\text{bit}}^{\left(0\right)}=1$ and ${\text{bit}}^{\left(1\right)}=0$, (e) $2^1\text{mod}21$ for ${\text{bit}}^{\left(0\right)}=0$ and ${\text{bit}}^{\left(1\right)}=1$, and (f) $2^1\text{mod}21$ for ${\text{bit}}^{\left(0\right)}=1$ and ${\text{bit}}^{\left(1\right)}=1$.

Figure 10

Modular exponentiation circuits for $N=35$. (a) $4^4\text{mod}35$. (b) $4^2\text{mod}35$. (c) $4^1\text{mod}35$.