11
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Are you familiar with the Aaronson-Ambainis conjecture? That conjecture puts a bit of a constraint on the structure required for exponential speedups of certain problems. This structure is often what’s exploited in QFT-based algorithms. But the AA conjecture is limited to NP decision problems, and certain search problems, or even non-NP problems, may avoid the AA conjecture. $\endgroup$ Jun 20 at 12:55

2 Answers 2

10
$\begingroup$

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"

$\endgroup$
11
  • 4
    $\begingroup$ IIRC this algorithm is BQP complete, isn't it? So this is the absolute strongest contender one could have for an exponential speed-up. As strongly as we believe quantum computers have some speedup, this algorithm exhibits it. $\endgroup$
    – DaftWullie
    Jun 20 at 8:39
  • 1
    $\begingroup$ I'm not very familiar with that problem - is the output a complex number? (Or more precisely, some finite-bit approximation of a complex number, where the algorithm runtime is polynomial in the desired number of bits of precision for the exact solution? Is that what "approximates" means in this context?) $\endgroup$
    – tparker
    Jun 20 at 12:42
  • 1
    $\begingroup$ Are there any (non-oracle) decision problems with a conjectured exponential quantum speedup with an algorithm that doesn't use the QFT? $\endgroup$
    – tparker
    Jun 20 at 12:44
  • 1
    $\begingroup$ @tparker the standard way to convert such problems into decision problems is to add a promise on the range of possible outputs. This is what’s meant by promise-BQP complete. Here we promise that we can only calculate the Jones polynomial up to a particular accuracy. It’s still a decision problem. $\endgroup$ Jun 20 at 12:48
  • 3
    $\begingroup$ ALJ algorithm uses Hadamard test to evaluate the real and imaginary components of Jones polynomial. When we say that this problem is PromiseBQP-complete, we mean the "decision version" of it. $\endgroup$ Jun 20 at 14:31
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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