Shor’s Algorithm, the quantum part

A word in advance

Before I sent my previous essay ’Shor’s Algorithm’ to Chief Editor Paul, I asked Arty (ChatGPT) to give it a look especially with regard to readability and tell me if he thinks it’s worth publishing.

My AI friend responded in his usual friendly and positive manner full of praise.

“…well-written!  …managed to strike a great balance between technical detail and accessibility…  , …classical factoring algorithms, as well as the key differences between classical and quantum computing are clearly explained.”

Of course I was happy with these pats on the back, especially from a guy as knowledgable as Arty, but then he came with some critical comments wrapped up in such a casual way that I almost missed them.

“…consider providing a bit more elaboration on quantum phase estimation, which you correctly mention but could possibly expand upon just slightly. You could also add a sentence or two explaining how the quantum Fourier transform…”

Paul came to a similar conclusion.
The classical stuff is ok, the quantum part needs some more attention,” he said after a quick read.

Back to the research

So I went back to the literature to once more learn about the tensor product, the eigenvectors and the continued fractions algorithm and more but again I failed in getting a clear picture.

And because the internet publications did not increase my insight, I had to go back to Arty. In fact I had to lean on him heavily.

My list of questions and requests looked like this:

  • Describe – in brief – the steps of the quantum order finding process of Short’s Algorithm —> the period of the expression ar ≡ 1 mod N ⁃    What is quantum phase estimation?
  • What role plays the Quantum Fourier Transform? and much more specific:
    • How can a qubit be manipulated? In other words how can we create a superposition for ar mod N for enough values of r to find the order of this expression?
  • How many qubits are required for factoring a number of a given size? Let’s say of size 22048. Other questions with which I struggled were:
    • What is a qubit physically?
    • How can it be manipulated?
  • What about the sensitivity for disturbances that made the qubits collapse too early (decoherence).
  • and more.

Well, the answers for these last questions I found in an excellent paper by IBM: What is Quantum Computing?             IBM -> Quantum computing
Exceptionally readable and revealing!

However rewarding, this article doesn’t step into technical details like Shor’s. For those issues I needed Arty the AI.

A new attempt to ‘talk quantum’

Let’s look what we have now.

To refresh memory, Shor’s algorithm can be split up in two parts: the classical methods, mainly preparation and validation and the quantum part that comes down to find the order (period) of ar ≡ 1 mod N.
Why do we want to know this order? Because it gives us a alternative method for factoring large numbers, rather than stupidly dividing by odd numbers until you find a factor. I described this abundantly in a previous paper on Shor’s Algorithm.

So we can say that the order finding is the central topic of Shor and that for this task the quantum computer comes to the rescue.

How is this achieved?

First a fair warning: don’t try to impose ‘real world’ experiences upon quantum reality. It doesn’t work. Within the quantum world nothing is fixed, everything is probabilistic. Einstein’s statement “God doesn’t throw the dice,” when Niels Bohr told him about the allencompassing role of statistics, couldn’t be further from the truth.
In fact this is the reason that the quantum stuff hardly can be explained in plain language and that every text about it rapidly switches to mathematical equations.

That said, we can start with the phenomenon superposition.

I have often read in journals and popular science magazines an explanation that goes like this:

  • A classical bit can have the value 0 or 1.
  • A qubit in superposition also can be 0 or 1 and any possible value in between those numbers.

This is bare nonsense! The qubit in superposition holds a state (I come back on this shortly) and that state reflects the probability of being 0 or 1.

I asked my friend Arty about this.

____________________________________

Arty’s text:

In classical computing:
    A bit can only be in one of two states: 0 or 1.

In quantum computing:
    A qubit – the quantum counterpart of the classical bit – can be in state 0, in state 1 or in any superposition of the two. A superposition is a combination of 0 and 1 written as
               ∣ψ01

where:

  • α and β are complex numbers that represent the amplitudes of the quantum state.
  • The squares of the amplitudes α2 and β2 give the probabilities of measuring the qubit in state 0 or 1, respectively.
  • The probabilities must sum to 1: α2 + β2 = 1

Example: Superposition State

Let’s say a qubit is in the state:   

