The Acrobatics of BQP

Just in case anyone is depressed this afternoon and needs something to cheer them up, students William Kretschmer, DeVon Ingram, and I have finally put out a new paper:

The Acrobatics of BQP

Abstract: We show that, in the black-box setting, the behavior of quantum polynomial-time (BQP) can be remarkably decoupled from that of classical complexity classes like NP. Specifically:

– There exists an oracle relative to which NPBQP⊄BQPPH, resolving a 2005 problem of Fortnow. Interpreted another way, we show that AC0 circuits cannot perform useful homomorphic encryption on instances of the Forrelation problem. As a corollary, there exists an oracle relative to which P=NP but BQP≠QCMA.

– Conversely, there exists an oracle relative to which BQPNP⊄PHBQP.

– Relative to a random oracle, PP=PostBQP is not contained in the “QMA hierarchy” QMAQMA^QMA^…, and more generally PP⊄(MIP*)(MIP*)^(MIP*)^… (!), despite the fact that MIP*=RE in the unrelativized world. This result shows that there is no black-box quantum analogue of Stockmeyer’s approximate counting algorithm.

– Relative to a random oracle, Σk+1⊄BQPΣ_k for every k.

– There exists an oracle relative to which BQP=P#P and yet PH is infinite. (By contrast, if NP⊆BPP, then PH collapses relative to all oracles.)

– There exists an oracle relative to which P=NP≠BQP=P#P.

To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which BQP⊄PH, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a “quantum-aware” version of the random restriction method, a concentration theorem for the block sensitivity of AC0 circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.

Incidentally, particularly when I’ve worked on a project with students, I’m often tremendously excited and want to shout about it from the rooftops for the students’ sake … but then I also don’t want to use this blog to privilege my own papers “unfairly.” Can anyone suggest a principle that I should follow going forward?

