PDQP/qpoly = ALL
I’ve put up a new paper. Unusually for me these days, it’s a very short and simple one (8 pages)—I should do more like this! Here’s the abstract:
- We show that combining two different hypothetical enhancements to quantum computation—namely, quantum advice and non-collapsing measurements—would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.
I welcome discussion in the comments. The real purpose of this post is simply to fulfill a request by James Gallagher, in the comments of my Robin Hanson post:
The probably last chance for humanity involves science progressing, can you apply your efforts to quantum computers, which is your expertise, and stop wasting many hours of you [sic] time with this [expletive deleted]
Indeed, I just returned to Tel Aviv, for the very tail end of my sabbatical, from a weeklong visit to Google’s quantum computing group in LA. While we mourned tragedies—multiple members of the quantum computing community lost loved ones in recent weeks—it was great to be among so many friends, and great to talk and think for once about actual progress that’s happening in the world, as opposed to people saying mean things on Twitter. Skipping over its plans to build a 49-qubit chip, Google is now going straight for 72 qubits. And we now have some viable things that one can do, or try to do, with such a chip, beyond simply proving quantum supremacy—I’ll say more about that in subsequent posts.
Anyway, besides discussing this progress, the other highlight of my trip was going from LA to Santa Barbara on the back of Google physicist Sergio Boixo’s motorcycle—weaving in and out of rush-hour traffic, the tightness of my grip the only thing preventing me from flying out onto the freeway. I’m glad to have tried it once, and probably won’t be repeating it.
Update: I posted a new version of the PDQP/qpoly=ALL paper, which includes an observation about communication complexity, and which—inspired by the comments section—clarifies that when I say “all languages,” I really do mean “all languages” (even the halting problem).
Follow
Comment #1 May 19th, 2018 at 8:13 am
Hi Scott, quick question – does there exist a class called PDQP/poly? i.e. one where the advice is classical but we still have non-collapsing measurements? If so, is there any known relationship between that class and PDQP/qpoly? I’m guessing the former would be a subset of the latter?
Comment #2 May 19th, 2018 at 9:34 am
Shozab #1: Yes, of course you can define PDQP/poly if you want, and of course it’s a subset of PDQP/qpoly (indeed, by my result, everything is 🙂 ). Unlike the latter, PDQP/poly does not equal ALL (a counting argument suffices to show that, indeed for any uniform complexity class with poly-size classical advice). I don’t know of anything especially interesting to say about PDQP/poly right now, though maybe someone will have something in the future.
Comment #3 May 19th, 2018 at 9:39 am
Interesting result! Why did you revert back to PDQP from naCQP?
A burning question that this paper makes even more interesting is the power of QSZK/qpoly. My conjecture is that it is not ALL (I thought about it for a week and I couldn’t prove it so…). Also, QSZK seems strictly less powerful than PDQP (Grover’s search is optimal for QSZK while you can search in cuberoot(n) time in PDQP.) (The other containment—QSZK in PDQP—also seems unlikely.)
Comment #4 May 19th, 2018 at 10:01 am
Sanketh #3: Remind me what naCQP is? I’m getting old and senile (for godsakes, it’s my 37th birthday in a couple days…)
I didn’t know that anyone had looked at the QSZK/qpoly question before I did two weeks ago! May I ask what your motivation was? I also suspect it’s not ALL, but couldn’t show it, even for (say) classical non-interactive perfect zero-knowledge protocols with /rpoly advice. I did manage to show that certain special kinds of protocols won’t give you ALL—-e.g. because they would give you 2-query LDCs of subexponential size, which Kerenidis and de Wolf ruled out. At the end of the day, all we’re asking for here is a computation of a fat-shattering dimension (namely, of the concept class of problems solved by QSZK/qpoly algorithms), but it’s a nontrivial computation.
I also suspect that QSZK and PDQP might be incomparable. It would be nice to prove that relative to suitable oracles.
Comment #5 May 19th, 2018 at 11:11 am
Given the earlier results QIP/qpoly and PP/rpoly are also ALL it seems like this result is part of a general pattern that it takes surprisingly little advice to get to ALL, which makes me wonder if we are in general underestimating the strength of advice, and maybe that are general attitude that classical advice shouldn’t be able to do much is wrong.
Incidental related question: Does your result allow for a quicker proof that QIP/qpoly=ALL?
Comment #6 May 19th, 2018 at 12:15 pm
naCQP is what you call PDQP in the ITCS version of *your* paper!
My motivation was as follows: Raz showed that QIP(2)/rpoly = ALL, and you and Andy Drucker showed that BQP/qpoly ⊆ QMA/poly ≠ ALL. And we know (due Watrous) that QSZK ⊆ QIP(2). Moreover, QSZK is very nice to deal with due to the complete problem—quantum state distinguishability (due Watrous). It is easy to see that there is an analogous complete problem for QSZK/qpoly in which the polynomial size quantum circuits have advice.
I also thought about simplifying my question to NISZK/rpoly but it didn’t seem any easier. Keep in mind that this was around the same time that I was studying the paper of Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan, so I was sufficiently convinced. I knew of Kerenidis-de Wolf but I didn’t go that far.
I mentioned this problem in John Watrous’ group meeting last summer and also mentioned it to Andy Drucker but that was the end of it.
Yes, abstractly, the question boils down to what is the fat-shattering dimension of the concept class of problems solved by QSZK/qpoly algorithms? (But that formulation doesn’t seem to give me any new information about the problem.)
My approach was to show the existence of a QIP(2)/qpoly problem (notice the “q”) that cannot be reduced to advice quantum state distinguishability by some kind of Nayak-type argument. (Maybe one can use Kerenidis-de Wolf here?)
Comment #7 May 19th, 2018 at 1:47 pm
Wow!
Comment #8 May 19th, 2018 at 2:07 pm
Are you claiming that PDQP/qpoly is powerful enough to solve the Halting Problem? If not, maybe you should say that it’s equal to the class of all decidable languages instead of all languages.
Comment #9 May 19th, 2018 at 4:21 pm
Aula #8: Yes, I’m absolutely claiming that PDQP/qpoly is powerful enough to solve the halting problem. And the halting problem with a HALT oracle, and … you get the idea.
Adding advice always gives you the ability to solve some undecidable problems (since now you can decide an uncountable infinity of languages, rather than only a countable infinity). It’s just that normally, you’re highly constrained in which undecidable problems you can solve (e.g., you could solve the halting problem, but only if the input machine were encoded in unary notation). The surprise about /rpoly and /qpoly is that sometimes—it’s hard to predict where—they boost a complexity class up to solving undecidable problems with no constraints.
Comment #10 May 19th, 2018 at 4:52 pm
Joshua #5: If by classical advice you mean /poly, then it acts in basically the same way on every complexity class C. I.e., instead of all languages L for which there exists a C-machine that accepts all x∈L and rejects all x∉L, now you get all L for which there exists a C-machine M, together with an advice sequence a1,a2,…, such that M accepts all (x∈L,an) and rejects all (x∉L,an). So, the advice can always be thought of as just an auxiliary “helper” input string—one that boosts us from a countable to an uncountable set of languages (because of the enormous freedom in choosing the an‘s), but that otherwise behaves reasonably predictably. For example, if C⊆D, then we always have C/poly⊆D/poly (exercise for the reader).
But /rpoly and /qpoly? Those are like highly reactive and dangerous chemicals. For many complexity classes, adding them does nothing more than adding normal /poly advice (or, in the case of /qpoly, adding /poly advice plus a bit more computational power). But their interaction with certain classes produces an explosion that results in ALL. Furthermore, the set of classes for which this happens doesn’t obey the usual rules of complexity theory. For example, even if C⊆D, the ALL-explosion could easily happen for C and not happen for D.
It would be nice to have better principles for predicting when this ALL-explosion will happen—ones that would let us, for example, guess the answer to my and Sanketh’s question about SZK/rpoly.
Comment #11 May 19th, 2018 at 5:30 pm
Ha! I just noticed you put the PDPP idea I’ve mentioned in your paper and also proved PDPP/rpoly=ALL. Of course I was going to ask about that if you didn’t. 🙂
(Unrelatedly, um, not sure who’s running the complexity zoo these days, but its certificate seems to have expired…)
Comment #12 May 19th, 2018 at 6:16 pm
Scott #4: Another approach I fiddled with for a while was to show that QSZK/qpoly ⊆ PSPACE/poly using an argument similar to the one in your paper on de-Merlinizing quantum protocols. (I am mentioning it here because someone smarter than me might be able to make it work.)
Comment #13 May 19th, 2018 at 6:29 pm
Scott,
Is there some intuition for why we should expect qpoly and rpoly to be so much more “reactive” than poly?
Comment #14 May 19th, 2018 at 6:41 pm
Scott #10: To make the notion of ALL-explosion slightly more concrete consider this:
Aaronson showed that PP/rpoly = ALL, Raz showed that IP/rpoly = ALL, and now Aaronson showed that PDPP/rpoly = ALL. But notice that PSPACE/rpoly = PSPACE/poly ≠ ALL.
My guess is that the explosion only happens when one is allowed non-determinism post-advice. And rightly the complexityzoo says
(Also, from the history of the page, I am pretty sure that Scott wrote this pre-2012.)
Comment #15 May 19th, 2018 at 6:51 pm
Sniffnoy #11: I am yet to see a result that only works with quantum advice (and doesn’t work with random advice.) I am still astounded by the fact that no one in classical complexity theory thought of randomized advice before quantum computing came along. Since I am already making daft conjectures—I conjecture that every ALL-explosion with quantum advice has a randomized advice analog. (Actually, this may be provable.)
Comment #16 May 19th, 2018 at 7:03 pm
Sanketh #15: I formulated exactly that conjecture in my 2006 QMA/qpoly paper, where I called it the “Quantum Advice Hypothesis.” However, I’m not sure whether I stand behind the hypothesis: I say only that, if it’s false, then I really want to see a counterexample.
Comment #17 May 19th, 2018 at 7:07 pm
Joshua #13: Yes, the intuition is simply that a probability distribution or quantum state on poly(n) qubits (i.e., /rpoly or /qpoly advice) takes exponentially many bits to specify even approximately. So in some sense, the advice state can always encode the entire truth table of whatever language you’re trying to decide, on all inputs of size n. The question is just whether, given an input x, your complexity class is able to read out the xth entry of the truth table by measuring the advice.
Comment #18 May 19th, 2018 at 7:38 pm
Scott #15: Interesting! That’s actually kind of surprising…
Comment #19 May 19th, 2018 at 9:59 pm
Scott #16: Sorry… I remember now, I recall reading that part of the paper and then immediately asking John Watrous if he had any intuition for QRG(1)/qpoly. (If there is anyone on the planet who has an intuition for QRG(1), it is him.)
(Professor Watrous likes to call QMA with two competing provers QRG(1), I occasionally call it QS2p although it is a horrible practice, S2 is an operator on complexity classes…)
If I may ask, why do you no longer stand behind it? Do you smell a counterexample??
Comment #20 May 19th, 2018 at 10:43 pm
Sanketh #19: No, I don’t have a proposed counterexample in mind—it’s just that the space of complexity classes is vast, and within that space, probably most things happen somewhere unless there’s a very good reason why they can’t.
Comment #21 May 19th, 2018 at 10:48 pm
Sniffnoy #11: I contacted Vincent Russo about the Complexity Zoo’s expired SSL certificate, and he’s on the case (though it might take the Waterloo people a few days because of a long weekend).
Comment #22 May 20th, 2018 at 12:06 am
Non-collapsing measurements by itself sounds really powerful.
I’m surprised by your N^1/4 lower bound for Grover search under PDQP.
I have to give that some thought.
Comment #23 May 20th, 2018 at 12:30 am
I am relieved (but knowing Scott, not surprised) to see the key acknowledgment in the paper that you already get PDPP/rpoly = ALL. The paper goes onto say:
Fair enough, but this is closely related to a good reason to give the initial statement in terms of classical randomized advice instead. Namely, it is a huge cliché, and often an outright misconception, that non-determinism “in physics” is the same thing as quantum voodoo. In reality, non-determinism is already there in the Bayesian interpretation of classical probability, as well as in thermodynamics and statistical mechanics. (In fact, the physical concepts of “temperature” and “entropy” require non-determinism whether or not anything is quantum; or at least they are vastly easier to understand that way.) In my view, classical Bayesianism is a great analogy for learning and demystifying quantum probability. Results such as PDPP/rpoly = ALL = PostBPP/rpoly are also helpful for the basic point.
So I’m glad that this was mentioned, but I would be even happier if it were mentioned in page 2, and maybe in the abstract as well, rather than on page 6. Of course it’s up to Scott, though; it’s not my paper.
Comment #24 May 20th, 2018 at 1:24 am
Greg #23: I actually spent some time looking for a place to discuss PDPP/rpoly earlier in the paper, but couldn’t figure out how to do it without interrupting the narrative flow.
I should mention an additional issue in this case, though: PDQP has been a subject of (some) independent interest, whereas PDPP has not.
Or to put it another way: treating quantum states realistically might be a mistake, but it’s a mistake that’s tempted many, many people, which makes it of greater interest to study the mathematical consequences of that mistake, than of a mistake that nobody ever made. 🙂
Comment #25 May 20th, 2018 at 7:42 am
[…] PDQP/qpoly = ALL 3 by weinzierl | 0 comments on Hacker News. […]
Comment #26 May 20th, 2018 at 8:11 am
Hi Scott, Question from a complete layperson who couldn’t understand maybe 1/3 of QC Since Democritus. When Alibaba announces it figured out how to simulate Bristlecone’s 72 Qubits using classical computing, does this have important implications for (does it change) conventional wisdom on the limits or rates of general advancement in classic computing, or is it more of a narrow, idiosyncratic trick? Thanks!
Comment #27 May 20th, 2018 at 8:57 am
dlr #26: Needless to say, the interesting recent Alibaba paper was a subject of conversation at the Google workshop. But in the end, I don’t think it changes the situation that much. The methods it uses—e.g., tensor network contraction, my and Lijie Chen’s recursive method for saving memory—are the same basic ones that were known before; the chief technical innovation here is to massively parallelize the computation of a single amplitude, so that you get a speedup from parallelization even if you don’t want many amplitudes. Apparently, previous simulations didn’t do this largely just because they wanted thousands of amplitudes rather than just one. The other thing to bear in mind is that, while the classical simulation side gets better, the quantum side can get better too! Apparently, there were special features of the gate set and the circuit layout that the Alibaba paper took clever advantage of, and by modifying the quantum supremacy hardware as well as the circuits run on that hardware, one could square or more the running time of the best known classical simulation, holding the circuit depth constant.
Comment #28 May 20th, 2018 at 9:08 am
Thank you!
Comment #29 May 20th, 2018 at 10:07 am
Scott #20: If we restrict ourselves to the case where we have access to some sort of non-determinism post-advice, then we can always replace the quantum advice by randomized advice. My almost-always-wrong intuition is that this is the only type of ALL-explosion one can have. (ALL-explosions are all about being able to extract a lot of information from a tiny amount of advice, I don’t see a way of doing this without any kind of non-determinism. Do you have any ideas?)
Comment #30 May 20th, 2018 at 1:38 pm
Scott #9: OK, let’s say I pick a Turing machine and try to use your PDQP/qpoly algorithm to decide whether it halts or not. After encoding my chosen TM as a binary string x, it looks like I need a Boolean function f such that f(x)=1 if the TM halts and 0 if it doesn’t. How exactly am I supposed to find that f? I mean, evidently I need to already have the ability to solve the Halting Problem before I can even get started with your algorithm. Now it may well be that you understand how the quantum advice can enhance my ability to find Boolean functions for any possible decision problem, but in that case you seem to have done a very good job of excluding that understanding from the paper.
Comment #31 May 20th, 2018 at 5:03 pm
Scott, the reason why we say that the Halting problem is undecideable is because it leads to a contradiction. Is it reasonable then to say that PDQP/qpoly is impossible, because it leads to a contradiction? Unless, of course, one allows for the existence of contradictions (which is logically possible, I just don’t think we have seen one).
Comment #32 May 20th, 2018 at 8:00 pm
Thanks for the name check – and highlighting of ungrammatical and expletive language!
I do wonder how I ever ended up posting on your blog, I started on Lubos’ about 10 years ago, and he was great fun, and I still love the guy even though he banned me after an, admittedly, not great posting session where I dissed Bohr and Von Neumann for not really making such great contributions to Science as everyone thinks (and especially annoying for me is the attribution of the invention of the digital computer architecture to Von Neumann)
But anyway, I myself have nothing to contribute at the level you do even with this paper, and my only hope is that humanity progresses scientifically. If I stir the pot a little to help that now and then with my silly comments I would hope you understand.
Comment #33 May 20th, 2018 at 8:06 pm
“you time” is actually a thing
Comment #34 May 20th, 2018 at 8:08 pm
That is a well-specified function right there. You just stated its definition. It’s not a computable function, but it’s a function. Which is all that’s required for advice — advice doesn’t have to be computable!
(Unrelatedly, Scott, new website bug: The blog no longer seems to be storing my session or whatever when I comment? So my name/email aren’t saved, and I can’t see my moderated comments?)
Comment #35 May 20th, 2018 at 9:55 pm
Does ALL include undecidable languages?
Comment #36 May 20th, 2018 at 10:50 pm
OOOO #35: Yes. See above.
Comment #37 May 20th, 2018 at 11:04 pm
Aula #30: The entire concept of “advice” is: something that’s fixed for each input length n, and that’s independent of the particular input x∈{0,1}n, but such that otherwise you don’t need to worry about how it was found. It’s just given to you. The crucial limitation, the thing that makes this model nevertheless interesting, is how many bits (or qubits) long the advice is allowed to be.
While obviously not “practical,” advice has been a central concept in CS theory since Karp and Lipton introduced it in 1982; see Wikipedia for more.
As one example of its applications, if you could show that breaking your cryptosystem was not in P/poly, then you’d get its security no matter how much time the NSA might have spent precomputing data (provided it could only store a reasonable-sized summary of the precomputation). This is why nonuniform adversaries are typically assumed in crypto.
In the paper, I did review and define (quantum) advice, but it’s true that I assumed enough familiarity with the decades-old concept that it wasn’t going to blow the reader’s mind. Probably I should’ve expanded on it in the blog post.
Comment #38 May 20th, 2018 at 11:35 pm
Trishank #31: Absolutely not. There’s nothing the slightest bit contradictory about the class PDQP/qpoly—it just equals ALL, is all. 🙂
The error in your comment is the following: you don’t get a contradiction from anything whatsoever solving the halting problem; you only get a contradiction from a single Turing machine solving it.
But a PDQP/qpoly algorithm is not a single Turing machine, because it includes the advice states |ψn⟩. If you liked, you could think of it as an infinite collection of polynomial-time quantum Turing machines (enhanced by non-collapsing measurements), one for each input length n. And there’s absolutely nothing to say that such a collection couldn’t solve the halting problem. (But despite the lack of any diagonalization obstruction, it was still surprising to me that it could be done in polynomial time—read the paper if you want to see the trick.)
Comment #39 May 20th, 2018 at 11:48 pm
Scott #38: Thanks for your reply!
Okay, but I feel you’re handwaving this. The point is, whether a single classical TM, or an infinite number of quantum TMs, solves the HP, you arrive at a contradiction, because solving the problem means you can realize a machine that halts iff it doesn’t halt. So you have to take that implication seriously.
Also, do you mean an uncountably infinite number of these P-time quantum TMs?
Comment #40 May 21st, 2018 at 12:21 am
Trishank #39: No, you don’t arrive at a contradiction. You’re not listening to what I say!
In Turing’s proof, you get a contradiction because you assumed a Turing machine could solve the halting problem—and then you manipulate things to feed that TM its own code as input, in such a way that it halts it runs forever when given its own code, and runs forever if it halts when given its own code. Right?
If, by contrast, you assumed some magical oracle to solve the halting problem for Turing machines, then you do not get a contradiction, because a magical oracle is not something whose code you could feed to a Turing machine (and that the TM could then run) in Turing’s diagonalization proof. And indeed, you better not get a contradiction—because a “magical oracle to solve the halting problem” is a perfectly mathematically consistent object, is regularly considered in computability theory, and could probably even be physically realized if it weren’t for the existence of the Planck scale, which Turing’s proof knows nothing about.
If you like, any language in PDQP/qpoly is another potential example of such an oracle. The surprise, in my paper, is simply that being in PDQP/qpoly places no restriction whatsoever on which oracle it could be.
Incidentally, no, we’re not talking about an uncountable infinity of polynomial-time quantum TMs; that doesn’t even make sense, since TMs can be enumerated. We’re talking about a countable infinity, one for each input length n. But, obviously, there are uncountably many countable lists of TMs.
Comment #41 May 21st, 2018 at 8:09 am
Scott, your comment #10 says in essence that one interesting feature of these poly advice is why they boost some complexity classes to all powerful and not others, and in particular why they sometimes boost seemingly less powerful classes and not seemingly more powerful ones.
I’m having trouble understanding the later case. Can you explain an example where the poly advice surprisingly doesn’t boost to ALL?
Comment #42 May 21st, 2018 at 1:43 pm
Plenty of people — definitely including me! — are looking forward to these promised Shtetl Optimized posts.
On-line quantum appetizers in recent weeks have notably included John Martinis’ overview lecture “Quantum Computing and Quantum Supremacy” (HPC User Forum, April 16-18, 2018, video here) — Martinis’ phrase “qubit speckle” in particular is an elegant contribution to quantum language and culture.
At this same HPC User Forum, the quantum computing groups at Microsoft, Intel, D-Wave, Rigetti, and NASA generously shared their various quantum roadmaps (PDFs here).
Recent arxiv preprints that are directly relevant to the above plans for quantum supremacy demonstrations notably include the Alibaba Group’s “Classical Simulation of Intermediate-Size Quantum Circuits” (arXiv:1805.01450), Dalzell / Harrow / Koh / Placa “How many qubits are needed for quantum computational supremacy?” (arXiv:1805.05224), and Willsch / Nocon / Jin / De Raedt / Michielsen “Testing quantum fault tolerance on small systems” (arXiv:1805.05227).
Earlier this month, too, I personally enjoyed a wonderfully interesting visit to LIGO Hanford Observatory, where folks are super-busy preparing for the first quantum-squeezed runs of Advanced LIGO … I’d be pleased to contribute to post a Shtetl Optimized comment that compared and contrasted the various “quantum yanni(s)” that real-world gravitational wave observation encounter, with Scott’s account of the various “quantum laurel(s)” that planned computational supremacy demonstrations are encountering.
There’s so much top-quality / enduring-value quantum research going on in 2018, that it seems a pity to expend overmuch Shtetl Optimized bandwidth on culture-war topics.
Comment #43 May 21st, 2018 at 10:39 pm
Should a new grad student focus on quantum computing in search for tomorrow’s jobs?https://www.barrons.com/articles/intel-puts-its-own-spin-on-quantum-computing-1526922383.
Comment #44 May 21st, 2018 at 11:02 pm
Does ALL=PP/poly a possibility?
Comment #45 May 21st, 2018 at 11:04 pm
https://www.zdnet.com/article/ibm-warns-of-instant-breaking-of-encryption-by-quantum-computers-move-your-data-today/
Should we be worried about quantum and more importantly ‘It has been known since the 1980s that quantum computers would be great at factoring large numbers, which is the foundation of public key cryptography’ implies someone beat Shor?
Comment #46 May 22nd, 2018 at 12:37 am
aa #43-45:
I can’t put myself into the mindset of doing anything whatsoever “in search of tomorrow’s jobs.” Like, we all need to support ourselves, and most of us like to do things considered exciting and relevant. But there are many paths in life besides academia, and for the academic track to be worth it at all, I’d hope you’d feel free enough to choose a subject that intrinsically excites you.
No, PP/poly is not ALL, by a counting argument: there are only exp(nO(1)) possible advice strings at each n, which is far less than the exp(2n) different Boolean functions.
“Quantum factoring was known since the 80s” is such a risible error that I’m not inclined to click the link to see what else is wrong there.
Comment #47 May 22nd, 2018 at 1:43 am
Is this thing about quantum speed limits significant?
https://phys.org/news/2018-03-quantum-limits.html
Do the limits in the quantum realm follow from the Schroedinger equation?
Thanks.
Comment #48 May 22nd, 2018 at 3:33 am
Hi Scott, I was attending Eurocrypt in Tel Aviv and I saw you walking around, unfortunately I did not get the chance to come to you asking for an autograph 🙂 any talks you attended and found interesting?
Comment #49 May 22nd, 2018 at 6:00 am
asdf #47: Speed limits and time/energy tradeoffs in general are an extremely interesting story. I can’t comment on this new work, claiming that QM isn’t needed for the tradeoffs, because I’m not familiar with it. The thing to look for is whether QM is getting snuck in through the back door—certainly I’ve had many disagreements with Margolus in the past where he claimed that QM wasn’t needed for something, whereas I thought it clearly, obviously WAS needed, and we never even got past the semantics (i.e., what it means to “need QM” for something, which supposedly “classical” facts are really just QM in disguise) to isolate what the core disagreement was.
Yes, the Schrödinger equation does imply a tradeoff between time and energy. If, on the other hand, you want absolute limits on processing speed or information storage density, without needing to say anything about energy, then it becomes a statement of quantum gravity rather than pure QM.
Comment #50 May 22nd, 2018 at 6:09 am
Thomas #48: I didn’t attend nearly as many talks as I should have, but I really liked Matt Green’s keynote, with its concrete examples of terrible random number generation practices, and also the talk about lower bounds for discrete log with preprocessing in the generic group model.
Comment #51 May 22nd, 2018 at 10:19 am
This is not a coincidence because nothing is ever a coincidence.
Comment #52 May 22nd, 2018 at 1:23 pm
Hi Scott. I apologize for going on a complete tangent here, but I was curious if you had come across and read this new book The Great Formal Machinery Works: Theories of Deduction and Computation at the Origins of the Digital Age by Jan von Plato. It feels a bit like Quantum Computing Since Democritus, but more technical, and more historical, perhaps closer in spirit to Penrose’s Road to Reality.
Just wanted to put that out there.
Comment #53 May 22nd, 2018 at 2:31 pm
Scott, speaking of lower bounds in the generic group model, are there any known (quantum) lower bounds for LWE (or some of other problems that are considered good candidates for post-quantum crypto) in some reasonable oracle model?
Comment #54 May 22nd, 2018 at 2:39 pm
Scott, thanks. Another thing I wonder: where does the Schrödinger equation “come from”? I.e. is there a way to derive it from the Hilbert space formulation by adding some presumptions, and what are the presumptions? I googled around about this a little and didn’t find anything clear.
Comment #55 May 22nd, 2018 at 4:19 pm
One more question then: PDQP is only slightly bigger than BQP but unlike BQP is unlikely to be physically realizable in any meaningful fashion. You mention in the paper that we know that BQP/qpoly is contained in QMA/poly intersect coQMA/poly which gives us that BQP/qpoly is not all. Given your comment 17 above, I’m now wondering if I should be surprised that BQP/qpoly isn’t ALL.
Is there any reasonably natural class between PDQP and BQP where it is open whether giving it qpoly advice gives ALL? What happens if we look at variants of PDQP where we restrict how many times we may take a measurement without collapse, possibly as a slow growing function of the input?
Comment #56 May 22nd, 2018 at 8:23 pm
Sid #52: No, I hadn’t come across it.
Comment #57 May 22nd, 2018 at 8:28 pm
RandomOracle #53: Well, of course there’s the BBBV lower bound and the collision lower bound, which apply whenever you assume there’ so little usable structure in your cryptosystem that a quantum algorithm might as well either brute-force search or search for collisions, respectively. If you assume more structure than that, then I’m not aware of quantum black-box lower bounds with relevance to cryptographic primitives like LWE—but maybe someone else is (or maybe I’m forgetting something obvious)? There was the seminal work of Oded Regev around 2005, which related the post-quantum security of LWE and lattice-based cryptography to the Hidden Subgroup Problem over the dihedral group and the average-case subset sum problem, but that work wasn’t in the black-box setting. (Indeed, in the black-box setting, the Hidden Subgroup Problem is quantumly easy, by the 1997 result of Ettinger, Hoyer, and Knill.)
Comment #58 May 22nd, 2018 at 8:37 pm
Joshua and Eve #55: Those are great questions, and you can tell I think so because they’re both explicitly discussed in the paper! 😀
A good class intermediate between BQP and PDQP is QCSZK (i.e., Statistical Zero Knowledge with quantum verifier and classical interaction with the prover). I left as my main open problem whether QCSZK/qpoly = ALL.
I also discussed what happens when only a small number of non-collapsing measurements are allowed. Briefly: if there exist good enough 3-query Locally Decodable Codes (LDCs), then it’s possible to do ALL using only 3 measurements (let’s say, 2 non-collapsing and then a final one that’s collapsing without loss of generality). Even using the 3-query LDCs that are already known, it should be possible to do this using a subexponential-size advice state and/or subexponential time, but I didn’t work out all the details (just gave the relevant references in the paper).
I don’t know whether it should be possible to do ALL with only two measurements, and subexponential time and a subexponential-size state. A central obstacle here is the 2003 no-go theorem of Kerenidis and de Wolf, which says that there are no 2-query LDCs of subexponential size. So, that rules out the approach taken in my paper, but it leaves open the possibility of some other approach. This is probably related to the earlier question of whether QCSZK/qpoly = ALL.
Comment #59 May 22nd, 2018 at 9:06 pm
P=BPP implies rpoly=poly and so PP/rpoly=PP/poly?
Comment #60 May 22nd, 2018 at 10:01 pm
aa #69: No. P=BPP doesn’t mean that randomness can be eliminated in every situation, and indeed, PP/poly vs. PP/rpoly is one situation where we know for certain that it can’t be.
Comment #61 May 22nd, 2018 at 11:46 pm
What exactly is rpoly?
poly is poly size advice string.
rpoly is poly size advice string (with random pepper and salt).
Both look edible to a hungry person.
Comment #62 May 23rd, 2018 at 12:01 am
aa #61: By academic standards, I spend a ridiculous amount of time answering questions on my blog. But it’s all worth it whenever I see my replies met by that level of comprehension and engagement.
Comment #63 May 23rd, 2018 at 7:48 am
“Those are great questions, and you can tell I think so because they’re both explicitly discussed in the paper! ????”
And this shows I should finish reading papers before asking questions about them. (Also that comment labeled Joshua and Eve was from me; Google autocomplete does seem weird things sometime.)
Comment #64 May 23rd, 2018 at 9:16 am
I am certainly not an expert on these things, but I like reading your blog. But I have a question about this paper.
Theorem 2 gives a method to compute any f(x). But it seems to require an advice state consisting of g(x) for all x. Evaluating g(x) seems as hard as evaluating f(x), so by the time the advice state is created, all work seems to be done?
Comment #65 May 23rd, 2018 at 11:10 am
Petter #64: As discussed in earlier comments, that’s precisely the idea with advice—that you don’t care how long it takes to prepare it, it’s just a resource that’s given to you. The restrictions, with advice, are
(1) you get the same advice state for every input of length n, and
(2) the advice is limited in size (typically, to poly(n) bits or qubits).
With those constraints, you’re often severely limited in what you can compute, even supposing you had all the time in the world to prepare the advice state, because of a “communication bottleneck” issue. That’s what happens, for example, with BQP/qpoly and QMA/qpoly. The point of the new paper was to show that, for slightly non-obvious reasons, it’s not what happens with PDQP/qpoly.
Comment #66 May 23rd, 2018 at 1:16 pm
Scott #57: Thanks!
Another, unrelated, question: given 2 efficiently computable functions f,g : {0,1}^n -> {-1, +1}, is computing their forrelator (sum_{x,y} f(x) g(y) (-1)^{x.y}) GapP-complete?
Comment #67 May 23rd, 2018 at 1:30 pm
RandomOracle #66: Yes. Indeed, it’s GapP-complete even in the special case that f is the constant all-1 function, in which case the sum reduces to 2n Σy g(y).
Comment #68 May 23rd, 2018 at 2:06 pm
Scott #67: I’m a bit confused. When f is the constant all-1 function, the sum reduces to sum_{x,y} (-1)^{x.y} g(y). Why would this be 2^n sum_y g(y)? (it seems to me like that would be the case if (-1)^{x.y} weren’t there)
If we take x and y to be one bit, and g(0) = -1, g(1) = 1, then sum_y g(y) = 0. However, sum_{x,y} (-1)^{x.y} g(y) = -2.
Am I missing something?
Comment #69 May 23rd, 2018 at 2:13 pm
RandomOracle #68: If f is the all-1 function, then for every nonzero value of x, you get complete cancellation, with (-1)x.y positive and negative equally often as you range over the y’s. So then all that’s left is x=0, where you get Σy g(y). Sorry, I was mistaken about the 2n factor.
Comment #70 May 23rd, 2018 at 2:49 pm
Scott #69: But shouldn’t you sum over x to get the cancellation? It’s true that the x = 0 case is sum_y g(y), but for some non-zero x it’s not necessarily the case that sum_y g(y) (-1)^{x.y} is 0.
So shouldn’t it be:
sum_{x,y} g(y) (-1)^{x.y} = sum_y g(y) (sum_x (-1)^{x.y})
For all non-zero y’s, we have that sum_x (-1)^{x.y} = 0.
So then the sum becomes g(0) * 2^n. This is also what I’ve been getting with the examples I’ve tried.
Comment #71 May 23rd, 2018 at 3:28 pm
RandomOracle #70: Err, yes, you’re right. I apologize for denseness.
Just for you, here’s a (hopefully) corrected GapP-hardness proof. Set f(0n)=-1, and f(x)=1 for all nonzero x. Then we can calculate:
sumx,y f(x) (-1)x.y g(y)
= 2n g(0n) – 2Σy g(y).
So the value of the forrelation encodes the sum of exponentially many g-values, as desired.
Comment #72 May 23rd, 2018 at 3:45 pm
Scott #71: Ah, right… so essentially in sum_x f(x) (-1)^{x.y}, for non-zero y, you flip one of the (-1)’s, but the rest stay the same and so the sum is -2. Cool! Thanks 😀
Comment #73 May 23rd, 2018 at 9:08 pm
Ok I don’t understand why randomized advice could be different from advice when both are precomputed essentially.
Comment #74 May 23rd, 2018 at 11:30 pm
aa #73: It’s because an n-bit string takes n bits to specify, whereas a probability distribution over n-bit strings takes exp(n) bits to specify (even approximately). The difficulty is reading out a desired bit from among those exp(n)—but some complexity classes (like PostBPP, PP, IP(2), and PDQP) can do it. Perhaps the easiest to understand is PP: with that class, you only need to guess the right answer with some probability greater than 1/2, so you can just take a sample from the advice distribution and hope that it happens to tell you the answer for your particular input x.
Comment #75 May 24th, 2018 at 2:40 am
If non-collapsing measurements boost Grover’s lower bound to N^1/4, then I wonder if you could pair non-collapsing measurements with quantum-simulation optimizations to actually improve performance for some problems.
That seems like a long shot since the quantum simulator’s performance depends on the total number of bits (including ancilla and output) rather than just the input bits…
It’s like the classical simulator has the advantage of a shorter circuit depth (N^1/4 vs N^1/2) at the cost of a larger circuit width (plus all the amplitude extravaganza).
Comment #76 May 24th, 2018 at 4:24 am
Job #75: A detail, but we only know how to do Grover search in ~N1/3 time in the PDQP model.
~N1/4 is our best current lower bound, but my guess is that ~N1/3 is actually the tight answer.
I seriously doubt that this observation about PDQP could lead to better classical algorithms to simulate quantum circuits. Now that you mention it, though, what the observation might be useful for is the converse: putting limits on how much advantage classical simulation algorithms could get over brute force for various tasks, if they’re not going to be solving CircuitSAT or whatever in sub-2n time.
Comment #77 May 24th, 2018 at 2:43 pm
Scott #40:
Right.
Sure.
Uhh, what?
Comment #78 May 24th, 2018 at 4:34 pm
Nick #77: Just build a “Zeno computer,” which simulates the first step of a Turing machine in 1 second, the second step in 1/2 second, the third in 1/4 second, and so on infinitely, raising a flag if the machine ever halts within the 2-second time limit. Sure, this would require an unbounded amount of energy. But in a hypothetical world with no Planck scale, no quantum gravity, and no risk of anything collapsing to a black hole because you tried to stuff too much or do too much in too small a region of spacetime, what would there be in fundamental physics to rule this out? (“Mere engineering difficulties” are trivial to list and don’t count. 🙂 )
Comment #79 May 24th, 2018 at 10:03 pm
I guess a typical simulator would also be able to support post-selection?
An ideal simulator would exactly match the power of a QC and nothing more.
It’s not efficient to simulate a QC using a PDQP or PostBQP machine.
That’s like using NP to simulate BPP.
Comment #80 May 25th, 2018 at 3:03 am
BTW, I guess I don’t get any credit for my repeatedly bugging you about PDPP? 😛
Comment #81 May 25th, 2018 at 3:32 am
Sniffnoy #80: I apologize for having totally forgotten about your comments—though of course, I can’t prove that there was no subconscious influence on me.
But the other issue is: should I actually acknowledge you in my paper as “Sniffnoy”? 😀 I’ll do it if I can use your real name.
Comment #82 May 25th, 2018 at 4:07 am
9 pages including references, not 8. 🙂
Comment #83 May 25th, 2018 at 5:33 am
marc #82: Well, it was 8 when I put the post up. As mentioned in the update, I since added some material.
Comment #84 May 25th, 2018 at 8:30 am
I wonder if you get the same complexity class as PDQP if instead of non-collapsing measurements you do regular measurements with the modified Born rule proposed by Galley and Masanes in arXiv:1610.04859, where \(p(a|\psi) = \tr(E_a |\psi\rangle\langle\psi|^{\otimes N} \) for some effects \(E_a\) that make the probabilities normalised and non-negative.
It seems to work for your example of finding collisions.
Comment #85 May 25th, 2018 at 9:35 am
Job #79: no, definitely not post-selection. Post-selection is too strong, even without quantum madness, because it lets you go from random algorithms to nondeterministic algorithms.
Comment #86 May 25th, 2018 at 12:34 pm
Scott: Yes of course you can use my real name. It’s not like I really make much of an effort to hide. 🙂 But yes definitely glad to see PDPP appear “for real” (it’s not like I was going to write a paper on or even mentioning it anytime soon!), so thanks for that! 🙂
Comment #87 May 25th, 2018 at 3:27 pm
Jonas #85, Scott says:
PostBQP in particular is “post-selecting on a measurement yielding a specific outcome”.
If a quantum simulator has access to all amplitudes, at measurement time, why can’t it evaluate to one of the post-selected outcomes? Isn’t that the same as post-selection?
Comment #88 May 26th, 2018 at 1:14 am
Also thank you Scott for the acknowledgement. 🙂