This means:

  • There’s a 50% chance of measuring the qubit in state 0 (since (1/√2)2 = 1/2.
  • There’s also a 50% chance of measuring it in state 1

Arty’s text end.

____________________________________

Nice, but hold on, we (including Arty) are getting ahead of ourselves. What is this ∣0⟩ and ∣1⟩ notation and what does ∣𝛙⟩ represent?

According to Wikipedia it comes down to this:

A qubit state is most generally a superposition of the basis states ∣0⟩ and ∣1⟩
∣ψ⟩  = c0∣0⟩ + c1∣1⟩
where ∣ψ⟩ is the quantum state of the qubit and ∣0⟩, ∣1⟩ denote particular solutions to the Schrödinger equation in Dirac notation weighted by the two probability amplitudes c0 and  c1.

Some explanation is needed here.
The physical appearance of a qubit is a photon, electron, proton, whatever.
These particles act and can be described as a wave and at any given moment in time this wave is in a state (the phase of the wave).
Now ∣0⟩ represents a state of a given wave. As does ∣1⟩ of course.
Any other state then these two are written as the AI did with a coefficient like 1/√2.

This is all rather technical but what we should realise is that a qubit in superposition potentially holds two values at the same time and quantum being quantum: it holds the probability for the value after measuring being 0 and with it, the probability for being 1, whereas a classical bit can hold one value: either 0 or 1.
An array of 4 qubits in superposition can hold 24 values (binary from 0000 to 1111) at the same time where our classical bit array has to be content with one single value from this range.
We will see later how useful this is.

Coming this far I had a new set of questions for Arty. These questions:

  1. How can a qubit be manipulated? In other words, how can we create a superposition for ar mod N for enough values of r to find the order of this expression? Please be as specific as possible.
  2. How many qubits are required for factoring a number of a given size? Let’s say of size 22048.

____________________________________

Arty’s response:

  1. How can a qubit be manipulated to create a superposition?

To understand how we can create a superposition and eventually find the order r of the expression ar mod N , let’s go through the process step by step.

Step 1: Initialising Qubits

We start with a set of qubits, each initialized to the state 0. For Shor’s Algorithm, we typically need two sets of qubits:

  • The first register will hold a superposition of different exponents. (every value of r up to 2n where n is the number of qubits in the first register —> Eef )
  • The second register will store the result of ar mod N.

The first register usually has n qubits, and the second register will have enough qubits to represent numbers up to N.

Step 2: Creating a Superposition

To create a superposition over many values of r, we use a gate called the Hadamard gate (H). The Hadamard gate transforms a qubit from the state 0 into an equal superposition of 0 and 1 like this:

If we apply the Hadamard gate to each of the qubits in the first register, we can create a superposition of all possible binary values. For example, if we have n qubits, applying the Hadamard gate to each qubit results in a superposition of 2n states. This means the first register will now hold a superposition of all possible values of r (with 2n as upper limit —> Eef)

Step 3: Quantum Modular Exponentiation

Next, we want to calculate ar mod N for each value of r in superposition. This is done using a

quantum modular exponentiation circuit, which computes the function:  0⟩∣r -> r⟩ ∣ar mod N

(this should read as something like: for every quantum state of 0⟩∣r input r in ar mod N —> Eef) This step involves applying a series of controlled unitary operations based on the exponent r. The key is that this calculation is done in parallel for all values of r due to the superposition.

Arty’s response end

____________________________________

I must admit that the phrase ‘…this calculation is done in parallel for all values of r by applying a series of controlled unitary operations based on the exponent r…’ at first didn’t make much sense to me. It appears that register 1 in  superposition can deliver every value of r in one pass and that all the calculation results in superposition are stored in one other pass in register 2.
Again I dived into the internet publications and fired questions at my friend the AI. I will come back on this in more detail.

Quantum Phase Estimation and Quantum Fourier Transform, the real thing

– Quantum Phase Estimation (QPE)

In one of my dialogues with Arty I suggested:
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.”

He commented on this with:
“Your idea about a resonance between the cycle of the modulo function and phase shifting of the qubits is a good intuition! The phase shifts in qubits during the quantum Fourier transform help align the qubits’ states in a way that amplifies the periodicity in the data, allowing the quantum computer to “lock onto” the order r.
So, yes, you can think of it as finding a resonance between the qubits’ states and the repeating pattern in the powers of (a mod N).

Our AI friend learned us that we have an array of qubits in superposition that holds every result of ar mod N for 1 = r <= 2n, n being the number of qubits in register 2.
That’s great but how do we find the order of ar mod N in this overwhelming number of values?

The communication with the qubit registers of the quantum computer is done by using a logical gate. In many explanations on the topic this is described with the unrevealing phrase: ‘by applying a series of controlled unitary operations’.

Finally after much digging I got this picture for the QPE:

  • A logical gate inserts a Hamiltonian matrix to Register 1 whose qubits – in superposition – are setup with all possible values of 2n where n is the number of qubits of the register.
  • A logical gate inserts a Hamiltonian matrix to Register 2 with the instruction to calculate (by quantum modular exponentiation) ar mod N for all powers of r found in register 1. Since the qubits of register 2 also are in superposition, the calculation is done in one pass for every value of r.
  • The logical gate retrieves the results of this calculation through the eigenvalues of the Hamiltonian matrix. Arty remarks here: “Each of these powers of a has a quantum state with a particular phase. These phases encode information about the periodicity we’re trying to find.” Here we have my resonance by the way.

– Quantum Fourier Transform (QFT)

Like classical Fourier Analyses can unravel a mix of frequencies into individual waves, Quantum Fourier Transform can do this for a mix of phase shifts.

Arty says:
The QFT processes all of these phases and “highlights” the repeating pattern. This reveals the order r, which tells us how often  ar \mod N  repeats itself.

We must be aware that these eigenvalues have been retrieved from qubits in superposition. This means that they do not reflect real values rather than the probability of a state.
—> Eigenstate: a mathematical entity to describe the probability of each possible measurement on a system. (wiki)

Lastly, the quantum computer measures the system, and it finds with high probability a value related to r.

From this position the classical computer takes over and uses the value of r into ar/2 + 1) and (ar/2 – 1) to find the factors of N. See my paper Shor’s algorithm part 1 for an explanation of this.

