# I Confusion about factoring in quantum computation

#### Haorong Wu

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.

Related Quantum Physics News on Phys.org

"Confusion about factoring in quantum computation"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving