We develop an efficient quantum implementation of an important signal processing algorithm for line spectral estimation: the matrix pencil method, which determines the frequencies and damping factors of signals consisting of finite sums of exponentially damped sinusoids. Our algorithm provides a quantum speedup in a natural regime where the sampling rate is much higher than the number of sinusoid components. Along the way, we develop techniques that are expected to be useful for other quantum algorithms as well—consecutive phase estimations to efficiently make products of asymmetric low rank matrices classically accessible and an alternative method to efficiently exponentiate non-Hermitian matrices. Our algorithm features an efficient quantum–classical division of labor: the time-critical steps are implemented in quantum superposition, while an interjacent step, requiring much fewer parameters, can operate classically. We show that frequencies and damping factors can be obtained in time logarithmic in the number of sampling points, exponentially faster than known classical algorithms.We develop an efficient quantum implementation of an important signal processing algorithm for line spectral estimation: the matrix pencil method, which determines the frequencies and damping factors of signals consisting of finite sums of exponentially damped sinusoids. Our algorithm provides a quantum speedup in a natural regime where the sampling rate is much higher than the number of sinusoid components. Along the way, we develop techniques that are expected to be useful for other quantum algorithms as well—consecutive phase estimations to efficiently make products of asymmetric low rank matrices classically accessible and an alternative method to efficiently exponentiate non-Hermitian matrices. Our algorithm features an efficient quantum–classical division of labor: the time-critical steps are implemented in quantum superposition, while an interjacent step, requiring much fewer parameters, can operate classically. We show that frequencies and damping factors can be obtained in time logarithmic in the number of sampling points, exponentially faster than known classical algorithms.

Feb 1, 201711 citations

A Quasi-Random Approach to Matrix Spectral Analysis

Michael Ben-Or, Lior Eldar

Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in $O(\log^2 n)$ parallel time with a total cost of $O(n^{ω+1})$ Boolean operations. This Boolean complexity matches the best known rigorous $O(\log^2 n)$ parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases $(\mod (2π))$ is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in $O(\log^2 n)$ parallel time and $O(n^ω)$ Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in $O(\log^2 n)$ parallel time with a total cost of $O(n^{ω+1})$ Boolean operations. This Boolean complexity matches the best known rigorous $O(\log^2 n)$ parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases $(\mod (2π))$ is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in $O(\log^2 n)$ parallel time and $O(n^ω)$ Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.

arXiv:1505.08126Leibniz international proceedings in informaticsMay 29, 20153 citations

A quantum algorithm for estimating the determinant

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

We present a quantum algorithm for estimating the matrix determinant based on quantum spectral sampling. The algorithm estimates the logarithm of the determinant of an $n \times n$ positive sparse matrix to an accuracy $ε$ in time ${\cal O}(\log n/ε^3)$ , exponentially faster than previously existing classical or quantum algorithms that scale linearly in $n$ . The quantum spectral sampling algorithm generalizes to estimating any quantity $\sum_j f(λ_j)$ , where $λ_j$ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function $Z(β) =\sum_j e^{-βE_j}$ of a Hamiltonian system with energy eigenvalues $E_j$ , and of the entropy $ S =-\sum_j p_j \log p_j$ of a density matrix with eigenvalues $p_j$ .We present a quantum algorithm for estimating the matrix determinant based on quantum spectral sampling. The algorithm estimates the logarithm of the determinant of an $n \times n$ positive sparse matrix to an accuracy $ε$ in time ${\cal O}(\log n/ε^3)$, exponentially faster than previously existing classical or quantum algorithms that scale linearly in $n$. The quantum spectral sampling algorithm generalizes to estimating any quantity $\sum_j f(λ_j)$, where $λ_j$ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function $Z(β) =\sum_j e^{-βE_j}$ of a Hamiltonian system with energy eigenvalues $E_j$, and of the entropy $ S =-\sum_j p_j \log p_j$ of a density matrix with eigenvalues $p_j$.

arXiv:2504.11049Apr 15, 20250 citations

Practical Guide to Quantum Computing: Phase Estimation and Factoring # 3

Mikhail Pavlov

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.

Mar 3, 20260 citations

Faster Phase Estimation

Krysta M. Svore, Matthew B. Hastings, Michael Hartley Freedman

We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of log* of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of log* of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.

arXiv:1304.0741Apr 2, 20133 citations

Faster phase estimation

Krysta M. Svore, Matthew B. Hastings, Michael Hartley Freedman

We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of $\log^*$ of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.We develop several algorithms for performing quantum phase estimation based on basic measurements and classical post-processing. We present a pedagogical review of quantum phase estimation and simulate the algorithm to numerically determine its scaling in circuit depth and width. We show that the use of purely random measurements requires a number of measurements that is optimal up to constant factors, albeit at the cost of exponential classical post-processing; the method can also be used to improve classical signal processing. We then develop a quantum algorithm for phase estimation that yields an asymptotic improvement in runtime, coming within a factor of $\log^*$ of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.

Quantum Information and ComputationMar 1, 201447 citations

O(\log^2 n)

parallel time with a total cost of

O(n^{ω+1})

Boolean operations. This Boolean complexity matches the best known rigorous

O(\log^2 n)

parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases

(\mod (2π))

is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in

O(\log^2 n)

parallel time and

O(n^ω)

Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.

We present a quantum algorithm for estimating the matrix determinant based on quantum spectral sampling. The algorithm estimates the logarithm of the determinant of an

n \times n

positive sparse matrix to an accuracy

ε

in time

{\cal O}(\log n/ε^3)

, exponentially faster than previously existing classical or quantum algorithms that scale linearly in

n

. The quantum spectral sampling algorithm generalizes to estimating any quantity

\sum_j f(λ_j)

, where

λ_j

are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function

Z(β) =\sum_j e^{-βE_j}

of a Hamiltonian system with energy eigenvalues

E_j

, and of the entropy $ S =-\sum_j p_j \log p_j$ of a density matrix with eigenvalues

p_j

\log^*

of the minimum number of measurements required while still requiring only minimal classical post-processing. The corresponding quantum circuit requires asymptotically lower depth and width (number of qubits) than quantum phase estimation.