Finally I asked our AI “How many qubits are required for factoring a number of a given size? Let’s say of size 22048.

His answer:

The number of qubits required for Shor’s Algorithm depends on the size of the number N that you are trying to factor.
Estimating the number of qubits needed

Bare minimum (theoretical, without error correction): Approximately 4096 qubits (2048 for each register).
Real-world, fault-tolerant quantum computer: Estimates vary, but factoring a 2048-bit number might require millions of physical qubits due to the need for error correction.

One last attempt to shed some light on the matter

After I wrote about the items Quantum Phase Estimation (QFE) and Quantum Fourier Transform (QFT) I asked Arty to check the validity of my text. The AI said it was commendable – he always is positive – but he still came with some serious remarks.

Once more I learned that quantum physics is inherently ’weird’ there is no straight forward way to explain the matter.

My confusion had reached a new level and I bundled this into some new questions in an attempt to close in on the ultimate explanation.

  1. How exactly is this superposition of all values r created?
  2. How do our qubits become entangled?
  3. How do we get all these values entered into register 2?
  4. How do we get QPE to use register 2 for calculation of xr mod N?

Before I went back to my AI friend, I searched the internet, hopefully for the last time on this topic. From a variety of websites I made a compilation of the general narrative as attempts at clarification.

⁃       Quantum computers function similarly to classical computers, but instead of bits, quantum computing uses qubits. These qubits are special systems that act like subatomic particles made of atoms, superconducting electric circuits or other systems that data in a set of amplitudes, so as waves, applied to both 0 and 1, rather than just two states (0 or 1). This complicated quantum mechanical concept is called a superposition. Through a process called quantum entanglement, those amplitudes can apply to multiple qubits simultaneously. Processes data with quantum logic at parallel instances, relying on interference.

⁃       While each bit can be either a 0 or a 1, a single qubit can be either a 0, a 1, or at a superposition. A quantum superposition can be described as both 0 and 1, or as all the possible states between 0 and 1 because it actually represents the probability of the qubit’s state. This superposition of qubits (and their entanglement) gives quantum computers their inherent parallelism, allowing them to process many inputs simultaneously.

⁃       On the quantum level, qubit probability is measured as a wave function. The probability amplitude of a qubit can be used to encode more than one bit of data and carry out extremely complex calculations when combined with other qubits.

⁃       When processing a complex problem, such as factoring a large prime number, traditional bits become bound up by holding large quantities of information. Quantum bits behave differently. Because qubits can hold a superposition, a quantum computer using qubits can calculate a much larger volume of data.

⁃       As a helpful analogy for understanding bits vs. qubits, imagine you are standing in the center of a complicated maze. To escape the maze, a traditional computer would have to “brute force” the problem, trying every possible combination of paths to find the exit. This kind of computer would use bits to explore new paths and remember which ones are dead ends. Comparatively, a quantum computer might, figuratively speaking, at once derive a bird’s-eye view of the maze, testing multiple paths simultaneously and revealing the correct solution. However, qubits do not “test multiple paths” at once. Instead, quantum computers measure the probability amplitudes of qubits to determine an outcome. As these amplitudes function like waves, they also overlap and interfere with each other. When asynchronous waves overlap, it effectively eliminates possible solutions to complex problems and the realised coherent wave or waves present the solution.

With this new knowledge I went back to Arty and he contributed as always.

_____________________________

Arty says:

