We present a comprehensive and pedagogical study of two core quantum algorithms in quantum linear algebra: the Hadamard test (HT) and quantum phase estimation (QPE). Building on Prof. Lin's lecture notes on Quantum Algorithms for Scientific Computing, we detail their mathematical formulations, circuit implementations, and convergence behavior. Both algorithms are benchmarked on simulators and IBM's 127-qubit Eagle processor (ibm rensselaer) using a simple eigenvalue problem. While QPE performs well in simulation, its hardware performance degrades beyond t = 3 ancilla qubits due to circuit depth and two-qubit gate noise. In contrast, HT shows stable, sampling-based convergence and greater resilience to hardware noise. We further apply QPE to the transversefield Ising model (TFIM), demonstrating the importance of ansatz quality for accurate ground state energy estimation. These results provide a realistic baseline for implementing phase estimation on noisy intermediate-scale quantum (NISQ) era devices.We present a comprehensive and pedagogical study of two core quantum algorithms in quantum linear algebra: the Hadamard test (HT) and quantum phase estimation (QPE). Building on Prof. Lin's lecture notes on Quantum Algorithms for Scientific Computing, we detail their mathematical formulations, circuit implementations, and convergence behavior. Both algorithms are benchmarked on simulators and IBM's 127-qubit Eagle processor (ibm rensselaer) using a simple eigenvalue problem. While QPE performs well in simulation, its hardware performance degrades beyond t = 3 ancilla qubits due to circuit depth and two-qubit gate noise. In contrast, HT shows stable, sampling-based convergence and greater resilience to hardware noise. We further apply QPE to the transversefield Ising model (TFIM), demonstrating the importance of ansatz quality for accurate ground state energy estimation. These results provide a realistic baseline for implementing phase estimation on noisy intermediate-scale quantum (NISQ) era devices.

May 29, 20250 citations

THEORETICAL FRAMEWORK AND ALGORITHMIC IMPLEMENTATION OF THE QUANTUM FOURIER TRANSFORM AND PHASE ESTIMATION

Medak Srinivas

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.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.

Iterative International Publishers eBooksMay 1, 20260 citations

An Improved Implementation Approach for Quantum Phase Estimation on Quantum Computers

Hamed Mohammadbagherpoor, Young-Hyun Oh, Patrick Dreher +3 more

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.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.

arXiv:1910.11696IEEE International Conference on Rebooting Computing (ICRC)Nov 1, 201951 citations

Fisher information based lower bounds on the cost of quantum phase estimation

Ryosuke Kimura, Kosuke Mitarai

Quantum phase estimation (QPE) is a cornerstone of quantum algorithms designed to estimate the eigenvalues of a unitary operator. QPE is typically implemented through two paradigms with distinct circuit structures: quantum Fourier transform-based QPE (QFT-QPE) and Hadamard test-based QPE (HT-QPE). Existing performance assessments fail to separate the statistical information inherent in the quantum circuit from the efficiency of classical post-processing, thereby obscuring the limits intrinsic to the circuit structure itself. In this study, we employ Fisher information and the Cramer-Rao lower bound to formulate the performance limits of circuit designs independent of the efficiency of classical post-processing. Defining the circuit depth as $T$ and the total runtime as $t_{\rm total}$ , our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product $T\,t_{\rm total}$ , although previous studies have typically treated the circuit depth $T$ and the total runtime $t_{\rm total}$ as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.Quantum phase estimation (QPE) is a cornerstone of quantum algorithms designed to estimate the eigenvalues of a unitary operator. QPE is typically implemented through two paradigms with distinct circuit structures: quantum Fourier transform-based QPE (QFT-QPE) and Hadamard test-based QPE (HT-QPE). Existing performance assessments fail to separate the statistical information inherent in the quantum circuit from the efficiency of classical post-processing, thereby obscuring the limits intrinsic to the circuit structure itself. In this study, we employ Fisher information and the Cramer-Rao lower bound to formulate the performance limits of circuit designs independent of the efficiency of classical post-processing. Defining the circuit depth as $T$ and the total runtime as $t_{\rm total}$, our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product $T\,t_{\rm total}$, although previous studies have typically treated the circuit depth $T$ and the total runtime $t_{\rm total}$ as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.

quant-pharXiv:2603.12706Mar 16, 20260 citations

