Introduction

Quantum computing is an expression frequently to be found in the news of every self respecting media outlet.
Time and again, yet another breakthrough is described towards the event of becoming fully operational of such a device.
The method of working of a quantum computer (QC) in those reports always comes down to:

• The QC does not work with bits like all our present computers do, but with qubits.
• The bits of our familiar classical computers can have the value 0 or 1 but qubits can have both values at the same time. This phenomenon is called superposition.
• For this reason, a quantum computer reduces today’s supercomputer to an abacus.

It does not seem that this conclusion satisfies the average packet of questions one has about an entirely new technology.

Note:
This article is part of a series of articles. Please check here for the other articles in this series and the best order in which to read them.

The formidable computing power of the QC is considered to be used for applications as:

• Weather forecasting
• Financial modeling
• Medication development

But inevitably, the news articles proceed with the disturbing message that our most important encryption schemes (e.g bank accounts, money transfers) no longer are safe. The quantum device should be able to break the encryption algorithms in no time while our classic supercomputers need thousands of years to perform the trick.

Few people should feel adequately informed by these explanatory descriptions.
This is why I will attempt to shed some light on the matter, without lifting it to the level of the highly technical articles found on the scientific internet sites. Also it is a logical continuation of my text about RSA encryption.

Factoring large numbers

As I earlier explained in the essay ‘The secrets of RSA encryption’:

“The digital protection of valuable data comes down to encrypting it with a gargantuan number that is the product of two large prime numbers p and q. A typical key is of the size 2²⁰⁴⁸ let’s call it N. There is no known fast algorithm for factoring such large numbers. The primitive way to find a factor of the not even N is to divide by the odd numbers one by one, starting with 3 and go up to ultimately √N. Why √N? When there is a bigger factor than that, we would have found a smaller one already.”

It wouldn’t be very smart to choose a small p or q, since such a factor would be found early in the check, whereas the other factor can be rapidly calculated from q = N/p.
We may assume that for RSA the factors p and q both are in the vicinity of √N. So why not start with our factor finding at the first odd number smaller than √N and step down one by one?

Well, let’s see how this works out. Assume we have a √N of 10¹⁵⁰ and p and q are within the range 10¹⁴⁹ — 10¹⁵⁰. How big is this range? It appears that 10¹⁵⁰– 10¹⁴⁹ =  9 x10¹⁴⁹. This means that our range from which we would extract the factors p and q holds 90% of the numbers from 1 to 10^150.
So much for the idea of working top down.

The price to pay

Mathematicians like to express the complexity of an algorithm in the number of steps to get at the solution. They call this the time complexity and for the most trivial factoring method this is O(√N / 2). O stands for Big O, which assures an upper bound that will not be exceeded. The division by 2 is because the method can ignore the even numbers and merely tests odd numbers for being a factor.
The time complexity for an N of the size 2²⁰⁴⁸ is √2²⁰⁴⁸ / 2 = 9 x 10³⁰⁷ (approx.) This is about the maximum number of steps needed for finding a factor.

Our trivial algorithm can easily be enhanced somewhat. Numbers with a last digit of 5 can be skipped. Same for the numbers which digits add up to an amount divisible by 3.
A sieve could be applied, to take out multiples of numbers that are not a factor. But of course these methods bring their own performance costs.

Other classical factoring algorithms have been developed from which the General Number Field Sieve is the most efficient. Its Time Complexity is expressed by which comes down for our 2²⁰⁴⁸ number N to a value of 7.04280… × 10¹⁶².
I did not calculate this on my slide rule, WolframAlpha was helpful once again.
The Field Sieve gives a massive improvement in time consumption of course compared to the trivial algorithm, but large numbers like 2²⁰⁴⁸ are still way out of reach.

The American Peter Shor developed a quantum algorithm in 1994 and this is still one of the few quantum based algorithms. It is particularly suited for factoring numbers and promises to be able to do this in a reasonable time.

Shor’s Algorithm

Having read about these issues, one would expect that the quantum computer starts attacking the two factor Number N of the size of 2²⁰⁴⁸ . The device is supposed to force N to reveal its factors, doing so with amazing speed due to the alleged capability of parallelism of the qubits.
But this is not how Shor’s algorithm works.

Instead of directly extracting the factors, the Shor’s algorithm first reduces the factoring problem to a problem of order-finding.
And then it uses the quantum computer to find the desired order.
Let me explain.

– The order problem