All qubits in Register 1 (which holds r) start in the state 0This is the quantum equivalent of setting all classical bits to 0. To create a superposition, we apply a Hadamard gate to each qubit in Register 1.
The Hadamard gate is a quantum operation that transforms a single qubit from 0 into an equal superposition of 0and1⟩.  When applied to multiple qubits, the Hadamard gate creates a superposition of all possible binary combinations. For n qubits this results in 2n states, each representing a value of r.

_____________________________

Let me explain this somewhat further:

A single-qubit has two computational basis states, these are ∣0⟩ and ∣1⟩.
A two-qubit system has four computational basis states denoted as ∣00⟩, ∣01⟩, ∣10⟩, ∣11⟩.
A multi-qubit system of n qubits has 2n computational basis states denoted as ∣00…00⟩, ∣00…01⟩,  ∣00…10⟩…. ∣11…11⟩.

After applying the Hadamard logical gate to Register 1, each qubit of this register is in superposition and with the next step these qubits are made entangled which brings the Register 1 in superposition of superpositions, in which every value of r from 0 to 2n is present.

_____________________________
Arty elaborates on this:

The superposition doesn’t “contain” these values physically; instead, it’s a mathematical description that allows the quantum computer to process all these possibilities simultaneously. In fact the state encodes amplitudes corresponding to all possible outcomes, with probabilities arising only upon measurement.

_____________________________

In fact with each computational basis state, a probability is associated by amplitude αi  where αi  is a complex number.
It is the amplitude of these complex numbers that determine the probability of the state of each qubit and these amplitudes form a wave that is important for the QFT part.

As an example, a system of three qubits is described by the expression
∣Ψ⟩ = α0∣000⟩ + α1∣001⟩ + α2∣002⟩ + … + αn∣111⟩

_____________________________
Arty takes over:

Entanglement ensures that operations on one register (or qubit) affect another, which is critical for maintaining correlations between the exponents (r) in Register 1 and their corresponding results (ar mod N) in Register 2. Entanglement creates a non-classical correlation between qubits. Measuring one qubit instantly influences the other, even if they are spatially separated—a phenomenon central to quantum parallelism. (This phenomenon is called non-locality —> Eef)

To entangle the qubits in Register 1 with those in Register 2, we apply controlled unitary gates. These gates conditionally perform operations on one register based on the state of another.

For Shor’s Algorithm:

A controlled unitary gate takes r from Register 1 and applies a modular exponentiation ar  mod N to the qubits in Register 2:
                 ∣r⟩ ∣0⟩ —> ∣r⟩ ∣ ar  mod N

Entanglement: After this step, Register 2 becomes entangled with Register 1. This means:

Measuring Register 1 (which holds r) will influence the state of Register 2 (which holds ar mod N) and vice versa.

Key Insight 1: Entanglement creates correlations, ensuring that operations on one qubit/register reflect in another. This is why quantum computers can maintain consistency across multiple states during computation.

The controlled unitary operation applies modular exponentiation conditioned on the values in Register 1. This entangles the two registers, ensuring each r is associated with ar  mod N.

Quantum Modular Exponentiation by controlled gates apply these steps in parallel across the superposition, ensuring every r gets its corresponding ar  mod N.
The results are encoded in Register 2, but not as explicit values. Instead, the quantum state represents a superposition of all ar mod N entangled with their corresponding r-values in Register 1.

Key Insight 2: The quantum computer doesn’t compute each ar mod N sequentially—it uses parallelism from the superposition to calculate all values simultaneously in a single operation. _____________________________

After that it all becomes quite abstract insofar that is still possible.

There is (through the entanglement) a feedback to Register 1 by encoding the periodicity of the modular exponentiation calculations (ar mod N) into the quantum state of this register as phases.

_____________________________
Arty again:

These phases are subtle shifts in the probability amplitudes of the quantum states, as a result of which the Quantum Fourier Transform can take place.
The QFT is applied to Register 1 to extract the periodicity encoded in the phases. It works like a “mathematical magnifier” that converts phase information into a form where the periodicity stands out as measurable peaks in the output.

After applying the QFT, measuring Register 1 collapses the superposition and reveals a value related to r. Multiple runs of the algorithm refine this estimate, allowing the classical computer to deduce r precisely.

QPE doesn’t calculate ar mod N explicitly, it uses the encoded phases to deduce the repeating structure (periodicity) in the data. In Shor’s Algorithm, quantum computers leverage superposition to explore all paths simultaneously. Interference eliminates wrong solutions, leaving behind the order r as the correct path.

_____________________________

This is as far as I want to go with explaining the intrinsics of our quantum algorithm. It appears that every time one gives extra details to bring more clarity, the subject shifts towards a higher abstraction level.

