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:
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?
Follow
Comment #1 November 19th, 2021 at 5:19 pm
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!
Comment #2 November 19th, 2021 at 5:33 pm
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!
Comment #3 November 19th, 2021 at 5:35 pm
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.
Comment #4 November 19th, 2021 at 7:30 pm
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.
Comment #5 November 19th, 2021 at 11:51 pm
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.)
Comment #6 November 20th, 2021 at 12:09 am
Oh, so simple… Privilege, for instance, my upcoming paper(s) on QM when(ever) they arrive.
Best,
–Ajit
Comment #7 November 20th, 2021 at 1:54 am
Privilege them unfairly. 100%.
Comment #8 November 20th, 2021 at 4:17 am
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.
Comment #9 November 20th, 2021 at 10:18 am
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.
Comment #10 November 20th, 2021 at 10:43 am
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.
Comment #11 November 20th, 2021 at 11:10 am
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?
Comment #12 November 20th, 2021 at 11:13 am
Yay complexity! This looks really interesting. Keep it coming 🙂
Comment #13 November 20th, 2021 at 12:09 pm
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.
Comment #14 November 20th, 2021 at 12:53 pm
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.
Comment #15 November 20th, 2021 at 3:34 pm
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!
Comment #16 November 20th, 2021 at 11:31 pm
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. 🙂 )
Comment #17 November 20th, 2021 at 11:32 pm
Tim Converse #16: I’ll consider doing one after the end of the semester.
Comment #18 November 21st, 2021 at 9:21 am
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.
Comment #19 November 21st, 2021 at 11:02 am
Thanks Lance!! Indeed, virtually every result in our paper codifies that intuition in one way or another.
Comment #20 November 21st, 2021 at 5:24 pm
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.
Comment #21 November 21st, 2021 at 7:33 pm
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?
Comment #22 November 21st, 2021 at 8:52 pm
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?
Comment #23 November 21st, 2021 at 9:26 pm
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.
Comment #24 November 21st, 2021 at 10:14 pm
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?
Comment #25 November 21st, 2021 at 10:29 pm
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.
Comment #26 November 21st, 2021 at 11:35 pm
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.)
Comment #27 November 22nd, 2021 at 1:21 am
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?
Comment #28 November 22nd, 2021 at 1:28 am
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!
Comment #29 November 22nd, 2021 at 11:09 am
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!
Comment #30 November 22nd, 2021 at 2:35 pm
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.
Comment #31 November 22nd, 2021 at 3:15 pm
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\).
Comment #32 November 22nd, 2021 at 3:58 pm
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).
Comment #33 November 22nd, 2021 at 4:02 pm
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).
Comment #34 November 22nd, 2021 at 9:49 pm
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.
Comment #35 November 22nd, 2021 at 10:09 pm
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. 🙂
Comment #36 November 23rd, 2021 at 9:27 am
Where can I buy one of the black boxes? Oracle?
Comment #37 November 23rd, 2021 at 9:56 am
ABCDEFG #36: Querying Oracle first is a … relatively good idea, but you might need to adapt based on the query outcome.
Comment #38 November 23rd, 2021 at 11:43 am
“…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.
Comment #39 November 24th, 2021 at 2:21 am
“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.
Comment #40 November 24th, 2021 at 3:00 am
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.
Comment #41 November 24th, 2021 at 2:36 pm
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.
Comment #42 November 24th, 2021 at 3:20 pm
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.
Comment #43 November 24th, 2021 at 4:12 pm
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?”.
Comment #44 November 24th, 2021 at 5:22 pm
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?
Comment #45 November 24th, 2021 at 6:06 pm
Yes simple direct English is traditionally better to read for a non quantum researcher.
Comment #46 November 27th, 2021 at 11:21 pm
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.
Comment #47 November 28th, 2021 at 8:17 am
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.
Comment #48 November 28th, 2021 at 10:18 am
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. 🙂
Comment #49 November 28th, 2021 at 9:21 pm
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?
Comment #50 November 28th, 2021 at 10:05 pm
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.