Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on one of the most important breakthroughs in quantum computing: the quantum phase estimation (QPE) algorithm and its application to Shor’s factoring algorithm. The lesson begins with the phase estimation problem, Solving this problem efficiently is a cornerstone of many quantum algorithms. Spectral Theorem and Mathematical Foundations The discussion starts with the spectral theorem from linear algebra. In the context of this lesson, it is applied to unitary matrices, which can be diagonalized in an orthonormal eigenbasis. This property makes it possible to extract phase information using interference effects and controlled unitary operations. Later, the same mathematical framework extends to Hermitian operators, which are central to quantum mechanics and Hamiltonian simulation. Quantum Phase Estimation (QPE) The Quantum Phase Estimation algorithm combines: Controlled unitary operations Superposition and interference The Quantum Fourier Transform (QFT) The QFT plays a crucial role by transforming phase information encoded in amplitudes into measurable computational basis states. Importantly, the QFT can be implemented efficiently with a quantum circuit whose complexity scales polynomially with the number of qubits. From Phase Estimation to Shor’s Algorithm By applying QPE to a specific modular exponentiation operator, one obtains Shor’s algorithm, an efficient quantum algorithm for integer factorization. Shor’s algorithm demonstrates an exponential speedup over the best-known classical factoring algorithms and has profound implications for cryptography, particularly for RSA-based systems. Significance This lesson illustrates a major milestone in quantum computing: It connects abstract linear algebra (spectral theorem) to concrete algorithmic advantage. It shows how quantum interference enables extraction of hidden periodicity. It demonstrates a real-world cryptographic impact through efficient factorization. Through hands-on experimentation on IBM Q, theoretical concepts are translated into working quantum circuits, reinforcing the deep relationship between mathematics, algorithm design, and quantum computational power.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on one of the most important breakthroughs in quantum computing: the quantum phase estimation (QPE) algorithm and its application to Shor’s factoring algorithm. The lesson begins with the phase estimation problem, Solving this problem efficiently is a cornerstone of many quantum algorithms. Spectral Theorem and Mathematical Foundations The discussion starts with the spectral theorem from linear algebra. In the context of this lesson, it is applied to unitary matrices, which can be diagonalized in an orthonormal eigenbasis. This property makes it possible to extract phase information using interference effects and controlled unitary operations. Later, the same mathematical framework extends to Hermitian operators, which are central to quantum mechanics and Hamiltonian simulation. Quantum Phase Estimation (QPE) The Quantum Phase Estimation algorithm combines: Controlled unitary operations Superposition and interference The Quantum Fourier Transform (QFT) The QFT plays a crucial role by transforming phase information encoded in amplitudes into measurable computational basis states. Importantly, the QFT can be implemented efficiently with a quantum circuit whose complexity scales polynomially with the number of qubits. From Phase Estimation to Shor’s Algorithm By applying QPE to a specific modular exponentiation operator, one obtains Shor’s algorithm, an efficient quantum algorithm for integer factorization. Shor’s algorithm demonstrates an exponential speedup over the best-known classical factoring algorithms and has profound implications for cryptography, particularly for RSA-based systems. Significance This lesson illustrates a major milestone in quantum computing: It connects abstract linear algebra (spectral theorem) to concrete algorithmic advantage. It shows how quantum interference enables extraction of hidden periodicity. It demonstrates a real-world cryptographic impact through efficient factorization. Through hands-on experimentation on IBM Q, theoretical concepts are translated into working quantum circuits, reinforcing the deep relationship between mathematics, algorithm design, and quantum computational power.
The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.
Quantum computing is the field that studies computation using quantum mechanical systems, exploiting properties such as superposition or entanglement. The focus of this project will be on quantum phase estimation algorithms. The formalism commonly used to represent quantum algorithms as quantum circuits composed by qubits and quantum gates will be presented. Then, we will be able to explain the quantum Fourier transform (that is exponentially faster than its classical analogue) and three quantum phase estimation algorithms: Kitaev’s phase estimation (KPEA), the phase estimation algorithm based on QFT (PEA) and the iterative quantum phase estimation algorithm based on a semiclassical Fourier transform (IPEA). We will use the Qiskit framework in order to run simulations of such algorithms, and even run them in real IBM Q Experience quantum computers (specifically, we will use the 5 qubit computer ibmq_essex). Statistical post-processing techniques will be essential in order to extract a phase estimation from the results obtained. We will use two post-processing techniques: the majority and the average rule. The performance of these methods applied to the results of several simulations and executions in ibmq_essex will be studied. At last, we will talk about the possible applications of phase estimation algorithms. Phase estimation is used as a subroutine in the field of quantum simulation, allowing us to obtain several magnitudes of a quantum system such as the energy levels. We will present an efficient quantum algorithm for factoring called Shor’s algorithm. The cost of factorization with a classical computer increases exponentially with the size of the input, so this is a example of a task that cannot be solved efficiently on a classical computer, but can be solved efficiently by a quantum computer. Phase estimation is also used in the field of quantum metrology. Specifically, an N-V center can be used to measure magnetic fields with high sensitivity and spatial resolution operating at room temperature thanks to a measuring protocol based on phase estimation.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
Shor's algorithm proved a significant milestone in quantum computing since it promises an exponential speedup over conventional algorithms for integer factorization, a problem critical to modern cryptography systems. This work covers implementation steps of Shor’s algorithm and analyzes Quantum Fourier Transform (QFT) usage for extracting periodicity from quantum superpositions. Firstly, theoretical foundations of algorithm are illustrated concentrating on QFT construction and operation within the setting of the quantum circuit. Thereafter, each implementation step such as qubit optimization, modular exponentiation, and circuit design is discussed. Our findings validate the theoretical effectiveness of the QFT in solving the period-finding subroutine, while also highlighting the practical difficulties and scaling constraints presented by existing quantum hardware. The paper ends with a summary of possible advancements and future paths for error mitigation strategies and quantum algorithm design.
In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.
Quantum phase estimation (QPE) is one of the core algorithms for quantum computing. It has been extensively studied and applied in a variety of quantum applications such as the Shor's factoring algorithm, quantum sampling algorithms and the calculation of the eigenvalues of unitary matrices. The QPE algorithm has been combined with Kitaev's algorithm and the inverse quantum Fourier transform (IQFT) which are utilized as a fundamental component of such quantum algorithms. In this paper, we explore the computational challenges of implementing QPE algorithms on noisy intermediate-scale quantum (NISQ) machines using the IBM Q Experience (e.g., the IBMQX4, 5-qubit quantum computing hardware platform). Our experimental results indicate that the accuracy of finding the phase using these QPE algorithms is severely constrained by the NISQ computer's physical characteristics such as coherence time and error rates. To mitigate these physical limitations, we propose implementing a modified solution by reducing the number of controlled rotation gates and phase shift operations, thereby increasing the accuracy of the finding phase in near-term quantum computers.