An efficient quantum algorithm for spectral estimation

Abstract

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 only exponentially few 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.

20 pages

References in corpus (7)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Exponential algorithmic speedup by quantum walk
• Quantum Data Fitting
• Architectures for a quantum random access memory
• Nearest-Neighbor Detection of Atoms in a 1D Optical Lattice by Fluorescence Imaging
• Quantum field tomography

Cited by in corpus (6)

• Quantum singular value decomposition of non-sparse low-rank matrices
• A Practical Introduction to Benchmarking and Characterization of Quantum Computers
• Quantum-enhanced least-square support vector machine: simplified quantum algorithm and sparse solutions
• Forecasting long-time dynamics in quantum many-body systems by dynamic mode decomposition
• A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
• Tensor-based phase difference estimation on time series analysis