The Quantum Fourier Transform for Earth Observation

Abstract

The Fourier transform algorithm is ubiquitously used and essential for applications like digital signal processing, as well as audio and video compression. Its quantum analogue, the quantum Fourier transform (QFT), first became famous as a part of Shor’s Algorithm for factoring numbers in the nineties. Since then, many influential algorithms have been built on top of the QFT and the associated quantum phase estimation. One of these is a quantum algorithm for solving systems of linear equations. It was developed by Harrow, Hassidim and Loyd in 2009 [HHL09] and is hence often called HHL for short. Under certain conditions, HHL is able to find the solution x of the system Ax = b with a complexity of only O(log n), where n is the number of variables. This stands in contrast to classical techniques which achieve a runtime of O(n 2) at best. In this work, we develop the HHL algorithm and the components upon which it is built, including the quantum Fourier transform. While the theoretical speedup of HHL is exponential, the conditions which must be met can pose difficult problems for actual implementations. We give an in-depth overview of these conditions and the research aimed to improve them. At DLR large amounts of earth observation data from satellites needs to be processed. This presents a possible future use case for quantum algorithms. We evaluate the applicability of HHL for space-borne synthetic aperture radar tomography, which is a technique to reconstruct three-dimensional surface features from radar data.