Experimental Challenges of Implementing Quantum Phase Estimation Algorithms on IBM Quantum Computer

Hamed Mohammadbagherpoor, Young-Hyun Oh, Anand Singh +2 more

Many researchers have been heavily investigated on quantum phase estimation (QPE) algorithms to find the unknown phase, since QPE is the core building block of the most quantum algorithms such as the Shor's factoring algorithm, quantum sampling algorithms, and finding the eigenvalues of unitary matrices. Kitaev's algorithm and QPE algorithms using inverse Quantum Fourier transform were proposed and widely used by researchers as a key component for their quantum algorithms. In this paper, we explore the experimental challenges of QPE algorithms on Noisy Intermediate-Scale Quantum (NISQ) computers by implementing various QPE algorithms on the state-of-the-art IBM quantum computer. Our experimental results demonstrate that the accuracy of finding the phase using these algorithms are severely constrained by NISQ's physical characteristics such as coherence time and error rates. To mitigate such physical limitations, we propose modified solutions of these algorithms by reducing the number of control gates and phase shift operations. Our experimental results showed that our solutions can significantly increase the accuracy of the finding phase in near-term quantum computers.Many researchers have been heavily investigated on quantum phase estimation (QPE) algorithms to find the unknown phase, since QPE is the core building block of the most quantum algorithms such as the Shor's factoring algorithm, quantum sampling algorithms, and finding the eigenvalues of unitary matrices. Kitaev's algorithm and QPE algorithms using inverse Quantum Fourier transform were proposed and widely used by researchers as a key component for their quantum algorithms. In this paper, we explore the experimental challenges of QPE algorithms on Noisy Intermediate-Scale Quantum (NISQ) computers by implementing various QPE algorithms on the state-of-the-art IBM quantum computer. Our experimental results demonstrate that the accuracy of finding the phase using these algorithms are severely constrained by NISQ's physical characteristics such as coherence time and error rates. To mitigate such physical limitations, we propose modified solutions of these algorithms by reducing the number of control gates and phase shift operations. Our experimental results showed that our solutions can significantly increase the accuracy of the finding phase in near-term quantum computers.

arXiv:1903.07605Mar 18, 20197 citations

Practical numerical integration on NISQ devices

Kwangmin Yu, Hyunkyung Lim, Pooja Rao

This paper addresses the practical aspects of quantum algorithms used in numerical integration, specifically their implementation on Noisy Intermediate-Scale Quantum (NISQ) devices. Quantum algorithms for numerical integration utilize Quantum Amplitude Estimation (QAE) (Brassard et al., 2002) in conjunction with Grover’s algorithm. However, QAE is daunting to implement on NISQ devices since it typically relies on Quantum Phase Estimation (QPE), which requires many ancilla qubits and controlled operations. To mitigate these challenges, a recently published QAE algorithm (Suzuki et al., 2020), which does not rely on QPE, requires a much smaller number of controlled operations and does not require ancilla qubits. We implement this new algorithm for numerical integration on IBM quantum devices using Qiskit and optimize the circuit on each target device. We discuss the application of this algorithm on two qubits and its scalability to more than two qubits on NISQ devices.This paper addresses the practical aspects of quantum algorithms used in numerical integration, specifically their implementation on Noisy Intermediate-Scale Quantum (NISQ) devices. Quantum algorithms for numerical integration utilize Quantum Amplitude Estimation (QAE) (Brassard et al., 2002) in conjunction with Grover’s algorithm. However, QAE is daunting to implement on NISQ devices since it typically relies on Quantum Phase Estimation (QPE), which requires many ancilla qubits and controlled operations. To mitigate these challenges, a recently published QAE algorithm (Suzuki et al., 2020), which does not rely on QPE, requires a much smaller number of controlled operations and does not require ancilla qubits. We implement this new algorithm for numerical integration on IBM quantum devices using Qiskit and optimize the circuit on each target device. We discuss the application of this algorithm on two qubits and its scalability to more than two qubits on NISQ devices.

arXiv:2004.05739Apr 24, 20209 citations

T

and the total runtime as

t_{\rm total}

, our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product

T\,t_{\rm total}

, although previous studies have typically treated the circuit depth

T

and the total runtime

t_{\rm total}

as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.