# Confusion about factoring in quantum computation

• I
• Haorong Wu
In summary, the conversation discusses the use of a program in Matlab for factoring numbers using Nielsen's QCQI algorithm. The program was used for factoring 15, 18, and 25, and while it produced correct results for some numbers, it also gave error reports for others. It was discovered that the issue was with the probability distributions of the first register after applying ##FT^+##. The continued fraction expansion was mentioned as a way to find a rational number close to the phase estimate produced by the algorithm. However, for certain numbers like 18 and 25, finding a suitable value for ##x## to continue the algorithm can be difficult due to certain assumptions not being met. Overall, the conversation touches on the
Haorong Wu
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.

The continued fraction expansion is a way of finding a rational number close to a phase estimate produced in the order-finding algorithm. Since that algorithm operates on ##t## qubits, it only produces an approximation of the phase ##\tilde \phi##. If you work through the continued fraction algorithm with ##\tilde {s / r} = \frac {5461}{8192}##. You get successive rational numbers 0,1, ##\frac 1 2##, ##\frac 2 3##, ##\frac {5461}{8192}##. So the closest rational number to ##\tilde \phi## other than ##\frac {5461}{8192}## itself is ##\frac 2 3##, making ##r=3##. In fact ##7^3 = 1 \text{ mod } 18##, so it is the correct value for ##r##. Unfortunately, it is not an even number, so it won't work for the rest of the algorithm. It appears that the other non-zero phase value is ##\frac 1 3##, so it will not give a solution either. I suppose that in this case you would need to choose a different value for ##x## and try again.

I think using a perfect square as ##N## violates some assumption of the proof that gcd(##x^\frac r 2 -1, N##) or gcd(##x^\frac r 2 +1, N##) divides ##N##. This, I am sure, is why you cannot get the algorithm to work for ##N=25##.
Edit: It appears to me that with ##N## a perfect square, every value of ##x## results in either a) an odd value of ##r##, or b) ##x^{\frac r 2} = -1 \text{ mod } N##. I do not have a proof for this, but I have not found a counter example either.
Edit: OK, here is the proof. The goal of the algorithm is to find an integer ##y## such that ##y^2 = 1 \text { mod } N## and ##y \ne \pm1 \text { mod } N##. Suppose ##N=p^2## for some prime ##p > 2##. Then ##y^2-1 = (y+1)(y-1) = 0 \text { mod } N##, or equivalently, ##p^2## divides (y+1)(y-1). Then either ##p## divides both of the factors ##y+1## and ##y-1## or ##p^2## divides one of them. The first case implies that ##p\le2##, contradiction. The second case implies ##y = \pm 1 \text { mod } N##, contradiction.
This does not prevent the method from working on squares of composite numbers.

Possibly, this will also prevent you from finding a value of ##x## that works for ##N=18=2(3^2)##. It seems to me that no value of ##x## works for that case.
Edit: The same kind of argument used for ##N=p^2## above also works for ##N=kp^2## where ##k## is an integer not divisible by ##p##.

Last edited:
Haorong Wu
tnich said:
The continued fraction expansion is a way of finding a rational number close to a phase estimate produced in the order-finding algorithm. Since that algorithm operates on ##t## qubits, it only produces an approximation of the phase ##\tilde \phi##. If you work through the continued fraction algorithm with ##\tilde {s / r} = \frac {5461}{8192}##. You get successive rational numbers 0,1, ##\frac 1 2##, ##\frac 2 3##, ##\frac {5461}{8192}##. So the closest rational number to ##\tilde \phi## other than ##\frac {5461}{8192}## itself is ##\frac 2 3##, making ##r=3##. In fact ##7^3 = 1 \text{ mod } 18##, so it is the correct value for ##r##. Unfortunately, it is not an even number, so it won't work for the rest of the algorithm. It appears that the other non-zero phase value is ##\frac 1 3##, so it will not give a solution either. I suppose that in this case you would need to choose a different value for ##x## and try again.

I think using a perfect square as ##N## violates some assumption of the proof that gcd(##x^\frac r 2 -1, N##) or gcd(##x^\frac r 2 +1, N##) divides ##N##. This, I am sure, is why you cannot get the algorithm to work for ##N=25##.
Edit: It appears to me that with ##N## a perfect square, every value of ##x## results in either a) an odd value of ##r##, or b) ##x^{\frac r 2} = -1 \text{ mod } N##. I do not have a proof for this, but I have not found a counter example either.
Edit: OK, here is the proof. The goal of the algorithm is to find an integer ##y## such that ##y^2 = 1 \text { mod } N## and ##y \ne \pm1 \text { mod } N##. Suppose ##N=p^2## for some prime ##p > 2##. Then ##y^2-1 = (y+1)(y-1) = 0 \text { mod } N##, or equivalently, ##p^2## divides (y+1)(y-1). Then either ##p## divides both of the factors ##y+1## and ##y-1## or ##p^2## divides one of them. The first case implies that ##p\le2##, contradiction. The second case implies ##y = \pm 1 \text { mod } N##, contradiction.
This does not prevent the method from working on squares of composite numbers.

Possibly, this will also prevent you from finding a value of ##x## that works for ##N=18=2(3^2)##. It seems to me that no value of ##x## works for that case.
Edit: The same kind of argument used for ##N=p^2## above also works for ##N=kp^2## where ##k## is an integer not divisible by ##p##.
Hi, tnich. Great ideas about the perfect squares. It would be an interesting topic on how to tackle those perfect squares, especially when ##k## is not ##1##.

Haorong Wu said:
Hi, tnich. Great ideas about the perfect squares. It would be an interesting topic on how to tackle those perfect squares, especially when ##k## is not ##1##.
##N=kn^2## where ##k## is a special case. For any value of ##r## such that ##x^r = 1 \text { mod } kn^2##, it is also true that ##x^r = 1 \text { mod } n^2##. So about the best we can do with this method is obtain the factors k and ##n^2##. However, we can also find the square root of each of those factors and determine whether it is an integer. It seems like that would resolve the issue.

## 1. What is factoring in quantum computation?

Factoring in quantum computation is a mathematical process that involves breaking down a large number into its prime factors. It is an important problem in computer science and cryptography, with applications in data encryption and decryption.

## 2. How is factoring different in quantum computation compared to classical computation?

In classical computation, factoring is a very time-consuming process, especially for large numbers. However, in quantum computation, it is possible to factor large numbers in a much shorter amount of time due to the use of quantum algorithms and principles such as superposition and entanglement.

## 3. What is the significance of factoring in quantum computation?

The ability to efficiently factor large numbers in quantum computation has major implications for cryptography and data security. It could potentially render traditional encryption methods obsolete and open up new possibilities for secure communication and data storage.

## 4. What are some challenges in factoring using quantum computation?

One of the biggest challenges in factoring using quantum computation is the issue of error correction. Quantum computers are prone to errors, and these errors can greatly affect the accuracy of the factoring process. Another challenge is the scalability of quantum computers, as larger numbers require more qubits and more complex algorithms.

## 5. Are there any real-world applications of factoring in quantum computation?

While factoring in quantum computation is still in its early stages, there have been some real-world applications demonstrated, such as factorization of small numbers and the implementation of quantum key distribution for secure communication. However, further research and development are needed before it can be fully utilized in practical applications.

Replies
1
Views
935
Replies
11
Views
2K
Replies
2
Views
1K
Replies
4
Views
6K
Replies
13
Views
2K
Replies
2
Views
879
Replies
2
Views
2K
Replies
2
Views
2K
Replies
2
Views
2K
Replies
9
Views
2K