50 Responses to “The Acrobatics of BQP”

  1. Tu Says:

    Scott,

    This is your blog. It is completely fine for you to celebrate your students work on your blog. If other students don’t have advisors with awesome blogs, that is their problem!

  2. JimV Says:

    I don’t see any problem with announcing any or all of your papers on your blog.

    (If I had a blog I would talk about new stuff I had done, as well as other things.)

    Congratulations on the paper!

  3. DS Says:

    Perhaps allow student-authors of student-led papers (for some definition of that term, e.g., primary authors are students) that prove “major results” to guest-post on this blog at some periodic cadence? Since this is your blog, you get to decide what constitutes a major or interesting result; also, in the spirit of your blog, this can inspire students to write up a version of their result for a broad audience. The banner of this blog can also help shed light on nice results by students from less-well-known institutions.

  4. Grad student Says:

    I follow this blog in part *because* I am curious about what you, who I like as a person because I’ve been reading your blog for nearly a decade now, have been working on. It would be a shame if you were to post less about your work.

  5. Scott Lawrence Says:

    If you use this blog to promote your own papers, then others will feel pressure to start their own blogs. Then we’ll end up with more computational complexity blogs. So from a slightly consequentialist/utilitarian standpoint… sounds good to me!

    (And of course I also agree with the takes of Tu and JimV and Grad student above.)

  6. Ajit R. Jadhav Says:

    Oh, so simple… Privilege, for instance, my upcoming paper(s) on QM when(ever) they arrive.

    Best,
    –Ajit

  7. Jay Searson Says:

    Privilege them unfairly. 100%.

  8. Bruno Loff Says:

    It’s your blog, no one really expects it to be a cold, unbiased source of universal truth. If you want to distinguish such posts from posts where you are actually trying to be unbiased, just prefix the post with a disclaimer, like you did now.

  9. John Preskill Says:

    I’m always interested in what Scott Aaronson is “tremendously excited” about, even if it does not involve students. I’m sure many other readers feel the same way.

  10. Scott Says:

    Ok, thanks everyone!! I’m constantly making the error of seeking out the people on social media who dislike me most, and assuming their views should be paramount in my mind, and everything I write or don’t write from that point forward should be in an effort to try to satisfy them. I’m sure I’ll make that error many more times, despite all my attempts to correct for it.

  11. A student Says:

    Hi Scott. A basic question that you may have answered many times. Why do we believe quantum computers maynot solve NP-hard problems in polynomial time?

  12. Michael Ball Says:

    Yay complexity! This looks really interesting. Keep it coming 🙂

  13. Scott Says:

    A student #11: We have indeed discussed many times (especially in this blog’s early days), but briefly, it’s the same sort of reasons someone might have for believing P≠NP, just “quantized.” I.e.,

    (1) Shor’s algorithm works only by exploiting extremely special structure in factoring and discrete log, which isn’t shared by any known NP-complete problem.

    (2) Grover’s algorithm is provably optimal for speeding up brute-force search. Thus, any attempt to do better would indeed need to exploit structure in an NP-complete problem.

    (3) There have by now been 25 years of attempts to find quantum algorithms that exploit the structure of NP-complete problems, including the adiabatic algorithm and QAOA. None of these have succeeded in beating the Grover speedup in the worst case.

    Together, this obviously doesn’t add up to a proof of NP⊄BQP—we don’t even have a proof of P≠NP!—but it makes clear that any quantum algorithm that even beat the Grover speedup for typical NP-complete problems, let alone solving them in polynomial time, would be a revolutionary advance.

  14. asdf Says:

    but then I also don’t want to use this blog to privilege my own papers “unfairly.”

    That’s right! If Aaronson wants to publicize his papers, let him post about them on his own blog! Oh wait…

    More seriously, look at Terry Tao’s blog for example. He always announces his new papers there and I’m sure no one has a problem with it.

  15. HasH Says:

    John Preskill #9: “I’m always interested in what Scott Aaronson is “tremendously excited” about, even if it does not involve students. I’m sure many other readers feel the same way.”

    Thank you Sir, I feel the same but I cannot express myself with my primitive English! *heart* and *hi5″ emojis.

    I read every post when Scott upload (checking almost everyday). Even I have no idea what is “Σk+1⊄BQPΣ_k” or “P=NP≠BQP=P#P” but I feel my intelligent point increase every post and comments I read 🙂

    Peace and Cheers from Overseas!

  16. Tim Converse Says:

    Scott,

    I have a question that I’d like to ask – relevant to the computational content on your blog, but not relevant to this post or any other recent post. So – do you have any plans for an Ask Me Anything anytime soon? (I ask forgiveness for the fact that this very comment is itself a question that is relevant to your blog but not to this post. 🙂 )

  17. Scott Says:

    Tim Converse #16: I’ll consider doing one after the end of the semester.

  18. Lance Fortnow Says:

    Let me tell your readers why I’m excited by this work. It highlights a fundamental difference between quantum and probabilistic computing–that you can’t pull out the quantumness in a computation like you can for randomness.

  19. Scott Says:

    Thanks Lance!! Indeed, virtually every result in our paper codifies that intuition in one way or another.

  20. Matt Says:

    Just go for it IMO, especially when you’re genuinely excited about the work. If you found yourself being artificially quiet (or negative) about other people’s papers because you saw them as competitors, that would be something to fight against. But a personal blog is a perfectly good place for enthusiastic promotion of whatever interests you, including stuff you have done or played a role in.

  21. matt Says:

    Scott 13: when you say “any quantum algorithm that even beat the Grover speedup for typical NP-complete problems, let alone solving them in polynomial time, would be a revolutionary advance”, what is a “typical NP-complete problem”? Would random instances of high degree MAX-2-SAT count as typical? Or worst case instances, or what?

  22. Scott Says:

    matt #21: What I had in mind there was, NP-complete problems like 3SAT or CircuitSAT or Clique or TSP, etc., rather than artificial monstrosities like

    “if the first bit of the input is 0, then factor the number encoded by the remaining n-1 bits; otherwise, solve 3SAT on the next n0.01 bits.”

    The above is indeed an NP-complete problem for which QCs can get more than the Grover speedup, but in a completely uninteresting way! 🙂

    I was still thinking about worst-case instances.

    Average-case NP-complete problems are a different beast. There, it would surprise me a lot less if it was possible to beat the Grover speedup for some natural input distributions, although I still haven’t seen a compelling case that the adiabatic algorithm, QAOA, or other such algorithms actually do so—have I missed something?

  23. matt Says:

    Scott 22: assuming widely believed statistical physics “conjectures” on the entropy of low energy states in the Sherrington-Kirkpatrick model, the short-path algorithm provably achieves a (fairly small) polynomial speedup over Grover for the exact ground state.

    Actually I am not sure if these are conjectures or not. They might be rigorously proven.

  24. Scott Says:

    matt #23: For Sherrington-Kirkpatrick, doesn’t Montanari’s algorithm also find a near-optimal solution in classical polynomial time, at least under some plausible conjecture? (I’m just going off what Ed Farhi said when he spoke in our group meeting recently.)

    In general, the relevant question is of course super-Grover improvement over the best known classical algorithm—many or even most natural NP-complete problems have nontrivial-but-still-exponential classical algorithms, and no one is shocked unless you beat that by more than a square root.

    If you’re telling me that the short-path algorithm gets a super-Grover improvement even in this strong sense, what’s a good reference?

  25. matt Says:

    Montanari’s finds a near-optimal solution under a widely believed conjecture.
    Short-path is for the exact optimal solution, not a near optimal solution.
    https://arxiv.org/pdf/1802.10124.pdf

    I don’t know a classical algorithm that finds a strictly optimal solution in time 2^{cN} for c<1 for typical instances. But of course such an algorithm may exist…. And one obvious guess to find it is to think about the entropy of low energy solutions and somehow be able to explore a space of slightly smaller than maximal entropy by perhaps ruling out certain possible configurations (e.g., brute force loop over all assignments to 0.99N spins. On the remaining 0.01 spins, hope that this allows you to reduce the entropy enough to ignore many of the configurations). In which case, it would take a lot of thinking to figure out which is better.

  26. Scott Says:

    matt #25: OK, thanks very much! I vaguely remembered your paper on the short path algorithm but hadn’t connected it to the Sherrington-Kirkpatrick model. By how much do you expect the algorithm beats Grover—is it more like 20.49n or 20.01n, or something else entirely? (Apologies; I looked through the paper and must have missed where you say.)

  27. Mitchell Porter Says:

    Lance #18, Scott #19: So if this paper shows the difficulty of pinning down what’s quantum about BQP, perhaps it should be considered in conjunction with 2111.09079, which studies how to dequantize quantum-SVT, recently (2105.02859) proposed as the common ingredient of most known quantum algorithms?

  28. Scott Says:

    Mitchell Porter #27: If anything, the situation is the opposite—our paper shows that, in the black-box setting, you really can “pin down what’s quantum about BQP,” demonstrating a bunch of dramatic differences between it and BPP basically by leveraging BQP’s ability to solve the Forrelation problem.

    Yes, there’s also a lot of important work happening right now on the dequantization of “applied” (non-black-box) quantum algorithms, but that’s very different from what we do!

  29. matt Says:

    Scott 26: It is a small improvement. Definitely not 2^{0.01 n}. The reference to S-K is written in the style of “it would be crazy given what we know about S-K if this didn’t give at least 2^{0.49n}”. But I made no real attempt to figure out what the actual power would be given our understanding of S-K. I would expect it is better than 2^{0.49 n} but I don’t remember. It’s been a while!

  30. Douglas Knight Says:

    Scott,
    Use the Harrison Bergeron heuristic for fairness: don’t cripple yourself. Maybe you should take positive actions to increase fairness, but failing to take action (eg, promoting papers on your blog) is probably just making the world worse.

  31. Timothy G Flynn Says:

    Scott:

    If \(C_1\) and \(C_2\) are complexity classes and \(R\) is a relation such as: \(=\), \(\neq\), \(\subseteq\), \(\not\subseteq\), etc, do we know of any triple \(C_1, C_2, R\) such that it can be proven that there does not exist an oracle \(A\) such that \({C_1}^A R {C_2}^A\).

  32. Scott Says:

    Timothy G Flynn #31: Absolutely, yes! Any inclusion or separation among complexity classes that’s proven in a relativizing way — and that means most of the ones we know — gives another example of what you’re asking for. To give just two examples out of hundreds, there are no oracles relative to which P=EXP (because of the Time Hierarchy Theorem), and there are no oracles relative to which PH⊄P#P (because of Toda’s Theorem, which also relativizes).

  33. Jonathan Thornburg Says:

    Scott: Yes, IMHO it is perfectly appropriate to use your blog to describe/announce/publicise/summarise your (and your students’) own papers (or any other papers that strike your fancy, for that matter).

  34. Dave Says:

    I second what everyone else said, but I must add that you should **really** delete your twitter account and quit reading that website. Really, you’ll live better and have more time to spend for your life, family and research, instead of worrying what the twitterverse thinks, which in any case is irrelevant. Same thing with Facebook and other social media you may use, perhaps (and just perhaps) with the exception of LinkedIn. It’s clearly grown into a massive, useless waste of time (at least with ole fashioned TV the waste of time brought some solace, education or relaxation….)

    You have this blog for some public interaction, an email address for private communication, and these suffice.

    It goes without saying that I’ve done exactly that myself.

  35. Scott Says:

    Dave #34: Thanks! Just to clarify, though, I don’t have and have never had a Twitter account—it reminds me too much of being in high school, and I do indeed feel like email, Facebook, and this blog are more than enough for me. The trouble is that, if people are talking about me on some public platform, then even if I don’t have an account there, I can’t help but look. Even if I know it will just depress me while providing zero useful new insight. It’s like picking at scabs, which I also do.

    The one big bright spot is that, having survived a thermonuclear online denunciation campaign 7 years ago, I can always say to myself, “oh, this isn’t nearly as bad as that was,” and immediately feel better. 🙂

  36. ABCDEFG Says:

    Where can I buy one of the black boxes? Oracle?

  37. Scott Says:

    ABCDEFG #36: Querying Oracle first is a … relatively good idea, but you might need to adapt based on the query outcome.

  38. arch1 Says:

    “…when I’ve worked on a project with students, I’m often tremendously excited and want to shout about it from the rooftops for the students’ sake … but then I also don’t want to use this blog to privilege my own papers ‘unfairly.'”

    I suspect you may be overthinking this in the context of a personal blog, but if you’re not convinced by this or the other comments in that direction, you might just ask yourself whether your rooftop-shouting is any louder than it would have been if the project had been done by the student(s) independently of you. If it wouldn’t (and in your case I suspect it rarely would), and your thought experiment is reasonably unbiased, then you *can’t* be privileging your own papers unfairly.

  39. Curious Says:

    “This result shows that there is no black-box quantum analogue of Stockmeyer’s approximate counting algorithm.”

    Why?

    Also on “By contrast, if NP⊆BPP, then PH collapses relative to all oracles.”.

    PH is known to be infinite wrt to a random oracle. So contrapositive means something unknown on np vs bpp. I am confused.

    Please explain both.

  40. Scott Says:

    Curious #39: How about if I just paste the passage from our paper that directly answers your first question?

      We mention another interesting interpretation of Theorem 7: it can be understood as showing that in the black box setting, there is no quantum analogue of Stockmeyer’s approximate countingalgorithm [Sto83]. For a probabilistic machine M that runs in poly(n) time and an error bound ε ≥ 1 , the approximate counting problem is to estimate the acceptance probability of M up to a multiplicative factor of 1 + ε. Stockmeyer’s algorithm [Sto83] gives a poly(n)-time reduction from the approximate counting problem to a problem in the third level of the polynomial hierarchy, and moreover, this reduction relativizes.
      One might wonder: is there a version of Stockmeyer’s algorithm for the quantum approximate counting problem, where we instead wish to approximate the acceptance probability of a quantum algorithm? By well-known reductions involving Aaronson’s postselection theorem [Aar05], all problems in PP = PostBQP efficiently reduce to the quantum approximate counting problem (see e.g. [Kup15, Proposition 2.14]). Hence, Theorem 7 implies that the quantum approximate counting problem cannot reduce efficiently to the QMA hierarchy in a black box manner, giving some sense in which a quantum analogue of Stockmeyer’s algorithm is impossible.

    As for your second question, the meaning of the sentence is that every oracle that causes NP⊆BPP, also causes PH to collapse. A random oracle causes neither to happen, and therefore is consistent with what I just said.

  41. Sniffnoy Says:

    Curious #39, Scott #40:

    I think there’s an issue of parenthesization here. The statement “If NP⊆BPP, then PH collapses relative to all oracles” can be read as “(If NP⊆BPP, then PH collapses) relative to all oracles” or as “If NP⊆BPP, then (PH collapses relative to all oracles)”. It looks like Scott intended the first meaning and Curious read it as the second.

  42. Scott Says:

    Sniffnoy #41: Ah, thanks! This is one of those cases where the intended interpretation was so obvious to me that I didn’t even notice the other one.

  43. Curious Says:

    There is no quantum stockemeyer because “By well-known reductions involving Aaronson’s postselection theorem [Aar05], all problems in PP = PostBQP efficiently reduce to the quantum approximate counting problem (see e.g. [Kup15, Proposition 2.14]). Hence, Theorem 7 implies that the quantum approximate counting problem cannot reduce efficiently to the QMA hierarchy in a black box manner, giving some sense in which a quantum analogue of Stockmeyer’s algorithm is impossible.”

    .. or in easy to read English for beginners “.. else PP is in QMA hierarchy?”.

  44. Scott Says:

    Curious #43: Classical Stockmeyer says that PostBPP (or, multiplicatively approximating the acceptance probability of a classical algorithm) is easy if NP is easy. So wouldn’t a natural quantum Stockmeyer say that PostBQP (or, multiplicatively approximating the acceptance probability of a quantum algorithm) is easy if QMA is easy? That’s exactly what we rule out in the black-box setting. Should we have worded it differently to be clearer?

  45. Curious Says:

    Yes simple direct English is traditionally better to read for a non quantum researcher.

  46. Taymon A. Beal Says:

    Scott, have you said anything about what you personally believe about the third fundamental question from the introduction (“What is the best classical upper bound on the power of quantum computation?”)? Your 2009 paper “presents evidence” that it’s higher than PH, but do you actually believe that’s the case? If so, do you think it tops out at AWPP (the smallest class I could find that’s been proven to contain BQP), or might there be some smaller interesting classical class that contains it?

    Apologies if this was in QCSD or an earlier blog post and I missed it.

  47. Scott Says:

    Taymon A. Beal #46: I strongly believe that there are search, sampling, and promise problems that are solvable in quantum polynomial time but are not in the polynomial hierarchy (good candidates being BosonSampling or dozens of other tasks involving quantum simulation). Many outsiders don’t even realize that that’s different from BQP⊄PH, which refers strictly to languages (ie total decision problems). The latter is a much harder question—if forced to bet, I’d bet on BQP⊄PH, but we still don’t have a single good candidate language for the separation and I’m very open to the possibility that it goes the other way.

  48. OhMyGoodness Says:

    Your students are just very fortunate to have an enthusiastic supportive mentor with a widely read blog, you. If you didn’t have results of your own then they wouldn’t benefit from a widely read blog. 🙂

  49. matt Says:

    Scott 47: what does it mean when you say that you conjecture that some sampling problems are not in the polynomial hierarchy? I thought that PH is a class of decision problems (exactly the point you were making in that comment, I thought!), so by definition sampling problems aren’t in there. Do you mean that you conjecture that some sampling problems cannot be solved by a classical poly time algorithm with an oracle for PH? Or something else?

  50. Scott Says:

    matt #49: Yes, that’s exactly what I meant. Define SampPH = SampBPPPH; then even if exact BosonSampling was only in SampPH rather than SampBPP, my paper with Arkhipov showed that PH would still collapse.

Leave a Reply

Comment Policy: All comments are placed in moderation and reviewed prior to appearing. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, or snide and patronizing tone. Also: comments that link to a paper or article and, in effect, challenge me to respond to it are at severe risk of being left in moderation, as such comments place demands on my time that I can no longer meet. You'll have a much better chance of a response from me if you formulate your own argument here, rather than outsourcing the job to someone else. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email.

You can now use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.