Shor’s Algorithm — Unravelling Encryption with Quantum
The first non-trivial quantum algorithm that, to implement, is comparable to the ‘Hello, World’ of classical computing.
In 1994, a mere nine years after David Deutsch devised the first quantum computational algorithm, Peter Shor, applied mathematician working at New Jersey’s Bell Labs, initiated the ‘beginning of the end’ for encryption schemes; that is, with a quantum algorithm of his own. Aside from exposing an unexpected vulnerability of present-day communications, Shor’s dramatic breakthroughs have fuelled the modern quantum information revolution, selectively demonstrating which classically unbreakable problems become tractable with quantum computation.
What begun as a fascination with the Bernstein-Vazirani problem, Shor, post-graduate school, exhaustively pondered the potential-for-disruption that quantum may-or-may-not hold. Even whilst surrounded by skeptics, he was fascinated by the feasibility of these devices. It was not until Shor had read a paper of Dan Simon’s, though, that his uncertain postulations transpired into one of the foremost pivotal QC advancements to-date. Given a certain function which can only be accessed as an oracle, Simon sought to determine its respective parameters; that is, if the function is one-to-one or two-to-one. Shor quickly came to realize that a similar period-finding mechanism holds for the factorization of integers — the heart of his polynomial-time quantum algorithm.
Before we jump into the body of this article, I must preface that this read will be very lengthy and slightly heavier on the math side. If you are more-so interested in the conceptual foundations of quantum computing, or simply want to explore a fascinating application of this technology in the pharmaceutical industry, feel free to give another article of mine a read. For those unfamiliar with quantum algorithms as a whole, I would recommend taking a look at my work on Deutsch’s algorithm; a much simpler circuit framework that, likewise, solves a much simpler problem than Shor’s.
Table of Contents
In order to delve into the abstract depths of quantum computing and gain an intuitive understanding of Shor’s Algorithm, we will begin with a brief exploration of classical encryption. Public key security relies upon a seemingly simple area of mathematics that many mastered in grade school; prime factorization. Like many complex topics, cryptography is best explained using an analogy. Suppose that there are two boxes of secrete colours, blue for one and red for the other. In addition to these two boxes, there is a third colour; yellow, which is shared to the public. Once said public colour is added to both boxes, each now has a unique, hybrid colour; the red one turning a particular shade of orange and the blue now a hue of green. These boxes of mixed colours, now ‘encrypted’, can be sent publicly. Considering it is easy to mix colours together, yet very difficult to ‘un-mix’ them, a bystander who observes these cross-bred colours cannot uncover what the initial secret colours are.
Just as combining colours is a very simple feat, the same principle holds for multiplying numbers. But going in the opposite direction — either returning a hybrid of colours to their original states or factoring a large number — holds exponential difficulty. An integer with a mere two-hundred digits would take the device that you are reading this article on seventy-five years to factor, hence the assumption that factoring thousands of digits on classical computers (even whilst operating in parallel) is practically impossible. Under RSA encryption, prime factors of a very large integer are utilized as keys, ones that are both public and private. While the public key, parallel to the above yellow colour, is used as an accessible address, the private keys are solely held by the sender and receiver of the sent data. The above analogy is an over-simplification, but, in essence, without both prerequisite keys, encrypted information is nonsensical gibberish. This process, though quite intricate in the classical world, can be shattered with the phenomena of quantum physics. Note that if your wallet is secured with a 2048-bit RSA, Shor’s factoring algorithm could break the encryption in just a few minutes; a process that a classical machine would accomplish in roughly a thousand years (if luck is in your favour).
While quantum computers are still in their infancy, a code-breaking catastrophe that threatens all public security remains a future possibility, not a peril. Nonetheless, in addition to its proof-of-concept and educational merit, many researchers and scientists foresee Shor’s Algorithm to, in the relatively near future, be straightforwardly scalable. As remarked by Kristin Lauter, a cryptologist at Microsoft, “once we have a quantum computer at scale in a future world, cryptography will have to be different”.
Quantum Fourier Transform (QFT)
For those with a background in engineering or mathematics, Fourier Transforms — the general class of decomposition functions for which QFT is a member — are no strangers. QFT’s are imperative for many quantum algorithms including Shor’s, so, to construct some intuition, let’s begin in the world of sound. Note that sound, itself, is a mechanical wave that vibrates away from its source, creating compressions and rarefactions in the surrounding medium which the ear interprets as noise.
Suppose we have the sinusoidal graph of an A note, as denoted as a function of air pressure and time. This pitch has a frequency of 440 oscillations per second, otherwise known as 440 Hertz (Hz).
A lower pitch note, such as D, holds the same structure, but with fewer oscillations per second (294 Hz).
By playing these two notes simultaneously, the function simply becomes the sum of each individual frequency. Points in which the peaks match up, or oppositely, where they cancel out, result in constructive and destructive interference, respectively.
The decomposition of the final graph; that is, the summation of two pure frequencies, is where our problem lies. Enter the mighty Fourier transform.
We can take the above, combination graph, and, bear with me, ‘wrap’ it around a circle. In short, the amplitudes of the given function transform to the oscillating distance from the origin. Note that as the mapping frequency changes, otherwise known as the rate at which the original function is ‘wrapped’ around the circle, the shape of the new graph likewise changes. And as said shape changes, the x-coordinate of its centre of mass moves as well. By creating a third graph of the centre of mass x-coordinate as a function of mapping frequency, we observe a very profound trend. When the mapping frequency is equal to one of the pure sound frequency components, there is a spike in the x-coordinate location. This occurs for each pitch that combines to make the above, hybrid sound signal. By observing this deconstruction, we can conclude that the Fourier Transform is simply a frequency domain view of the original time domain function.
The QFT, in essence, is nothing more than a quantum application of this mathematical construct; a shift of basis states to obtain a desired yield. In the computational basis, numbers are stored using the binary values of zero and one. The Fourier basis, however, exhibits numerical values using superposed quantum states. Visualizing this concept with the Bloch sphere, let’s consider the single-qubit case; the Hadamard transform. This gate takes the Z-basis states, |0⟩ and |1⟩, and, post-QFT, outputs the X-basis states, |+⟩ and|−⟩. For multi-qubit systems, this transform acts in an identical manner, where different numerical values are represented by respective qubit rotations about the Z-axis. To fully gauge this rigorous concept, let’s explore it mathematically.
The QFT utilizes a discretized family of rotational operators, Zᵩ gates. They act upon qubits as follows:
While a |0⟩ state qubit remains unchanged, for a given positive number, φ, the Zᵩ gate rotates the |1⟩ state qubit about the Z-axis by an angle of 2π/2ᵠ. We can further dissect this through the general task of rotating |ψ⟩ about the Z-axis by an angle 2π/2ᵠ J; that is, applying Zᵩ on |ψ⟩ j-times. With a slight nuance to the above unitary, the matrix for this problem is,
As ‘J’ is a base-ten number, it can be denoted in binary as:
Now, accounting for the phase, beginning with the reciprocal 2ᵠ component:
To finalize this mathematical breakdown,
In short, where N = 2ⁿ basis state, we can say that,
Let’s now observe the QFT in action. As mentioned above, the single-qubit case of a QFT is a Hadamard gate:
In a more general mathematical proof,
To build a circuit that performs the QFT on n-qubits, two ingredients are needed; Hadamard gates and controlled unitary rotation gates (UROTᵩ); an adaptation of the Zᵩ gates outlined above. Recall,
In its most general form, the QFT circuit is constructed as follows:
To fully understand what is going on, let’s walk through this system step-by-step.
Step 0
Step 1
Step 2
Step 3
Step ‘n’
Note that a likewise process occurs for the following qubits. A SWAP gate is then applied such that the qubit’s phases are ordered according to conventional sequence.
QFT in PennyLane
Having investigated the mathematical backbone of the Quantum Fourier Transform, we can now program the algorithm component using PennyLane’s framework. Note that I have coded the inverse QFT for reasons that will become clear in subsequent sections of this article.
Inverse QFT — Specific Case (Four Qubits)
Firstly, we must define a phase-shift function (UROTᵩ).
Then, we follow the inverse circuit structure by applying Hadamard gates and phase shifts in their appropriate order. The final step is to measure the qubits and call the circuit.
Inverse QFT — General Case
In addition to constructing a four-qubit specific circuit, I have also coded a general, n-qubit program.
Quantum Phase Estimation (QPE) — Shor’s Subroutine
Now, with the technicalities of QFT under our belts, we can delve into its foremost fundamental application; Quantum Phase Estimation. Given a unitary matrix, U, and a prepared eigenvector, |ψ⟩, the algorithm estimates the phase, θ, where θ ∈ [0, 1) such that,
Below is the general case for a QPE circuit. Note that with an increased number of top-register qubits, the accuracy of theta estimation, likewise, becomes greater.
The first step involves applying an n-bit Hadamard gate operation on the counting register.
After applying the n-controlled operations as per the above circuit, with 0 ≤ j ≤ n-1, we are left with,
Or, more concisely, as,
The perceptive reader might notice that this stage of QPE appears incredibly similar to that of QFT, the only relevant difference being the incorporation of an inverse 2ⁿ:
Therefore, by performing an inverse QFT, given below:
And sparing the reader — as well as myself — any further calculation, the remaining state is,
By simply dividing by 2ⁿ, we have found θ.
QPE in PennyLane
Let’s observe a simplistic example of QPE at work, where |ψ⟩ = |1⟩ and U = T; the well-known T-gate acting on a basis vector. Recall the T-gate unitary matrix, which, when acting upon |1⟩, appears as follows:
Since QPE estimates θ, where,
Should we run the algorithm under these parameters, we expect to determine a phase of 1/8. Let’s observe this under PennyLane’s framework. We begin by appropriately initializing the qubits with Hadamard transforms or, for the final qubit, an X-gate.
Next, we perform the controlled unitary operations.
We must now apply the inverse Quantum Fourier Transform. For the sake of simplicity, rather than use the lengthy, variable-saturated code I developed in the previous section, I applied PennyLane’s pre-existing QFT operator. Finally, the counting register must be measured.
With certainty, we get a singular result each time; 001. This translates to the integer value of one. Now, in classical post-processing, by dividing our result by 2ⁿ, we get θ.
Shor’s Algorithm
With the necessary prerequisites covered, we finally reach the crux of this article; Shor’s Algorithm. We begin with a topic that, surely, our twelve-year-old selves loved oh-so-dearly — factorization. Suppose we have a large integer, denoted as ’N’. ’N’ is made up of factors, ‘g’ and ‘h’. Shor’s Algorithm begins with, well, for a lack of better words, a ‘crappy’ guess that is < ‘N’. Although it’s possible that this random conjecture could be a factor of ’N’ (or even share a factor with ‘N’), especially when working with larger integers, it’s highly unlikely. In essence, Shor’s Algorithm takes our poor guess factor into a better one.
And it’s all based upon a simple mathematical framework.
For any pair of whole numbers that do not share a factor (for example, ‘a’ and ‘b’), if you multiply one of them by itself enough times (a ⋅ a ⋅ a ⋅ a …), you will eventually arrive at some whole number multiple of the other number plus one ( … = x ⋅ b + 1). In short,
Suppose that a = guess number, and b = ’N’. We are guaranteed that ‘a’ to some power, ‘p’, is equal to a constant multiplied by ’N’ plus one. By subtracting the one from both sides, and expanding using my tenth-grade difference-of-squares factoring skills, we can now write this using two terms; that is, Shor’s new-and-improved output guesses, which are (almost) factors of N:
Simple, right?
Well, not quite. There are a few intricacies to Shor’s Algorithm. Firstly, the ‘p’ value cannot be an odd number. If we raise our guess number to an odd/even fraction, the yielded value will likely become a decimal value, which is of no use in the investigation of factors. The reader might also be wondering how we determine what ‘p’ actually is, which is where quantum computing comes in. In short, quantum computation harnesses the ability to simultaneously cycle through a bunch of possible values which are arranged to destructively and constructively interfere for the incorrect and correct answers, respectively. As we further examine the algorithm’s technicalities, this will become more intuitive.
Recall the first equation that we derived above. We can expand upon this further to include the desired ‘p’ value:
Note the repeating nature of this mathematical construct. When ‘a’ is raised to some power, ‘y’, with any multiple of the ‘p’ value added to or subtracted from ‘y’, the output is a changing multiple of ‘N’ multiplied by ‘N’ plus ‘r’. Realize that ‘r’, the amount more than a multiple of ‘N’, does not change! I invite the reader to confirm this for themselves by substituting numerical values into the above equation. Suppose, in a quantum computation that superposes all possible powers of ‘a’, we measure the ‘r’ term. In return, the program will yield the the correct powers for which ‘r’ is the remaining value to be added to a multiple of ‘N’. And because of the repeating property I mentioned previously, all said outputs will be ‘p’ apart, or rather, have a period of ‘p’, which brings us back to our trusty Quantum Fourier Transform. In short, by passing a superposition of values that are separated by an amount, ‘p’, through a QFT, interference yields the single quantum state, 1/ ‘p’; that is, one over the period, otherwise known as a familiar term from the QFT section; frequency.
Let’s now run through the protocol for Shor’s Algorithm which depends entirely upon the above period finding problem. Given a periodic function, there exists an ‘r’ of ‘a’ where aʳ mod N is equal to one. And further, given integers ‘N’ and ‘a’, we must find the smallest positive integer ‘r’ such that aʳ - 1 is a multiple of ‘N’.
We begin by randomly selecting an integer, ‘a’ that is co-prime (shares no common divisors) with ‘N’. Suppose, for the sake of simplicity, ‘N’ — the number we want to factor — is equal to 15 and our ‘a’ value is 13. Since their greatest common divisor is one, these two numbers are adequate inputs for Shor’s Algorithm. This has been — and will continue to be — a pretty variable-heavy section of this article, but bear with me here. To begin our quantum circuit, we will prepare four qubits as our counting, ‘x’, register, and four for the unitary to act upon, the ‘w’ register. See the circuit below for reference.
Note that the following notation will express the values of the qubits in binary, rather than their actual, four-bit representation.
Step 0
Step 1
While the ‘w’ register begins in the |0⟩ state, the ‘x’ register, after passing through Hadamard gates, has qubits in the positive superposition.
Step 2
This section of the circuit is where the order-finding framework comes into play. Recall that the function we seek to apply is as follows:
Applying the unitary thereby gives the transformation,
And for the specific case of our qubits,
Note that 0⊕ Ƶ= Ƶ for any integer, Ƶ, in four-bit representation.
Step 3
Now, after measuring the ‘w’ register, suppose we yield seven. With our qubits entangled as a result of the controlled unitary application, what remains in the computation are those ‘x’ register qubits that correspond with a ‘w’ register value of seven. Notice the normalization change due to only four conditions now present.
Step 4
We are now prepared to pass our ‘x’ register through a Quantum Fourier Transform:
When this is computed, remarkably, only four values in this continuous summation for ‘y’ are non-zero. This is quantum interference at its finest; getting rid of the wrong answers whilst making the right ones more pronounced.
Step 5
Finally, we must measure the ‘x’ register, which, if performed correctly, yields zero, four, eight, or twelve with equal probability, as per the above equation.
Classical Post-Processing
We can now analyze what happens for each outcome outside of the quantum world. It is pertinent to note that the measurement results for this algorithm peak near j(2ⁿ/r) for some integer, ‘j’, such that j ∈ Ƶ and ‘n’ represents the number of qubits. Let’s break this down on a case-by-case basis.
Measure |0⟩
This is the singular trivial answer for any number we seek to factor. If |0⟩ is yielded as an output, the algorithm must run again.
Measure |4⟩
Measure |8⟩
Measure |12⟩
QPE in Disguise
Through some careful investigation, we can see that the Shor’s Algorithm unitary in which the function, aˣ(modN), is applied, we are performing a near identical operation to that of quantum phase estimation.
Recall,
Such that,
We can see that by implementing this oracle, we are actually passing the qubits through a modular exponentiation circuit, which, indeed, is why quantum phase estimation is considered Shor’s subroutine. In reality, the algorithm’s schematic is,
The product is actually an eigenvalue for the function, thereby yielding an ultimate phase that is a multiple of the reciprocal of ‘r’.
Shor’s Algorithm in Qiskit
As I have been getting pretty comfortable with programming in PennyLane, I decided to switch it up and use Qiskit to code a simulation of Shor’s Algorithm.
We must first define our ‘N’ value as well as establish what constitutes an appropriate ‘a’ value. If ‘N’ is divisible by ‘a’, we have found a factor and do not need to perform Shor’s Algorithm.
Next, I created the gate for the function we defined above. This series of SWAP gates is hardcoded for N = 15 and taken directly from the Qiskit textbook.
We then define our modular exponentiation function.
Next comes the inverse QFT.
We must now make a final circuit function, which includes all the above gates/operations.
Lastly, we define our registers, call the function, and draw our circuit.
Let’s get the results!
Note that I ran the code until I had an ‘a’ value of 13 such that it is consistent with the above descriptions.
And with that, our program yields 0, 4, 8, and 12, with relatively equal probability — exactly what we expect.
While factoring an integer as manageable as fifteen might seem trivial, the ability to do so on a quantum computer, nonetheless, suggests that, though unfeasible in current standings, Shor’s Algorithm may — one day — render RSA useless.
Well, in a far-from-brief read, we have covered the many complex sub-procedures of Shor’s factoring algorithm, as well as had a detailed look at the algorithm itself. I invite the reader to revisit the sections where intuition might lack. Remind yourself that these topics are incredibly complex to the untrained eye, and without doubt, will require both practice and repetition to fully comprehend.
If you enjoyed or learned something new from this article, feel free to share. Connect with me on LinkedIn, visit my personal website, and/or shoot me an email at anytime. You can also subscribe to my newsletter, here.