Does the quantum Fourier transform have many applications beyond period finding?

Question

(This is a somewhat soft question.)

The quantum Fourier transform is formally quite similar to the fast Fourier transform, but exponentially faster.

The QFT is famously at the core of Shor's algorithm for period finding. It also comes up in a few other places, like the HHL algorithm for solving (certain very special) linear systems of equations.

The FFT, on the other hand is used in countless different applications throughout applied math, science, engineering, finance, and music (notably for signal processing and solving differential equations). Gilbert Strang called it "the most important numerical algorithm of our lifetime."

Given that the QFT is exponentially faster than the FFT, there seems to me to be a strange discrepancy between the literally thousands of known applications of the FFT and the relatively few applications of the QFT (even at the theoretical level, setting aside the obvious practical implementation challenges). I would have expected that, given the exponential speedup that the QFT delivers over the FFT, a quantum computer capable of implementing the QFT would instantly render many classical computing applications obsolete, and would also open up many more potential applications that are currently impractical. And yet the only application of the QFT that people seem to really discuss is using Shor's algorithm for decryption. (I don't mean "application" in the academic's sense of "something that will get me a paper published", but in the business person's sense of "something that there might be a commercial market for".) It's not even clear if the HHL algorithm would actually deliver a useful speedup in practice.

Is there some conceptual explanation for why the QFT doesn't seem to be as big of a deal in practice as one might expect? Is it just the usual I/O challenge of (a) efficiently reading a large data set in memory and (b) only being able to statistically sample the output amplitudes over many runs instead of being able to read them out all at once?

Answer 1

Given that the QFT is exponentially faster than the FFT,

The problem with quantum computing is that they are not actually parallel computers: One is tweaking the qubits in such a way that when reading out the result, the desired result gets a high probability.

The power of quantum computing comes from the vast phase-space that grows exponentially with the number of the entangled qubits, and all of the parameters representing that phase space are manipulated at once during a quantum computation step. However, reading out will "collapse" the quantum state and you'll only see the projection of the state. A bit like a 2-d shadow has less information than a 3-d object casting that shadow.

While you get all the $2^n$ frequency components with FFT, you'll basically just find one frequency with QFT, and this works nicely in cases where you are only interested in one frequency. The latter is the case for Shor's algorithm where you basically compute the order of the multiplicative group of $\mathbb Z/n\mathbb Z$.

Answer 2

QFT is used for phase and amplitude estimation and hence it can be found in many application of quantum computing in finance, for example portfolio construction using HHL in its core, Monte Carlo simulation and quantum principal component analysis. There is also application in travelling salesman problem.

See list of articles on these applications here: Quantum computing in finance - list of articles

Disclaimer: I can imagine that there are application in other fields of science but I am particularly interested in finance, so I provided examples only for this field.

Answer 3

TL/DR: The QFT is a powerful (indeed in a sense BQP-complete) subroutine but has a lot of asterisks to its applicability. I think an issue may be that the QFT in conjunction with Hamiltonian simulation is powerful especially on large matrices that have certain, potentially restrictive, properties on the eigenvalues such as condition number, etc. and separately properties on the access to entries of the underlying matrix $A$ such as sparsity, etc. that may limit their applicability in a certain sense.

---

In more detail, these limitations may come from (A) requirements on the Hamiltonian simulation of the underlying matrix and (B) the specific implementation of the QFT, which in Shor's algorithm allows for exponential precision but otherwise may only allow for polynomial precision.

For example a number of algorithms from Janzing and Wocjan show that computation of entries of (small) powers of (large) matrices can be done efficiently with a quantum computer.

Much as HHL performs eigenvalue surgery on the eigenvalues $\lambda$ of a large matrix $A$ to determine $\lambda^{-1}$, Janzing and Wocjan calculate the expectation of $\lambda^m$ for integral $m\ge 1$ to compute elements of $A^m$. Both rely critically on Hamiltonian simulation to work with $U=e^{-iAt}$, and the QFT to determine $\lambda$ with phase estimation.

Furthermore, HHL requires a small enough condition number (~smallest eigenvalue) to make sure that $\lambda^{-1}$ doesn't go crazy while Janzing and Wocjan require a bound on the operator norm (~largest eigenvalue) to make sure that $\lambda^m$ is also reasonable.

Additionally compared to Shor's algorithm, HHL and Janzing and Wocjan's algorithms, Shor's algorithm uses fast modular exponentiation by repeated squaring; HHL and other algorithms can only achieve a polynomial precision when they compute powers of respective Hamiltonians to perform the Quantum Phase Estimation (QPE).