1 Order Finding
Let x and N be two integers, and let x a1 …as and N b1 …bt, where ai,bj are primes. We say that x and N are coprime if
ta1, , asu X tb1, , btu m. Forexampleintegersx1553, N282…27arecomprime.
Definition 1 The least positive r such that xr pmod Nq 1 is called the order of x pmod N q.
Copyright By PowCoder代写 加微信 powcoder
Example 1 Let x3 and N 4. Then
31 pmod4q3
32 pmod 4q9 pmod 4q1
There are no classical algorithms for finding r with complexity OpLq(polynomial
Let L rlog2 Ns. in L).
1.1 Unitary rotation corresponding to multiplication pmod Nq and its eigenvectors
For0¤y¤2L 1wedefine2L 2L matrixU by
” |xy pmod Nqy, y N,
U|yy |yy,N¤y¤2L1. (1) Example 2 Let x3, N 4,ñL2
|yy |0y |1y |2y |3y
|xy pmod Nqy : |0y |31 pmod 4qy|3y |32 pmod 4qy|2y |33 pmod 4qy|1y
It is not difficult to see that
1 0 0 0 U 0 0 0 1
It is easy to check that U is unitary: U:U I4. Lemma 1 U is unitary.
Proof xa1as, Nb1bt,ai bj x.
All xy pmod Nq are distinct. To show this let us assume that y1, y2 are such that
y2 y1 N, andxy1 pmodNqxy2 pmodNqc. xy1 Nt1c, xy2 Nt2c, forsomet1,t2, andt1 ¡t2.
xy xy xpy y qNpt t qb b p p pheret t p p q.
12 12 12l1oomoont1q 121q Do not contribute to x, only to py1 y2q
ñy1 y2 b1 …bt pmaybesomepjq
ñ y1 y2 ¥ N which is a contradiction, since we assumed y2
Thus we have
U ÝÝÝÝÝÑ |0y
ÝÝÝÝÝÑ |πp1qy
U ÝÝÝÝÝÑ|πpN1qy
Ý ÝÝÝÝÝÑ | N y U
ÝÝÝÝÝÑ|2L1y, 2
where π is a permutation of the set t1,…,N 1u. Thus U is a permutation matrix ñ U is unitary.
For 0 ¤ s ¤ r 1 we define the state ̧
We further find
1 r1 2πis k
|usy?r expr r ks|x pmodNqy
1 r1 2πis
U|usy ?r expr r k0
pmod Nqy ?r expr r ks|x pmodNqy
1 r1 2πis
ks U|x k1
1 ̧r 2πis 1 k1
?r expr r pk1qs|x pmodNqy k11
1 ̧r 2πis1 2πisk1
expr r s?r
expr r ksexpr r s|x pmodNqy
2πis 1 r ̧1
expr r ks|x pmodNqy
k10 expr2πiss|usy.
Note that we used here
U|xk pmod Nqy
|x pxk pmod Nqq pmod Nqy |xxk pmodNqy
|xk1 pmod Nqy.
We also used the observation that in the summation we can replace k1 r with k1 0. Indeed
expr2πis rs expr2πiss 1 expr2πis 0s, and rr
|xr pmod Nqy |1y |x0 pmod Nqy. 3
According to (2), we have
U|usy expr2πiss|usy,
which means that |usy, s 0, . . . , r 1, are eigenvectors of U with phases ψ p s q rs .
Note that (details are omitted)
” expr2πirss 0, k0.
For example, for r 3 and k 1 the roots of unity are shown on Fig. 1, and
one can see that their sum is 0.
Figure 1: Sum of the powers of a root of unity is 0
Using this observation we can compute the sum of the vectors |usy:
|xk pmodNqy k0 s0
expr2πirss|1y.
1 r1 1r1 r1 k
eigenvectors of U
Remark 1 Note that quantum circuits that do not involve measurement blocks are linear. So, a linear combination of inputs leads to the linear com- bination of the corresponding outputs, as it is shown in Fig. 2.
Figure 2: Quantum Circuits are linear Let us consider the binary expansion of the phase
ψpsq s ψpsq{2ψpsq{2t ψpsq {2t1 r1 t t1
Let us for the moment assume that we use the phase estimation circuit (Fig. 4 of the Lecture Notes on Phase Estimation) with U defined in (1) and with the input |uy |usy (note that we need L qubits for the state |usy). Then the joint state of the t L qubtis before the measurement blocks would be
|φpsq . . . φpsqy|u y, t1s
and therefore at the outputs of the measurement blocks we would get the values of the first t bits in the binary expansion of ψpsq.
The problem is, however, that we cannot prepare the state |usy, since we do not know r. To overcome this problem, we take into account Remark 1 and see that if we use the input
|uy|0lo.om..o0on1y?1 p|u0y…|ur1yq,
then the joint state of the t L qubtis before the measurement blocks is
?r|ψt …ψ1
r ̧11psq psq
Thus at the classical output of the t measurement blocks we obtain ψpsq, . . . , ψpsq, s P
r0, r 1s with probability 1r . Butwedonotknows. Howdowefindr?
1.2 The Continued Fraction Algorithm
aPZ,a,,a PZ 001M
ra0 aMs a0 1 a1
a0,,aM canbefoundforanyrationalnumbers{r. Example 3
505010 1 13 13 13 23
1 a2 1 … a1
0 1 0 1 0 1 21 21 21
a0 a1 a2 a3 a4 021111
Theorem 1 If we are given the continued fraction ra0, , ans of a rational
number sn then we can find this ration number using the following algorithm rn
s0 a0, r0 1, s1 1a0a1, r1 a1, and for j 2,…,n
sj ajsj1 sj2, rj ajrj1 rj2.
In fact this theorem allows us to find all the rational numbers sj{rj corre-
sponding to ra0, ,ajs,j 0,…,n. Example 4
53 1 23 0 1 0 1
21 21 1 1 1 1
121 111 11
r0,2s r0,2,1s r0,2,1,1s r0,2,1,1,1s r0,2,1,1,1,1s
sj {rj ñs1 1,r1 2 1{2 ñs2 1,r2 3 1{3 ñ s3 2,r3 5 2{5 ñ s4 3,r4 8 3{8
ñ s5 5,r5 13 5{13 6
Definition 2 The j-th convergent of continued fraction is defined as
raaaas 01jn
loooomoooon
j-th convergent
Theorem 2 Let x and s{r be rational numbers such that
s 1 r x ¤ 2r2 .
Then the continued fraction of s{r is a j-th convergent of the continued frac- tion of x.
This means that
s{r ra0 ajs, x ra0,ajaj1 als. Note that we do not know j.
1282 1 1 1
1 11 1 ..
223. Thus49{128 0 2 1 1 1 1 1 2 …
For s{r 5{13 we have |5{13x| 0.0018 1 0.00296. The continued 2132
fraction of 5{13, as we found before, is r021111s. So, we see that it is the 5-convergent of r0211112 . . .s.
If t is not very small, we have
ψ ̃ p s q ψ p s q { 2 ψ p s q { 2 t s .
Then with high probability |s ψ ̃psq| ¤ 1 , and we can find r by the “guess
and check” method using the following algorithm.
Algorithm for Order Finding
We run our quantum circuit and obtain bits ψpsq,…,ψpsq. Note that 1t
we get only bits, but we do not know s.
We compute the rational number
ψ ̃psq ψpsq{2ψpsq{2t. 1t
We compute the continued fraction for this ration number ψ ̃psq ra0,a1,…ans.
For j 1, . . . , n we
– take the j-th convergent ra0,…,ajs and, using Theorem 1, com-
pute the rational sj{rj;
–ifxrj modN1thenwefoundtheorderrrj.Stop.
Example 6 Let x4 and N 2713.
Let us assume that we use quantum circuit with t 7. Our goal is to find
the order r using the above algorithm. ( Note that in this example r 13 since413 pmod2713q1and4m pmod2713q1foranym 13,butin our algorithm we do not assume, of course, this knowledge.)
Let us assume that our circuit produced for us results corresponding to s 5 (we of course do not know that s 5). The binary expansion of 5{13:
5{130111110 1 0 1 0 1 1 1 0 1 2 4 8 16 32 64 128 256
011111
512 210 211
However, since t 7, we get at the output of the measurement blocks only the first 7 bits of this binary expansion:
pψs,…,ψpsqq 0 1 1 0 0 0 1. 17
Using these bits, we obtain the rational number
ψ ̃psq 0111110 1 0 1 0 1 1 1 49. 2 4 8 16 32 64 128 128
So, for the moment we did not manage to reconstruct s{r 5{13. However, we hope that this ψ ̃psq is sufficiently close to the true s{r and that ψ ̃psq will allow us to find r. (This is indeed the case, since according to Example 5
| 5 49 | 1 13 128 2132
and therefore the continued fraction of 5{13 is a j-th convergent of 49 .) 128
We compute the continued fraction for 49 (it is already found in Exam- 128
ple 5), take its j-th convergent, find sj and rj and check whether rj is the order of x:
r0,2sñs1 1, r1 2 r0,2,1sñs2 1, r2 3 r0,2,1,1sñs3 2, r3 5 r0,2,1,1,1sñs4 3, r4 8
r0,2,1,1,1,1s ñ s5 5, r5 13
p42 16q pmod 2713q1 p43 64q pmod 2713q1 p45 1024q pmod 2713q1 p48 65536q pmod 2713q1 p413q pmod 2713q 1
We found r 13 !
Please note that in all our computations we did not use values r 13,
s 5. We simply followed the above Algorithm and used only the 7 bits produced by the quantum circuit and numbers x and N.
So if t is large enough, so that |s ψpsq| ¤ 1 , the continued fraction algo- r 2r2
rithm allows us to find r.
1.3 Possible Problems
1. ψ ̃psq is not close enough to s{r. Theorem 3 If
t¥2L1rlog2p2 1qs 2ε
then with probability p1 εq the value ψ ̃psq will allow us to find r.
2. s and r have a common factor. For instance r 12 and at the output
of the phase estimation algorithm we get the value ψp3q s{r 3{12 1{4.
Then the continued fraction of 1{4 will never allow us to find r 12. However, according to the well known result of the number theory:
pNumber of primes rq ¥ r 2logr
Further, it is easy to see that in the prime factorization of
r p1 …pm (3) the number of distinct primes m ¤ log2 r. Hence
Prps and r are coprime q ¥ Prps is a prime that does not occur in (3)q ¥1p r log2rq.
For a small N the order finding problem can be solved by a classical computer – simply by computing all xr mod N for all r 2,…,N 1. So, let us say that we are interested in N ¥ 10,000. We proceed as follows.
We first use classical computer to compute xr mod N for say r 2,…,1000.
If the order is not found among these r-s, we use the quantum circuit. It is easy to check that for N ¥ 10, 000 we have
max 1p r log2rq 1p N log2Nq rPr1000,Ns r 2logr N 2logN
This expression behaves like Op 1 q. Hence running our quan- 2 log2 N
tum algorithm Op2log2 Nq times, with high probability, we get s that is coprime to r. Thus the overall complexity is polynomial in log2 N, while the complexity of any classical algorithm is OpNq, and therefore we have an exponential speed up.
3. Complexity of implementing Controlled U defined in (1). This complexity is only OpL3q gates (details are omitted).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com