https://www.scottaaronson.com/blog/?p=5460 Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. Also, next pandemic, let's approve the vaccines faster! --------------------------------------------------------------------- << The ACM Prize thing Doubts about teapot supremacy: my reply to Richard Borcherds Richard Borcherds is a British mathematician at Berkeley, who won the 1998 Fields Medal for the proof of the monstrous moonshine conjecture among many other contributions. A couple months ago, Borcherds posted on YouTube a self-described "rant" about quantum computing, which was recently making the rounds on Facebook and which I found highly entertaining. Borcherds points out that the term "quantum supremacy" means only that quantum computers can outperform existing classical computers on some benchmark, which can be chosen to show maximum advantage for the quantum computer. He allows that BosonSampling could have some value, for example in calibrating quantum computers or in comparing one quantum computer to another, but he decries the popular conflation of quantum supremacy with the actual construction of a scalable quantum computer able (for example) to run Shor's algorithm to break RSA. Borcherds also proposes a "teapot test," according to which any claim about quantum computers can be dismissed if an analogous claim would hold for a teapot (which he brandishes for the camera). For example, there are many claims to solve practical optimization and machine learning problems by "quantum/classical hybrid algorithms," wherein a classical computer does most of the work but a quantum computer is somehow involved. Borcherds points out that, at least as things stand in early 2021, in most or all such cases, the classical computer could've probably done as well entirely on its own. So then if you put a teapot on top of your classical computer while it ran, you could equally say you used a "classical/teapot hybrid approach." Needless to say, Borcherds is correct about all of this. I've made similar points on this blog for 15 years, although less Britishly. I'm delighted to have such serious new firepower on the scoffing-at-QC-hype team. I do, however, have one substantive disagreement. At one point, Borcherds argues that sampling-based quantum supremacy itself fails his teapot test. For consider the computational problem of predicting how many pieces a teapot will break into if it's dropped on the ground. Clearly, he says, the teapot itself will outperform any simulation running on any existing classical computer at that task, and will therefore achieve "teapot supremacy." But who cares?? I'm glad that Borcherds has set out, rather crisply, an objection that's been put to me many times over the past decade. The response is simple: I don't believe the teapot really does achieve teapot supremacy on the stated task! At the least, I'd need to be shown why. You can't just assert it without serious argument. If we want to mirror the existing quantum supremacy experiments, then the teapot computational problem, properly formulated, should be: given as input a description of a teapot's construction, the height from which it's dropped, etc., output a sample from the probability distribution over the number of shards that the teapot will break into when it hits the floor. If so, though, then clearly a classical computer can easily sample from the same distribution! Why? Because presumably we agree that there's a negligible probability of more than (say) 1000 shards. So the distribution is characterized by a list of at most 1000 probabilities, which can be estimated empirically (at the cost of a small warehouse of smashed teapots) and thereafter used to generate samples. In the plausible event that the distribution is (say) a Gaussian, it's even easier: just estimate the mean and variance. A couple days ago, I was curious what the distribution looked like, so I decided to order some teapots from Amazon and check. Unfortunately, real porcelain teapots are expensive, and it seemed vaguely horrific to order dozens (as would be needed to get reasonable data) for the sole purpose of smashing them on my driveway. So I hit on what seemed like a perfect solution: I ordered toy teapots, which were much smaller and cheaper. Alas, when my toy "porcelain" teapots arrived yesterday, they turned out (unsurprisingly in retrospect for a children's toy) to be some sort of plastic or composite material, meaning that they didn't break unless one propelled them downward forcefully. So, while I can report that they tended to break into one or two large pieces along with two or three smaller shards, I found it impossible to get better data. (There's a reason why I became a theoretical computer scientist...) [teapot] The good news is that my 4-year-old son had an absolute blast smashing toy teapots with me on our driveway, while my 8-year-old daughter was thrilled to take the remaining, unbroken teapots for her dollhouse. I apologize if this fails to defy gender stereotypes. Anyway, it might be retorted that it's not good enough to sample from a probability distribution: what's wanted, rather, is to calculate how many pieces this specific teapot will break into, given all the microscopic details of it and its environment. Aha, this brings us to a crucial conceptual point: in order for something to count as an "input" to a computer, you need to be able to set it freely. Certainly, at the least, you need to be able to measure and record the input in its entirety, so that someone trying to reproduce your computation on a standard silicon computer would know exactly which computation to do. You don't get to claim computational supremacy based on a problem with secret inputs: that's like failing someone on a math test without having fully told them the problems. Ability to set and know the inputs is the key property that's satisfied by Google's quantum supremacy experiment, and to a lesser extent by the USTC BosonSampling experiment, but that's not satisfied at all by the "smash a teapot on the floor" experiment. Or perhaps it's better to say: influences on a computation that vary uncontrollably and chaotically, like gusts of air hitting the teapot as it falls to the floor, shouldn't be called "inputs" at all; they're simply noise sources. And what one does with noise sources is to try to estimate their distribution and average over them--but in that case, as I said, there's no teapot supremacy. A Facebook friend said to me: that's well and good, but surely we could change Borcherds's teapot experiment to address this worry? For example: add a computer-controlled lathe (or even a 3D printer), with which you can build a teapot in an arbitrary shape of your choice. Then consider the problem of sampling from the probability distribution over how many pieces that teapot will smash into, when it's dropped from some standard height onto some standard surface. I replied that this is indeed more interesting--in fact, it already seems more like what engineers do in practice (still, sometimes!) when building wind tunnels, than like a silly reductio ad absurdum of quantum supremacy experiments. On the other hand, if you believe the Extended Church-Turing Thesis, then as long as your analog computer is governed by classical physics, it's presumably inherently limited to an Avogadro's number type speedup over a standard digital computer, whereas with a quantum computer, you're limited only by the exponential dimensionality of Hilbert space, which seems more interesting. Or maybe I'm wrong--in which case, I look forward to the first practical demonstration of teapot supremacy! Just like with quantum supremacy, though, it's not enough to assert it; you need to ... put the tea where your mouth is. Update: On the suggestion of Ernest Davis, who I can now reveal as the Facebook friend mentioned above, I just ordered some terra cotta flower pots, which look cheap, easily smashable, and environmentally friendly, and which will hopefully be acceptable substitutes for porcelain teapots in a new experiment. (Not that my main arguments in this post hinge on the results of such an experiment! That's the power of theory.) Another Update: Some of you might enjoy John Horgan's Scientific American column on reality vs. hype in quantum computing, based on conversations with me and with Terry Rudolph of PsiQuantum. This entry was posted on Tuesday, April 20th, 2021 at 1:55 pm and is filed under Complexity, Quantum. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. 72 Responses to "Doubts about teapot supremacy: my reply to Richard Borcherds" 1. Ted Says: Comment #1 April 20th, 2021 at 2:28 pm A remarkably similar discussion took place on Physics Stack Exchange, regarding a falling cup of pudding rather than a teapot: https://physics.stackexchange.com/questions/511067/ why-is-googles-quantum-supremacy-experiment-impressive. It seems to me that the two top answers both capture different aspects of your argument in this post. 2. dankane Says: Comment #2 April 20th, 2021 at 2:38 pm But if we're talking about supremacy experiments (which don't require having an asymptotic improvement), then having an Avagadro's number-sized speedup may well be enough. 3. Eric Says: Comment #3 April 20th, 2021 at 2:38 pm As a side-note to all this, it's been really wonderful having Borcherds (and many others!) post so many freely-available lectures online, in part incentivised by COVID. 4. Dana Says: Comment #4 April 20th, 2021 at 2:40 pm Speaking of gender stereotypes: Our 4 year old son was indeed happy to (try to) smash teapots with his father (I tried too), while our 8 year old daughter was busy watching some new movie on Netflix, but when our son heard that our daughter took a set for her dolls, he immediately insisted that he should have a set for his dolls too! 5. Boaz Barak Says: Comment #5 April 20th, 2021 at 2:40 pm I agree. The interesting thing about the quantum sampling experiments is not that you cannot simulate them classically, but rather that you CAN simulate them at an exponentially growing cost. This shows that this is not about difficulty of cloning a physical object, such as a wax seal or ink stain, but rather about simulating a controlled and replicable experiment. Note that if you could really manufacture identical teapots with unpredictable randomness, you could use that for crypto. For example, maybe we would share two sets of teapots, and break them to generate some shared randomness. Let's just say that if I was a VC, a "teapot crypto startup" would not be high on my list of companies to invest in.. 6. dankane Says: Comment #6 April 20th, 2021 at 2:46 pm In terms of computational problems most easily solved by direct experimentation though, might I propose the protein folding problem as an example. 7. Boaz Barak Says: Comment #7 April 20th, 2021 at 2:48 pm P.s. As I wrote on Twitter, I also disagree with Borcherds's description of problems such as simulating quantum systems and traffic optimization as "useless". Indeed, they may well be more useful than integer factoring! 8. Scott Says: Comment #8 April 20th, 2021 at 2:59 pm dankane #2: But if we're talking about supremacy experiments (which don't require having an asymptotic improvement), then having an Avagadro's number-sized speedup may well be enough. Yes, if you had an Avogadro's-number-sized speedup that was actually for real, that would certainly be of interest! I confess that for me, though, a quantum speedup (even if not yet scalable) is of greater interest--precisely because it hints at an asymptotic speedup, and seems difficult to explain if such a speedup isn't possible (a point that, notably, even Gil Kalai agrees about). 9. Jon Awbrey Says: Comment #9 April 20th, 2021 at 3:02 pm In the multitude of arguments I've had over the years concerning various forms of pseudo-reductionism I have called this the Stone Soup Fallacy, after the old French fable. The fallacy of the "Alchemist's Dodge" or the "(Philosophers') Stone Soup". It goes a bit like this: You can make a hearty soup out of nothing but stones and hot water ... if you add a pinch of salt ... if you add a dash of pepper ... if you add a few potatoes ... if you add a carrot or two ... if you add a hock of ham ... if you add ... And so it goes. The moral of this particular telling of the story is that a reduction is not a proper reduction if it does not reduce something to something lower. 10. Steve E Says: Comment #10 April 20th, 2021 at 3:15 pm This is an excellent blog post, but it would be even better if you bought and then smashed $250,000 worth of teapots. 11. Craig Gidney Says: Comment #11 April 20th, 2021 at 3:45 pm I've been calling your objection the *encodability requirement*. You want the problem to be specified as data. You want to be able to write the problem down. For reasons perhaps best exemplified by how SI definitions have changed over time, individual physical objects are not ideal for defining this sort of thing. Encodability is perhaps not strictly necessary. The real underlying property you want to guarantee is that two competing systems are instantiating the same problem, and their accuracy is being measured against the same standard. But encodability sure is convenient for achieving that! As you note, an encodable version of the teapot problem would be to have a parameterized physics model of a teapot, and to ask *according to the model* how many pieces the modelled teapot will break into. Crucially, this means differences between the teapot and the model are now errors in the teapot instead of errors in the model. Having made this conceptual change, the question becomes whether or not you can find a model with enough detail to be difficult to solve for a computer and to accurately match the behavior of the real teapot, but not so much detail that you can't initializes its parameters by scanning a teapot or 3d print a teapot matching specified parameters. I suspect the answer is that you can't find a model meeting both criteria. If someone found such a model, demonstrated that teapot experiments agreed with the model on the cases they can actually run, and that the model became intractable to solve in some regime where teapots were still constructible and we had reason to think they were still matching the model, I would admit they demonstrated beyond-classical teapot computational powers. 12. Anon Says: Comment #12 April 20th, 2021 at 4:08 pm I would add that "specifying the input" is also important for gauging purely algorithmic advances - cf. Ewin Tang's dequantization of recommendation. Unlike shards of the teapot, this requirement can't be swept under the rug. 13. Radford Neal Says: Comment #13 April 20th, 2021 at 4:25 pm From my (not very deep) perusal of the Google "quantum supremacy" claim, it seemed to me that it had the problem that it's not reproducible. Suppose that, rather incredibly, I actually want to solve the exact problem that their quantum computer solved (despite it apparently being a useless curiosity). I phone them up, say "I want to order ten of those quantum computers! We need one for each of our factories. When can you deliver?". The answer, as I understand it, is "never". The exact parameters of the problem are specific to their particular hardware. (Amazing, isn't it, they their hardware just happened deliver parameters that are the ones our factories need!) Unfortunately, if they construct a new quantum computer of the same design, it will only work for the problem with different parameters, determined by the exact properties of that particular physical computer. It will be of no use in our factories. At least that's my not-very-informed reading. Maybe those who know more can say whether their computer is actually reproducible. 14. Vincent Says: Comment #14 April 20th, 2021 at 4:52 pm Maybe I'm missing something, but the 'classical computer' you use to get a sample from the teapot distribution seems like the perfect example of a classical computer/teapot-hybrid. Not the kind that Borcherds is talking about, but rather the opposite kind, where the teapots do all the real work and the classical computer is just sitting there to make things look fancy and modern. I mean what was the computer gonna do if the small warehouse of teapots hadn't provided it with the distribution first? So as it stands it seems to me that instead of explaining why the proposed teapot supremacy experiment does not show that the teapot is superior to a classical computer you merely explained why the proposed teapot supremacy experiment does not show that the teapot is superior to a teapot-computer hybrid. But that is not very surprising. Nobody would expect a teapot to be superior to a clever teapot-computer-hybrid, much like noone would expect a quantum computer to outperform a quantum/ classical-hybrid or a classical computer to outperform a computer-human hybrid etc. I guess I misinterpret the argument, but how? 15. DR Says: Comment #15 April 20th, 2021 at 5:13 pm What fun! I predict this will be one the kids' long lasting memories of childhood :). Good thing they have this blog post to use, to explain the context to their grand kids :). Now I better read this essay again to understand that better myself! 16. Scott Says: Comment #16 April 20th, 2021 at 5:21 pm Vincent #14: In Sipser's computability theory textbook, there's a wonderful problem that goes like-- Let f:N-N be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? The solution is yes, f is computable, and it doesn't depend at all on your beliefs about God. The proof is that every constant function f is computable. I.e., whatever effort it takes to determine whether God exists or not, that's "precomputation" and is utterly irrelevant to the question of computability. Either answer, once found, could simply be "hardwired" into your program. (But of course, not all functions are computable! E.g., the halting problem isn't!) If you understand that, then you should also understand the point I made in this post. Whatever smashing of teapots it takes to determine the probabilities to put into your program, that's precomputation, which is utterly irrelevant to the question of the computational complexity of generating samples from the distribution considered as a distribution. The latter question is settled by the distribution having small support. (But not all fixed probability distributions over n-bit strings are efficiently samplable by a classical computer! BosonSampling distributions probably aren't!) 17. Scott Says: Comment #17 April 20th, 2021 at 5:26 pm Craig Gidney #11: That was beautifully put! Except that for me, encodability is not just a practical convenience, but more like a prerequisite to considering a problem a properly computational problem at all, as opposed to any of the other kinds of problems you might encounter in life (e.g., the data you need being behind lock and key, protected by armed goons, etc.) 18. Joshua Zelinsky Says: Comment #18 April 20th, 2021 at 5:49 pm If your recent prize money is supposed to encourage further research, then that's an argument for using some of it to buy some of the actual porcelain teapots and smash them. (Please do not actually do this.) 19. Scott Says: Comment #19 April 20th, 2021 at 6:08 pm Radford Neal #13: I believe they've gotten substantially better at calibration just within the last year or two, and could now reliably produce multiple chips with the exact same gates. But I'll ask Sergio Boixo to clarify. 20. Nick Says: Comment #20 April 20th, 2021 at 6:41 pm Scott #16 > Let f:N-N be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? > The solution is yes, f is computable, and it doesn't depend at all on your beliefs about God. The proof is that every constant function f is computable. That problem doesn't depend on your beliefs about God, but it does depend on your having some belief about God. In particular, it requires that you believe either that God exists or not. If you don't believe either of those things, then f is not defined and the question is ill-posed. The definition of f depends on a particular instance of the law of excluded middle, and not a trivial one. Maybe you think it's obvious that everything either exists or not, but once you head down that road it's not long before you wind up in "perfect beings exist necessarily" cuckoo-land. (I don't know whether this affects your analogy.) 21. Scott Says: Comment #21 April 20th, 2021 at 6:51 pm Nick #20: Fine, then let's say that f is "computable to whatever extent it's well-defined." There isn't any sense in which it's uncomputable. Likewise, in my analogy, the probability distribution over number of teapot shards is efficiently samplable to whatever extent it's well-defined. And this is fundamentally different from the distributions we see in quantum supremacy experiments, which are well-defined but not (we don't think) efficiently samplable. 22. RX Says: Comment #22 April 20th, 2021 at 7:12 pm Speaking of QC hype, I really wish you would call out Xanadu as much as you called out d-wave back in the day. They emply very smart people, but their claims are outrageous, and it this case they are using something you invented to raise millions based on lies. As someone who lives in Canada, it's sad to see them raising money from the government and from Canadian VCs. 23. Sergio Boixo Says: Comment #23 April 20th, 2021 at 7:57 pm Radford Neal #13: Please note that we have published multiple experiments with standard quantum gates on Sycamore chips, such as arXiv:2101.08870 and arXiv:2102.06132. Perhaps your objection is that in the main text we used "arbitrary unitaries", with parameters measured in calibration before the experiment, and slightly different for every pair of qubits. Using "Sycamore unitaries" with standard parameters, the same for every pair of qubits, would have lowered the fidelity by a factor of 1/2 (see Fig. S30 in the supplement arXiv:1910.11333). This is OK. 24. James Gallagher Says: Comment #24 April 20th, 2021 at 8:16 pm But I can drop a randomly constructed teapot made of 53 atoms in a vacuum and have the system mathematically well defined. That's just what Google did. 25. Scott Says: Comment #25 April 20th, 2021 at 8:20 pm James Gallagher #24: It's not what they did--superconducting qubits are made of the states of billions of electrons, they're not in vacuum, and it's only the list of operations applied to the qubits that's randomly constructed--but OK! 26. James Gallagher Says: Comment #26 April 20th, 2021 at 8:36 pm Scott #25 Well you argued that the macroscopic teapot falling in air was too complicated to mathematically define, which is a bit unfair when Google only demonstrated a 53 qubit system Also the fact the qubits are not in vacuum is not relevant, they aren't falling through the air. Anyway, just a bit of fun, I enjoyed the post, and hadn't heard of these arguments and discussions. I'm impressed you ordered a load of cheap crap on Amazon and then smashed it all up - right on bruv!!! 27. Radford Neal Says: Comment #27 April 20th, 2021 at 8:53 pm Sergio Boixo #23: Thanks for the explanation! It's good to know that things work well enough that one can have a system with reproducible properties. 28. ghost learner Says: Comment #28 April 20th, 2021 at 10:27 pm Scott #0, So clear that it makes you feel like you always knew it. Thanks! But, wait, couldn't you apply this line to the Church-Turing-Deutsch principle as well as the terra cotta flower pots? Like, even if this principle was morally true, *any physical process* has no input then it's not computable. Or is *any* the input? 29. Scott Says: Comment #29 April 20th, 2021 at 10:47 pm ghost learner #28: Sorry, I don't understand your question. 30. Dmitri Says: Comment #30 April 20th, 2021 at 10:54 pm To try to rescue Vincent #14's point: if the problem is changed from "sample the number of shards for the teapot", then you can make the smashing experiment be part of precomputation. But if the problem is "sample the number of shards for this ceramic object X", where X is an input, then the smashing experiment becomes a subroutine rather than precomputation. In that case it seems like a ceramic-object-classical-computer hybrid has an advantage over just the classical computer (at least if you accept that the smashing experiment is really necessary, and that you couldn't do as well by some computation without it). 31. Arul Says: Comment #31 April 20th, 2021 at 11:00 pm I am not certain if the video was worth commenting by a computer scientist since it is unlikely Borcherds knows half as much as Professor Aaronson. I think the analogy is a bit misleading. It would be as much as Professor Scott Aaronson shines light on the moon. T={ teapots on the condition when dropped from a height of 1m at a particular room in Berkeley on a particular data and time shatters into 1000 pieces}. The correct question should be if the teapot in hand and in kitchen are both in T. I think teapot can answer for only its own membership. However when we define a limited model of quantum computation and constructivize it in the lab it answers for membership for a particular Language (however narrow the definition of the language may be the quantum computer can realize membership for potentially infinite members in the language depending on the model scalability and definition). As Professor Barak puts it nicely "The interesting thing about the quantum sampling experiments is not that you cannot simulate them classically, but rather that you CAN simulate them at an exponentially growing cost.". 32. Job Says: Comment #32 April 21st, 2021 at 12:39 am I think something like an optical device is a better analogy for the supremacy experiment (though the teapot is fine for traffic optimization, etc). The claim would be that a "quantum optical device" can see things at a much higher resolution than a classical (i.e. lesser-quantum) device. That seems inherently true, and definitely biased towards quantum devices, but it would still be a test of one of the device's most useful applications. You might end up with the teapot scenario if the optical device can only be pointed at a very specific scene (i.e. not sufficiently programmable), or requires such deliberate calibration that it misrepresents the device's actual capabilities. But that's a problem with the experiment, not the test. As a curiosity, in the Sycamore experiment, the "optical device" would be sampling individual pixels from an image large enough to require a few thousand laptop screens in width and height (IIRC). That's its own problem, once you zoom in that much it really dilutes the results. And then the discussion shifts to whether a non-optical classical device can fool the "human eye" at that zoom level. 33. Scott Says: Comment #33 April 21st, 2021 at 2:31 am Dmitri #30: Yes, see the paragraph in the original post beginning "A Facebook friend said to me..." 34. DavidM Says: Comment #34 April 21st, 2021 at 5:42 am >then as long as your analog computer is governed by classical physics, it's presumably inherently limited to an Avogadro's number type speedup over a standard digital computer, whereas with a quantum computer, you're limited only by the exponential dimensionality of Hilbert space Apologies if this is dumb, but I was under the impression that if we think of an `asymptotic version' of the Google experiment, for large sizes the noise comes to dominate and so the output is easy to simulate (just simulate the noise). Is this incorrect? Otherwise it seems like the Sycamore experiment is basically also a constant-factor speedup (albeit with an astronomical constant, depending on physical gate fidelity). (I agree with the point that the teapot problem is not mathematically well-posed - has anyone tried to come up with a family of initial conditions for the Navier-Stokes equations that are hard to simulate?) 35. Scott Says: Comment #35 April 21st, 2021 at 8:09 am DavidM #34: You might describe a speedup from a NISQ device as a "constant-factor speedup on the shores of an exponential speedup." I.e., a constant-factor speedup that was possible only because of the asymptotic exponentiality of Hilbert space, an exponentiality that we hope to exploit just as soon as we're past the fault-tolerance threshold. Whereas an Avogadro's-number speedup from a classical analog system, even assuming it's for real, is ... not really on the shores of anything else. It's up against the wall of Avogadro's number. 36. fred Says: Comment #36 April 21st, 2021 at 8:31 am I made the very same argument using "dog turds" instead of "teapots" on this very blog a couple years ago, and Scott quickly dismissed it in a few words. I'm glad this has now been properly addressed... 37. fred Says: Comment #37 April 21st, 2021 at 8:50 am As a curiosity, there has been tremendous progress in recent years in the classical simulation of physics: 38. LK2 Says: Comment #38 April 21st, 2021 at 8:56 am To me, this "rant" is exactly...a rant! A rant from a person (besides the inaccuracies he might have said) who had enough from all the hype about QC. A bit of topic, Scott: the threshold theorem says that if the error per gate is a small enough constant, then QC is scalable (with error correction). Has anybody treated a case where the error per gate is not constant increasing as a function of the number of gates? Depending on the exact physical implementation of the gates in a QC, this might be possible. This requires some physics instead of TCS I guess. 39. Scott Says: Comment #39 April 21st, 2021 at 9:03 am LK2 #38: Well, what's the limit of the error rate as the number of gates goes to infinity? If it's less than the fault-tolerance threshold, then fault-tolerance is still possible; if not, then not. That didn't require any physics, just logic. 40. Scott Says: Comment #40 April 21st, 2021 at 9:39 am Incidentally, Ted #1: Thanks so much for that link (which I just had a chance to read this morning)! The answers there do indeed render most of this post superfluous. I especially liked that, rather than quibble over semantics (the exact definition of "quantum supremacy," etc etc) as so many like to do with this topic, the questioner just zeroed in immediately on what's really at issue here: namely, why was Google's experiment impressive? And then got direct and accurate answers to that question. 41. LK2 Says: Comment #41 April 21st, 2021 at 10:28 am Scott #39: the logic you outline is obvious, but my question remains and I believe it is tied to how physically the qbits/ gates are realised. I was just wondering if there any studies suggesting that the error rate for a qbit (or gate) grows with the number of qubits (gates) in the QC. Of course I agree with you that if this growth does not surpass the threshold everything is fine but I still think that TCS cannot really answer this. 42. domotorp Says: Comment #42 April 21st, 2021 at 10:43 am Something bothers me about your arguments against teapot supremacy. Take the following different example. I claim myRSA supremacy. Whatever pubkey(x) you give me, I can fast compute x= privkey(pubkey(x)), but no one else can. This is a useless supremacy, because I cannot do anything else. Also, in this case, of course we know that there is a classical algorithm that does the job, but why couldn't BosonSampling be the same? I know that even BQP=P is possible as well, but what I'm saying is that at the moment I don't see why Boson Sampling is any better than myRSA. 43. Scott Says: Comment #43 April 21st, 2021 at 10:45 am LK2 #41: Yes, of course, whether you can build a large system where the qubits remain below the fault-tolerance threshold is ultimately a question for engineering (if you're an optimist) or physics (if you're a pessimist) , but in any case one where TCS plays only a side role. And yes, experimentalists have found that as you scale to larger numbers of qubits, you get more cross-talk between the qubits, and other issues that tend to push the error rate higher. That's why some people worried that even a quantum supremacy experiment, of the sort Google did two years ago, wouldn't be achievable, but of course it ultimately was. The view of most of us is that cross-talk between qubits and so forth are all "temporary" problems (where "temporary," alas, could mean decades in this context)--you just need to get over this finite-sized hump to where fault-tolerance starts working, and then you get a massive wind pushing you in the opposite direction, as more qubits and gates let you implement better error-correcting codes and thereby push the effective error rate lower rather than higher. Gil Kalai, of course, takes the opposite view, that the "finite-sized hump" is actually an infinite mountain that can never be scaled even in principle. Aren't you interested to find out who's right? 44. LK2 Says: Comment #44 April 21st, 2021 at 10:54 am Scott #42: thanks for the clear answer! Of course I'm interested in finding what will happen with all this. I'm absolutely not skeptical about QC (otherwise I would be skeptical about QM, and I am not) but the physical implementation of a QC is a really exciting challenge. I admit that I am slightly (only slightly) edging towards Gil's side, but I would be VERY happy if the thing will work! Thanks again. 45. Scott Says: Comment #45 April 21st, 2021 at 10:56 am domotorp #42: Once again, "myRSA supremacy" depends on secret information, known only to you. Quantum supremacy doesn't. The classical computer gets exactly the same information as the quantum computer about which distribution to sample from; it just can't sample as quickly. That's the difference. 46. domotorp Says: Comment #46 April 21st, 2021 at 11:09 am Scott #44: I don't think it is a secret information, anyone can compute privkey from pubkey (in exponential time). To give another example, whenever someone discovers a new algorithm for any specific task, that person has supremacy over the whole world in that task until they share their method, don't they? 47. domotorp Says: Comment #47 April 21st, 2021 at 11:26 am More generally, I think that any function might be a trapdoor function until it is proved to be complete for some complexity class. Even NP might have a trapdoor (a poly alg), just the more problems we reduce to something, the less likely it is, I suppose, that it has a trapdoor. But until more things are reduced to BosonSampling, the only evidence we have against it not having a trapdoor, is our intuition and physical experience. 48. David Says: Comment #48 April 21st, 2021 at 11:29 am How exactly do qubits scale in performance? The pop-sci answer is that n qubits have the power of 2^n classical bits, but digging around suggests that that's incorrect, and refers only to the number of states that can be represented. I found some of Scott's writing that suggests that there isn't a global performance increase at all, only the ability to use faster quantum algorithms for certain tasks. Unfortunately, having spent quite a bit of time Googling, I wasn't able to find anything definitive, though it sounds like there may be a speedup somewhat akin to 2^n on highly parallel tasks, and less of one/none at all on purely serial ones. In particular, how do qubits scale for artificial neural nets? To the best of my knowledge there's been very little work in that area so far, but if one could use near-future qc systems to get an exponential speedup in (highly parallel) neural nets, that would be fascinating. 49. Scott Says: Comment #49 April 21st, 2021 at 12:32 pm domotorp #46: Alright, if you want to call being able to invert a trapdoor function "private-key supremacy," I'm not going to argue. But it's "supremacy" based on having explicitly generated and therefore not needing to compute some particular private key, rather than based on having physically engineered a new type of computer. You and I both know that this is semantics of the most fruitless and boring kind, akin to arguing that the Wright brothers weren't the first to achieve powered flight because someone before them threw a motor, or attached a small cargo to a pigeon. 50. Scott Says: Comment #50 April 21st, 2021 at 12:43 pm David #48: n qubits are a fundamentally new kind of resource--one that for almost all purposes, is at least as powerful as n classical bits and at most as powerful as ~2^n classical bits. As for where it falls between those two extremes--well, that's the subject matter of this entire field! I think the trouble is just that you were looking for the sort of answer that would fit into a blog comment, when an honest answer, even just covering what we already know, is the size of a textbook or a semester-long course. (Exactly like if you'd asked the question, "what sorts of problems have efficient classical algorithms?") Yes, problems that admit large quantum speedups (especially exponential speedups) are extremely special in nature. Yes, those problems need to be parallelizable, but that's only a necessary condition, not a sufficient one. For example, computing the parity of n-bit string is extremely parallelizable, but it admits no asymptotic quantum speedup (only a speedup by a constant factor of 2). If you want to learn more, my Scientific American article and undergrad lecture notes (feel free to skip around) are two possible places to start. 51. fred Says: Comment #51 April 21st, 2021 at 1:49 pm Scott #43 "Aren't you interested to find out who's right?" Do you think that overcoming that finite-size hump for scalable QC could end up requiring a collaborative effort like the LHC (9B$ budget), the ITER project for nuclear fusion (50B$), or the ISS(100B$)? Or do you think that this will be achieved by private companies, as different instances of proprietary tech? (it's usually the case for computing tech) 52. Des Smith Says: Comment #52 April 21st, 2021 at 2:54 pm I am very glad that the comment of Ted #1 was highlighted. I think the comment illuminates an interesting part of the sociology science, which is that a high profile individual gets attention for making an observation previously made by others who are less well known (or even annonymous, as is the case in this situation). No-one is a villain here. Richard Borcherds may well have come up with his teapot observation independently, or had subconciously absorbed the Stack Exchange conversation and forgotten about it in his concious mind. And it is only human nature to give preferential attention to prominent members of the hierarchy. But the commonplace nature of the event somehow makes me feel sad. 53. Raoul Ohio Says: Comment #53 April 21st, 2021 at 3:09 pm LK2 #44: Disagree on the logic. I, for example, am much more skeptical about QC than QM. While QM certainly has some mysteries and conceivably will be superseded by a deeper theory, there is zero doubt that useful calculations can be done, and in fact are all the time. QC is another matter, and it is debatable if any useful calculation has been done. 54. asdf Says: Comment #54 April 21st, 2021 at 3:15 pm I look forward to your joint paper with Noah about smashing the flower pots. 55. DavidM Says: Comment #55 April 21st, 2021 at 3:22 pm David #48, Scott #50: I will impertinently remark that of course we have a slightly stronger* upper bound of ~n classical bits and ~2^n time David #48: If you want a one-sentence summary, roughly speaking for general `unstructured' parallelisable problems you get a speedup of sqrt(T); for an exponential speedup you want your problem to have something to do with finding the period of a function (e.g. for factoring, the function x|->a^x mod N=pq has period which divides (p-1)(q-1)). [of course this is all so far as we know] *(maybe) 56. TonyK Says: Comment #56 April 21st, 2021 at 3:28 pm I have a tenuous personal link with Richard Borcherds, being one of the people he beat in the 1977 British Mathematical Olympiad. I came third, and he came joint first. But in fact he really came first, because after waltzing through all six problems, he had time to improve on one of them. You had to prove that given a certain number of points inside a cube, there must exist points closer than a certain distance. It wasn't the most difficult of the questions. But Richard proved, using his tiny-cubes, in his spare time so to speak, that this distance could be reduced from 13 to 10 (IIRC). After this came out in the post-mortem, I was in awe of him. Richard, if you're reading this: you have a fan! So I kind of followed his career, on a once-every-few-years basis, and was immensely gratified when he got his Fields Medal: hey, I can stand losing to that! And I was delighted by your "less Britishly". The video proves that he is as British as the day he was born! But your tale of failing to smash the toy teapots is what really made my day. 57. DavidM Says: Comment #57 April 21st, 2021 at 3:36 pm Scott #35: Right, though I guess the `skeptic' position is that nature abhors quantum error-correction and so when you try it the almighty will smite you down, or line up the errors against you, or something, so maybe they would say there's still a wall but it's invisible for now... Which makes me wonder: is there a way to make precise the property that a particular quantum circuit doesn't do error correction? In particular might we dare to dream of a theorem that the behaviour (with constant gate fidelity) of any non-error-correcting circuit can be simulated in polynomial time? 58. Scott Says: Comment #58 April 21st, 2021 at 3:38 pm TonyK #56: Great story! 59. Scott Says: Comment #59 April 21st, 2021 at 3:41 pm asdf #54: Noah? Do you mean Daniel (my 4-year-old)? I'll see if he wants to coauthor... 60. Scott Says: Comment #60 April 21st, 2021 at 3:49 pm Des Smith #52: To complete the picture, I've had nearly-isomorphic conversations many times over the last decade, on this blog and elsewhere, preceding that Physics StackExchange thread as well (though I found the answers there unusually crisp). With the Borcherds video, though, what prompted me to write this post was not merely that Borcherds is justly distinguished, but also that (1) he was exceedingly clear in the video--which made it easy to pinpoint my disagreement, (2) the video kept showing up in my Facebook feed, and (3) the video was entertaining. 61. bertgoz Says: Comment #61 April 21st, 2021 at 4:28 pm There is a point that it is still not clear to me. One of the arguments against the teapot experiment is that it is not mathematically well defined while the (say) Sycamore experiment is. However, that swept under the rug how hard was to mathematically define the Sycamore experiment in the first place. You may have had to individually measure and calibrate to the point of operation each individual gate in order to make your problem well defined. Similarly if you were building your teapot in an advanced fabrication facility you can take long time fabricating and measuring the individual "chunks" of the teapot down to the atomic level. That way you would have had a well defined "mathematical" model of the teapot to start with. 62. Scott Says: Comment #62 April 21st, 2021 at 5:04 pm bertgoz #61: The way this point was explained on Physics StackExchange was so clear that I'll just quote it: The big difference between the quantum supremacy experiment and your pudding experiment is that the quantum supremacy experiment solved an unambiguous, well-posed mathematical problem. While people sometimes describe the computational task as "simulating the physical Sycamore computer", that's not right. The actual task was calculating the output of an abstract quantum logical circuit, of which the Sycamore computer was an approximate physical instantiation. The difference is subtle but crucial. From a computational perspective, the math came first and the physics came second. Crucially, the quantum supremacy problem was mathematically well-specified, and so it could be checked on a classical computer. The parallel classical computation wasn't just there to provide a time benchmark, but also - crucially - to check the quantum computation for accuracy. There's no such "slower but equivalent" computation to the pudding experiment... 63. Scott Says: Comment #63 April 21st, 2021 at 5:11 pm DavidM #57: Which makes me wonder: is there a way to make precise the property that a particular quantum circuit doesn't do error correction? In particular might we dare to dream of a theorem that the behaviour (with constant gate fidelity) of any non-error-correcting circuit can be simulated in polynomial time? Oh man, you have no idea how many times that exact question has come up. There are results that do parts of what you're asking for--especially the 2018 work of Gao and Duan, which shows (roughly speaking) that a random noisy quantum circuit can be efficiently simulated classically in the asymptotic regime. (See also the related, much earlier work of Aharonov and Ben-Or.) But no, I don't know of any general way to formalize the concept of "not doing error-correction," and I'm skeptical that that's possible--since once you have a universal quantum computer with intermediate measurements, error-correction is simply one of the things you can do with it! 64. bertgoz Says: Comment #64 April 21st, 2021 at 5:12 pm Scott #62, sorry Scott but I might be quite obtuse but I still don't get it. If I have built beforehand an atomistic model of the teapot and I capture to a high enough degree of precision the conditions of the experiments (height, wind, etc), what's preventing me to then run the experiment in a supercomputer? In which I will have to painfully calculate the (quantum?) interactions of all the atoms as the teapot smashed the floor 65. Scott Says: Comment #65 April 21st, 2021 at 5:55 pm bertgoz #64: Because you don't, in fact, have such an atomistic model of a teapot. And even if you did, an actual teapot wouldn't conform to the model, because of machining errors and so forth, and therefore it wouldn't help you in deterministically predicting the chaotic behavior of the atomistic model. At most, the actual teapot could tell you in general what teapots like that one (but not atomistically identical) tend to do when smashed. But a simulation running on a classical computer could've told you the same! And that's why you almost certainly don't have teapot supremacy. By contrast, there's an ideal mathematical model of a 53-qubit, ~1000-gate quantum circuit, and Google's Sycamore chip managed to produce samples consistent with that model (though if you changed even a single one of the 1000 gates, you no longer had consistency). This is no longer a hypothesis or a supposition but a demonstrated fact. And as far as we know, spoofing the samples with a classical computer would take much longer and/or require a large number of cores. In both cases, the teapot and the Sycamore chip, you don't start with a physical system and then challenge people to simulate it. Instead, you start with a mathematically well-defined problem and then challenge various physical systems--classical computers, quantum computers, teapots--to solve the problem. A failure is not a failure of the mathematical problem to capture all aspects of the physical system, but the exact opposite: a failure of the physical system to capture the problem. I've explained the above point over and over and over and over for the past decade, but it hardly ever seems to get through. Now might be a good time for someone else to take a stab at it! 66. Tommaso Says: Comment #66 April 22nd, 2021 at 4:28 am Hi Scott, you beat me in time on this I had written a rebuttal of the teapot experiment for our internal discussion group at work but you did it first: http://www.gagliardoni.net/# quantum_teapot_apr_2021 67. asdf Says: Comment #67 April 22nd, 2021 at 5:12 am Scott whoops! Yes, I meant Daniel. I don't know why I remembered his name as Noah. I thought you had written that in your post but I must have gotten confused. Sorry! TonyK #56 "The video proves that he [R. Borcherds] is as British as the day he was born!": According to Wikipedia, he was born in South Africa.... 68. Aspect Says: Comment #68 April 22nd, 2021 at 5:26 am Smashing teapots on your driveway seems like quite a Texan way to do science. You come across as a calm person so the image this paints is pretty funny 69. Michael Marthaler Says: Comment #69 April 22nd, 2021 at 5:51 am "If so, though, then clearly a classical computer can easily sample from the same distribution! Why? Because presumably we agree that there's a negligible probability of more than (say) 1000 shards. " I think even if the number of shards goes to infinity, it should be possible to derive a good approximation of a continuous probability distribution which e.g. describes the size distribution of the shards. And similarly for shape. Of course that might be a lot of work and difficult to do. Also: To compare Boson sampling to something else, the 'something else' should not be chaotic. Meaning it should not depend exponentially on the initial conditions. Which could be the case for the teapot example. Than of course we can probably not find a good probability distribution for the shard, but than it is also not a well defined problem and quite different from Boson sampling. That said: I do like teapot test as a way to judge quantum computing proposals. 70. fulis Says: Comment #70 April 22nd, 2021 at 6:42 am The teapot supremacy argument falls apart as soon as you ask yourself what you actually use a computer for. Of course you can view any system in nature as simulating itself, but if we can't control it then it's useless to us. Try doing something useful with a quantum system and you'll figure out the difference right quick. A lattice of coupled spins, isn't that a quantum computer? Each spin is a qubit and the Hamiltonian governing their interaction encodes some particular problem. Well if you can control the Hamiltonian then yes congrats, it actually is a quantum computer. A piece of iron in your pocket isn't though, even if it's hard to simulate. 71. Ingrid Says: Comment #71 April 22nd, 2021 at 7:19 am "as long as your analog computer is governed by classical physics, it's presumably inherently limited to an Avogadro's number type speedup over a standard digital computer" How come? 72. Scott Says: Comment #72 April 22nd, 2021 at 8:29 am Ingrid #71: Because, as long as we've assumed many-body quantum effects aren't important, a simulation on a digital computer could always just go atom by atom or molecule by molecule. Leave a Reply Comment Policy: All comments are placed in moderation and reviewed prior to appearing. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, or snide and patronizing tone. Also: comments that link to a paper or article and, in effect, challenge me to respond to it are at severe risk of being left in moderation, as such comments place demands on my time that I can no longer meet. You'll have a much better chance of a response from me if you formulate your own argument here, rather than outsourcing the job to someone else. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email. You can now use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations. [ ] Name (required) [ ] Mail (will not be published) (required) [ ] Website [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Submit Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] --------------------------------------------------------------------- Shtetl-Optimized is proudly powered by WordPress Entries (RSS) and Comments (RSS).