The relativized BQP vs. PH problem (1993-2018)
Update (June 4): OK, I think the blog formatting issues are fixed now—thanks so much to Jesse Kipp for his help!
True story. A couple nights ago, I was sitting in the Knesset, Israel’s parliament building, watching Gilles Brassard and Charles Bennett receive the Wolf Prize in Physics for their foundational contributions to quantum computing and information. (The other laureates included, among others, Beilinson and Drinfeld in mathematics; the American honeybee researcher Gene Robinson; and Sir Paul McCartney, who did not show up for the ceremony.)
Along with the BB84 quantum cryptography scheme, the discovery of quantum teleportation, and much else, Bennett and Brassard’s seminal work included some of the first quantum oracle results, such as the BBBV Theorem (Bennett, Bernstein, Brassard, Vazirani), which proved the optimality of Grover’s search algorithm, and thus the inability of quantum computers to solve NP-complete problems in polynomial time in the black-box setting. It thereby set the stage for much of my own career. Of course, the early giants were nice enough to bequeath to us a few problems they weren’t able to solve, such as: is there an oracle relative to which quantum computers can solve some problem outside the entire polynomial hierarchy (PH)? That particular problem, in fact, had been open from 1993 all the way to the present, resisting sporadic attacks by me and others.
As I sat through the Wolf Prize ceremony — the speeches in Hebrew that I only 20% understood (though with these sorts of speeches, you can sort of fill in the inspirational sayings for yourself); the applause as one laureate after another announced that they were donating their winnings to charity; the ironic spectacle of far-right, ultranationalist Israeli politicians having to sit through a beautiful (and uncensored) choral rendition of John Lennon’s “Imagine” — I got an email from my friend and colleague Avishay Tal. Avishay wrote that he and Ran Raz had just posted a paper online giving an oracle separation between BQP and PH, thereby putting to rest that quarter-century-old problem. So I was faced with a dilemma: do I look up, at the distinguished people from the US, Canada, Japan, and elsewhere winning medals in Israel, or down at my phone, at the bombshell paper by two Israelis now living in the US?
For those tuning in from home, BQP, or Bounded-Error Quantum Polynomial Time, is the class of decision problems efficiently solvable by a quantum computer. PH, or the Polynomial Hierarchy, is a generalization of NP to allow multiple quantifiers (e.g., does there exist a setting of these variables such that for every setting of those variables, this Boolean formula is satisfied?). These are two of the most fundamental complexity classes, which is all the motivation one should need for wondering whether the former is contained in the latter. If additional motivation is needed, though, we’re effectively asking: could quantum computers still solve problems that were classically hard, even in a hypothetical world where P=NP (and hence P=PH also)? If so, the problems in question could not be any of the famous ones like factoring or discrete logarithms; they’d need to be stranger problems, for which a classical computer couldn’t even recognize a solution efficiently, let alone finding it.
And just so we’re on the same page: if BQP ⊆ PH, then one could hope for a straight-up proof of the containment, but if BQP ⊄ PH, then there’s no way to prove such a thing unconditionally, without also proving (at a minimum) that P ≠ PSPACE. In the latter case, the best we can hope is to provide evidence for a non-containment—for example, by showing that BQP ⊄ PH relative to a suitable oracle. What’s noteworthy here is that even the latter, limited goal remained elusive for decades.
In 1993, Bernstein and Vazirani defined an oracle problem called Recursive Fourier Sampling (RFS), and proved it was in BQP but not in BPP (Bounded-Error Probabilistic Polynomial-Time). One can also show without too much trouble that RFS is not in NP or MA, though one gets stuck trying to put it outside AM. Bernstein and Vazirani conjectured—at least verbally, I don’t think in writing—that RFS wasn’t even in the polynomial hierarchy. In 2003, I did some work on Recursive Fourier Sampling, but was unable to find a version that I could prove was outside PH.
Maybe this is a good place to explain that, by a fundamental connection made in the 1980s, proving that oracle problems are outside the polynomial hierarchy is equivalent to proving lower bounds on the sizes of AC0 circuits—or more precisely, constant-depth Boolean circuits with unbounded fan-in and a quasipolynomial number of AND, OR, and NOT gates. And proving lower bounds on the sizes of AC0 circuits is (just) within complexity theory’s existing abilities—that’s how, for example, Furst-Saxe-Sipser, Ajtai, and Yao managed to show that PH ≠ PSPACE relative to a suitable oracle (indeed, even a random oracle with probability 1). Alas, from a lower bounds standpoint, Recursive Fourier Sampling is a horrendously complicated problem, and none of the existing techniques seemed to work for it. And that wasn’t even the only problem: even if one somehow succeeded, the separation that one could hope for from RFS was only quasipolynomial (n versus nlog n), rather than exponential.
Ten years ago, as I floated in a swimming pool in Cambridge, MA, it occurred to me that RFS was probably the wrong way to go. If you just wanted an oracle separation between BQP and PH, you should focus on a different kind of problem—something like what I’d later call Forrelation. The Forrelation problem asks: given black-box access to two Boolean functions f,g:{0,1}n→{0,1}, are f and g random and independent, or are they random individually but with each one close to the Boolean Fourier transform of the other one? It’s easy to give a quantum algorithm to solve Forrelation, even with only 1 query. But the quantum algorithm really seems to require querying all the f- and g-inputs in superposition, to produce an amplitude that’s a global sum of f(x)g(y) terms with massive cancellations in it. It’s not clear how we’d reproduce this behavior even with the full power of the polynomial hierarchy. To be clear: to answer the question, it would suffice to show that no AC0 circuit with exp(poly(n)) gates could distinguish a “Forrelated” distribution over (f,g) pairs from the uniform distribution.
Using a related problem, I managed to show that, relative to a suitable oracle—in fact, even a random oracle—the relational version of BQP (that is, the version where we allow problems with many valid outputs) is not contained in the relational version of PH. I also showed that a lower bound for Forrelation itself, and hence an oracle separation between the “original,” decision versions of BQP and PH, would follow from something that I called the “Generalized Linial-Nisan Conjecture.” This conjecture talked about the inability of AC0 circuits to distinguish the uniform distribution from distributions that “looked close to uniform locally.” My banging the drum about this, I’m happy to say, initiated a sequence of events that culminated in Mark Braverman’s breakthrough proof of the original Linial-Nisan Conjecture. But alas, I later discovered that my generalized version is false. This meant that different circuit lower bound techniques, ones more tailored to problems like Forrelation, would be needed to go the distance.
I never reached the promised land. But my consolation prize is that Avishay and Ran have now done so, by taking Forrelation as their jumping-off point but then going in directions that I’d never considered.
As a first step, Avishay and Ran modify the Forrelation problem so that, in the “yes” case, the correlation between f and the Fourier transform of g is much weaker (though still detectable using a quantum algorithm that makes nO(1) queries to f and g). This seems like an inconsequential change—sure, you can do that, but what does it buy you?—but it turns out to be crucial for their analysis. Ultimately, this change lets them show that, when we write down a polynomial that expresses an AC0 circuit’s bias in detecting the forrelation between f and g, all the “higher-order contributions”—those involving a product of k terms of the form f(x) or g(y), for some k>2—get exponentially damped as a function of k, so that only the k=2 contributions still matter.
There are a few additional ideas that Raz and Tal need to finish the job. First, they relax the Boolean functions f and g to real-valued, Gaussian-distributed functions—very similar to what Andris Ambainis and I did when we proved a nearly-tight randomized lower bound for Forrelation, except that they also need to truncate f and g so they take values in [-1,1]; they then prove that a multilinear polynomial has no way to distinguish their real-valued functions from the original Boolean ones. Second, they exploit recent results of Tal about the Fourier spectra of AC0 functions. Third, they exploit recent work of Chattopadhyay et al. on pseudorandom generators from random walks (Chattopadhyay, incidentally, recently finished his PhD at UT Austin). A crucial idea turns out to be to think of the values of f(x) and g(y), in a real-valued Forrelation instance, as sums of huge numbers of independent random contributions. Formally, this changes nothing: you end up with exactly the same Gaussian distributions that you had before. Conceptually, though, you can look at how each tiny contribution changes the distinguishing bias, conditioned on the sum of all the previous contributions; and this leads to the suppression of higher-order terms that we talked about before, with the higher-order terms going to zero as the step size does.
Stepping back from the details, though, let me talk about a central conceptual barrier—one that I know from an email exchange with Avishay was on his and Ran’s minds, even though they never discuss it explicitly in their paper. In my 2009 paper, I identified what I argued was the main reason why no existing technique was able to prove an oracle separation between BQP and PH. The reason was this: the existing techniques, based on the Switching Lemma and so forth, involved arguing (often implicitly) that
- any AC0 circuit can be approximated by a low-degree real polynomial, but
- the function that we’re trying to compute can’t be approximated by a low-degree real polynomial.
Linial, Mansour, and Nisan made this fully explicit in the context of their learning algorithm for AC0. And this is all well and good if, for example, we’re trying to prove the n-bit PARITY function is not in AC0, since PARITY is famously inapproximable by any polynomial of sublinear degree. But what if we’re trying to separate BQP from PH? In that case, we need to deal with the fundamental observation of Beals et al. 1998: that any function with a fast quantum algorithm, by virtue of having a fast quantum algorithm, is approximable by a low-degree real polynomial! Approximability by low-degree polynomials giveth with the one hand and taketh away with the other.
To be sure, I pointed out that this barrier wasn’t necessarily insuperable. For the precise meaning of “approximable by low-degree polynomials” that follows from a function’s being in BQP, might be different from the meaning that’s used to put the function outside of PH. As one illustration, Razborov and Smolensky’s AC0 lower bound method relates having a small constant-depth circuit to being approximable by low-degree polynomials over finite fields, which is different from being approximable by low-degree polynomials over the reals. But this didn’t mean I knew an actual way around the barrier: I had no idea how to prove that Forrelation wasn’t approximable by low-degree polynomials over finite fields either.
So then how do Raz and Tal get around the barrier? Apparently, by exploiting the fact that Tal’s recent results imply much more than just that AC0 functions are approximable by low-degree real polynomials. Rather, they imply approximability by low-degree real polynomials with bounded L1 norms (i.e., sums of absolute values) of their coefficients. And crucially, these norm bounds even apply to the degree-2 part of a polynomial—showing that, even all the way down there, the polynomial can’t be “spread around,” with equal weight on all its coefficients. But being “spread around” is exactly how the true polynomial for Forrelation—the one that you derive from the quantum algorithm—works. The polynomial looks like this:
$$ p(f,g) = \frac{1}{2^{3n/2}} \sum_{x,y \in \left\{0,1\right\}^n} (-1)^{x \cdot y} f(x) g(y). $$
This still isn’t enough for Raz and Tal to conclude that Forrelation itself is not in AC0: after all, the higher-degree terms in the polynomial might somehow compensate for the failures of the lower-degree terms. But this difference between the two different kinds of low-degree polynomial—the “thin” kind that you get from AC0 circuits, and the “thick” kind that you get from quantum algorithms—gives them an opening that they’re able to combine with the other ideas mentioned above, at least for their noisier version of the Forrelation problem.
This difference between “thin” and “thick” polynomials is closely related to, though not identical with, a second difference, which is that any AC0 circuit needs to compute some total Boolean function, whereas a quantum algorithm is allowed to be indecisive on many inputs, accepting them with a probability that’s close neither to 0 nor to 1. Tal used the fact that an AC0 circuit computes a total Boolean function, in his argument showing that it gives rise to a “thin” low-degree polynomial. His argument also implies that no low-degree polynomial that’s “thick,” like the above quantum-algorithm-derived polynomial for Forrelation, can possibly represent a total Boolean function: it must be indecisive on many inputs.
The boundedness of the L1 norm of the coefficients is related to a different condition on low-degree polynomials, which I called the “low-fat condition” in my Counterexample to the Generalized Linial-Nisan Conjecture paper. However, the whole point of that paper was that the low-fat condition turns out not to work, in the sense that there exist depth-three AC0 circuits that are not approximable by any low-degree polynomials satisfying the condition. Raz and Tal’s L1 boundedness condition, besides being simpler, also has the considerable advantage that it works.
As Lance Fortnow writes, in his blog post about this achievment, an obvious next step would be to give an oracle relative to which P=NP but P≠BQP. I expect that this can be done. Another task is to show that my original Forrelation problem is not in PH—or more generally, to broaden the class of problems that can be handled using Raz and Tal’s methods. And then there’s one of my personal favorite problems, which seems closely related to BQP vs. PH even though it’s formally incomparable: give an oracle relative to which a quantum computer can’t always prove its answer to a completely classical skeptic via an interactive protocol.
Since (despite my journalist moratorium) a journalist already emailed to ask me about the practical implications of the BQP vs. PH breakthrough—for example, for the ~70-qubit quantum computers that Google and others hope to build in the near future—let me take the opportunity to say that, as far as I can see, there aren’t any. This is partly because Forrelation is an oracle problem, one that we don’t really know how to instantiate explicitly (in the sense, for example, that factoring and discrete logarithm instantiate Shor’s period-finding algorithm). And it’s partly because, even if you did want to run the quantum algorithm for Forrelation (or for Raz and Tal’s noisy Forrelation) on a near-term quantum computer, you could easily do that sans the knowledge that the problem sits outside the polynomial hierarchy.
Still, as Avi Wigderson never tires of reminding people, theoretical computer science is richly interconnected, and things can turn up in surprising places. To take a relevant example: Forrelation, which I introduced for the purely theoretical purpose of separating BQP from PH (and which Andris Ambainis and I later used for another purely theoretical purpose, to prove a maximal separation between randomized and quantum query complexities), now furnishes one of the main separating examples in the field of quantum machine learning algorithms. So it’s early to say what implications Avishay and Ran’s achievement might ultimately have. In any case, huge congratulations to them.
Follow
Comment #1 June 3rd, 2018 at 11:01 am
Wow, awesome result! Could this also be used to give an oracle separation between BQP and PH/poly (or even just P/poly)?
Comment #2 June 3rd, 2018 at 12:11 pm
If you had turned off your phone for the ceremony, then you would never have faced that dilemma. 🙂
Anyway, what about the reverse containment; is it possible that PH is contained in BQP (either absolutely or relative to some oracle)?
Comment #3 June 3rd, 2018 at 12:36 pm
RandomOracle #1: I think that, if C and D are any two “natural,” uniform complexity classes not differing merely by BP operators, and we have an oracle relative to which C⊄D, then we can extend it to get an oracle relative to which C⊄D/poly. Or in any case, I certainly think it for the case here!
(Would anyone care to flesh out the details of the above implication? It actually sounds like a meta-theorem worth writing up somewhere.)
Comment #4 June 3rd, 2018 at 12:41 pm
Aula #2: If PH⊆BQP, then certainly NP⊆BQP, which would be groundbreaking enough by itself that we might we well focus on the latter! A PSPACE oracle will put NP (and even PH for that matter) in BQP, while the BBBV oracle puts NP outside of BQP.
(Exercise: Classically, P=NP implies P=PH. Does NP⊆BQP similarly imply PH⊆BQP? If not, what does imply that?)
Comment #5 June 3rd, 2018 at 2:16 pm
Wonderful result, and a great explanation. Congrtulations to Ran and Avishai.
I suppose that for sampling problems (Quantum Sampling, or BosonSampling, or even samling distribution described by bounded depth quantum circuits) it is known that if those belongs to PH then PH collapses. Should we regard the new result as a support that BQP is going beyond PH just like those quantum sampling tasks (and thus perhaps BQP already capture the full supremacy power of QC) or perhaps would the new result of Raz and Tal may lead to stronger results also about hardness for quantum sampling problems?
On a related matter I vaguely remember that we discussed the conjecture that if a classical computer with BQP oracle can perform quantum sampling then PH collapses. (Perhaps this is even a theorem by now?) What is the status of this statement in view of the the evidence of beyond-PH-hardness for BQP itself.
Comment #6 June 3rd, 2018 at 2:18 pm
Wonderful result, and a great explanation. Congrtulations to Tal and Avishai.
I suppose that for sampling problems (Quantum Sampling, or BosonSampling, or even sampling distribution described by bounded depth quantum circuits) it is known that if those belongs to PH then PH collapses. Should we regard the new result as a support that BQP is going beyond PH just like those quantum sampling tasks or would the new result of Raz and Tal may lead to stronger results also about hardness for quantum sampling problems?
On a related matter I vaguely remember that we discussed the conjecture that if a classical computer with BQP oracle can perform quantum sampling then PH collapses. (Perhaps this is even a theorem by now?) What is the relation of such a statement in view of the the evidence of beyond-PH-hardness for BQP itself?
Comment #7 June 3rd, 2018 at 3:44 pm
Gil #5: I don’t see a path by which the Raz-Tal result leads to new results about sampling problems—after all, we already had the separation for sampling problems; the entire difficulty here is to get the separation for a decision problem like Noisy Forrelation. (But of course, any time you say you don’t see any path from A to B, you could just be making a statement about your own lack of imagination.)
If FBPPPromiseBQP can do quantum sampling, the conclusion you get is that P#P ⊆ BPPNP^BQP, which is almost but not quite a collapse of PH. I don’t see a direct relation to the Raz-Tal result, except that if BQP had turned out (counterfactually) to be contained in PH, then we would’ve strengthened the conclusion of that other result to PH collapsing.
Comment #8 June 3rd, 2018 at 5:53 pm
Sorry, off-topic, but something’s gone wrong with the blog formatting again:
1. On the main page, the background fails to appear behind the text, so the text is gray-on-black.
2. On the individual post, the “Shtetl-Optimized is proudly powered by WordPress” bar at the bottom doesn’t line up with whatever it’s supposed to line up with.
Comment #9 June 3rd, 2018 at 6:41 pm
Disappointed with Paul McCartney not turning up, some big hitters apart from Trump should show support or at least some basic sympathy for Israel.
Comment #10 June 3rd, 2018 at 11:50 pm
James #8: I didn’t actually know until visiting the website that McCartney had won; they didn’t say anything about him at the ceremony. The other music laureate, Adam Fischer (director of Hungary’s Haydn Orchestra), was there. Fischer’s acceptance speech was about human rights and the rule of law and how they’re being threatened in Hungary. The far-right Israeli politicians applauded that, even though I suspected some of his criticisms may have been implicitly directed at them as well.
Comment #11 June 4th, 2018 at 1:00 am
Sniffnoy #7: I noticed that too, and am very sorry about it! I didn’t change a thing, so it must have been triggered by a WordPress upgrade or something. I wrote to the WordPress people to ask for help. In the meantime, just go to the specific post rather than the blog homepage? Or, if someone were willing to try and help me fix it, please shoot me an email—I can give you temporary access in order to do so.
Comment #12 June 4th, 2018 at 8:56 am
Scott,
Notice that the problem on the website with the background colors does not occur when you click on the comments. It only occurs on the main page.
So I had a look at what is different. Turns out it is the use of “narrowcolumn” CSS class on the div with id “content”. Switching this to use the “widecolumn” instead makes things readable.
Digging further, here is how “narrowcolumn” is defined:
.narrowcolumn {
float: left;
padding: 0 0 20px 45px;
margin: 0px 0 0;
width: 450px;
}
If you comment out “float” property you will see this is the source of the problem.
Hope this helps!
Comment #13 June 4th, 2018 at 11:21 am
Speaking of BB* quantum things – do you think your presence in Israel had anything to do with Netanyahu having started to blurt “quantum” as a successor to “cyber” as Israel’s next frontier of excellence ?
Comment #14 June 4th, 2018 at 12:48 pm
Two questions: First, where does this put us in terms of whether BQP is outside PH relative to a random oracle? Obviously, this would be a strictly stronger claim than there being at least one such oracle; is there any plausible hope that these methods can work to place BQP outside PH relative to a random oracle?
Second, going in the other direction, how weak can oracle A be and still be an oracle for which we can prove that BQP^A is inside PH^A? We can take A to be PSPACE-complete, in which case it is trivial that BQP^A is in PH^A. Can we do better? For example, can we take A=PP?. Note that this doesn’t immediately follow from the fact that BQP is low for PP, since BQP^PP is not necessarily the same as PP^BQP (or if they are the same it isn’t immediately obvious to me). I’d be particularly curious if we can resolve whether BQP^AWPP is in PH^AWPP.
Comment #15 June 4th, 2018 at 1:26 pm
Joshua #13: Ambainis and I have a conjecture that, if true, implies that you can’t even separate BQP from P relative to a random oracle (without separating complexity classes in the “real” world), let alone put BQP outside of PH.
The weakest oracle I can think of that I can prove puts BQP inside PH, would be an oracle for the “quantum polynomial hierarchy” (say, constructed out of the classes QCMA and coQCMA), staggered so that accessing the kth level requires a query of size ~nk. Certainly the counting hierarchy CH, which contains that “QCPH” hierarchy, would suffice.
Comment #16 June 4th, 2018 at 1:49 pm
Thanks or the answer, Scott. It looks that the power of quantum computers comes in various strengths (according to the algorithmic tasks) and there is evidence that they all reach beyond PH. Can we hope for evidence that will take us beyond a higher complexity class? How high can we hope for? Is it fair to say (or even meaningful) that we don’t see evidence for the power of quantum computers going beyond #P? (Namely, an algorithmic task that a QC can perform for which there is evidence it is not in #P.)
Comment #17 June 4th, 2018 at 2:20 pm
Gil #15: Everything QCs can do (including sampling) can be simulated using #P, since #P can calculate the probability of any outcome of a measurement on any qubit, even conditioned on the outcomes of previous measurements.
So if you want to put BQP outside something “even higher” than PH, you’ll need to look at stuff that’s above PH but below (or incomparable to) P#P.
Comment #18 June 4th, 2018 at 5:59 pm
The homepage is still showing grey on black.
Comment #19 June 4th, 2018 at 6:11 pm
But with P there’s P⊆coNP which causes the collapse.
Can PH be contained in BQP without collapsing?
Comment #20 June 5th, 2018 at 12:12 am
Job #18: No one knows whether NP⊆BQP collapses the hierarchy. If, however, BQP⊆AM, then NP⊆BQP (and hence coNP⊆BQP) would certainly collapse PH. So, now that we have an oracle relative to which BQP⊄AM, we could work on an oracle relative to which NP⊆BQP but PH⊄BQP.
Comment #21 June 5th, 2018 at 2:35 am
That seems reasonable, but what would it mean?
Are we trying to show some type of independence between BQP and PH?
Comment #22 June 5th, 2018 at 4:11 am
Job #20: No, it would just mean what it literally says—that there’s no relativizing proof that if quantum computers can solve NP-complete problems in polynomial time, then they can also do everything in PH.
Comment #23 June 5th, 2018 at 9:51 am
Hi Scott,
When will you do another “ask me anything”?
Comment #24 June 5th, 2018 at 10:09 am
lewikee #22: Soon. Would it be better if I did one on Reddit, because of the abiity to upvote popular questions? If so, do you need to be invited to do it, or can you just do it?
Comment #25 June 5th, 2018 at 10:27 am
Scott,
I assume that what you are talking about here is what they are talking about there, right? https://www.newscientist.com/article/2170746-quantum-computers-are-weirder-and-more-powerful-than-we-thought/
I don’t have a subscription to that magazine.
Comment #26 June 5th, 2018 at 11:20 am
Craig #24: I also don’t have a subscription!
But yes, Jacob Aron is the journalist who asked me questions about this, so the article is indeed about it.
I already disagree with the title: for one thing, almost all of us already thought for 20+ years that relativized BQP was outside of PH; the issue was just that we couldn’t prove it! For another thing, BQP containing problems outside of PH maps extremely imperfectly onto QCs being “more powerful.” The BQP problems that are outside PH aren’t necessarily ones that we’d care about for any reason other than their not being in PH (they might be, but they don’t have to be).
Comment #27 June 5th, 2018 at 1:02 pm
In what proportion of the multiverse do we find an error in the proof?
Comment #28 June 5th, 2018 at 1:40 pm
As you’ve discussed before (e.g. in post p=613), David Deutsch takes the massive-parallelism picture more seriously than most complexity theorists, and holds the fairly heterodox view that quantum supremacy over classical computers would “prove” the Many-Worlds Intepretation (on the grounds that there aren’t enough physical resources in a single universe to solve difficult instances of problems in BQP).
Do you think that an unconditional proof that BQP⊄PH would tend to undermine this idea? It’s difficult for me to see how any kind of “exponential classical parallelism” could be more powerful than an alternating Turing machine and therefore solve problems outside of PH, as a quantum computer could if BQP⊄PH.
Comment #29 June 5th, 2018 at 2:02 pm
fred #26: Of course it hasn’t been verified yet (at any rate, I certainly didn’t work through it line by line), so some caution is advised. I’m giving it the benefit of the doubt based on the track record of the authors, and more importantly, the fact that everything I understood (including how the proof circumvents the “low-degree polynomial barrier”) was clear and sensible. But if there turned out to be a bug, I’d be sure to post an update! I’m not going to estimate a multiverse measure where that happens.
Comment #30 June 5th, 2018 at 2:13 pm
Ted #27: I’m not seeing the connection between the things. Any Many-Worlds proponent who knows anything, including Deutsch, will tell you that according to MWI, the class of decision problems that a quantum computer can efficiently solve is BQP, and BQP is exactly as large or small as complexity theory says it is. MWI proponents might be more eager than others to describe QC using the language of exponential parallelism, but when it gets down to brass tacks, their mathematical model of QC is exactly the same as that of anyone else who accepts quantum mechanics.
Even more to the point: if you could do exponential number of classical computations in parallel, and then combine the results using any formula of polynomial depth, the class of problems that you could solve would be PSPACE, which is larger than PH and which has long been known to contain BQP.
So, for those who dislike describing quantum computations using “parallel universe” imagery, the objection is not that an exponential number of classical parallel processes would be too weak to capture BQP! On the contrary, the objection is that classical exponential parallelism is overkill, that it gives you BQP but a ton of extra stuff besides, and thus it doesn’t tightly fit the data point that we’re trying to explain.
Comment #31 June 5th, 2018 at 3:14 pm
And, we have blog breakage again…
Comment #32 June 5th, 2018 at 3:39 pm
Scott #29: For the record, I certainly didn’t think that classical exponential parallelism was too *weak* to capture BQP! You have done your pedagogical job well with this blog :-). I just had in mind a slightly different model of the exponential parallelism fallacy, where you couldn’t combine results from different branches using arbitrary polynomial-depth circuits (which as you say would give PSPACE), but instead where one accepting branch magically “emerges” at the end and all the other branches “vanish” without otherwise “talking to” the accepting branch. If I understand correctly, this is exactly equivalent to a nondeterministic Turing machine and so would yield NP as the class of problems that could be solved in polynomial time.
Both versions of “exponential parallelism” are completely wrong for describing quantum computers, but they’re wrong in different ways: your version is (probably strictly) too powerful, in that it yields a class PSPACE that (probably strictly) contains BQP, while my version is (probably strictly) too powerful for most practical problems, like NP-complete ones, but is not powerful enough for a few quirky problems if indeed BQP⊄NP.
Comment #33 June 5th, 2018 at 4:28 pm
What a beautiful result!
By the way, I’m another author in that paper with Eshan Chattopadhyay, another connection to UT Austin 🙂
Comment #34 June 5th, 2018 at 5:51 pm
I confess I’m struggling to understand all this but this is what *I think* you’re saying:
This new result does not prove a quantum computer could solve all nondeterministic polynomial time problem in polynomial time but it does prove that even if P=NP and even if we had a algorithm that could solve NP problems on a conventional computer in polynomial time there would still be a class of problems a conventional computer couldn’t solve efficiently but a quantum computer could. And this class of very exotic problems may be of fundamental interest in themselves or they may be interesting for no reason other than that a conventional computer can’t solve them.
Is this even approximately correct?
John K Clark
Comment #35 June 5th, 2018 at 7:04 pm
John Clark #33: Yes, that’s pretty much right, except that you need to add the proviso “relative to an oracle.” I.e., Raz and Tal didn’t prove what you say for “ordinary” computational problems, where you’re given an n-bit input and that’s it. They proved it for problems where you’re given a “black box” that can return any of 2n bits depending on which input you feed it. Studying these black-box problems is a standard thing we do in theoretical computer science—among other reasons, because it’s much more feasible to prove lower bounds for them (we don’t need to, like, prove P≠PSPACE as a first step… 🙂 ).
(Also, a technical point: Raz and Tal constructed an oracle relative to which BQP⊄PH, which is not quite as strong as an oracle relative to which P=NP and yet quantum computers solve some decision problem that’s classically hard—the informal interpretation I used in my post. However, now that we have the former, it’s probably only a matter of time until someone gets the latter also. Basically, you first need to extend Raz and Tal’s oracle to make P=NP relative to it—e.g., by providing all the levels of the polynomial hierarchy in a “staggered” fashion. You then need to prove that doing that still leaves you with a classically hard problem in the first part of their oracle.)
Comment #36 June 6th, 2018 at 12:48 am
Is there a circuit implementation of the non-uniform distribution used in Raz & Tal’s paper?
They seem to refer to your paper in their oracle construction – i’m looking under “Oracle Separation Result”.
Basically, is there an example oracle we could experiment with, or has it only been shown to be possible? Is that perhaps why you mentioned that “we don’t really know how to instantiate [the oracle problem] explicitly”?
Comment #37 June 6th, 2018 at 1:06 am
Job #35: What, specifically, would you be hoping to learn from an experiment?
You could certainly code up a program to draw pairs of Boolean functions (f,g) from Raz and Tal’s probability distribution D—that’s by far the most relevant thing; the use of D to create an infinite oracle is just boring diagonalization stuff. And they tell you exactly how to draw from D in Section 4.1 of their paper.
That will give you yes-instances of the noisy Forrelation problem. To generate the no-instances is as easy as picking f and g completely at random!
And then, given these instances, you could certainly experiment with various algorithms to solve them. If you had a quantum computer (able to query the truth tables of f and g stored in a memory somewhere), you could even run the quantum algorithm for noisy Forrelation, and see that it gave you the expected result.
Comment #38 June 6th, 2018 at 1:13 am
I was wondering what the minimum gate set is that can implement the oracle.
For example, if it can be implemented using a non-universal quantum gate set, then you might have a separation between PH and wanna-BQP, the class containing all not-quite-quantum simulators that do ok with non-universal gate sets like H+CNOT.
Comment #39 June 6th, 2018 at 2:24 am
Job #37: If the oracle is implemented using H and CNOT gates only, then it can only express functions that are linear over GF(2), so Forrelation will be trivially in P. (Indeed, I believe the two Boolean functions will never be forrelated, since the Fourier transform of a GF(2) linear function is a point function and is therefore not Boolean!)
More broadly, what I meant in saying that we have no “explicit instantiation” of Forrelation, more precisely, is that we don’t know how to generate small circuits for the Boolean functions f and g, in such a way that
(1) the forrelation between f and g is either very large or very small (so the quantum algorithm can distinguish the two cases), but
(2) you actually need the quantum algorithm to tell you the answer (i.e., there’s nothing about the circuits that makes the problem easy classically).
Maybe this can be achieved using modern obfuscation techniques from cryptography; I’m not sure (but even then, it wouldn’t be a “natural” instantiation).
On the other hand, if you’re willing to have f and g be loaded from giant truth tables stored in a memory somewhere (in other words, work directly in the black-box model), then there’s no problem doing concrete experiments with Forrelation, either with a classical simulator or with a quantum computer if you have one.
Comment #40 June 6th, 2018 at 2:29 am
Pooya #32: It’s awesome that your techniques were able to be used for this! And I sincerely apologize for having “left you out.” I’m also sorry that we didn’t get to talk more, with me being away on sabbatical this year.
Comment #41 June 6th, 2018 at 8:08 am
Scott #23: Doesn’t matter much to me, as long as we’re made aware on this blog about where to ask the questions!
Comment #42 June 9th, 2018 at 9:59 pm
I’m curious about this: Boiled down, how does this relate, if at all, to the question of whether or not that quantum computers could solve NP-complete problems in sub-exponential time?
Comment #43 June 9th, 2018 at 10:01 pm
That is, does this have consequences for the truth or falsity of the “NP Hardness Assumption” you’ve conjectured about physics elsewhere? (i.e. that the laws of physics are such that no physical process can make NP complete problems tractable)
Comment #44 June 10th, 2018 at 7:06 am
Michael #41-42: No, it has no direct implications for that question—if it did, I would’ve said so in the post! 🙂
You’re asking about whether NP is contained in BQP, whereas Raz and Tal’s result is about nearly the converse: whether BQP is contained in a generalization of NP.
The closest thing to a connection I know, is a trivial observation I made a decade ago: namely, if BQP turned out to be contained in AM (something that we had no oracle evidence against before Raz and Tal), then BQP couldn’t contain NP without PH collapsing to the second level. Again, though, most of us do indeed think that NP⊄BQP. Just not because we think that BQP⊆AM, but for a dozen other reasons instead.
Comment #45 June 15th, 2018 at 11:16 am
[…] Scott Aaronson on the separation of QBP from the polynomial hierarchy. […]
Comment #46 June 22nd, 2018 at 6:05 am
@Scott : Hmm. However I was actually asking a slightly weaker option: whether or not, and how surprising would it be, it is possible the equivalent of *exponential-time hypothesis* (which is *stronger* than P != NP) for quantum computers could turn out false, leaving you with perhaps no polynomial solution to NP-complete problems but maybe one that runs in something like O(2^sqrt(N)) time. What’s the going on that, and why?
Comment #47 July 16th, 2018 at 10:39 am
Hi Scott, one follow-up question. We know that if classical computers can perform exact quantum sampling then PH collapses, and there are various conjectures regarding the harness of approximate sampling (in increasing difficulty) 1) that this applies to approximate quantum sampling, 2) that this applies to approximate Boson SAmpling, 3) that this applies to approximate BosonSAmpling for Gaussian matrices. Does the new oracle results for decision imply or gibe hope for oracle results (rather than full results) in the direction of 1) 2) and 3).
Best, Gil
Comment #48 July 17th, 2018 at 10:51 am
Gil #46: No, I don’t see any direct relationship, especially since the questions you mention involve sampling problems, whereas the whole difficulty with Raz and Tal was to get a separation for decision problems as well. Note, however, that Lijie Chen and I proved in our CCC’2017 paper that any “fast classical algorithm for approximate sampling collapses PH” theorem must be nonrelativizing, and that proof also involved an AC0 lower bound (but an already known one, for the Sipser functions, rather than a new one as in Raz and Tal’s case).
Comment #49 January 13th, 2019 at 12:12 am
[…] our first is this progress on the Unique Games Conjecture), and Scott Aaronson furnished a great discussion of its genesis and further ramifications in complexity theory. Several popular articles tried to […]