- #1

Haorong Wu

- 415

- 90

- TL;DR Summary
- Confusion about factoring in quantum computation

Hi, I'm currently learning QC with Nielsen's QCQI.

I've written a program in Matlab following the factoring algorithm in page 233 and 235.

I run the program for factoring 15, 18, and 25. I got the proper results several times, but I also got error reports sometime, especially when factoring 18 and 25.

After I checked the variables, I found that the probability distributions of the first register after ##FT^+## are spread. Well, I don't know how to describe it clear. Maybe I should put the data in the post:

First, it seems that there are just three results with considerable probabilities.

However, as we can see, the data from 5457 to 5466 are all big enough that anyone of them can be a result for a measurement.

And, in the algorithm, the next step would be computing ##r## from ##\frac s r##. For example, I got a measurement result of 5461, then from ##\frac {5461} {8192}##, the ##r## would just be 8192. Then ##gcd \left( N,x^{r/2}+1 \right)## would report error, where ##N=18, x=7##. I believe this is because the ##r## is too large to compute the greatest common divisor.

Then, if a measurement really gave me a result of 5461, how should I use the continued fraction expansion to get the proper order ##r##? I can't understand what role does the continued fraction expansion play.

Thanks for any suggestions.

I've written a program in Matlab following the factoring algorithm in page 233 and 235.

I run the program for factoring 15, 18, and 25. I got the proper results several times, but I also got error reports sometime, especially when factoring 18 and 25.

After I checked the variables, I found that the probability distributions of the first register after ##FT^+## are spread. Well, I don't know how to describe it clear. Maybe I should put the data in the post:

First, it seems that there are just three results with considerable probabilities.

However, as we can see, the data from 5457 to 5466 are all big enough that anyone of them can be a result for a measurement.

And, in the algorithm, the next step would be computing ##r## from ##\frac s r##. For example, I got a measurement result of 5461, then from ##\frac {5461} {8192}##, the ##r## would just be 8192. Then ##gcd \left( N,x^{r/2}+1 \right)## would report error, where ##N=18, x=7##. I believe this is because the ##r## is too large to compute the greatest common divisor.

Then, if a measurement really gave me a result of 5461, how should I use the continued fraction expansion to get the proper order ##r##? I can't understand what role does the continued fraction expansion play.

Thanks for any suggestions.