Effects of Imperfect Gate Operations in Shor's Prime Factorization
  Algorithm
Journal of the Chinese Chemical Society, 2001, 48: 449-454
Effects of Imperfect Gate Operations in Shor’s Prime Factorization Algorithm
Hao Guo1,2, Gui-Lu Long1,2,3,4,5 and Yang Sun1,2,6,7
Department of Physics, Tsinghua University, Beijing 100084
Key Laboratory for Quantum Information and Measurements, MOE
Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100080, P.R. China
Centre for Nuclear Theory, Lanzhou National Laboratory of Heavy Ions
Chinese Academy of Sciences, Lanzhou 740000, P.R. China
Center of Atomic, Molecular and Nanosciences, Tsinghua University, Beijing 100084
Department of Physics, Xuzhou Normal University, Xuzhou,
Jiangsu 221009
Department of Physics and Astronomy,
University of Tennessee, Knoxville, TN 37996, U.S.A.
(Dated: 2001)
The effects of imperfect gate operations in implementation of Shor’s prime factorization algorithm
are investigated. The gate imperfections may be classified into three categories: the systematic error,
the random error, and the one with combined errors. It is found that Shor’s algorithm is robust
against the systematic errors but is vulnerable to the random errors. Error threshold is given to the
algorithm for a given number N to be factorized.
PACS numbers: PACS numbers: 03.67.Lx, 89.70.+c, 89.80.+h
I. INTRODUCTION
Shor’s factorization algorithm [1] is a very impor-
tant quantum algorithm, through which one has demon-
strated the power of quantum computers. It has greatly
promoted the worldwide research in quantum computing
over the past few years. In practice, however, quantum
systems are subject to influence of environment, and in
addition, quantum gate operations are often imperfect
[2, 3]. Environment influence on the system can cause de-
coherence of quantum states, and gate imperfection leads
to errors in quantum computing. Thanks to Shor’s an-
other important work, in which he showed that quantum
error correlation can be corrected [4]. With quantum
error correction scheme, errors arising from both deco-
herence and imperfection can be corrected.
There have been several works on the effects of deco-
herence on Shor’s algorithm. Sun et al. discussed the
effect of decoherence on the algorithm by modeling the
environment [5]. Palma studied the effects of both deco-
herence and gate imperfection in ion trap quantum com-
puters [6]. There have also been many other studies on
the quantum algorithm [7, 8, 9, 10].
The error correction scheme uses available resources.
Thus it is important to study the robustness of the algo-
rithm itself so that one can strike a balance between the
amount of quantum error correction and the amount of
qubits available. In this paper, we investigate the effects
of gate imperfection on the efficiency of Shor’s factoriza-
tion algorithm. The results may guide us in practice to
suppress deliberately those errors that influence the algo-
rithm most sensitively. For those errors that do not affect
the algorithm very much, we may ignore them as a good
approximation. In addition, study of the robustness of
algorithm to errors is important where one can not apply
the quantum error correction at all, for instance, in cases
that there are not enough qubits available.
The paper is organized as follows. Section II is devoted
to an outline of Shor’s algorithm and different error’s
modes. In Section III, we present the results. Finally, a
short summary is given in Section IV.
II. SHOR’S ALGORITHM AND ERROR’S
MODES
Shor’s algorithm consists of the following steps:
1) preparing a superposition of evenly distributed
states
|ψ〉 = 1√
|a〉|0〉,
where q = 2L and N2 ≤ q ≤ 2N2 with N being the
number to be factorized;
2) implementing yamodN and putting the results into
the 2nd register
|ψ1〉 =
|a〉|yamodN〉;
3) making a measument on the 2nd register; The state
of the register is then
|φ2〉 =
|jr + l〉|z = yl = yjr+lmodN〉
where j ≤
4) performing discrete Fourier transformation (DFT)
on the first register |φ3〉 =
f̃ (c) |c〉
|z〉, where
f̃ (c) =
2πi(jr + l)
2πilc
2πijrc
http://arxiv.org/abs/0704.0516v1
This term is nonzero only when c = k q
, with k =
0, 1, 2...r − 1, which correspond to the peaks of the dis-
tribution in the measured results, and thus this term be-
comes f̃(c) = 1√
2πilc
q . The Fourier transformation is
important because it makes the state in the first register
the same for all possible values in the 2nd register. The
DFT is constructed by two basic gate operations: the
single bit gate operation Aj =
, which is
also called the Walsh-Hadmard transformation, and the
2-bits controlled rotation
Bjk =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 eiθjk
with θjk =
. The gate sequence for implementing
DFT is
(Aq−1)(Bq−2q−1Aq−2) . . . (B0q−1B0q−2 . . . B01A0).
Errors can occur in both Aj and Bjk. Aj is actually a
rotation about y-axis through π
Aj(θ) = e
Syθ = I cos(
)−i sin(θ
)σy =
cos( θ
) − sin( θ
sin( θ
) cos( θ
If the gate operation is not perfect, the rotation is not
exactly π
. In this case, Aj is a rotation of
Aj(δ) =
cos(δ)− sin(δ) −(sin(δ) + cos(δ))
sin(δ) + cos(δ) cos(δ)− sin(δ)
If δ is very small, we have:
Aj(θ) =
1− δ −(1 + δ)
1 + δ+ 1− δ
Similarly, errors in Bjk can be written as
Bjk =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 ei(θjk+δ)
With these errors, the DFT becomes
|a〉 →
i( 2π
+δc)a(1 + δ′c)|c̃〉 =
i( 2πc
+δc)a(1 + δ′c)|c̃〉,(1)
where δc and δ
c denote the error of Aj and Bjk, respec-
tively.
Let us assume the following error modes: 1) system-
atic errors, where δc or δ
c in (1) can only have system-
atic errors (EM1); 2) random errors (EM2), for which
we assume that δc or δ
c can only be random errors of
the Gaussian or the uniform type; 3) coexistence of both
systematic and random errors (EM3). In the next sec-
tion, we shall present the results of numerical simulations
and discuss the effects of imperfect gate operation on the
DFT algorithm, and thus on the Shor’s algorithm.
III. INFLUENCE OF IMPERFECT GATE
OPERATIONS
We first discuss the influence of imperfect gate opera-
tions in the initial preparation
Al−1Al−2...A0|0...0〉 = 1√
(|0〉+ |1〉+ δ1(|0〉 − |1〉))⊗ (|0〉+ |1〉+ δ2(|0〉 − |1〉))⊗ . . .⊗ (|0〉+ |1〉+ δn(|0〉 − |1〉))
i1i2...in=0
|i1i2...in〉+ 1√
R=1 δn
i1i2...in=0
(|i1..iR−10iR+1..in〉 − |i1..iR−11iR+1..in〉
If the errors are systematic, for instance, caused by the
inaccurate calibration of the rotations, then δ1 = δ2 =
. . . = δn = δ. In this case, we can write the 2nd term as
|ψ〉 = 1√
i1i2...in=0
(2s− n)|i1i2...in〉,
where s stands for the number of 1’s, and 2s− n = s −
(n − s) is the difference in the number of 1’s and 0’s.
Thus the results after the first procedure is
(|a〉+ δ(2s− n)|a〉) =
(1 + δa)|a〉. (2)
This implies that after the procedure, the amplitude of
each state is no longer equal, but have slight difference.
Combining the effect in the initialization and in the DFT,
we have
(1 + δa)(1 + δc)e
i( 2πc
+δ′c)a
= (1 + δ′′)ei(
+δ′c)a,
where δ′′c = δc + δa. In the DFT, we have
|ψ〉 ⇒
(1 + δj)e
i( 2πc
+δ′j)(jr+l)|c̃〉,
where we have rewrite δ′′ as δj here. Let Pc denote the
probability of getting the state |c̃〉 after we perform a
measurement, we have
(1 + δm)(1 + δk)e
i( 2πc
+δ′m)(mr+l)×e−i(
+δ′k)(kr+l)
(1 + δm)(1 + δk) cos[
r(m − k) + (mr + l)δ′m − (kr + l)δ′k](3)
From Eq. (3), we find that after the last measurement,
each state can be extracted with a probability which is
nonzero, and the offset l can’t be eliminated.
Eq. (3) is very complicated, so we will make some
predigestions to discuss different error modes for conve-
nience. Generally speaking, the influence of exponential
error δj is more remarkable than δj , so we can omit the
error δj , thus
DFTq |φ〉 =
j=0 e
i( 2πc
+δ′j)(jr+l)|c〉 .
A. Case 1
If only systematic errors (EM1) are considered, namely,
all the δj ’s are equal, then f̃(c) can be given analytically
f̃(c) =
i( 2πc
+δ)(jr+l)
il( 2πc
+δ) 1− ei(
1− ei(
The relative probability of finding c is
f̃(c)
sin2(
sin2(πcr
and if c = k q
, then
r sin2(
q2 sin2( δr
It can be easily seen that limδ→0 Pc =
, which is just
the case that no error is considered.
When δ takes certain values, say, δ = 2
(k− r
)π where
k is an integer, then the summation in Eq. (4) is on
longer valid. In our simulation, δ does not take these
values. Here we consider the case where q = 27 = 128
and r = 4. For comparisons, we have drawn the relative
probability for obtaining state c in Fig.1. for this given
example. We have found the following results:
(i) When δ is small, the errors do hardly influence the
final result, for instance when c = k q
, then
Pc = lim
r sin2( δq
q2 sin2( δr
The probability distribution is almost identical to those
without errors.
(ii) Let us increase δ gradually, from Fig.2, we see that
a gradual change in the probability distribution takes
place. (Here, we again consider the relative probabilities)
When δ is increased to certain values, the positions of
peaks change greatly. For instance at δ = 0.05, there
appears a peak at c=127, whereas it is Pc = 0 when no
systematic errors are present. In general, the influence of
systematic errors on the algorithm is a shift of the peak
positions. This influences the final results directly.
B. Case 2
When both random errors and systematic errors are
present, we add random errors to the simulation. To see
the effect of different mode of random errors, we use two
random number generators. One is the Gaussian mode
and the other is the uniform mode. In this case, the er-
ror has the form δ = δ0 + s, where δ0 is the systematic
error. s has a probability distribution with respect to
c, depending on the uniform or the Gaussian distribu-
tion. When δ0 = 0, we have only random errors which is
our error mode 2. When δ0 6= 0, we have error mode 3.
For the uniform distribution, s ∼ ±smax × u(0, 1) where
u(0, 1) is evenly distributed in [0,1]. smax indicates the
maximum deviation from δ0. For Gaussian distribution,
s ∼ N(0, σ0). Through the figure, we see the following:
(1) When only random errors are present (δ0 = 0), the
peak positions are not affected by these random errors.
However, different random error modes cause similar re-
sults. The results for uniform random error mode are
shown in Fig.3. For the uniform distribution error mode,
with increasing δmax, the final probability distribution of
the final results become irregular. In particular, when
δmax is very large, all the patterns are destroyed and is
hardly recognizable. Many unexpected small peaks ap-
pear. For the Gaussian distribution error mode, as shown
in Fig.4, the influence of the error is more serious. This
is because in Gaussian distribution, there is no cut-off
of errors. Large errors can occur although their proba-
bility is small. The influence of σ0 on the final results
is also sensitive, because it determines the shape of the
distribution. When σ0 increases, the final probability dis-
tribution becomes very messy. A small change in σ0 can
cause a big change in the final results.
(2) When δ0 6= 0, which corresponds to error mode 3,
the effect is seen as to shift the positions of the peaks in
addition to the influences of the random errors.
IV. SUMMARY
To summarize, we have analyzed the errors in Shor’s
factorization algorithm. It has been seen that the effect
of the systematic errors is to shift the positions of the
peaks, whereas the random errors change the shape of the
probability distribution. For systematic errors, the shape
of the distribution of the final results is hardly destroyed,
though displaced. We can still use the result with several
trial guesses to obtain the right results because the peak
positions are shifted only slightly. However, the random
errors are detrimental to the algorithm and should be
reduced as much as possible. It is different from the
case with Grover’s algorithm where systematic errors are
disastrous while random errors are less harmful [10].
[1] P.W. Shor, Proceedings of the 35th Annual Symposium
on the Foundations of Computer Science, edited by S.
Goldwasser (IEEE Computer Society Press, Los Alami-
tos, CA, 1994) p.124.
-20 0 20 40 60 80 100 120 140
FIG. 1: Relative probability for finding state c in the absence
of errors.
[2] A. Ekert and R. Jozsa, Rev. Mod. Phys. 68 (1996) 733.
[3] W.G. Unruh, Phys. Rev A51 (1995) 992.
[4] I. Chuang and R. laflamme, ”Quantum error correction
by codding” (1995) quant-ph/9511003.
[5] C.P. Sun, H. Zhan and X.F. Liu, Phys. Rew. A58 (1998)
1810.
[6] G.M. Palma, K.A. Suominen and A.K. Ekert, Proc. R.
Soc. London, A 452 (1996) 567.
[7] R.P. Feynman, Int. J. Theo. Phys., 21 (1982) 467.
[8] D. Deutsch, Proc. R. Soc. Land. A 400 (1985) 97.
[9] L.K. Grover, Phys. Rev, Lett, 79 (1997) 325.
[10] G.L. Long, Y.S. Li, W.L. Zhang, C.C. Tu, Phys. Rev. A
61 (2000) 042305.
[11] L.K. Grover, Phys. Rev. Lett, 80 (1998) 4329.
http://arxiv.org/abs/quant-ph/9511003
-20 0 20 40 60 80 100 120 140
-20 0 20 40 60 80 100 120 140
-20 0 20 40 60 80 100 120 140
-20 0 20 40 60 80 100 120 140
FIG. 2: The same as Fig.1. with systematic errors. In sub-
figures (1), (2), (3), (4), δ are 0.02, 0.03, 0.05 respectively. In
sub-figure (4), the curve with solid circles(with higher peaks)
is the result with δ = 0.1, and the one without solid cir-
cles(with lower peaks) denotes the result with δ = 0.33.
-20 0 20 40 60 80 100 120 140
c -20 0 20 40 60 80 100 120 140
-20 0 20 40 60 80 100 120 140
-20 0 20 40 60 80 100 120 140
0.000
0.005
0.010
0.015
0.020
0.025
0.030
FIG. 3: The same as Fig.1. with uniform random errors. In
sub-figures (1), (2), (3), (4), smax are set to 0.01, 0.03, 0.05,
0.1 respectively.
-20 0 20 40 60 80 100 120 140
-20 0 20 40 60 80 100 120 140
-20 0 20 40 60 80 100 120 140
0.004
0.006
0.008
0.010
0.012
0.014
0.016
0.018
0.020
-20 0 20 40 60 80 100 120 140
FIG. 4: The same as Fig.1. with Gaussian random errors
and systematic errors. In sub-figures (1), (2), and (3) τ are
set to 0.01, 0.03 and 0.05 respectively, and δ0 = 0(without
systematic errors). In sub-figure (4), both systematic and
random Gaussian errors exist, where δ0 = 0.33, τ = 0.02.
