Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?

Question

The Quantum Fourier Transform (QFT) subroutine seems ubiquitous in most quantum algorithms that are conjectured to give an exponential (or at least superpolynomial) speedup over the best classical algorithms for the same classical (non-oracle, non-promise) problem, such as Shor's algorithm, the HHL algorithm, and using the phase estimation algorithm for simulating quantum systems.

Are there any classical non-oracle non-promise problems for which a known quantum algorithm is believed to give an exponential (or superpolynomial) advantage over the best classical algorithm, which doesn't use the QFT as a subroutine? Ideally, I'd prefer a problem of practical real-world interest, but I'd also accept a problem that was constructed solely to prove a complexity-theoretic result. Oracle problems and promise problems are out of scope.

The answer to this question may be somewhat subjective, in that it depends on whether a close variant of the traditional QFT "counts". I'll say that for the purpose of this question, a valid algorithm can't use anything "like" the QFT as a subroutine, although I admit that there may be somewhat some subjectivity in just what quantum subroutines are considered to be "like" the QFT. (The Hadamard transform is perhaps a borderline case; I'll accept an algorithm that uses the Hadamard transformation, but would prefer one that doesn't.)

Answer 1

Aharonov–Jones–Landau algorithm is a polynomial time quantum algorithm that approximates the #P-hard problem of evaluating the Jones polynomial at certain roots of unity. The best classical algorithm for this problem is exponential.

The original paper^[1] stated that:

"It does so not by using the Fourier transform, but instead, by exploiting a certain structure of the problem and encoding it into the nature of the unitary gates being used"

Answer 2

If you (1) don't like oracle problems, (2) wish to have a total, non-promise problem that also has an NP-certificate, and (3) are hesitant to use the full QFT over $\mathbb Z/N\mathbb Z$ but can live with Hadamard gates over $\mathbb Z/2\mathbb Z$, one option may be the $x^2\bmod N$ hash-based proof of quantumness of Kahanamoku-Meyer et al.. This is an interactive proof using trapdoor hashes and includes other features that you might not like, but at least it's non-oracular and not based on a promise, and is conjectured to provide an exponential speedup (while using the Hadamard transform in lieu of a QFT). Whether this is useful for anything other than proving quantumness or certifiable randomness generation is unknown.

I think of this as a "simpler" version of Shor's algorithm, in that with Kahanamoku-Meyer et al., we calculate $\frac{1}{\sqrt{2^n}}\sum|x\rangle|x^2\bmod N\rangle$ in superposition and apply Hadamard gates to the first register. While, in Shor's algorithm, we calculate $\frac{1}{\sqrt{2^n}}\sum|x\rangle |a^x\bmod N\rangle$ in superposition and apply the full quantum Fourier transform to the first register. Calculating $a^x\bmod N$ is harder than calculating $x^2\bmod N$, and calculating the full QFT over $\mathbb Z/N\mathbb Z$ is harder than doing a series of Hadamard gates.

With a hash such as $x^2\bmod N$ where $N$ is the product of two primes $p\times q$, upon measuring the second register $y$, doing the Hadamard transform on the first register gives a random string $d\ne\bf 0$ that is orthogonal to the bitwise sum/XOR of the two preimages $x_1$ and $x_2$ that satisfy $x_1^2\bmod N=x_2^2\bmod N=y$. Finding such a string $d$ such that $d\cdot (x_1\oplus x_2)=0$ without knowing the factors of $N$ is conjectured to be exponentially difficult classically.

Answer 3

I won't name an explicit example of an algorithm. But I will add a reason why a search for a QFT-less Quantum algorithm with superpolynomial speedup (w.r.t classical) might be extremely challenging.

(For generality, I assume the Hadamard transform is a particular version of QFT.)

Also, @trparker has mentioned in the last two lines of the post:

(The Hadamard transform is perhaps a borderline case; I'll accept an algorithm that uses the Hadamard transformation, but would prefer one that doesn't.).

If you look at the paper by Y. Shi(2003), it mentions the Fourier Hierarchy ($FH$) in the discussion section. Informally, it gives an idea of why layers of QFT in an algorithm could provide a computational advantage over classical algorithms.

As quoted in Complexity Zoo:

$FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels of Hadamard gates and all other gates preserving the computational basis.

There is some consensus that FH is robust (or less likely to collapse). (See Greg Kuperberg's answer here.)

Thus, getting rid of QFT (including Hadamard) and still getting quantum advantage might be intrinsically challenging.