Originally posted at the Classiq Blog on July 3rd 2024.
Why is Shor’s algorithm such a keystone application of quantum computing? This is the first algorithm many hear about when diving into the world of quantum technology.
Though the applications that we hope to achieve with quantum computing could allow for advances in fundamental physics, medicine, materials, and many other industries, Shor's algorithm, invented by Peter Shor in 1994, demonstrated one of the first practical use cases and the potential of quantum computers by breaking the security of many of our asymmetric encryption systems used today, like RSA and ECC cryptography.
The goal of Shor’s Algorithm is to find the prime factors of a large number, which are used to secure data sent across the internet. This problem is very difficult for classical computers, especially as the numbers get larger. In the classical world, the time it takes to factor these numbers increases exponentially with their size. But Shor’s algorithm accelerates the factoring process by transforming it into a problem of finding the period of a function, which means increasing the size of the number to break (the key size of the encryption algorithm) does little to prevent Shor’s algorithm from finding the factors.
While large enough quantum computers to actually break encryption don’t exist yet, Shor’s algorithm is a great way for newcomers to the field to begin exploring quantum computing. It demonstrates how quantum computers could change our day-to-day lives in a practical application while building up our quantum computing intuition and knowledge.
Read more about Shor’s algorithm here: https://www.classiq.io/insights/shors-algorithm-explained
HOW TO TEACH SHOR’S ALGORITHM USING CLASSIQ
As quantum technology evolves, integrating quantum computing into the educational curriculum is important for finding practical applications in industry. There are not enough physicists in the world to run all the quantum computers that will exist, let alone discover and implement all the applications.
Educational institutions face the challenge of preparing students for a future where quantum technology plays a central role. This includes teaching the principles of quantum mechanics and quantum computing and fostering an environment where students can appreciate the potential and limitations of these technologies.
One of the biggest hurdles to learning quantum computing is the perception that too much math and programming are required to understand all the components of running and executing a quantum program. We don’t need to know how the CPU and GPU in our laptops work together to render graphics when we want to play a video game—the system handles it. This is how quantum computing should evolve, too.
Once learners become more comfortable with Shor’s algorithm, they may want to explore more of the code itself. While most of these changes can be done in the Classiq platform, a project to convert the platform input into a Jupyter Notebook is an excellent way for an educator to teach learners basic Python programming, clean code, and deployment.
Let's examine a specific example by factoring the number 15 using Shor's algorithm. We can do this with both the SDK and the Classiq platform, which has built-in functions to ease the transition into learning quantum technology. By combining these approaches, learners can gain a deeper understanding of the underlying code while also benefiting from the visual interpretation provided by the Classiq platform.
The full notebook to factor 15 with Shor’s algorithm is provided here: https://github.com/Classiq/classiq-library/blob/a66c4169be7e723c9d9e676356d000ef283cb36f/algorithms/algebraic/shor/shor.ipynb
Understanding Shor's Algorithm
Understanding Shor’s algorithm means understanding the basic principles that underpin quantum computing, including superposition and entanglement. This algorithm also creates a segue into going deeper into topics like Quantum Fourier Transform to start building up the quantum equivalents of how bits and gates work in our classical world.
Shor's algorithm is a quantum algorithm for integer factorization, which is the process of finding the prime factors of a given number. The algorithm consists of classical parts and a quantum subroutine.
The steps of Shor’s Algorithm are:
- Choose a random number a that is co-prime to the number N we want to factor. This means that a and N have no common factors other than 1. We can check this by computing the greatest common divisor (GCD) of a and N. If the GCD is 1, we proceed; otherwise, we have already found a factor of N.
- Use the quantum period-finding subroutine to find the period r of the function f(x) = a^x mod N. This is where the quantum computation comes into play. The quantum subroutine uses the principle of superposition to efficiently find the period r.
- If the period r is odd or if a^(r/2) ≡ -1 (mod N), go back to step 1 and choose a different random number a. This step ensures that the conditions necessary for the next step are met.
- Compute the greatest common divisor (GCD) of a^(r/2) ± 1 and N. One of these GCDs will be a non-trivial factor of N, which is the desired output of the algorithm.
The quantum period-finding subroutine is the key to Shor's algorithm. It uses a quantum Fourier transform (QFT) to find the period of the function f(x) = a^x mod N. This is done by applying a series of quantum gates to a set of qubits, creating a superposition of states that encode the period. By measuring the qubits after the QFT, we can extract the period r with high probability.
Period Finding With Shor’s Algorithm
Once we understand Shor’s algorithm, we want to prepare two layers:
- The modular multiplication matrix
- The quantum period-finding circuit
The provided code demonstrates the implementation of a modular multiplication matrix circuit using the Classiq platform. The goal is to estimate the eigenvalue corresponding to an eigenvector of a unitary operator that performs modular multiplication
The next step is the period-finding algorithm. The code in the Jupyter Notebook now implements a period-finding algorithm using the modular multiplication matrix.
Synthesizing a Quantum Circuit with Built-In Functions in Classiq
One of the tenets of pedagogy, especially for online and volunteer learners, is to get to “meaningful interaction” as soon as possible within the system being learned. This means that by using a visual system, the educational focus stays on “what” an algorithm should achieve instead of dealing with the details of programming before understanding the fundamentals of quantum computing.
Classiq's synthesis engine has built-in functions to kickstart that pedagogically “meaningful interaction”.
When you’ve registered for the Classiq platform,
- Open the synthesis engine here on the Classiq platform
- On the left-hand side, a list of Built-in Functions is available to browse or search. For us, we will search for Shor’s algorithm, but there are built-in tutorials for Grover’s search, Variational Quantum Eigensolver, functions like Quantum Fourier Transform, and applications in chemistry, finance, optimization, and more.
After clicking the desired function, the synthesis model is loaded.
The learner doesn’t have to change anything here to synthesize the circuit and move to the next step. However, he or she could set constraints based on gate depths and width, pick an optimization parameter, as well as add circuit connectivity maps for modeling on real hardware.
Read more about how to use the additional parameters of Classiq’s visualizations in this blog post here: https://www.classiq.io/insights/getting-started-in-quantum-computing-using-classiqs-visualizations
All this is done visually in the Classiq platform with no code. This also introduces a lot of new quantum terminology that can be easily broken down into lessons. As a learner clicks down into the circuit, they can explore the circuits top down:
- Overall Program
- Period Finding
- Hadamard Transform
- Individual Hadamard Gates
Shor’s algorithm: period_finding circuit breakdown
Now, we can laser-focus on learning about the Hadamard transform to build knowledge of Shor’s algorithm and quantum computing. Each larger quantum circuit is broken down visually into smaller components, allowing a learner to understand how qubits interact with each other and what gates are critical for a real-world implementation of Shor’s algorithm.
Shor’s algorithm: broken down into hadamard_transform, repeat, and qft_qinverse
Shor’s algorithm: hadamard_transform broken down into individual gates
Quantum Circuit Execution on Hardware
The Azure Quantum Resource Estimator is used to build more intuition for quantum computing. While the circuits look small in textbooks, the actual implementation of these algorithms can be very complex. The program information provides a list of the gates that are used in the circuit that can be further explored to break down learning from the top-up.
There is no standardized set of gates or software for quantum computing. Additionally, because of issues with calibration or construction, every chip requires fine-tuning. For an engineer, that may require days of work to analyze the specific hardware chip and re-write the circuit for the specific backend.
Classiq optimizes the space to choose the best circuit, making code more portable across different types of quantum computing hardware. This allows for a deeper understanding and practical hands-on application of Shor’s algorithm.
Beyond just algorithms, Classiq offers:
- Resource Estimation
- Hardware Comparison Tables, and
- Circuit Connectivity Maps.
All these parameters can be tweaked.
Quantum Circuit Execution on Hardware
SHOR’S ALGORITHM LEADING QUANTUM COMPUTING EDUCATION
While the hardware to run Shor’s algorithm on numbers large enough to make a difference in cryptography hasn’t happened yet, it has influenced a new group of people interested in quantum technologies.
Universities and even some high schools are beginning to offer courses in quantum computing, where Shor's Algorithm serves as a key case study. These courses often start with the basics of quantum mechanics and quantum computation, gradually building up to more complex concepts like Shor's Algorithm.
The algorithm itself is based on principles of quantum mechanics, which can be counterintuitive and complex for learners accustomed to classical physics and traditional computing concepts. Conveying these abstract ideas in an accessible manner and working with different visual aids, simulations, and hands-on experiments with quantum computing software, like Classiq’s platform, opens doors to inspiring a new generation of learners.
This build-up educates learners about quantum computing and challenges them to think fundamentally differently about problem-solving and computation in a world where quantum computers are accessible to many.
Shor’s algorithm represents an introduction to a very exciting cutting-edge technology. Its study can spark interest in STEM fields, encouraging learners to pursue careers in quantum computing without having to start from scratch and get a Ph.D. before being hands-on with a quantum computer. The excitement around quantum computing and its potential applications is a powerful motivator for learners, driving innovation and interest in a field that will impact many industries.