6
$\begingroup$

(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?

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But how many of these applications rely on the HHL algorithm? I'm asking about applications beyond the HHL algorithm. $\endgroup$ – tparker Feb 13 at 14:51
  • $\begingroup$ @tparker: only this one "Quantum computational finance: quantum algorithm for portfolio optimization". Others uses QFT for phase or amplitude estimation. $\endgroup$ – Martin Vesely Feb 13 at 17:44
2
$\begingroup$

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.