An efficient quantum algorithm for spectral estimation
Open Access
- 1 March 2017
- journal article
- research article
- Published by IOP Publishing in New Journal of Physics
- Vol. 19 (3) , 033005
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 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.Keywords
All Related Versions
Funding Information
- John Templeton Foundation
- European Research Council (TAQ)
- Army Research Office
- European Commission (AQuS, RAQUEL)
- Studienstiftung des Deutschen Volkes
- Air Force Office of Scientific Research
- Deutsche Forschungsgemeinschaft (CRC 183, EI 519/7-1)
This publication has 37 references indexed in Scilit:
- Application of compressed sensing to the simulation of atomic systemsProceedings of the National Academy of Sciences, 2012
- A COMPARATIVE STUDY ON ISAR IMAGING ALGORITHMS FOR RADAR TARGET IDENTIFICATIONProgress In Electromagnetics Research, 2010
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Nearest-Neighbor Detection of Atoms in a 1D Optical Lattice by Fluorescence ImagingPhysical Review Letters, 2009
- Architectures for a quantum random access memoryPhysical Review A, 2008
- Quantum Random Access MemoryPhysical Review Letters, 2008
- Estimating two-dimensional frequencies by matrix enhancement and matrix pencilIEEE Transactions on Signal Processing, 1992
- Multiple emitter location and signal parameter estimationIEEE Transactions on Antennas and Propagation, 1986
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965
- Norms and exclusion theoremsNumerische Mathematik, 1960