There is this old theorem that says: for any two whole numbers, a and b there exists a power r and a multiple m such that a^r= m x b + 1.
We prefer this statement written as: for a given r, a^r mod b = 1 is true. For this given r we can write: a^r ≡ 1 mod b.
_______
The value of the exponent r determines the cycle of the expression
We find this value by starting at 1 and increasing by one until a^r ≡ 1 mod b comes true.
_______

I give examples for both methods. We use 5 and 39 as a and b.
First a^r= m x b + 1.
5¹  = 5 = 0 x 39 + 5
5² = 25 = 0 x 39 + 25
5³ = 125 = 3 x 39 + 8
5⁴ = 625 = 16 x 39 + 1

Because the cycle repeats, we call 4 the order of our number choice. It is the value 4 that makes a^r ≡ 1 mod 39 true for a = 5.

It can be derived from the congruence a^r ≡ 1 mod b that b divides into a^r – 1 and this binomial can be factored using difference of squares.
But wait, how is a^r a square? Well, it is the square of a^r/2 since (a^r/2)² = a^r. Easy no?

So we can factorize a^r – 1 into (a^r/2 + 1)(a^r/2 – 1).
And because we know that these factors divide into b, we may proceed with looking for a common factor by using the good old Euclidean algorithm for the Greatest Common Divisor (GCD).
First 5^4/2 + 1 = 5² + 1 = 26.      —>              GCD(26,39) = 3
Then 5^4/2 – 1 = 5^{2 –} 1 = 24.        —>              GCD(24,39) = 13
And indeed these are the factors from the ‘large’ number b (39).

– Summary of the algorithm

It’s time to make a summary of Shor’s procedure to factorize the number N.

1. Make a wild guess for a factor of N and call it a.
2. Calculate f1 = gcd(a,N) the greatest common divisor of a and N
3. If f1 ≠ 1 then it was a lucky guess and the other factor f₂  is N/f1_.
4. If f1 = 1 (nontrivial factor not found) use the quantum order finding routine to determine the order of a^r mod b
5. If r not is even, go back to 1.
6. Calculate f1 = gcd((a^r/2, N) + 1) and f₂ = N/f1
7. Verify that f1 x f2 gives the number N.

The preparation and final work can be done on a classical computer, merely the order finding part runs on the quantum device.

_________________________________________________________________

The difference of squares

My high school math instructor wasn’t a passionate teacher.
His lessons were boring and unimaginative, which one day made us disciples inquire about the usefulness of all this abstract mathematics.

He thought long and hard and finally came up with an answer.
“Suppose you have to calculate the product of 505 times 495 and you do not carry pencil and paper.
There is no need for those items, since you can do it mentally.
Our numbers can be written as 500 + 5  and 500 – 5, does anything now come to mind?
Remember the lecture about the special binomials and in particular the binomial (a² – b²) which can be factored as (a + b)(a – b)? Well, our ‘a’ is 500 and our ‘b’ is 5 so we end up with the binomial 500² – 5² and it is blatantly obvious that its solution is 250.000 minus 25 which is 249.975.”

And triumphantly he looked around the class.
Many of us were still checking his result but eventually we argued that in real life one rarely gets such imposed opportunities and challenged him to give us the answer of 433 times 519 mentally. Or even (433 + 2)(433 – 2).
In those days calculators didn’t exist so he couldn’t cheat under his desk but he declared the lesson closed.

Much later I found that this special binomial (aka as the difference of two squares) often is used in a mathematical proof together with lots of other handy tools from the extended toolbox mathematicians have at their disposal. _________________________________________________________________

The quantum computer part of Shor’s algorithm

We saw that the factoring method of Shor shifted from exhausting stepwise trial division to a completely different path: the order finding approach.
This by itself is not new, the classic champion factoring method: the General Number Field Sieve takes the same route but though this Field Sieve gives a massive improvement on time complexity, it still is impractical for numbers as big as 2²⁰⁴⁸.

I think that at this point it is sensible to repeat the essence of this order finding. In the expression a^r mod N = 1 where a and N are coprime, we look for the smallest r which makes this true.
The exponent r follows a repeating pattern and after the first value of r that makes a^r mod N equal to 1, the pattern starts all over again. We call this value of r the order of the modular expression and from this we can extract the factors of N.

– How does it actually work?

Classic computers have to test r stepwise by increments of 1 and that is very costly. I showed here before that the Number Field Sieve brings a Time Complexity of 7 x 10¹⁶²  algorithmic steps

