IT代考 1 Order Finding

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. Forexampleintegersx􏰔15􏰔5􏰓3, N􏰔28􏰔2…2􏰓7arecomprime.
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 x􏰔3 and N 􏰔4. Then
31 pmod4q􏰔3
32 pmod 4q􏰔9 pmod 4q􏰔1
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¤2L􏰑1. (1) Example 2 Let x􏰔3, N 􏰔4,ñL􏰔2
|yy |0y |1y |2y |3y
|xy pmod Nqy : |0y |3􏰓1 pmod 4qy􏰔|3y |3􏰓2 pmod 4qy􏰔|2y |3􏰓3 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 x􏰔a1􏰓􏰓􏰓as, N􏰔b1􏰓􏰓􏰓bt,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 pmodNq􏰔xy2 pmodNq􏰔c. xy1 􏰔Nt1􏰐c, xy2 􏰔Nt2􏰐c, forsomet1,t2, andt1 ¡t2.
xy 􏰑xy 􏰔xpy 􏰑y q􏰔Npt 􏰑t q􏰔b 􏰓􏰓􏰓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 ÝÝÝÝÝÑ|πpN􏰑1qy
Ý ÝÝÝÝÝÑ | N y U
ÝÝÝÝÝÑ|2L􏰑1y, 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 r􏰑1 2πis k
|usy􏰔?r expr􏰑 r 􏰓ks|x pmodNqy
1 r􏰑1 2πis
U|usy 􏰔?r expr􏰑 r k􏰔0
pmod Nqy 􏰔?r expr􏰑 r 􏰓ks|x pmodNqy
1 r􏰑1 2πis
􏰓 ks U|x k􏰐1
1 ̧r 2πis 1 k1
􏰔?r expr􏰑 r 􏰓pk􏰑1qs|x pmodNqy k1􏰔1
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
k1􏰔0 􏰔 expr2πiss|usy.
Note that we used here
U|xk pmod Nqy
|x 􏰓 pxk pmod Nqq pmod Nqy 􏰔|x􏰓xk pmodNqy
􏰔|xk􏰐1 pmod Nqy.
We also used the observation that in the summation we can replace k1 􏰔 r with k1 􏰔 0. Indeed
expr􏰑2πis 􏰓 rs 􏰔 expr􏰑2πiss 􏰔 1 􏰔 expr􏰑2π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)
” expr􏰑2πi􏰓r􏰓ss􏰔 0, k􏰖0.
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 k􏰔0 s􏰔0
expr􏰑2πi􏰓r􏰓ss􏰔|1y.
1 r􏰑1 1r􏰑1 r􏰑1 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 {2t􏰐1 􏰐􏰓􏰓􏰓 r1 t t􏰐1
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􏰐…􏰐|ur􏰑1yq,
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 a􏰐1
a0,􏰓􏰓􏰓,aM canbefoundforanyrationalnumbers{r. Example 3
5􏰔0􏰐5􏰔0􏰐1􏰔0􏰐 1 13 13 13 2􏰐3
1 a2 1 …􏰐 a1
􏰔0􏰐 1 􏰔0􏰐 1 􏰔0􏰐 1 2􏰐1 2􏰐1 2􏰐1
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 􏰔1􏰐a0a1, r1 􏰔a1, and for j 􏰔 2,…,n
sj 􏰔 ajsj􏰑1 􏰐 sj􏰑2, rj 􏰔 ajrj􏰑1 􏰐 rj􏰑2.
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
2􏰐1 2􏰐1 1􏰐 1 1􏰐 1
􏰔 1􏰐21 􏰖􏰔1􏰐11 􏰖 1􏰐1
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
raa􏰓􏰓􏰓a􏰓􏰓􏰓as 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,􏰓􏰓􏰓ajaj􏰐1 􏰓􏰓􏰓als. Note that we do not know j.
1282􏰐 1 1􏰐 1
1􏰐 11 1􏰐 ..
􏰔 2􏰐23.􏰖 Thus49{128􏰔 0 2 1 1 1 1 1 2 …
For s{r 􏰔 5{13 we have |5{13􏰑x| 􏰕 0.0018 1 􏰕 0.00296. The continued 2􏰓132
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 modN􏰔1thenwefoundtheorderr􏰔rj.Stop.
Example 6 Let x􏰔4 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 pmod2713q􏰔1and4m pmod2713q􏰖1foranym 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{13􏰔0􏰓1􏰐1􏰓1􏰐1􏰓1􏰐0􏰓 1 􏰐0􏰓 1 􏰐0􏰓 1 􏰐1􏰓 1 􏰐0􏰓 1 2 4 8 16 32 64 128 256
􏰐0􏰓1􏰐1􏰓1􏰐1􏰓1􏰐􏰓􏰓􏰓
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 􏰔0􏰓1􏰐1􏰓1􏰐1􏰓1􏰐0􏰓 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 2􏰓132
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 2713q􏰖1 p43 􏰔64q pmod 2713q􏰖1 p45 􏰔1024q pmod 2713q􏰖1 p48 􏰔65536q pmod 2713q􏰖1 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¥2L􏰐1􏰐rlog2p2􏰐 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