Quantum computing motte-and-baileys
In the wake of two culture-war posts—the first on the term “quantum supremacy,” the second on the acronym “NIPS”—it’s clear that we all need to cool off with something anodyne and uncontroversial. Fortunately, this holiday season, I know just the thing to bring everyone together: groaning about quantum computing hype!
When I was at the Q2B conference in San Jose, I learned about lots of cool stuff that’s happening in the wake of Google’s quantum supremacy announcement. I heard about the 57-qubit superconducting chip that the Google group is now building, following up on its 53-qubit one; and also about their first small-scale experimental demonstration of my certified randomness protocol. I learned about recent progress on costing out the numbers of qubits and gates needed to do fault-tolerant quantum simulations of useful chemical reactions (IIRC, maybe a hundred thousand qubits and a few hours’ worth of gates—scary, but not Shor’s algorithm scary).
I also learned about two claims about quantum algorithms that startups have made, and which are being wrongly interpreted. The basic pattern is one that I’ve come to know well over the years, and which you could call a science version of the motte-and-bailey. (For those not up on nerd blogosphere terminology: in medieval times, the motte was a dank castle to which you’d retreat while under attack; the bailey was the desirable land that you’d farm once the attackers left.)
To wit:
- Startup makes claims that have both a true boring interpretation (e.g., you can do X with a quantum computer), as well as a false exciting interpretation (e.g., you can do X with a quantum computer, and it would actually make sense to do this, because you’ll get an asymptotic speedup over the best known classical algorithm).
- Lots of business and government people get all excited, because they assume the false exciting interpretation must be true (or why else would everyone be talking about this?). Some of those people ask me for comment.
- I look into it, perhaps by asking the folks at the startup. The startup folks clarify that they meant only the true boring interpretation. To be sure, they’re actively exploring the false exciting interpretation—whether some parts of it might be true after all—but they’re certainly not making any claims about it that would merit, say, a harsh post on Shtetl-Optimized.
- I’m satisfied to have gotten to the bottom of things, and I tell the startup folks to go their merry way.
- Yet many people continue to seem as excited as if the false exciting interpretation had been shown to be true. They continue asking me questions that presuppose its truth.
Our first instance of this pattern is the recent claim, by Zapata Computing, to have set a world record for integer factoring (1,099,551,473,989 = 1,048,589 × 1,048,601) with a quantum computer, by running a QAOA/variational algorithm on IBM’s superconducting device. Gosh! That sure sounds a lot better than the 21 that’s been factored with Shor’s algorithm, doesn’t it?
I read the Zapata paper that this is based on, entitled “Variational Quantum Factoring,” and I don’t believe that a single word in it is false. My issue is something the paper omits: namely, that once you’ve reduced factoring to a generic optimization problem, you’ve thrown away all the mathematical structure that Shor’s algorithm cleverly exploits, and that makes factoring asymptotically easy for a quantum computer. And hence there’s no reason to expect your quantum algorithm to scale any better than brute-force trial division (or in the most optimistic scenario, trial division enhanced with Grover search). On large numbers, your algorithm will be roundly outperformed even by classical algorithms that do exploit structure, like the Number Field Sieve. Indeed, the quantum computer’s success at factoring the number will have had little or nothing to do with its being quantum at all—a classical optimization algorithm would’ve served as well. And thus, the only reasons to factor a number on a quantum device in this way, would seem to be stuff like calibrating the device.
Admittedly, to people who work in quantum algorithms, everything above is so obvious that it doesn’t need to be said. But I learned at Q2B that there are interested people for whom this is not obvious, and even comes as a revelation. So that’s why I’m saying it.
Again and again over the past twenty years, I’ve seen people reinvent the notion of a “simpler alternative” to Shor’s algorithm: one that cuts out all the difficulty of building a fault-tolerant quantum computer. In every case, the trouble, typically left unstated, has been that these alternatives also cut out the exponential speedup that’s Shor’s algorithm’s raison d’être.
Our second example today of a quantum computing motte-and-bailey is the claim, by Toronto-based quantum computing startup Xanadu, that Gaussian BosonSampling can be used to solve all sorts of graph problems, like graph isomorphism, graph similarity, and densest subgraph. As the co-inventor of BosonSampling, few things would warm my heart more than finding an actual application for that model (besides quantum supremacy experiments and, perhaps, certified random number generation). But I still regard this as an open problem—if by “application,” we mean outperforming what you could’ve done classically.
In papers (see for example here, here, here), members of the Xanadu team have given all sorts of ways to take a graph, and encode it into an instance of Gaussian BosonSampling, in such a way that the output distribution will then reveal features of the graph, like its isomorphism type or its dense subgraphs. The trouble is that so far, I’ve seen no indications that this will actually lead to quantum algorithms that outperform the best classical algorithms, for any graph problems of practical interest.
In the case of Densest Subgraph, the Xanadu folks use the output of a Gaussian BosonSampler to seed (that is, provide an initial guess for) a classical local search algorithm. They say they observe better results this way than if they seed that classical local search algorithm with completely random initial conditions. But of course, the real question is: could we get equally good results by seeding with the output of some classical heuristic? Or by solving Densest Subgraph with a different approach entirely? Given how hard it’s turned out to be just to verify that the outputs of a BosonSampling device come from such a device at all, it would seem astonishing if the answer to these questions wasn’t “yes.”
In the case of Graph Isomorphism, the situation is even clearer. There, the central claim made by the Xanadu folks is that given a graph G, they can use a Gaussian BosonSampling device to sample a probability distribution that encodes G’s isomorphism type. So, isn’t this “promising” for solving GI with a quantum computer? All you’d need to do now is invent some fast classical algorithm that could look at the samples coming from two graphs G and H, and tell you whether the probability distributions were the same.
Except, not really. While the Xanadu paper never says so, if all you want is to sample a distribution that encodes a graph’s isomorphism type, that’s easy to do classically! (I even put this on the final exam for my undergraduate Quantum Information Science course a couple weeks ago.) Here’s how: given as input a graph G, just output G but with its vertices randomly permuted. Indeed, this will even provide a further property, better than anything the BosonSampling approach has been shown to provide (or than it probably does provide): namely, if G and H are not isomorphic, then the two probability distributions will not only be different but will have disjoint supports. Alas, this still leaves us with the problem of distinguishing which distribution a given sample came from, which is as hard as Graph Isomorphism itself. None of these approaches, classical or quantum, seem to lead to any algorithm that’s subexponential time, let alone competitive with the “Babai approach” of thinking really hard about graphs.
All of this stuff falls victim to what I regard as the Fundamental Error of Quantum Algorithms Research: namely, to treat it as “promising” that a quantum algorithm works at all, or works better than some brute-force classical algorithm, without asking yourself whether there are any indications that your approach will ever be able to exploit interference of amplitudes to outperform the best classical algorithm.
Incidentally, I’m not sure exactly why, but in practice, a major red flag that the Fundamental Error is about to be committed is when someone starts talking about “hybrid quantum/classical algorithms.” By this they seem to mean: “outside the domain of traditional quantum algorithms, so don’t judge us by the standards of that domain.” But I liked the way someone at Q2B put it to me: every quantum algorithm is a “hybrid quantum/classical algorithm,” with classical processors used wherever they can be, and qubits used only where they must be.
The other thing people do, when challenged, is to say “well, admittedly we have no rigorous proof of an asymptotic quantum speedup”—thereby brilliantly reframing the whole conversation, to make people like me look like churlish theoreticians insisting on an impossible and perhaps irrelevant standard of rigor, blind to some huge practical quantum speedup that’s about to change the world. The real issue, of course, is not that they haven’t given a proof of a quantum speedup (in either the real world or the black-box world); rather, it’s that they’ve typically given no reasons whatsoever to think that there might be a quantum speedup, compared to the best classical algorithms available.
In the holiday spirit, let me end on a positive note. When I did the Q&A at Q2B—the same one where Sarah Kaiser asked me to comment on the term “quantum supremacy”—one of my answers touched on the most important theoretical open problems about sampling-based quantum supremacy experiments. At the top of the list, I said, was whether there’s some interactive protocol by which a near-term quantum computer can not only exhibit quantum supremacy, but prove it to a polynomial-time-bounded classical skeptic. I mentioned that there was one proposal for how to do this, in the IQP model, due to Bremner and Shepherd, from way back in 2008. I said that their proposal deserved much more attention than it had received, and that trying to break it would be one obvious thing to work on. Little did I know that, literally while I was speaking, a paper was being posted to the arXiv, by Gregory Kahanamoku-Meyer, that claims to break Bremner and Shepherd’s protocol. I haven’t yet studied the paper, but assuming it’s correct, it represents the first clear progress on this problem in years (even though of a negative kind). Cool!!
Follow
Comment #1 December 28th, 2019 at 2:04 pm
Scott, great post as always. VQF is of course just a special application of QAOA. Is there a specific reason why this particular application of QAOA is fundamentally different from, for example, using QAOA to solve MAX E3LIN2 as per the Boaz Barak paper from a complexity theory perspective or for some other reason I am missing? According to your previous post on this forum, you were apparently ok with at least the possibility that there may be some advantage of using QAOA versus the best currently available classical algorithm for certain problems like MAX E3LIN2. Not taking a position here, but it would appear to a non expert that the same criticisms above for using QAOA for solving factoring reframed as an optimization problem could be leveled at the Boaz Barak results as well. Is the factoring problem in the VQF example (post classical preprocessing) more tractable classically than MAX E3LIN2? Why?
Comment #2 December 28th, 2019 at 3:25 pm
What’s the state of the art in proving Quantum Supremacy to a classical skeptic, then?
Comment #3 December 28th, 2019 at 5:03 pm
Christopher Savoie #1: Thanks for your comment. To recap for you and others, the history was this. First, Farhi et al. (not Barak et al.) rigorously proved that QAOA could efficiently achieve a certain approximation ratio for MAX-E3LIN2—a ratio better than (at that time) anyone had shown how to achieve classically. So I blogged about their result, as something of obvious interest—I pointed out that, if the separation stood, then it was history’s first example of a quantum algorithm achieving a better provable approximation ratio for an NP-hard optimization problem than was possible classically.
Alas, my blog post then inspired several groups of computer scientists to design a polynomial-time classical approximation algorithm for MAX-E3LIN2, which not only matched but beat the approximation ratio achieved by QAOA. They then merged their efforts into the Barak et al. paper that you were referring to.
So, the Barak et al. paper killed the one clear candidate application of QAOA that had been known. Since then, no other clear candidate application has arisen to take its place. For all anyone knows, QAOA might have zero practical applications. Or maybe something else will be found. It’s a good research problem!
But let me reinterpret your question as follows. If I was open to the possibility that QAOA could yield an advantage for MAX-E3LIN2—even though that possibility turned out not to be realized—then why am I not likewise open to the possibility (even if we have no evidence at present) that QAOA could yield an advantage for factoring? This is a subtler question. I’ll answer it in three parts:
(1) MAX-E3LIN2 is an optimization problem, with better and worse solutions (Farhi et al.’s claim, which stood for a few months, was that QAOA could find a slightly better solution). By contrast, factoring is a problem with a single right answer, which you either find or you don’t. This means that for factoring, the only hope is to find the right answer a bit faster—it all comes down to speed.
(2) Alas, for special cases of Satisfiability, unless they’re so easy that your heuristic actually solves them in polynomial time, the plausible speed advantages look like solving them in cn time for some c<2. But that means you’re going to be totally lapped on large numbers by classical algorithms like the Number Field Sieve, which runs in ~exp(O(n1/3)) time (to say nothing of Shor’s algorithm). All of those algorithms exploit special number-theoretic structure that a Satisfiability heuristic, whether classical or quantum, has basically no hope of accessing.
(3) And actually the situation is even worse, because unlike MAX-E3LIN2, Factoring is not directly solvable by QAOA—it first needs to be encoded as a SAT instance (indeed, much of the Zapata paper that I linked to is about the details of that encoding). And no matter how clever you are with it, the blowup from the encoding seems likely to wipe out even a 2n → cn speedup, leaving you with no speedup at all over brute-force trial division (let alone the Number Field Sieve).
Hope that clarifies things!
Comment #4 December 28th, 2019 at 5:54 pm
Eric #2:
What’s the state of the art in proving Quantum Supremacy to a classical skeptic, then?
Great question!
(1) If you have a full fault-tolerant QC, then we have several great ways for it to prove its supremacy to a classical skeptic, under plausible hardness assumptions, even assuming that the classical skeptic is polynomial-time-bounded. The “obvious” way, which remains an excellent one, is just to use Shor’s algorithm to factor a huge composite number chosen by the skeptic! But recent works—including, notably, last year’s breakthrough by Urmila Mahadev—have shown that you could actually take any problem solvable in polynomial time by a quantum computer, and have the QC prove its answer to a polynomial-time classical skeptic via an interactive protocol. (In the case of Mahadev’s protocol, under plausible cryptographic assumptions.)
(2) If you only have a “NISQ” device—that is, one without error-correction—then we have protocols for demonstrating quantum supremacy, like the Linear Cross-Entropy Benchmark that Google recently used, which however all share the drawback that the classical verification requires ~2n time, where n is the number of qubits. For that reason, the classical verification is only feasible today when n is ~50 or less.
Now, can you demonstrate quantum supremacy with a NISQ device, in a way that can be verified by a polynomial-time classical algorithm? That’s exactly the central open question that I was talking about! It remains open. To my knowledge, the only real results we have are negative in character—i.e., ruling out various ways you might’ve hoped that it could be done. For an example of such a negative result, besides Kahanamoku-Meyer’s, see this paper by me and Hoi Nguyen. Our result there says that it’s nearly impossible that you could “smuggle” a very-high-probability output into a BosonSampling instance, in such a way that a classical algorithm couldn’t also quickly find that output.
Comment #5 December 29th, 2019 at 12:11 am
Hi Scott. Jonny from Zapata/VQF here. First, I appreciate the criticism from yourself and the scientific community with regard to quantum startups and misleading or false claims. I particularly want to be able to speak with support from the academic community that any science I generate is sound; I would personally consider it a moral failure if funds were ever allocated to Zapata based on wrong or highly misleading science. You seem to be making an assertion that this was our intention, based on “a false exciting interpretation”. Can you point to precisely what you see this interpretation as being? Perhaps the article you linked contains this interpretation, though this article was in no way generated by us.
You might mean that the “false exciting interpretation” is implied, which is certainly a fair concern in a world of quantum misinterpretation (although I assert that steps #2 and #5 will happen regardless of how careful you are otherwise). I thought our paper said it clearly: “Although we show that it is in principle possible to factor using VQF, as with most heuristic algorithms, it remains to be seen whether it is capable of scaling asymptotically under realistic constraints posed by imperfect optimization methods and noise on quantum devices.”
Is this misleading by omission? It would certainly be for the situation that we can a priori discount the algorithm from succeeding. Indeed, this seems to be your assertion. “…you’ve thrown away all the mathematical structure that Shor’s algorithm cleverly exploits, and that makes factoring asymptotically easy for a quantum computer.”
I think this criticism is incomplete, at least with respect to how you paint the picture in your post. Here’s why:
The algorithm is a heuristic and doesn’t rely on the existence of Shor’s algorithm or its mathematical structure to succeed. Instead, it relies on either QAOA to be a good solver, or QAOA+some other mathematical structure which is preserved in the translation to optimization problem. As a heuristic, to be relevant in a security setting, there need only exist a non-negligible-sized set of instances which classical algorithms fail to factor quickly but for which the heuristic succeeds. That is, we don’t need to factor any bi-prime, just enough of a fraction of bi-primes that we don’t feel secure in using the method. However, as a churlish theoretician myself, I admit that this seemed unlikely, especially since there is no explicit exploitation of structure in QAOA. (Note: it is fair to say that the motivation for checking the possibility for factoring came from the fact that we know quantum computers can factor efficiently via Shor, but this is only part of the origin story, not part of the argument that we make).
But, while it still seems sensible to hand-wave the result away as just another “factoring scam”, we have no evidence to show that the heuristic actually fails (see numerics in the paper). Granted, a reasonable skeptic should not be convinced that the numerics for these small instances will continue to scale. I certainly am not. But the results surprised me in that they seem inconsistent with the success rate that I would have expected in my most skeptical view (i.e. it does seem to scale better than brute-force trial division for the small set of examples we looked at).
So, I hardly feel it is a sin of omission when, “Admittedly, to people who work in quantum algorithms, everything above is so obvious that it doesn’t need to be said.” I would certainly vilify Zapata if they launched some ad campaign claiming that VQF is clearly better than Shor, but we don’t make that claim or anything close to it. I’m sympathetic with you having to explain to non-experts to take any claim of NISQ factoring extremely skeptically, but I don’t think it’s fair to say that someone is intentionally misleading simply because some people get a wrong idea and don’t do their homework; I imagine that those same people are the ones who aren’t actually reading our paper, so I don’t expect that these misunderstandings are the result of any such subtle omission. Do you have a sense that they are? If so, we’d be happy to make changes to better reflect an academically honesty position.
Comment #6 December 29th, 2019 at 3:08 am
Re: the “Fundamental Error of Quantum Algorithms Research”
Is “error” really the right word? The word “error” suggests that this is unintended. But isn’t the problem really caused by the nature of science funding? The incentive structure promotes motting with scientists and baileying with funders.
I’m not accusing anyone of actually doing this on purpose, but it’ll just be awfully convenient (wink wink nudge nudge) if this limited truthful scientific claim that one is making just happens to be misinterpreted by the popular press or general public or business or government to be much more than it is.
Until the incentive structure is fixed (and I have no ideas on how to go about this), it’s not so much an error as a plausible strategy.
Comment #7 December 29th, 2019 at 8:05 am
Jonathan Olson #5: Thanks for your comment.
Let me start with an apology: if anyone got the impression, from my post, that I thought that Zapata was purposefully misleading people, that certainly wasn’t my intention.
In the same way, if all the business and government people who came to me had gotten the impression that crypto might be imminently threatened by QAOA (as it’s eventually threatened by Shor’s algorithm) … well, I’m sure that wasn’t YOUR intention! 🙂
I guess we should all try to be more sensitive to unintended messages.
More seriously, and to come to the core of the matter, let’s consider the sentence from your paper that you quoted here:
“Although we show that it is in principle possible to factor using VQF, as with most heuristic algorithms, it remains to be seen whether it is capable of scaling asymptotically under realistic constraints posed by imperfect optimization methods and noise on quantum devices.”
Yes, I do think that this sentence seriously misleads by omission. For starters, there’s the completely orthogonal concern thrown in about “noise on quantum devices,” when you and I both know that the real question is whether, even with an ideal noiseless device, there’s any reason whatsoever to expect VQF to yield any scaling advantage over classical factoring algorithms.
But more fundamentally, I feel like the phrase “remains to be seen” does a pretty breathtaking disservice to our knowledge about the scaling behaviors of algorithms. In the present context, it’s like: “While we’ve had some success in throwing rocks faster and faster, it remains to be seen whether we’ll be able to scale to where we can throw them faster than the speed of light.”
We’ve had decades of experience to tell us that empirical results, on small instance sizes, are almost totally uninformative about asymptotic scaling behavior. The adiabatic algorithm also “looked,” from simulations on instances of up to size 20, like it could just outright solve NP-complete problems in polynomial time in the worst case. And I clearly the remember the period, from roughly 1999 and 2002, when we were all supposed to regard that as “promising.” Though only a beginning student then, I was one of the few who refused to go along with that, since I knew that a combinatorial explosion often fails to kick in until you have enough “wiggle room” in your instance to get it started. Of course we were vindicated once people started analytically calculating spectral gaps.
So in this case as well, I would say: our prior expectation is that, if you don’t know anything whatsoever about multiplicative groups, or elliptic curves, or anything else from number theory, as we both agree that VQF doesn’t, then whatever you do to factor a number, it’s going to amount to some form of trial division. (In the quantum case, possibly trial division enhanced by Grover search.) Let’s say this is true with at least ~99.99% probability. It’s true unless VQF, blindly twiddling bits in the binary representations of the candidate factors, is somehow able to “magically rediscover” the relevant number theory on its own, like some AI mathematician.
So then whatever “promising” empirical results someone showed me, on numbers with ~13 digits or fewer, do you think they’d do more than shave a single 9 off of that? 🙂
Comment #8 December 29th, 2019 at 10:18 am
Hi Scott.
Thanks a lot for sharing your opinions with such honesty. While I agree that they’re shared by a large fraction of the community, your post has the great advantage of making them common knowledge.
If I may ask a question in the same vein, do you feel that there are any applications of QML that look promising?
Thanks!
Comment #9 December 29th, 2019 at 1:23 pm
Anthony #8: Here at Shtetl-Optimized, “Sharing Opinions With Honesty” has been our official motto since 2005. I mean, is that not the defining quality that makes a few people like this blog, while making a bunch of other people hate it? 😀
Regarding QML: I’m optimistic about speedups for ML problems that themselves involve learning quantum states or processes. For classical ML problems, I’m optimistic about Grover-type speedups.
Ah, you ask, but what about exponential speedups for ML-problems of real-world significance that are not themselves about quantum? There, I don’t know in the sense of really, genuinely not knowing. I wouldn’t bet 10:1 for such an application existing, and I wouldn’t bet 10:1 against.
Comment #10 December 29th, 2019 at 1:35 pm
Scott #9:
In the spirit of “Sharing Opinions With Honesty,” some tweets suggest that your commentary is influenced by personal financial ties to companies operating in this space.
Leaving aside whether industry ties are genuinely influencing – which is a very thorny question – I wonder whether you have any such financial relationships and, if so, whether you publicly declare them. A quick search of this site and your academic home page didn’t turn up anything.
Comment #11 December 29th, 2019 at 3:03 pm
Scott #9:
Thanks for the answer!
By sharing with honesty, I meant “sharing *about this specific topic* (one of the elephants in the room!) with honesty”. There are not so many places where such topics can be discussed in full honesty: researchers tend to be overly polite/cautious when discussing others’ papers and at the same time tend to oversell their own results, so it’s not always easy to form an informed opinion.
Comment #12 December 29th, 2019 at 3:16 pm
Ed #10: Alright then, I’m the chief scientific adviser at QC Ware (which involves a few hours’ work per month). I accepted that position specifically because of assurances that I could continue to speak my mind about anything, with no professional commitment to specific algorithms or projects. And I’ve tested that, by repeatedly saying things (including at QC Ware’s Q2B conference) that are the opposite of what I might say if I were trying to drum up more QC consulting business. My job for QC Ware, just like my job on this blog, is to try as hard as I can to tell the truth and to be right (and whether I’m right is often checkable not long after the fact).
Let it be known to anyone who cares: I stand by any scientific claim that I make because someone directly asked me. (Well, most of them … if you really want to be sure ask me twice. 🙂 ) There are no scientific claims that I endorse “by default,” just by virtue of some association between me and some other person. At most I might tell you that an entire textbook, series of books, website, person, etc. is generally reliable.
Besides the QC Ware thing, UT Austin’s Office of Technology Commercialization licensed my certified randomness protocol to Google, in a non-exclusive way. I don’t have any formal relationship with Google outside of that. I did get to know the Google team pretty well because of their focus on demonstrating sampling-based quantum supremacy. But if some other team had seriously gone for that, I would’ve spent as much time talking to that other team. I continue to talk to many people at Microsoft, IBM, PsiQuantum, various other startups, etc — so that whatever conflicts of interest might arise, hopefully they’re cancelled against other conflicts of interest! 🙂
Besides that … uhh, I’m on the scientific board of Quantum Machines, Inc, an Israeli company that builds electronics for shaping pulse signals to send to QCs. I’m honestly having trouble imagining how that would bias someone for a discussion like the one in this post.
I’ve previously discussed all of that on this blog, with the exception of the Quantum Machines thing, which I don’t think I ever had occasion to discuss (but I’m happy to do so now).
Wouldn’t it be more persuasive if you could identify a way in which you thought I was biased for or against something, and give examples, rather than just casting random aspersions? Again, a priori it would seem like any financial biases should only bias me toward the opposite of what I actually said in this post!
Comment #13 December 29th, 2019 at 4:10 pm
A contrast and a question
1) A journalists goal is to get out an interesting story. Hence they might not want to check to carefully if a claimed breakthrough is real. So I understand why they might, not quite lie, but not be as careful as they should be (and to be fair, some are careful).
2) If a Venture Capitalist puts money into a quantum startup that has no reason to succeed, that is less understandable. They are actually risking their money on it.
So here is my question- are Venture Captilists foolishly funding some quantum startups that whey shouldn’t be (given that the VC’s goal is to make money)? And if so, then why?
Comment #14 December 29th, 2019 at 5:22 pm
William Gasarch #13:
So here is my question- are Venture Captilists foolishly funding some quantum startups that whey shouldn’t be (given that the VC’s goal is to make money)? And if so, then why?
I don’t know the answer to this question (and don’t pretend to know when I’m asked). One problem is that many, many things that are easy to recognize as “foolish” in retrospect were hard to recognize as foolish at the time, even by the best experts that there were. Or the people who correctly said that these were foolish investments (and gave correct reasons), also said that Apple, Facebook, and Bitcoin were foolish investments.
One thing you learn, from even short exposure to the VC world, is that VCs are not even trying to answer the same question that an academic would: “is this proposal intellectually sound, or isn’t it?” They’re looking at a large number of other ways they might recoup the investment, like accumulating valuable IP, a buyout by a larger company (which might be more for the people than for the idea), etc. That makes it even more impossible for me to judge, except in some very special cases, whether people are making good or bad investments.
Comment #15 December 29th, 2019 at 6:54 pm
Scott 11: Thanks for the response. I know it’s a sensitive issue, and that it seems crass to raise it. I genuinely am not trying to cast aspersions.
You suggest I would be more persuasive in arguing that you’re biased “if [I] could identify a specific WAY in which [I think you are] biased.” No doubt. But totally irrelevant, since I’m not trying to persuade anyone of anything.
If you’re suggesting that my failure to identify any particular bias is evidence that no bias exists, well, I disagree. I’m actually totally unqualified to assess the technical arguments either way! In any case, I don’t really believe there are specific identifiable ways in which you’re biased (and no, I’m not just being coy here.)
Look, I know these conversations can be tough, because they overlap with various sensitive issues: money, private moral character, public image, persuasion dynamics, expertise, etc. Nevertheless, I think they have a place.
Some months back, I took my partner to the ER for abdominal pain. The doctor recommended a CAT scan, which is expensive, and which can (possibly) cause long-term health complications. I asked the doctor whether he had any financial interest in the decision (this is in the U.S.), and he responded predictably: he became agitated, ranted about experience, suggested that I was an asshole for even considering that he might be anything other than the purely selfless individual that he is, intimated that he could make more money in finance, mockingly suggested that I must be a great expert (I have no special knowledge of medicine), etc. Again, maybe this doctor was completely financially disinterested, and maybe the scan was totally warranted (I take no position either way.) Even so, it seems wrong to me to treat questions of financial interest as out-of-bounds aspersions-casting.
Comment #16 December 29th, 2019 at 7:16 pm
Ed #15: Well, I hope to have given a contentful answer. To recap, I’ve never accepted any money to serve as an “attorney” for either side in any dispute within QC, and I don’t intend to. I’ve only ever accepted outside compensation to serve as “expert witness” or “judge”—or occasionally, to work on some specific technical problem. But crucially, the compensation never hinged on which answer I gave. In that sense, consulting work has only ever been a slightly more topic-directed version of what I do in my ordinary research or on this blog.
Having said that: there’s indeed no way to ask what you’re asking, without calling the expert’s judgment into doubt! In which case, a reasonable response might be: then why did you go to this particular expert at all? Why not go to a different one? In the case of a doctor, you may have had no other choice (say for insurance reasons), but in the case of a blogger… 😀
Comment #17 December 30th, 2019 at 7:06 am
I came across your blog following the discussion with Steven Pinker about banning names (supremacy and NIPS). So sometimes controversial topics help in a way or another.
I just want to say this is heaven for me. I am trying to read as many posts as I can.
Thanks!
Comment #18 December 30th, 2019 at 8:15 am
Esam #17: That’s great to hear–enjoy! (Unless you’re procrastinating, in which case: stop reading Shtetl-Optimized and get back to work! 😀 )
Comment #19 December 30th, 2019 at 9:50 am
Scott #18: hahaha well I am kind of procrastinating. However, this time, it is mandatory. Our university IT infrastructures have been under cyberattacks for almost one week. The system has been inaccessible and this will continue for at least one more week.
It is worthy to check it: https://www.maastrichtuniversity.nl/news/update-5-um-cyber-attack?fbclid=IwAR1bYDsR6sI5TwKY6p_0GdPje4Y-dExhahF-UqQd1OPYB7cbksrIrDOCY2g
I wouldn’t have imagined such a cruel cyberattack to an educational organization, given the heroic image of hackers in popular culture :(.
Happy new year!
Comment #20 December 30th, 2019 at 10:27 am
I was looking at an article entitled “Here are six reasons to be optimistic about 2020”
(https://www.cnbc.com/2019/12/20/here-are-six-reasons-to-be-optimistic-about-2020.html) where I was surprised to see the following paragraph:
Writing for the World Economic Forum, Jeremy O’Brien says quantum computing could help beat climate change through simulations that could uncover new catalysts for carbon capture that are cheaper and more efficient than current models. “A catalyst for ‘scrubbing’ carbon dioxide directly from the atmosphere could be a powerful tool in tackling climate change,” he writes.
I wonder if most readers of the blog would agree that this crosses the line in terms of making reasonable statements given our current knowledge. If so, my intent is not to criticize any individual; rather, to suggest that that there’s lots of information out there that enables people to casually make such statements.
Comment #21 December 30th, 2019 at 11:13 am
Richard #20: Like, I can’t say for certain that Jeremy is wrong! But first scalable QCs would have to be built, and second the more practical carbon-capture reactions would have to exist, and third they’d have to be discovered using the QCs, and fourth they’d have to NOT be discovered first in a more prosaic way, and fifth they’d have to be deployed on a large scale, and sixth it would have to be in time to make any difference. So if this is a reason for optimism about climate change, then probably only for very optimistic people! 🙂
Comment #22 December 30th, 2019 at 2:49 pm
Hi Scott,
speaking of potential applications of Boson Sampling, what do you think of cryptosystems based on this problem, as an alternative to more standard QKD protocols?
for instance,
https://arxiv.org/abs/1907.01788
https://arxiv.org/abs/1905.03013
Comment #23 December 30th, 2019 at 4:22 pm
Anthony #22: I confess that those proposals did not make sense to me. Like, even setting aside the question of their soundness, what’s the point of using BosonSampling to do these well-known cryptographic tasks? Couldn’t classical PRGs and one-way functions accomplish the same ends much more easily? Maybe someone who understands could explain it to me?
Comment #24 December 30th, 2019 at 4:32 pm
Scott #23: well, I feel exactly the same way but I was wondering whether I was being too harsh with these ideas.
Of course, the main raison d’être of such protocols is probably to justify performing complicated quantum optics experiments (by allowing their authors to publish in respectable journals for instance), which is helpful in the long run if our goal is to improve quantum technologies.
Comment #25 December 30th, 2019 at 5:30 pm
Wouldn’t a one-way function based on Boson sampling be less vulnerable to something like Grover’s search?
At least it seems like it would be more difficult to reverse using quantum machinery. Isn’t it a better black box?
Comment #26 December 30th, 2019 at 6:04 pm
Job #25: No.
Firstly, it’s not clear how you even get a one-way function from BosonSampling. As much as various people claiming applications for BosonSampling have tried to ignore this fact for years, BosonSampling is a sampling problem. For any given beamsplitter network, there will be exponentially many outputs, and (generically) you’ll have to run for exponential time before you even see the same output twice. So then which output is the output of the “one-way function”? The first paper linked above tries to solve this problem, but it doesn’t succeed—and then, having not succeeded, it just plows ahead anyway.
But secondly, even if you could get a unique output for each given input, still, what would be the point? You’d have no better resistance than with a classical OWF against attacks based on Grover’s algorithm—as in none, zero. Why would you? It’s just as easy to use a quantum algorithm as a classical algorithm for the Grover oracle. The only new thing is that you’d now have a one-way function that required a quantum computer to evaluate it even in the forward direction. For many applications, it’s clear that this is very bad. Are there any applications for which it’s good?
Maybe I should issue a general public service announcement: BosonSampling is not like garlic. It does not magically enhance anything it’s added to. And if some candidate application of BosonSampling makes no sense, there is always the option not to publish it! 🙂
Comment #27 December 30th, 2019 at 6:16 pm
Well, that’s the only thing i could think of, some kind of immunity to quantum attacks.
What else could it be?
Comment #28 December 30th, 2019 at 6:41 pm
Job #27: Right, the central argument that still bothers me, for why there must be some point to the various claimed applications of BosonSampling, is simply: if there were no point, then why would all these people who know quantum information keep talking about this? But then I look at the papers and the question “why BosonSampling, as opposed to some simple classical solution for the task at hand?” is never raised, let alone answered…
Comment #29 December 31st, 2019 at 5:59 am
Scott #4
“Now, can you demonstrate quantum supremacy with a NISQ device, in a way that can be verified by a polynomial-time classical algorithm? That’s exactly the central open question that I was talking about!”
How well-defined is this question? I thought that “NISQ” is not a precise concept, because the difference between NISQ and fully-fledged quantum computer is just the number of qubits, and there is no sharp boundary. In other words, there is no complexity class defined in terms of asymptotic conditions that formalizes what it means for a problem to be “solvable by NISQ” (and that is a proper subset of BQP). Am I wrong? Is the open question really about the minimal number of qubits needed for a classically-verifiable demonstration *in practice*, given the properties of the quantum *and* classical hardware we actually have? Or, is there a way to formulate it in a “purer” abstract form?
Comment #30 December 31st, 2019 at 7:21 am
Vanessa #29: Yes, you’re entirely right. NISQ implementability is an “I know it when I see it” type of condition, which in practice amounts to “something like random circuit sampling or BosonSampling or IQP, but at any rate, not requiring arithmetic on superposed integers written in binary, like Shor’s algorithm or Urmila Mahadev’s protocol.” I’d love to know whether there’s any formal definition that captures this.
Having said that, maybe the best way to state this challenge is to abandon asymptotics, go entirely to the practical side, and say: we want a quantum supremacy demo that you can perform with a NISQ device, and for which verification of the output can be done in a few seconds on a standard laptop.
Comment #31 December 31st, 2019 at 8:33 am
Hi Scott. I’ve followed your blog for some time, in the process learning at least a little bit of quantum computing (an area far outside of my own field). In the process you have served as a corrective to the excess hype that seems to be endemic in the discussions regarding quantum computing.
This latest post further reiterates the problem of hype with respect to QC. At the same time, it does raise a question in my mind, about whether there are ANY applications to QC algorithms (or hardware) that are feasible in the near future that are demonstrably superior to classical algorithms
Comment #32 December 31st, 2019 at 8:35 am
Apologies as I accidentally submitted my earlier comments. I wanted to add whether there are QC algorithms that are feasible in the near future, demonstrably superior to classical algorithms, AND that are of any practical use, other than breaking current RSA-style cryptographic systems.
Comment #33 December 31st, 2019 at 9:53 am
Aaron G #31 and #32: Breaking RSA is definitely not a “near-term”/NISQ application! It requires fault-tolerance. If there are any useful applications in the near term, the best bet (besides things like generating certified random bits) is almost certainly simulations of quantum chemistry and condensed-matter physics. There have been many other posts on this blog touching on this, or see (e.g.) Preskill’s surveys.
Comment #34 December 31st, 2019 at 11:54 am
Ed, I can sympathize with the Doctor in that situation. They must have felt you were impugning their character as the question is essentially asking if they are making a recommendation that is possibly tainted by financial motivations, especially given how much emphasis is placed on caring for patients in a Doctor’s training.
That said, I agree that it is a valid concern, but maybe more sensitivity is needed in how to ask it. Maybe Doctors should disclose all sources of income for transparency.
In Scott’s case, he can state that he doesn’t have any financial motive to not tell the truth, but at the end of the day, you have to make your own judgement based on the veracity of the comments themselves or of any rebuttal of those comments.
Personally, I have found Scott’s analysis to be trustworthy in most cases and if we are to look at the finance angle here, it seems that these startups have more financial motivation than Scott to speak non-truths.
Comment #35 December 31st, 2019 at 4:36 pm
Follower #34: Maybe another point worth making is that I never sought out consulting work (or used this blog to advertise for that). All that happened was that some people in QC investing and startups read this blog, and wanted me to spend a few hours here or there to look at questions of interest to them. And I didn’t have time, so I named a fee that was meant to be just a polite way of saying “go away.” And then, in a few cases, they were like “OK sure! When can you start?” 🙂
Comment #36 January 1st, 2020 at 8:47 am
Hi Scott, browsing your blog I’m learning a great deal about QC, also using the referenced material and reading QC since Democritus. A question I’m not able to completely clear is the following (sorry, I’m just a physicist 😉 ): I’m having the impression that real useful QC algorithms are based on the quantum Fourier transform and this is really the core algorithm a QC can perform efficiently (not surprisingly to me actually, since states are written on a complete basis and this is similar to a transform). Is this true, or could you give me examples of useful Q algorithms which are not based on the QFT? Thanks in advance and have a great 2020. Cheers, K.
Comment #37 January 1st, 2020 at 8:52 am
Just to be clearer, I’m aware of (still simple) physics “applications like:
https://arxiv.org/pdf/1801.03897.pdf
but I do not think these things are comparable to Shor or Grover.
Thanks again, K.
Comment #38 January 1st, 2020 at 9:58 am
LK2 #36: Well, Grover’s algorithm is not based on Fourier transforms (except insofar as it involves Hadamard gates)—it’s based on something different, the “Grover diffusion transform.” Similarly for all the quantum walk algorithms that are Grover-inspired.
Probably the #1 application of QC is still quantum simulation, which doesn’t necessarily involve any Fourier transforms (although it could—for example if you want to do phase estimation).
Random circuit sampling, and its application to generating certified random bits—i.e., the one application of QC that looks feasible with already-existing technology—also doesn’t involve any Fourier transforms.
Having said that, yes, the QFT is an absolutely central primitive for quantum algorithms, much like “dynamic programming” or “solving linear equations” or whatever is for classical algorithms.
Comment #39 January 1st, 2020 at 1:15 pm
Scott, great: thanks for the informative answer!
Comment #40 January 1st, 2020 at 4:14 pm
It’s interesting that Boson Sampling is both non-universal and yet classically hard.
What kind of gate set do you need in order to simulate Boson Sampling with a general purpose QC?
I’m guessing that it would require a universal QC, and it’s just sufficiently constrained that you can’t get universal computation out of it?
And can you change it to be universal and still classically hard? If not, that’s a little strange.
Comment #41 January 1st, 2020 at 5:06 pm
Job #40: It’s not that weird; we know several other examples of non-universal models (IQP, low-depth circuits, conjugated Clifford, one clean qubit, …). To simulate BosonSampling, yes, you’d either want a universal set of gates, or you could make do with “bosonic gates” (which simulate beamsplitters), with the caveat that those don’t act on qubits, qutrits, or any other fixed-dimensional quantum system — the dimension grows as the total number of photons.
Comment #42 January 1st, 2020 at 11:22 pm
The weird part is that there seems to be stronger evidence that these non-universal models are classically hard, compared to universal ones.
Normally, i would expect universality on the quantum side to just make things worse for a classical machine, and result in stronger evidence.
I guess it’s just easier to prove a narrower case?
It’s counter intuitive to me if the polynomial hierarchy collapses more easily for these non-universal models.
I don’t know if that’s true or not, but it sounds like it.
Comment #43 January 2nd, 2020 at 7:32 am
Scott re #9: I thought the official motto of Shtetl-Optimized was “Quantum computers are not known to be able to solve NP-complete problems in polynomial time, and can be simulated classically with exponential slowdown.” then later “If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.”
Comment #44 January 2nd, 2020 at 7:48 am
Job #42: No, that’s a misconception—although one that I share some blame for, because Arkhipov and I developed BosonSampling before even the general principles of sampling-based quantum supremacy experiments were widely understood. (And Bremner, Jozsa, and Shepherd likewise developed the IQP model before anyone was talking about, e.g., the output distributions of general random quantum circuits.)
With equal or greater ease as one does so with BosonSampling or IQP, one can show that if classical computers could efficiently sample the output distributions of arbitrary quantum circuits, then the polynomial hierarchy would collapse.
So Arkhipov and I understood from the beginning that the real issue was going to be robustness to noise. (Well, classical verification of the outputs is an equally large issue, but that was less of a focus for us in 2009-2011.)
That’s what attracted us to BosonSampling in the first place: it involves amplitudes that are permanents of matrices, and we had reasonable hopes that we could use the known “error-correcting” properties of the permanent to prove a robust hardness of classical simulation theorem (again assuming that PH is infinite). The non-universality of BosonSampling, and the prospects for physically realizing it with photonics, were only secondary concerns for us at the time.
Alas, Arkhipov were never able to fully prove the robust hardness of classical simulation result that we’d wanted; the problem remains open to this day. We did make progress toward such a result, but even that progress was recently replicated in the setting of general random quantum circuits (by Bouland, Fefferman, Nirkhe, and Vazirani). So ironically, our original motivation for BosonSampling is now arguably obsolete, and BosonSampling lives on because
(1) it’s a non-universal model that might be easier to realize than full universal QC, all the more so if you’re a photonics lab, and
(2) it happens to be the place where many of the general results and questions about noisy sampling-based quantum supremacy experiments were first articulated.
Comment #45 January 2nd, 2020 at 8:54 am
Scott #43
“That’s what attracted us to BosonSampling in the first place: it involves amplitudes that are permanents of matrices”
Is there a deeper general connection?
QC rests on adding up amplitudes that are both positive/negative (interference) while classical systems rest on positive amplitudes (probabilities), but the hard-to-compute permanent of a matrix has terms of the same sign while its determinant (positivie/negative terms) is easy to compute?
Comment #46 January 2nd, 2020 at 12:50 pm
fred #44: Keep in mind that in BosonSampling, we deal with permanents of complex matrices, so the terms are not all of the same sign—that would be true only if we were talking about permanents of nonnegative matrices. The permanent vs determinant distinction is not about whether the terms are all of the same sign. Instead, for want of a better way of saying it, it’s about whether minus signs are placed in front of half of the terms in just such a way that you get a quantity that’s geometric, that’s connected to eigenvalues, and that can be efficiently computed using Gaussian elimination.
Comment #47 January 2nd, 2020 at 3:12 pm
“One can show that if classical computers could efficiently sample the output distributions of arbitrary quantum circuits, then the polynomial hierarchy would collapse.”
It is worth mentioning an even stronger result which combines the argument of Terhal and DiVincenzo and Aaronson and Arkhipov which asserts that if classical computers could efficiently sample the output distributions of arbitrary BOUNDED DEPTH quantum circuits then the polynomial hierarchy would collapse!
Comment #48 January 2nd, 2020 at 6:49 pm
jonas #43: The thing about quantum computing and NP-complete problems is the tagline. The motto was never before explicitly stated—but in the spirit of “Sharing Opinions With Honesty,” I’m doing so now. 😀
Comment #49 January 3rd, 2020 at 11:56 am
A just machine to make big decisions
Programmed by fellas with compassion and vision
We’ll be clean when their work is done
We’ll be eternally free, yes, and eternally young
What a beautiful world this will be
What a glorious time to be free!
Comment #50 January 4th, 2020 at 10:43 am
Scott #44:
” if classical computers could efficiently sample the output distributions of arbitrary quantum circuits, then the polynomial hierarchy would collapse.”
Are there any results that go in the opposite direction ? If the PH collapses (or if P = NP), would that imply anything about the ease of sampling from quantum circuits ?
Comment #51 January 4th, 2020 at 8:53 pm
Gerard #50: Superb question! I don’t currently know any results to the effect that if P=NP, then general quantum computations become easy to simulate. On the other hand, at least one interesting class of quantum computations—the “stoquastic” ones—would become easy to simulate classically in such a world. And also, if we go slightly beyond P=NP in assumption-land—specifically, to P=P#P—then general quantum computations really do become easy to simulate classically.
Comment #52 January 5th, 2020 at 7:34 am
Hi Scott. Thank you for elaborating and thank you for the apology.
Jumping to the core of the matter:
“Yes, I do think that this sentence seriously misleads by omission. For starters, there’s the completely orthogonal concern thrown in about “noise on quantum devices,” when you and I both know that the real question is whether, even with an ideal noiseless device, there’s any reason whatsoever to expect VQF to yield any scaling advantage over classical factoring algorithms.”
I am appreciating now that something was certainly omitted, though until you elaborated, it had not occurred to me. Perhaps this is a mistake born of too many internal conversations with the co-authors where the context seems more obvious than it really is. You are correct that the paper omits a very important conversation that may be overlooked particularly by folks who think of quantum algorithms in the usual “worst-case complexity” kind of way. Probably the first change to make would be to promote the word “heuristic” to appear in the title: “A Variational Quantum Factoring Heuristic”. Why? Our goal was never to develop an algorithm that solves the general problem (i.e. you expect it to do well on every instance), but rather that the algorithm solves some interesting subset of instances efficiently, or better than any other known approach (i.e. you expect it to do well on some instances).
What do I mean by “interesting subset” in this context? I mean any subset that is not already known to be easily factored. We know, for instance, that factoring N=pq can be solved very quickly with Fermat factorization if the difference between p and q is small (hence why these numbers are deliberately avoided in choosing p and q in security protocols). Our question is: “Could a NISQ quantum computer factor some family of bi-primes efficiently that a classical computer cannot?” My intuition tells me the answer to this question is “yes”, even if VQF may not be such an embodiment, though I can at least imagine that QAOA might do such a thing.
To highlight why this is important: if the answer to the question is yes, then some fraction of RSA-encrypted bi-primes may be at risk. Even if this amounts to only .01% of instances used today, you could imagine that this is a real security problem given the number of transactions that occur daily.
I imagine this context would already suffice to remove the kind of motte-and-bailey misunderstanding that you’ve presented. Our goal isn’t to compare ourselves to Shor’s algorithm in the first place; we never expected the algorithm would solve any and all instances efficiently. Moreover, this is also why I believe the intuition that we both share with respect to why the algorithm should fail to scale in the general case does not mean much. To give an analogy, suppose Fermat’s method never existed before 2020, but suddenly appears in the literature today. If the RSA protocol did not reject pairs of primes p, q where the difference between p and q is small, then Fermat exposes that family of instances to vulnerability. Yet, Fermat’s method doesn’t scale any better than trial division in general.
So, I think: “whether, even with an ideal noiseless device, there’s any reason whatsoever to expect VQF to yield any scaling advantage over classical factoring algorithms” (though I naturally agree that demonstrating a scaling advantage would be a sufficient condition to show the algorithm works). But, robbed of the above context, I totally admit that it may not have been at all obvious that we were considering that. So, after all, maybe we were committing a kind of motte-and-bailey by omission, though a bit different from the way you described. I apologize if you or others were misled, and completely get where you are coming from, Scott. As you say, I should be more sensitive to unintended messages.
To respond (or maybe just to provide more context) to the remaining pieces of your reply:
– I certainly agree that that if you don’t expect anything to work in the noiseless regime, there is no need to discuss the noisy. I guess to me, working for a company that spends a lot of time thinking about the actual logistics of implementing NISQ algorithms, the more practical concern of large-scale VQF is whether the construction of the quantum circuit makes any sense. In other words, I’m more concerned that even if the algorithm did do something useful in the noiseless case, the success of the algorithm would require so little error that it is essentially no easier to build than a fault-tolerant quantum computer. In that case, we should just run Shor’s algorithm anyway.
Moreover, implementation is a major problem when you solve problems variationally—you expect that, for some instances, your initial parameters and choice of optimizer will simply throw you into some local minimum in which you are doomed never to escape. This concern is precisely the kind of thing that tends to make these algorithms fail even for small instances, and hence why this issue gets the attention that it does.
– I disagree at least in part with: “We’ve had decades of experience to tell us that empirical results, on small instance sizes, are almost totally uninformative about asymptotic scaling behavior.“ I agree that, if things work well for the small instance, it will in no way guarantee that the asymptotic behavior scales well (i.e. you should worry about false positives). For algorithms that scale poorly for small instances, however, I rarely expect to see them scaling well asymptotically (i.e. you rarely see false negatives). I see it as an important step, then, to demonstrate that an algorithm works reasonably well in the small scale. If your point was only to suggest that our numerics don’t suggest anything about its potential for dealing with large instances—well, I can’t agree more.
Comment #53 January 5th, 2020 at 9:36 pm
Jonathan #47
I am not very familiar with your work, so apologies if I am mischaracterizing it, but here is my view as a classical computer scientist about attempts to use algorithms such as VQF for integer factorization.
This is very much analogous to using a SAT solver to try to solve factoring on a classical computer. It is possible to try to do so, but when you do this you lose all the structure of the factoring problem, and so end up doing much much worse than tailored factoring algorithms (see https://arxiv.org/abs/1902.01448 which I just came across now).
Moreover, especially if you are thinking of cryptography applications, the idea that the algorithms will work in “special instances” also doesn’t seem very promising. First, those “special instances” are likely to have some number theoretical structure which you lose when you encode the problem as a CSP. Second, when you’re talking about sampling 1024 or 2048 bit numbers at random, the probability of a “special instance” is likely to be exponentially small as opposed to merely 0.1%.
Unlike other optimization problem, where the instances that arise from different applications can have different structures, in RSA, the distribution is always the same one – random primes. For this reason, it’s often not needed to try to avoid “weak primes” : https://people.csail.mit.edu/rivest/pubs/RS01.version-1999-11-22.pdf
Comment #54 January 6th, 2020 at 8:09 am
Which part of the computational hierarchy would collapse if there was an efficient classical algorithm for factorization?
Comment #55 January 6th, 2020 at 1:40 pm
fred #54: Hardly any of it (as far as we know today). Just a tiny little piece that contains the factoring problem itself.
Comment #56 January 6th, 2020 at 2:16 pm
Scott #55
Isn’t it strange that a QC would be so much better for a problem that happens to be such an outlier?
I.e. a very powerful quantum algo exists (quantum supremacy), and a classical algo doesn’t seem to exist (classical impotence), but if it did, it wouldn’t collapse anything (its power would have a really narrow application).
Then there isn’t a whole zoo of such problems (afaik), but the one instance we’ve found happens to be super practical too (encryption).
That’s a lot of coincidences.
It seems to suggest that either factorization can be solved classically or that we’re really confused about the place of factorization in the computational hierarchy, no?
Comment #57 January 6th, 2020 at 3:53 pm
Actually, I wonder how much just the ability to “square” a classical probability distribution (in a normalized way) could accomplish.
If that makes sense. It would basically move probability from the less likely outputs to the more likely ones, which is difficult for a classical machine to do for an arbitrary circuit.
And it’s kind of like what we can do with interference, but without explicit negative or complex “probabilities”.
Especially if it can be done repeatedly. For example, i think it might allow a classical machine to solve period-finding efficiently.
But would it be as powerful as BQP?
Comment #58 January 6th, 2020 at 7:53 pm
Scott #51
“And also, if we go slightly beyond P=NP in assumption-land—specifically, to P=P^#P—then general quantum computations really do become easy to simulate classically.”
Wouldn’t that mean that the existence of a quantum algorithm giving an unconditional super-polynomial speedup for some problem would imply that P != P^#P (because otherwise you could simulate the algorithm classically in polynomial time) ?
But, I was under the impression that such algorithms exist (Deutsch–Jozsa and/or Bernstein–Vazirani).
(Sorry, for the notation, I don’t know how to get superscripts here.)
Comment #59 January 7th, 2020 at 7:32 am
Gerard #58,
“But, I was under the impression that such algorithms exist (Deutsch–Jozsa and/or Bernstein–Vazirani).”
Both of those algorithms give an unconditional separation in the black box model. A priori, it might be possible to have a black box separation but any black box that can be explicitly specified and where the classical computer has access to that specification, it may be able to do things efficiently. That seems unlikely but we can’t rule it out.
Comment #60 January 7th, 2020 at 7:58 am
Job #57
“Actually, I wonder how much just the ability to “square” a classical probability distribution (in a normalized way) could accomplish.”
I’m no expert, so I could be totally confused…
Isn’t this like doing he random experiment twice but excluding the possibility that you can get two different results in a row?
E.g. if you have a biased coin with probability p(H)=0.2, p(F)=0.8, when you square and renormalize, you get p(H)=0.04/0.68=0.058824, p(F)=0.64/0.68=0.941176.
When you flip the coin twice, you’d get
p(HH)=0.04, p(HF)=0.16, p(FH)=0.16,p(FF)=0.64, but if you reject the possibility of HF or FH, you’re left with p(HH)=0.04,p(FF)=0.64, and when you renormalize this you get that “square” distribution.
And the same holds for continuous probability distributions? (although in that case it’s not super clear what “same two results in a row” means)
Comment #61 January 7th, 2020 at 10:04 am
fred #56: The way I’d describe the situation is that the factoring problem has extremely special structure (arising e.g. from the multiplicative group mod N), and the RSA cryptosystem exploits that special structure, and Shor’s algorithm (ironically) exploits the same structure, and so for that matter do the best classical factoring algorithms that we know. So yes, all of those things ultimately have a related origin, but for whatever reason, that common structure has not yet led to a polynomial-time classical factoring algorithm. If it had, we wouldn’t have used factoring for crypto in the first place; we’d have used something else.
Comment #62 January 7th, 2020 at 11:57 am
Job #57: It’s an excellent question and something I’ve wondered about as well. The answer could depend a lot on what specific model you find to instantiate the intuition of “yes square roots of probabilities, but no destructive interference.” I should, however, mention the model of “stoquastic Hamiltonians,” which has very much this character: the ground states of such Hamiltonians involve positive real amplitudes only, but there’s still at least some “quantumness” present. I’m on my phone, but you can google for papers about this model. One way to think of it is “the class of problems that an idealized D-Wave machine could solve, in principle.”
So what do we know about that class? Well, not much! We know it can be simulated in the polynomial hierarchy (in a relativizing way), in contrast to what we know about full BQP. Meanwhile, we don’t currently have any evidence for a separation between stoquastic adiabatic evolution and classical polynomial time.
I’m extremely interested, as a research topic, in finding other complexity classes (including more discrete, gate-based ones) to model the intuition you said.
Comment #63 January 7th, 2020 at 12:46 pm
fred #59,
That’s my thinking as well, but the difficulty is that, for an arbitrary circuit, the distribution is over exponentially many outputs, where even the most likely outcomes are often still exponentially unlikely.
It would be very rare to get a collision, so we would have to reject and reflip most of the time.
But that’s one of the reasons why the ability to do this efficiently seems powerful.
Comment #64 January 7th, 2020 at 12:51 pm
So I’m guessing that the answer to my quandary in #58 probably has something to do with how black box functions get handled in classical simulations of quantum computers.
It seems like there must be some constraint that ensures that the classical simulator has enough classical information about the black box function f(x) to solve the problem (for example if you’re simulating Grover’s algorithm at some point the simulator must have evaluated f(x) for at least N different values of x). What I’m wondering is if this constraint is automatically implied by the computational complexity of the simulation or if it’s an additional assumption that needs to be considered (like a setup cost, for example).
Comment #65 January 7th, 2020 at 2:05 pm
In terms of circuits, does that translate to a quantum circuit where all intermediate states are described by positive real amplitudes, or only the final state?
If it’s all states then that seems very classical, with a non-classical amplification step right before measurement.
On the other hand if we can only amplify once (by measuring) then that seems alot more challenging to use for problems like period-finding.
Comment #66 January 7th, 2020 at 3:37 pm
Gerard #58 and #63: Yes, it’s all about the oracle. Yours is one of the most common confusions in all of quantum algorithms. It’s one of those things where, no matter how often I repeat it in class, a lot of students still get it wrong on the exam.
In the black-box setting (i.e. with an oracle present, and with complexity measured by the number of oracle queries), we have huge unconditional quantum speedups, for example for Simon’s problem. (Deutsch-Jozsa is not a great example, because it gives no speedup over classical randomized algorithms.) In the non-black-box setting, by contrast, all quantum speedups depend on assumptions such as P≠P#P.
These are two different settings. Those who pretend that they’re the same will continue saying things that are wrong forever.
Comment #67 January 7th, 2020 at 3:42 pm
Job #64: If you did a stoquastic adiabatic evolution, in which you stayed in the ground state the whole time, then yes, your state would have nonnegative real amplitudes only at all intermediate points. But keep in mind that it’s a continuous-time evolution, so you can’t really think about it in terms of discrete gates that map you from one nonnegative state to another nonnegative state. Sergey Bravyi once sketched for me a model with the latter character, but I don’t even know the relationship between it and the stoquastic adiabatic model, let alone the answers to broader questions about the power of nonnegative amplitudes.
Comment #68 January 7th, 2020 at 4:55 pm
Boaz #53
Thanks for the comment, and I don’t think you are mischaracterizing. I appreciate the rather succinct analysis of why one should be skeptical about VQF being successful. I think I agree with the entirety of it, insofar as you say “it is likely that…”. Though, it still feels a bit hasty to me to say that all structure is lost encoding into a CSP. We noticed, for instance, that runtime seems to depend on the number of carry bits in the CSP, all else being equal (not to suggest that this means this in particular is some special exploitable structure). Of course, both you and Scott have a lot more experience under your belt to draw on, and so I don’t expect you are wrong.
Still, I think of it this way: “If QAOA can solve some nontrivial set of problems more efficiently than a classical computer, is it possible that an equivalent set of factoring instances encodes the same problem?” To me, this is an interesting question that does not yet have a clear answer. Maybe there is some secret sauce there. But If the answer is indeed “no”, then it seems relevant to know precisely why. It could absolutely be the case that VQF’s mapping to CSP kills all the structure; well, what if did a different mapping in a bit more of a clever way? I would rather make sure we are asking the right questions. I don’t take any offense to the idea that VQF will fail, but I’m not really interested in that specific statement. If you think I am just completely barking up the wrong tree—that would be helpful advice that I would take to heart.
Comment #69 January 7th, 2020 at 6:26 pm
Here’s how being able to “square” a probability distribution might help with period-finding.
Suppose that we have f(x) = 2^x mod 69, which has a period of 22.
Then g(x) = x – f(x) has the property that the probability distribution over its output also has a period of 22.
So g(x) outputs 2, 24, 46… with the same probability.
But there are peaks, for example 5, 27, 49… each have higher probability than 2, 24, 46…
If you repeatedly square (or amplify in some way) the probability distribution of g(x), all the probability is focused on the peaks, so we’d ultimately be sampling from the following sequence:
5, 8, 27, 30, 49, 52, 71, 74, 93, 96
Which is really a mix of the two subsequences that share the highest probability:
5, 27, 49, 71, 93
8, 30, 52, 74, 96
Depending on how many subsequences share the peak probability (like at most a polynomial amount of them) then we could just figure out the period by sampling from the amplified distribution.
Normally i wouldn’t expect that to be true, but (and to borrow from VQF/QAOA) we’re using a non-classical method here so… it has to pay off in some way?
Comment #70 January 8th, 2020 at 11:40 am
Say you want to get the factors of N=77 (in this case, two primes 11, and 7).
You build a (circular) ring with 77 connected elements (under tension).
If you apply a step impulse to one element (covering a large spectrum of frequencies), the ring should be left vibrating with a period of 11 and/or 7.
Since this is a physical system, isn’t this enough to infer the theoretical existence of an “efficient” classical algorithm for factorization?
Unless the relaxation time to dampen unwanted frequencies is exponential with N?
Comment #71 January 8th, 2020 at 12:06 pm
correction above:
I don’t think that dampening is relevant, it’s more about the wide range of circular waves with “wrong” frequencies just canceling each other on average, so that a pattern with the frequencies 7/11 emerges.
Comment #72 January 8th, 2020 at 5:00 pm
Sorry – my proposal above isn’t “efficient”, in the same way that using dynamic programming on the subset sum problem is only pseudo-polynomial: it’s exponential with the number of bits of N, i.e. you need as many elements in the ring as N itself.
Comment #73 January 9th, 2020 at 1:24 am
You might also enjoy 1QBit papers:
https://1qbit.com/our-thinking/research-papers/
recent ones:
“Long-Short Minimum Risk Parity Optimization Using a Quantum or Digital Annealer”
“Optimal Feature Selection in Credit Scoring and Classification Using a Quantum Annealer”
“Quantum-Inspired Hierarchical Risk Parity”
Comment #74 January 12th, 2020 at 11:24 am
Hi Scott,
Off topic here for a second, I see on the MIT website that you will be giving a talk there in February. Is the talk open to the general public ( can you just walk in ? ) or do you have to sign up and be on a list ? Thank you, looking forward to the talk and getting to see the Strata building for the first time. 🙂
Comment #75 January 13th, 2020 at 3:27 am
Thanks Scott, and everyone. This is really a helpful post and discussion. I wonder if part of the problem is economic. People are assuming that the startup/spinoff company model that works well in classical computing will work well now in quantum. But it only did so from about the mid-80’s. Before that, you had to be huge company or a government to play.
Comment #76 January 13th, 2020 at 6:25 pm
Adam Miles Lewis #74
“Before that, you had to be huge company or a government to play.”
I don’t think that’s terribly accurate. Some of the most important computer companies from the 60’s on began as startups, such as DEC and Data General. Also most semiconductor technology, which of course underlies all modern classical computers, was developed by startups (Fairchild, Intel, etc.).
I think people tend to mostly remember IBM, because they’re still around, but they were far from the only player in that era. For example, in my experience, DEC machines were far more common in physics labs than were IBM’s in the 80’s-90’s.
Comment #77 January 13th, 2020 at 7:36 pm
Thanks for this wonderful conversation
Scott #9:
I was wondering how to demonstrate speedups for QML
As we mostly evaluate ML algorithms (accuracy, complexity, …) by empirical evidence, the way I see we can show a QML algorithm has some speedup (over classical ones) is the following:
– take an ML competition (lets say the imagenet challenge for example)
– show that your quantum algorithm is as good as the classical ones
– but that it needs less steps/space to get to the same results
After all this is how (classical) ML algorithms compare to one another, no ?
Do you see other ways to do so ?
Comment #78 January 13th, 2020 at 8:55 pm
Meanwhile, if QC becomes real and practical, will the P vs NP problem become less interesting? Like the continuum hypothesis, #1 of Hilbert’s 23 problems in 1900, but I suspect by the 1950s (well before it was proven independent), I think its perceived importance had decreased quite a lot.
Comment #79 January 14th, 2020 at 4:13 am
MIP*=RE https://arxiv.org/abs/2001.04383 !
Comment #80 January 20th, 2020 at 11:48 am
[…] we would now say bingo. But writing “proved” sets a higher standard. To judge from this and this, it appears the Google-led team is upping their qubit count from 53 to 57 in order to […]