The quantum computer can do this much more efficient.
It can bring its qubits in a superposition of many possible states so that it can explore many values of a^r mod N at the same time. In essence it holds all these values in superposition. Of course it needs enough qubits to do this.

In mathematics Fourier Analyses frequently is used for finding a recurring pattern in data.
The quantum computer uses an enhanced form of this: Quantum Fourier Transform. This tool ‘visualizes’ the repeating pattern of a^r mod N and ‘highlights’ the order r.

It is not as simple as I just described (there is no simplicity in the quantum world) in fact the Quantum Fourier Transform is better designated as Quantum Phase Estimation.

There is obviously a resonance between the order pattern and the quantum phase of the qubits and the final output of the Quantum Fourier tool is in fact an estimation rather than a solution. Admittedly an estimation with a high probability but still an estimation. The final output always has to be verified but as we know it is not complex to multiply two numbers and compare the product with N.
Also, the quantum process can be repeated several times, each time gaining on reliability.

A perfect quantum computer (abundant number of qubits and noise and error free) would break down our number N in less than no time.

– What’s the current situation?

Not as positive as my text here suggests. In an article on Wikipedia I read:

Theoretical analyses of Shor’s algorithm assume a quantum computer free of noise and errors. However, near-term practical implementations will have to deal with such undesired phenomena (when more qubits are available, Quantum error correction can help).

and this:

In 2001, Shor’s algorithm was demonstrated by a group at IBM who factored 15 into 3 x 5 using an NMR implementation of a quantum computer with seven qubit. Later, in 2012, the factorization of 21 was achieved. In 2019, an attempt was made to factor the number 35 by Shor but the algorithm failed because of accumulating errors.

So there is no need to worry that our bank accounts will be hacked any time soon.

Notes

The most powerful (classic) supercomputer in the world now exceeds 1 exaFLOP — 1 quintillion (10^18) FLOPS —

Perhaps all the shared classic computing power in the world would be able to break the credentials of my bank account in a reasonable time, but rest assured that this is not worth all that effort.

Sources:

• https://github.com/Qiskit/textbook/tree/main/notebooks/quantum-machine-learning
• https://www.nature.com/articles/s41598-021-95973-w
• https://www.classiq.io/insights/shors-algorithm-explained
• https://en.wikipedia.org/wiki/Shor’s_algorithm
• and finally ChatGPT of course.

Author’s accountability

I hesitated long before starting to work on this essay. Internet research revealed that the info on the subject of Shor’s algorithm merely exists in two flavours:

1. Oversimplification as an attempt to make up for the incomprehensible.
2. Summaries from experts, only to be understood by their peers.

None of this could be used for a mid-level explanation on the subject.
I was about to give up, as much as I wanted to give my essay on RSA encryption a logical continuation by a quantum factoring lecture.

But just in time I found a Wikipedia article that hinted about an intriguing alternative technique of factorisation called order-finding. The paper continued with description of the involved quantum process.

Due to my earlier study of asymptotic encryption (RSA) and its modular arithmetic I could easily understand how the – non quantum based – order-finding scheme could reveal the factors of numbers.

I decided to start with my paper and to describe Shor’s algorithm up-to the paragraphs about the quantum processes. Shor called these preliminary steps the classical reduction. Once this part has been completed, I would consider whether or not to proceed with the quantum stuff.

So finally I started to read about the quantum part of Shor’s method.
I read about the bra-ket notation, about the tensor product that replaces the logical AND, about the eigenvectors and the continued fractions algorithm. None of this made much sense. This is the expert gibberish, not meant to enlighten an interested audience rather than impress their colleague experts.

And then I did what I said I would never do halfway a paper: I asked ChatGPT to help me out. And that is what Arty did. He provided me with some phrases I could use for my intended mid-level explanation. Of course I rewrote the text added stuff, left out other stuff and finally my essay was completed.

Thanks to Arty.

Eef, October 2024.

Editorial comment:

In this article, Eef refers to ‘Arty’ a few times. While loyal readers of Eef’s content know about Arty, let me explain this for new readers.
When using ChatGPT in dialogue form, you get to speak with the ChatGPT AI. For simplicity, Eef named this virtual persona Arty, as abbreviation of Artificial Intelligence.
If you chose the AI category on this site, you’ll get all our AI-inspired content which includes Eef’s earlier conversations with Arty.

Paul
October 2024

Editorial comment:

This article was continued with an addition that sheds more light of the link between theoretical math of Shor’s Algolrithm and the physical implementation of Shor’s in Quantum Computing. I highly recommend to also read that article.

You can find the article here.

Paul
December 2024