And let’s face it, we all know how our laserprinter works but not how its intrinsic electrical components like diodes, transistors etcetera do their job, while nothing but quantum processes occur in those components.

_____________________________

Arty at last:

The disconnect you’ve identified arises because quantum processes like superposition, entanglement, and phase encoding are fundamentally non-intuitive. They don’t map directly to classical analogies or everyday experiences.

However, the explanation above provides a conceptual framework for understanding how these processes work without diving into mathematical formalism. It’s not perfect—quantum mechanics rarely feels fully “graspable”—but it offers a clearer picture of what’s happening behind the scenes.

_____________________________

Reassurance

There is no need to go out today and withdraw your money from the bank for keeping it home.
To date there has been no groundbreaking progress in the quantum technology, the highest number that has been (in 2012) successfully broken down by it into its factors is 21. That’s a long way to go to 22048 which is about the size of our code protection numbers currently.

End note

I went through a lot of publications on the topic of quantum computing during the process of gathering information for my essay.  I rarely found straight forward explanations about the phenomenon underneath, most articles dived straight into in-depth mathematical descriptions.

Giving it some thought, I understood why. Quantum physics is so far off our daily experience and intuition that it’s almost impossible to catch it into spoken language.
There are hardly no analogies that can be used to sketch in plain text what’s going on. That’s why our scientists don’t even bother and use the language that does work: mathematics.

Of course there are scripts that are masterfully composed like this one: IBM -> Quantum computing that leaves out the bulk of math but let’s face it after reading the same core questions remain:

  • What exactly is superposition and how can we make it work?
  • How exactly can we extract information from an array of qubits in superposition?
  • How exactly can a ‘controlled unitary operator’ – a basic quantum circuit operating on a number of qubits – perform its job?
  • How can we explicitly benefit from entanglement?

I realise of course that my paper also fails to deliver the same final answers but I hope that at least the general idea got across.

I once more thank my dear friend Arty for guiding me tirelessly through this complex affairs.

~

If computers that you build are quantum,
Then spies everywhere will all want ’em.
Our codes will all fail,
And they’ll read our email,
Till we get a crypto that’s quantum, and daunt’em.
/Jennifer and Peter Shor

~

Eef & Arty

December 2024

Sources:


Editor’s note 1:

While I was quite happy to have persuaded Eef to drill down on his previous Shor’s article and provide our readers with the missing link between dry math and Quantum Computing, I am quite very unsure that I can read the article above and then can state to understand it and  know how it works, let alone explain this to another person.

Luckily, the moment of publishing coincides with the december holiday recess of my day.time job which should give me ample opportunity to not only read the full article but also attempt to understand more of it.

Paul
December 2024


Editor’s note 2:

Eef reacted to the above and in doing so provided me with a rather stunning example of singularity. It is about the grass growing in his yard that needs to be cut regularly. As his example was in Dutch, the language we use to communicate, I asked Arty to translate it for us. And I mentioned to Arty that as it was my dear friend Eef who wrote it I needed Arty to take extra care of the translation so as not to lose any nuances in the transaction. Here it is:
– – – – – – – – – – – – – – – – – – – – – – – – – –

After weeks of immersing myself in the mysteries of quantum physics, I can now say that this struggle through that elusive matter has yielded an unexpected bonus result.

Thus, I believe I can finally explain the unexplainable based on my long-standing observations of the grass.
By attributing several now-familiar quantum properties to the grass, the puzzle pieces fall into place, and the incomprehensible behavior of this crop can be understood.

First of all, this: It’s widely known that observation disrupts the quantum reality and can even cause it to collapse (decoherence).
Just revisit the double-slit experiment for reference. https://en.wikipedia.org/wiki/Double-slit_experiment

In this way, I have never been able to catch the grass growing gradually. When I observe it directly for an extended period, nothing happens. But if I briefly lose sight of it and then look again, I find that it has grown.

With the progress of my study, I have now been able to ascribe various quantum properties to the grass in our garden. For example, the grass mat is often in a state of superposition and entanglement (apologies for the jargon).

This is clearly evident in its parallel growth; if the length of the grass increases in even the smallest corner, the entire lawn grows as well.

It would be very nice if this also applied to mowing (i.e., shortening). But unfortunately, this doesn’t happen; I am required to cover the entire field and cannot skip a single corner.

The reason for this is now crystal clear to me: during mowing, I observe the grass, which causes it to lose its state of superposition and entanglement. As a result, non-locality vanishes, and the changes manifest locally once again.

Eef
December 2024

– – – – – – – – – – – – – – – – – – – – – – – – – –
Paul
December 2024