12
$\begingroup$

The general adversary lower-bound is now known to characterize quantum query complexity due to breakthrough work by Reichardt et al. The same line of work also establishes connections to the span program framework to design quantum algorithms.

Many interesting quantum algorithms, including ones with exponential speed-up like Simon's algorithm and Shor's algorithm for period finding can be expressed in the quantum query model.

Is there any work showing lower-bounds for these algorithms in the general adversary model? Is there any work re-deriving Simon's or Shor's algorithms in the span-program framework?

Apparently, only quantum algorithms with polynomial speed-up, like Grover's , have been re-derived using span programs (or Belov's learning graph) framework.

There is work by Korian et al. showing lower-bounds for Simon using the polynomial method, but there is apparently no known way to translate polynomial-method lower-bounds to general adversary lower bounds.

$\endgroup$
  • 3
    $\begingroup$ I accidentally voted to close as "off-topic" because I thought I was voting on a different question and clicked the wrong tab. I think this is a great question and perfectly on-topic, but the system doesn't let me withdraw my accidental vote. $\endgroup$ – Artem Kaznatcheev Aug 15 '12 at 19:31
8
$\begingroup$

I guess there are at least 3 questions in your question. I don't have a satisfactory answer to all of them, so this isn't a complete answer. Hopefully there will be more answers that answer all your questions.

The question in the title: Can quantum algorithms with exponential speed-up be rederived using span-programs?

As you noted, the general adversary bound characterizes the quantum query complexity of all decision problems, including promise problems for which we have exponential speedups. So, in principle, there is a span program that solves the Abelian hidden subgroup problem, which is the query problem used in Simon's and Shor's algorithms. But whether there is an explicit span program for this is your next question.

Is there any work re-deriving Simon's or Shor's algorithms in the span-program framework?

I haven't heard of any such results. I don't know of a span program for Simon's problem or any other AHSP.

Is there a way to translate polynomial-method lower-bounds to general adversary lower bounds?

Yes, I believe there is. I can't seem to find the paper that has this result, but I can give you a link to a talk given by Jérémie Roland. In the abstract of the talk, he says the following:

... More precisely, we will show that the multiplicative adversary method, a variation of the original adversary method, generalizes not only the generalized adversary method, but also the polynomial method, so that it essentially encompasses all known lower bound methods. Therefore, this provides a constructive approach to cast polynomial lower bounds into the adversary method framework.

Update: The paper is now available online: Explicit relation between all lower bound techniques for quantum query complexity by Loïck Magnin and Jérémie Roland

$\endgroup$
  • 2
    $\begingroup$ I just want to point out something here. If the goal is to take the lower bound for Simon's algorithm using the polynomial method, turn it into an adversary one, and then again turn it into a learning graph algorithm, this would probably not work. (If it were me, I would find it directly in the learning graph framework). Our reduction is from the polynomial method to the multiplicative adversary method (which is stronger than the general additive). I am not aware of a connection with span-programs since the multiplicative adversary method is not a SDP. $\endgroup$ – Loïck Sep 14 '12 at 4:02
  • 1
    $\begingroup$ @Loïck: Right. Even if the optimal additive adversary matrix for Simon's problem is found, it's not clear how to construct a span program (or learning graph) for that. $\endgroup$ – Robin Kothari Sep 14 '12 at 4:39

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.