1
$\begingroup$

This is a (hopefully) sharper version of a question that I asked previously.

Which of these algorithms is believed to have a longer asymptotic runtime?

  1. The optimal algorithm guaranteed to solve some NP-complete problem using a standard Turing machine.
  2. The optimal algorithm guaranteed to solve the problem described by Raz and Tal using a Turing machine with access to the oracle described in their paper. (This is the oracle $O$ that achieves the oracle separation $\mathrm{BQP}^O \nsubseteq \mathrm{PH}^O$.)

(I understand that this is somewhat of an "apples-to-orange" comparison because the two Turing machines have different capabilities, but you can still compare the algorithm runtimes.)

Figure 3 of this essay suggests to me that NP-complete problems are much "harder" than BQP-complete problems, which would seem to suggest that algorithm 1 would need to take longer than algorithm 2. But Raz and Tal's result seems to identify an oracle problem in BQP that is outside of the entire polynomial hierarchy (including all of NP), which would seem to suggest that algorithm 2 would need to take longer than algorithm 1. Which of these intuitions is/are incorrect?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.