Quantum Oracle for Shor's Algorithm

This repository contains a Qiskit implementation of the period-finding oracle ($U_{a}$) used in Shor's quantum period-finding algorithm.

Description

In this notebook, we build a quantum period-finding oracle for Shor's algorithm, with demonstrations and verifications of each component part, primarily following the $2n +3$ qubit implementation designed by Beauregard [Bea03]. To execute this design in Qiskit, we used the provided course materials, primarily Jupyter notebooks, from the Erdös Institute 2025 Quantum Computing Bootcamp [Nag25], supplemented by Google's LLM, Gemini, as well as [NC10] for further explanation of the algorithm and [Qis25] for notational reference.

Google Gemini was particularly useful for testing the functions, debugging, and referencing syntax. In particular, we used it to explain and verify the binary arithmetic that is crucial for the algorithm.

Shor's algorithm makes use of the harmonic analytic properties of arithmetic, namely periodicity, to find a factor for a positive integer $N$. The quantum portion of Shor's algorithm is given here by the oracle $U_a$, which performs the controlled multiplication: $$U_a | c\rangle | x\rangle = | c \rangle |(a^c \cdot x) \pmod N \rangle$$

This quantum oracle is made up of the following composite parts, each built and verified in schoracle.ipynb:

• An adder (phi_add), similar to the Draper adder, with addition achieved via phase change in the Fourier basis.
• A QFT-based modular adder (phi_add_mod) built from the above.
• A controlled modular multiplier (c_mult_mod), built from successive applications of the modular adder.
• The final oracle $U_a$ (c_U), which uses the modular multiplier and controlled swaps to perform the desired computation.

Technical Requirements

This project requires Python 3 and the following Python libraries:

• Qiskit
• NumPy
• Matplotlib

Usage

The main implementation and verification for the oracle are contained within the schoracle.ipynb Jupyter Notebook.

References

[Bea03] Beauregard, S. (2003), Circuit for Shor's algorithm using 2n+3 qubits, arXiv:quant-ph/0205095.

[Nag25] Nagy, A. (2025), Course Notes: Erdos Institute Fall 2025 Quantum Computing Bootcamp

[NC10] Nielsen, M. A., & Chuang, I. L. (2010), Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press.

[Qis25] Qiskit contributors (2025), Learn Quantum Computation using Qiskit, https://qiskit.org/learn

[Sho97] Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, 26(5), 1484-1509.