Blurry but clear enough

My vision is blurry right now, because yesterday I had a procedure called corneal cross-linking, intended to prevent further deterioration of my eyes as I get older. But I can see clearly enough to tap out a post with random thoughts about the world.

I’m happy that the Netanyahu era might finally be ending in Israel, after which Netanyahu will hopefully face some long-delayed justice for his eye-popping corruption. If only there were a realistic prospect of Trump facing similar justice. I wish Benny Gantz success in putting together a coalition.

I’m happy that my two least favorite candidates, Bill de Blasio and Kirsten Gillibrand, have now both dropped out of the Democratic primary. Biden, Booker, Warren, Yang—I could enthusiastically support pretty much any of them, if they looked like they had a good chance to defeat Twitler. Let’s hope.

Most importantly, I wish to register my full-throated support for the climate strikes taking place today all over the world, including here in Austin. My daughter Lily, age 6, is old enough to understand the basics of what’s happening and to worry about her future. I urge the climate strikers to keep their eyes on things that will actually make a difference (building new nuclear plants, carbon taxes, geoengineering) and ignore what won’t (banning plastic straws).

As for Greta Thunberg: she is, or is trying to be, the real-life version of the Comet King from Unsong. You can make fun of her, ask what standing or expertise she has as some random 16-year-old to lead a worldwide movement. But I suspect that this is always what it looks like when someone takes something that’s known to (almost) all, and then makes it common knowledge. If civilization makes it to the 22nd century at all, then in whatever form it still exists, I can easily imagine that it will have more statues of Greta than of MLK or Gandhi.

On a completely unrelated and much less important note, John Horgan has a post about “pluralism in math” that includes some comments by me.

Oh, and on the quantum supremacy front—I foresee some big news very soon. You know which blog to watch for more.

125 Responses to “Blurry but clear enough”

  1. jonathan Says:

    “I urge the climate strikers to keep their eyes on things that will actually make a difference (building new nuclear plants, carbon taxes, geoengineering) and ignore what won’t (banning plastic straws).”

    May I ask then why you endorse Warren (who has called for nuclear to be phased out by 2035), and don’t mention (e.g.) Booker, who has explicitly repudiated Warren’s anti-nuclear position?

  2. jonathan Says:

    Just googled — found an interview with Booker where he mainly talks about nuclear and a carbon tax. Warren doesn’t want a carbon tax. So that’s 2/2 vs. 0/2.

    As far as I know, nobody has talked about geoengineering, which isn’t really up the D’s alley anyway.

    The only downside is Booker wants to ban fracking, which is counterproductive in the short run (since gas > coal).

  3. Israeli TCS guy Says:

    Sorry Scott, I like your posts but you were misled. Even Nethanyahu’s most extreme opponents never claimed his corruption is “eye-dropping”. His charges are all circumstancial, weak, and two of which are formally on the light end of the spectrum of corruption if at all: taking expensive cigarettes and drinks from a rich friend and having a discussion with a news outlet publisher who tried to blackmail him (and not agreeing to yield). The other charges are again about his relations with the media and their coverage of him and his wife. Nothing of personal greed.

    It is highly plausible that the charges are exaggerated and motivated politically and bureaucratically, based in part on the frustration of the left and far left who faced defeat after defeat by Nethanyahu.

    Since there are not even charges yet in his case, it is premature to conclude he is corrupt.

  4. Richard Gaylord Says:


    you write “if they looked like they had a good chance to defeat the madman”. Trump is many things (i’m not sure if you would allow the use of some of the appropriate descriptors) but there is no reason to identify him as a madman. moreover, it is a disservice to the mentally ill to call Trump mad.

  5. Scott Says:

    jonathan #1, #2: From about 50 different standpoints (including climate), the overwhelmingly highest priority has to be to defeat Twitler with the highest probability—every other issue takes a backseat. But yes, you’re right, nuclear is a real reason to favor Booker over Warren. I added Booker to the post. Thanks!

  6. Scott Says:

    Richard Gaylord #4: Thanks; changed “the madman” (which was Lenny Susskind’s term) to “Twitler.”

  7. Arch1 Says:

    Best wishes on your eye outcome (including not rubbing your eyes while asleep).

  8. Scott Says:

    Arch1 #7: Thanks!! Doing my best…

  9. Scott Says:

    Israeli TCS guy #3: The reports that I read painted a picture of a full range of classic Trumpian behaviors, from enriching himself at the public expense to flouting election laws and basic democratic norms. I’ll concede, though, that in the post-2016 world maybe none of that is “eye-popping” any longer. 🙁

  10. sokrates Says:


    Get well soon. We need you fit as a fiddle (or may I say as a butcher’s dog if you like the British version) for a long long time.

  11. Israeli TCS guy Says:

    Sorry Scott, “enriching himself at the public expense” is simply not true. There is not even a single claim of this sort even in the most extreme far-fetched and conspiratorial blogs out there. His alleged main “corruption” is that he indirectly via middlemen pressured a publisher of a minor online news outlet to publish few pieces of news that are flattering to his wife.

    “flouting basic democratic norms”. Sorry, but this does not fall under corruption, but politics.

  12. murmur Says:

    I think it’s over the top to say that civilization may not exist in the 22nd century due to climate change. There will probably be more extreme weather events, some sea level rise but nothing apocalyptic. Climate change will be seen as the latest in the long line of alarmist claims by the left – like population explosion, resource scarcity etc.

  13. Randall K McRee Says:

    On the quantum supremacy front–refer you to this?

    Seems like an extraordinary claim that will require some more evidence.

  14. Scott Says:

    murmur #12: It all depends on how long it takes for the permafrost/methane feedback thing to get started, doesn’t it?

  15. Scott Says:

    sokrates #10: When you spend a few minutes every day reading people attacking you on Twitter, Reddit, and elsewhere, it really makes your day to hear from someone who feels that way. An unironic thank you.

  16. Jacob Says:

    #13: Oops, looks like NASA spilled the beans. Are you allowed to talk about it Scott?

  17. JimV Says:

    I am sorry to hear that Warren is down on nuclear. Nuclear has had some bad teething problems, but every technology has them. (Boilers for steam engines used to blow up a lot in the 1800’s before that technology matured, killing many more people than nuclear has. Designs evolve and adapt, just like biological evolution.) I believe Warren is smart enough to be persuadable on that issue though, and the Democratic Party badly needs a leader. For my money, she is the most demonstrated one available.

    E.g., Pelosi is a good manager, but not a leader. She needs somebody above her to tell her to impeach Trump, or she won’t take the risks. I wish the Democrats had an opposition leader to tell her that.

    Biden has had plenty of opportunity to show leadership and what has he accomplished? I would hate to have to vote for him. If not Warren, I would prefer just about any of the other candidates. The world needs a good USA leader (that is, leader of the USA), not just an alternative to Trump. We need to move forward, not just stop marching backward.

    As for civilization ending or taking giant steps backward in the next century, it’s not just climate change that seems headed in that direction. Population size is in fact the driver on that and many other bad effects. The Earth will support just so many humans, and we are already exceeding our budget on renewable resources like fresh water (using up stores faster than they replenish). Meanwhile, there aren’t enough good jobs for the average person of IQ 100 in developed countries and they vote for people like Trump who promise them revenge on whomever is unfairly keeping them down. (I agree they need some support but it was obvious to me that Trump, who managed to go bankrupt building a casino, would not provide it with his walls and trade negotiations and other lies; not to them, however.) Of course much of humanity subsists on about a dollar a day of earnings and might not notice a collapse of civilization.

    A naturalist once remarked, “The male primate grows morose and savage with age.” Living proof, but in my defense, there is a lot to grow morose and savage about.

  18. asdf Says:

    The John Horgan post seems a bit thin but he might like Penelope Maddy’s well known 2 part article “Believing the Axioms” if he hasn’t seen it already.

    The quantum supremacy news sounds very exciting and I’ll eagerly watch Gil Kalai’s blog for updates ;).

  19. dualmindblade Says:

    In the Horgan post, it sort of seems like you’re implying that arithmetic/computer science is immune from axiom oriented pluralism. If computer scientists take seriously the possibility that P vs NP could be undecidable in standard set theories, isn’t it possible that there could be a divide over whether to accept something like this as an axiom? Like, maybe we accumulate enough no-go theorems or some other form of evidence that people start to get the feeling that it must be undecidable, in the same way they now sometimes feel strongly about whether P = NP.

  20. Don Says:

    The blog to watch…it’s this one, right?

  21. Shmi Says:

    Scott, I am lost as to why people feel that climate change is an emergency. Even 56 million years ago, when the Earth has been the hottest ever (, it was the time when life thrived, way more so than now. And, according to the Wikipedia “The IPCC states that “a ‘runaway greenhouse effect’—analogous to [that of] Venus—appears to have virtually no chance of being induced by anthropogenic activities.”

  22. Vanessa Says:

    Regarding “I’m happy that the Netanyahu era might finally be ending in Israel” (I’m Israeli). I’m not at all a fan of Netanyahu, but I prefer a coalition that includes the Likud to any coalition that includes religious parties. I am rather disappointed with the Israeli left for not making the right call on this.

    About your “arithmetical Platonism” (in the comment you wrote to Horgan): would you consider PA sentences with multiple quantifiers as “objective” or not? Because, as opposed to sentences with a single quantifier, there is no procedure that converges to the right answer even in the limit.

  23. Jr Says:

    What does the election results mean for the Israel-Palestine conflict? Will the Israeli government have any plans for achieving peace?

  24. Or Meir Says:

    Hi Scott,
    Get well soon!

    I think it is too early to celebrate the end of Netanyahu’s era. The results of the last elections are not too different from the last two elections. The only reason why it seems like Netanyahu lost is that Liberman, a right-wing politician who is probably even more corrupt and crooked than Netanyahu, decided to stop supporting Netanyahu’s government. If he changes his mind for any reason, then Netanyahu will be back in power almost as before. My guess is that Netanyahu and Liberman are currently negotiating the appropriate bribe for Liberman to change his mind.

    BTW, I think that Israeli TCS guy is exaggerating in diminishing Netanyahu’s crimes. The charges against Netanyahu’s are very severe. It is true that he is not charged with taking money, but rather a positive media coverage, but this is a bribe nonetheless. Moreover, in one case he is charged with buying this positive media coverage with billions of NIS of the Israeli taxpayers.

    Saying that “the charges are exaggerated and motivated politically and bureaucratically” is a conspiracy theory straight out of Netanyahu’s propaganda, and I am surprised that an academic has bought it. It is the Isreali analogue of Trump’s “deep state” conspiracy theory.

  25. Jamie Says:

    This is quite tantalizing on the quantum supremacy front! There are already commercial products available for random number generation, so it is plausible that Google used such a tact in pursuit of supremacy. And even with the tremendous strides by IBM, Regetti, IonQ, and others it always seemed Google had the edge in getting there first. I would love to read the paper once the public has a copy of it (if it exists) to learn more about where humankind has progressed in random number generation!

    …On the political front, I definitely found myself losing sleep last month watching two nights of Democratic debates in their entirety livestreamed on while traveling abroad for the first time ever (a previous trip to Canada doesn’t count) in London, England for QEC. Although I can’t really find a favorite out of either bunch (my favorite is currently in office), I was proud to be an American, in a foreign land for the first time (again, Canada doesn’t count), watching the process play out and issues come to the fore… I was very excited to get the email yesterday that the QEC lectures are now posted on YouTube!

    (Full disclosure, I am not an expert myself, I simply watch and read from them at this stage of my career.)

    It was cool to see the climate protests yesterday (one small quibble is I would have loved to have seen it happen on a Saturday or Sunday but I’ll settle for Friday over nothing). It is time for the Republicans to eschew from denying this reality and for Democrats to resist using this as pretense for economic restructuring. I think the burden is still on the scientists, innovators, and business leaders to partner with regulators to enable the climate conducive to solving or mitigating climate change.

    …Get well soon, Scott!!!

  26. Scott Says:

    Jacob #16: Yes, it looks like the results were leaked early, causing a huge PR disaster at what should’ve been one of Google’s proudest moments. I’ll wait for their official announcement if I can, or blog about it before then if I have no other choice.

  27. Scott Says:

    asdf #18: Gil Kalai’s blog will indeed be an extremely interesting one to watch … you might get to witness the real-time collapse of a worldview! 😉

  28. Scott Says:

    dualmindblade #19: Yes, in principle it’s conceivable that a statement like P vs. NP could be proved independent of ZFC, and that mathematicians would divide into camps with opposite beliefs with no prospect of a reconciliation (other than a proof from more powerful axioms that both sides accepted). My points were simply that:

    (1) In practice, in the “arithmetical” parts of math, nothing like that has ever happened, in contrast to set theory (where it has happened).

    (2) Even supposing it did happen, my philosophy of mathematics (and for what it’s worth, Gödel’s as well) would take it as given that one side was right and the other was wrong—e.g., a polynomial-time algorithm for 3SAT either exists or it doesn’t exist—even if we can’t prove which.

  29. Scott Says:

    Vanessa #22: I confess that I don’t know enough about Israeli politics to choose between a coalition with Likud and a coalition with the religious parties. Is it just a mistaken intuition, drawn from the American system, that causes me to feel like any realistic arrangement with Gantz at the top is preferable to Bibi maintaining his suffocating hold on power?

    Yes, absolutely, PA sentences with multiple quantifiers have definite truth-values according to my view.

  30. Scott Says:

    Jr #23: From what I know, Gantz is also rather hawkish—to whatever extent he has an ideology at all beyond “not being Bibi” —so even if he becomes prime minister, I wouldn’t get my hopes up for any big peace overtures anytime soon. On the other hand, getting rid of Bibi is certainly a necessary condition, even if not a sufficient one, for any movement in a positive direction. Bibi’s current position—“Trump is my friend and will let us get away with anything we want”—is not only morally empty but strategically shortsighted as well.

  31. Wyrd Smythe Says:

    “Twitler” — I love it! Consider it borrowed! (I’ve gotten tired of using “Cheeto Charlie” and “Tangerine Tony” and “Pumpkin Goblin”.) I, too, long for justice and character to finally prevail. What a fine mess we’ve gotten ourselves into.

    FWIW, my dream ticket would be Buttigieg-Gabbard. Two young, competent, intelligent, educated people of high character with military backgrounds. #justadream

    Eyes are so important. Hope yours are in tip-top shape ASAP!

  32. Ernest Davis Says:

    Scott —
    In your comment on Horgan’s blog you wrote, “I’m an “arithmetical Platonist,” who takes it for granted that, for example, any given Turing machine objectively either halts or runs forever, regardless of whether this or that axiom system can prove it. (I’m NOT similarly a Platonist about the statements of set theory.) So even if there *were* some interesting alternative set of axioms for arithmetic that proved that Fermat’s Last Theorem was false, or that there were only finitely many primes, or whatever, I would say that those axioms simply weren’t talking about the same thing that I mean when I say “the positive integers.” ”

    How about first-order statements over the natural numbers with alternating quantifiers, like “There are infinitely many twin primes”, which are not, in any obvious way, reducible to the halting problem on a standard Turing machine?

    There’s a literature, which I know of from Martin Davis and John Stillwell, of results of the form, “XYZ statement over the natural numbers is true” (which XYZ is entirely artificial — something about the Godel number of something) or “ABC statement over the reals is true” (where ABC is sometimes an actually interesting about measure theory) “if and only if DEF statement asserting the existence of a large cardinal is consistent/true”, which suggests that enforcing Platonism over the natural numbers/reals while allowing plurailism over set theory may not be all that easy.

  33. Curious Says:

    I’m curious about your comments about Mochizuki regarding work by Scholze and Stix – I’m evidently behind the times on that affair. Have you got a good reference to read up on regarding the current status as you understand it?

  34. Scott Says:

    Ernest #32: Yes, statements of first-order arithmetic with arbitrary numbers of quantifiers are still completely definite.

    Regarding large-cardinal statements, your comment elides the distinction between their consistency and their truth, which is absolutely crucial for this discussion. The consistency of a large-cardinal statement is itself an arithmetical statement: it just says that a Turing machine, searching for a contradiction from the large-cardinal statement plus the ZFC axioms or whatever, will never find one. So it’s not shocking, though it’s indeed interesting, that such a statement can sometimes be shown to imply, or be implied by, other more “natural” arithmetical statements.

    Statements that flat-out assert the existence of a large cardinal are in a completely different class: those are more “metaphysical” in nature, and are not equivalent to any purely arithmetical statement.

  35. Scott Says:

    Curious #33: The Scholze-Stix paper is here. I’m an outsider and can’t directly judge the arguments. I might be biased by the fact that Scholze and Stix’s style of mathematical writing is as clear as Mochizuki’s is turgid.

  36. James Gallagher Says:

    The Google “breakthrough” in quantum random number generation is not so exciting for me as others, and I do wonder if the media coverage of this as a demonstration of “quantum supremacy” is really justified? I mean, if Nature just does fundamental random jumps every planck time or so, it’s about time technology was able to sample that fundamental randomness? Isn’t Quantum Supremacy more about getting quantum algorithms to work? A more exciting development for me is the recent announcement that Grover’s Algorithm may actually exist in biological systems at the level of DNA

  37. Scott Says:

    James #36: That’s a profound misunderstanding of what we’re talking about here. Generating random bits quantum-mechanically is trivial, and has been done since the early 20th century. The interesting part, the new part, is to sample from a nonuniform probability distribution over (say) 50-bit strings that would take ~250 time to sample using the fastest known classical randomized algorithms.

  38. James Gallagher Says:

    Scott #37

    Trust me, while the results are restricted to random number sampling and such, not so many people will be impressed. OTOH If it’s provable that DNA uses the Grover Algorithm , then that’s a Nobel Prize.

  39. Will Says:

    Scott #35: I think some useful insight was provided by David Roberts here

    In particular I think the way that Mochizuki is unclear is very clarifying.

    There are two ways a text can be unclear. One is using complicated and difficult language to describe a new idea. The other way is to use new language to describe an old idea the reader is already familiar with.

    The first reason is unfortunately sometimes necessary. But one big problem with the second reason is that it is much easier to make and harder to catch mistakes.

    Mochizuki has coined a truly awe-inspiring list of neologisms of the second type. For instance if we have some set X and an automorphism f: X => X, Mochizuki would say that we have two “mutually alien copies” X_1, X_2 and an isomorphism f between them, but we must steadfastly refuse to identify them. Mochizuki claims that doing this is necessary to avoid mistakes, and gives some examples. But Roberts shows that all the mistakes arise from Mochizuki’s own misapplication of the standard formalism. So this leads us with the presumption that it’s easier to make mistakes in Mochizuki’s language.

    And one of Scholze-Stix or Mochizuki must have made a mistake.

    A strange twist is that Mochizuki, being a top mathematician before starting IUT, is also surely more experienced with the standard language than his own language, and anyways more experienced than me.

  40. Scott Says:

    James #38: So what I’m getting is, you have no clue what was accomplished and you don’t care to learn?

    This is probably the first time in human history that a programmable quantum computer was used to do something that isn’t feasible classically. It might or might not have any immediate use. If it doesn’t—well, the Wright Flyer also took years to find commercial applications.

    There’s obviously still a long, long way to go to get to fault-tolerance and scalability. But unlike some previous announcements (cough … D-Wave … cough) that people hyperventilated about, this is actually a big step in that direction.

    For a variety of reasons, it seems extraordinarily unlikely to me that DNA in its natural state would use Grover’s algorithm. So the fact that such a discovery might merit a Nobel Prize seems no more relevant to anything we’re talking about than the fact that flying pigs might also be Nobel-worthy.

  41. STEM Caveman Says:


    this is a mis-application of the narrow technical concept of Common Knowledge, which is actually rather short on practical applications, to much simpler phenomena like Thunberg and (in your linked lecture on CK), the Emperor New Clothes story and invitations to “come see my paintings” during a date.

    Thunberg is adding her voice to a massive international chorus, which is far better funded and supported than the opposite point of view. She is not pushing on an unstable equilibrium, she is helping entrench the dominance of the dominant side. The process by which a dominant party wins is not by triggering a preference cascade with a sudden truth-bomb, but by squelching (media coverage, funding and political support of) the opposition to the point that the party or Party can proceed unopposed. Speaking power to lesser power.

    In the Emperor’s Clothes story, common knowledge (I know that X knows that Y knows….) already exists. The opposite assertion is often seen in the Common Knowledge literature, but never with a proof. There’s a reason for that; it is easy to show that the definition of CK is satisfied, for the same reason there is common knowledge of the weather. Terry Tao made this mistake in his CK post on Trump.

    “Come see my etchings” (as mis-analyzed by Pinker) is not phrased indirectly due to a lack of common knowledge of the intent of the question. There is a lack of knowledge, by one or both parties, of the extent of relations jointly *and individually* desired (will I want to sleep with this person an hour from now, or just explore the possibility?), at the time of asking as well as of how that extent may change after coming in to see the etchings. There can be common knowledge that the negotiation concerns sex, but there is no precise and non-clunky way of defining in a single question the actual subject of the invitation, even if the word “intercourse” were used. When there IS certainty of common knowledge that both want sex, the indirect proposal is then part of the courtship dance, e.g., female interest is (usually) increased more by a cleverly stated question than a blunt “do you wanna?”. Capacity for seduction is, for better or worse, used as a fitness indicator and a combined social/mental IQ test.

  42. asdf Says:

    Scott and Curious #33, in case you haven’t seen it, Erica Klarreich wrote a popular-level article about the Mochizuki-Scholze-Stix situation right after the Scholze-Stix report was released:

    An arithmetic statement can’t assert the existence of a large cardinal, but it can assert the nonexistence of one (by saying it is inconsistent).

  43. dm Says:

    James #37

    This is that extremely rare case where I may have expertise relevant to this discussion. The problem with Patils idea is that DNA polymerase tests one nucleotide substrate at a time, not a super-position of the four bases. It samples them randomly with replacement. So assuming equal concentrations etc on average it will try ~2.5 nucleotides per base of template DNA, close to sqrt(4) but entirely classical.

  44. Scott Says:

    STEM Caveman #41: Maybe a better term than “common knowledge” is “coordination problem.” Most knowledgeable people, although not you apparently, are now in intellectual agreement that emissions need to be drastically curtailed if human civilization is to have any shot at a future. Yet despite that agreement, nothing remotely close to the required action is being taken. Partly that’s because of the deniers, as well as the populist strongmen like Trump and Bolsonaro who are moving in the opposite direction purely out of spite. (Like the drunk driver who speeds toward the cliff because the passengers in the backseat are screaming to slow down.) But the much larger factor, I think, is that no one has been able to solve a coordination problem. And that’s precisely what Greta Thunberg is trying to do: to solve the coordination problem, by putting what’s indeed childishly obvious into the mouth of an actual child, to the point where leaders are finally shamed into acting, and (more importantly) they know that the others are being shamed, they know that they know that others are being shamed, etc. We’ll see if it succeeds, but given that everything else has failed, it’s worth a try.

  45. STEM Caveman Says:

    Much more obvious than the science of climate change is that the Green climate change (reversal) movement is heavily influenced by Christian tropes, including a coming apocalypse, a threat of infinite future hell to compel present conduct, human sin and its wages, redemption through suffering, the evil of wealth and the good of its redistribution. Independent of the level of scientific support, it is in effect an atheistic Chrisian cult for the 99+ percent of its followers who are not in a position to read and evaluate scientific arguments on climate modeling. It is transmitted by the methods of religion (rhetoric, guilt, propaganda, fashion, etc), and is coming into a position of sufficient power to be enforced by the methods associated with a state religion.

    Thunberg is promoted because she fills in additional Christian tropes that are deep-seated in the European culture where the Green movement exclusively exists (the developing world is nowhere seriously interested in emissions reduction, which is to say that the project is doomed without ultraviolent coercion on a planetary scale). “From the mouths of babes”, child preachers, virgin warriors, itinerant proselytizing Jesus-figures, nuns, etc… not to mention the ancient pagan traditions of a sybil, vestal, and priestess. Whether or not she understands this or is at any level motivated by it, Greta has stepped forward and filled the role of Priestess and a Warrior For (secular) Christ. Having made herself available, the cultural resonance of her role then propels giant media amplification and so we have her as an instant candidate for the Nobel Prize (secular beatification) and so forth.

    “Coordination”, if not persuasion, happened long ago. Greta is part of the Compulsion phase that happens when religions capture the state.

  46. Scott Says:

    STEM Caveman #45: Any political movement in human history—communism, libertarianism, rationalism, abolition, women’s suffrage—had many features that could’ve been analogized to religion. So pointing out that environmentalism has parallels to religion is a profoundly lazy and cowardly way to dismiss it, without ever having to address the truth or falsehood of its underlying claims about the world. (In this case, particularly clear and testable empirical claims.)

  47. Ernest Davis Says:

    Scott #34: Yes, statements of first-order arithmetic with arbitrary numbers of quantifiers are still completely definite.

    OK. How about higher order statements? Is the proposition that there exists a well-ordering of the subsets of the natural numbers completely definite? If not, why not? If so, wouldn’t that make the continuum hypothesis definite?

  48. Scott Says:

    Ernest #47: Mu faith in definiteness starts wavering as the quantifier complexity of the statement about integers approaches the Church-Kleene ordinal.

  49. Sam Says:

    What is Scott’s take on Bernie Sanders? I didn’t find his name in the list of candidates you’d support. Doesn’t Bernie have one of the best chances to beat Twitler?

  50. Scott Says:

    Sam #49: He’s not my first choice. Protectionist, anti-nuclear, and seems to have done no reflection about how Marxism turned into one of the great tragedies of human history. But of course i’d still unreservedly support him over Twitler.

  51. dualmindblade Says:

    Scott #50: How is this different from ‘Muslim Americans seem to have done no reflection about how their religion led to the deadliest attack on Unites States soil’?

  52. Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube. | Combinatorics and more Says:

    […] In connection with some near announcement by Google regarding quantum computers,  Scott Aaronson commented on his blog  ” Gil Kalai’s blog will indeed be an extremely interesting one to watch … you might get […]

  53. Harvey Friedman Says:

    It was very gratifying to see so many comments related to f.o.m. = foundations of mathematics. Numbers 13,22,28,29,32,34,42,47,48. I have some comments and opinions. P not= NP is a Pi02 sentence that could conceivably be neither provable nor refutable in ZFC, but this seems unlikely. More likely (how likely I don’t know) is of course that the first proof of P not=NP uses a large cardinal hypothesis which is later removed. Regarding #22, “multiple quantifiers” should probably be “multiple alternating quantifiers”. Regarding #42. An arithmetic sentence implies the existence of a large cardinal if and only if that arithmetic sentence is refutable. An arithmetic sentence can imply the nonexistence of a large cardinal, but no arithmetic sentence is equivalent to the nonexistence of a large cardinal. With regard to objective truth values of arithmetic statements. Presently certain diehard set theorists – and there are some notable high achieving ones – would disagree with the assessment of Scott’s concerning the metaphysical nature of set theoretic assertions. Almost everybody else agrees with Scott’s view on this. And Scott’s view that arbitrary arithmetic assertions have a deep kind of objectivity (definite truth value) is fairly commonly held among mathematicians and logicians, but a significant minority would disagree. My own view on this is that the world is going to see a steady stream of results in what I call Tangible Incompleteness which, over time, will succeed in blurring the distinction between arithmetic sentences and highly set theoretic sentences so much that in any context even with all objects finite but infinitely many objects, the idea of definite truth values and objectivity will be abandoned as simply naive and associated with a bygone era. We now have discrete forms of large cardinal hypotheses which really have a common skeleton, and these are getting rather fine tuned and convincing. These discrete forms are equivalent to the consistency of the large cardinal hypotheses. These discrete forms are implicitly Pi01, and have new finite forms which assert that certain very easy to follow finitary constructions can be carried out for any finite number of steps. Reports on state of the art should come out on the FOM email list this coming week under “Tangible Incompleteness Restarted”.

  54. Scott Says:

    dualmindblade #51: It’s different because I was talking about an individual—the basic unit of moral reflection—and one who’s running for President of the US on an avowedly socialist platform. Were there an openly Wahabbist presidential candidate, your comparison would be fair.

  55. Eric Cordian Says:

    Hi Scott,

    My expectation is that the report by the Financial Times that Google has achieved “Quantum Supremacy” with a 53 qubit device will turn out to be a giant nothingburger. I would love to be surprised and have this turn out not to be the case.

    First, I think there’s going to be some reluctance to call a speedup of only 2.6 billion “Quantum Supremacy.” The limit on classical computing is a computer the size of the universe running for the age of the universe. So unless the quantum computer computes something that would require that, or does exponential classical computation in polynomial time in a way which scales smoothly with problem size, quantum supremacy should probably not be declared. Also, we don’t know how fast the classical computer could solve the problem using the best possible algorithm. Previous such claims have died on that hill.

    Second, 53 qubits is not enough to run up against the granularity of physical reality. It is possible the Hilbert Space containing the wavefunction of the universe is not infinite dimensional, but finite dimensional of very large dimension, like ten to the ten to the one hundred twenty. For most quantum mechanical calculations, it doesn’t change the answer if we pretend it’s infinite dimensional, and that coefficients of a superposition can be arbitrary complex numbers, which require an infinite number of bits to specify. However, faithfully representing the arbitrary entanglement of large numbers of qubits eventually becomes impossible as the size of the configuration space exceeds the number of quantum microstates. My back of the envelope guess is that if this limit exists, we will run up against it at around 100-150 qubits, which is more qubits than Google’s device, but less qubits than is needed to do things like break public key cryptography quickly.

    I look forward to your take on this result after the paper is officially published.

  56. Scott Says:

    Eric Cordian #55: What you’ve described is not at all a nothingburger. It’s not an everythingburger either, but it’s most certainly a somethingburger. Have a little respect for the magnitude and difficulty of what was accomplished. Meanwhile, in the wake of the leak, I’ll figure out what I can blog and when.

  57. Eric Cordian Says:

    Scott #56: I found a copy of the paper online. While I’ll agree it’s a “somethingburger,” I think it was probably a mistake to declare Quantum Supremacy in the title.

    They should have just reported their results, and left it to the community of their peers to decide the magnitude of their accomplishment.

    This now leaves Google in a really awkward and embarrassing position.

    It’s like the difference between naming your paper “Unexpected Warmth in Palladium” and naming it “Cold Fusion Demonstrated in Laboratory.”

    It’s unclear whether the device in question can be used to compute anything useful, and the usual problems with errors and qubit stability remain. IBM’s simulation of a 56 qubit device in 2017 was widely considered to have moved the bar for claiming quantum supremacy, making this paper’s bold declaration of 53 qubit supremacy a bit at odds with conventional wisdom.

    So it will be interesting to see how this all plays out over the next few weeks.

  58. Filip Says:

    Yang tweeted “Google achieving quantum computing is a huge deal. It means, among many other things, that no code is uncrackable.” [1] – he should lose some points in your list for spreading misinformation and completely ignoring post-quantum crypto.
    [1] –

  59. Scott Says:

    Eric Cordian #57: The real problem is almost the opposite of what you say. A factor of ~2 billion speedup is already so large that direct verification of the outputs on a classical computer is infeasible, and indirect verification methods need to be used. (Direct verification is still feasible for a factor of ~1 million speedup.)

    IBM is indeed building similar devices with similar numbers of qubits, but it has not made the clear demonstration of quantum supremacy a central goal. When I last looked at IBM’s materials on the web, there were no technical specs whatsoever, but a lot about the designer case for their QC that they’d had built in Italy (!).

    With any ordinary understanding of words, and ordinary standards of evidence, Google has demonstrated quantum supremacy with a programmable device for the first time. It’s sad that this leak means that the information is dribbling out piecemeal rather than in one clear burst. But it’s as if they’ve finally made it to the moon, and you’re asking whether it really counts as a “moonwalk” if they’re inside bulky spacesuits, and also pointing out that the moon has few or no natural resources, and that they’re nowhere near being able to get to Mars.

  60. Sniffnoy Says:

    So, uh, was anyone else’s reaction to this 53-bit number being “Why on earth are they using Javascript for this?” before realizing that the number of bits is just a coincidence? 😛

  61. dualmindblade Says:

    Scott #54: I have to say, it kind of feels bad to hear you express this opinion. I won’t expect you to agree with me, but I maintain the proper analogy is an openly Muslim candidate. I hope you can at least see why anyone who calls themselves a socialist, and that’s what we must call ourselves because it’s just part of the language, would find this a bit insulting.

  62. Bennett Standeven Says:

    @ Eric Cordian #55

    How did you get that figure of 100-150 qbits? From a Hilbert Space of dimension 10^10^120, I get 3*10^120 qbits as the upper limit. (Actually I expect the limit would be much lower, as it isn’t really possible to turn the entire universe into a computer.)

  63. gentzen Says:

    Harvey Friedman #53: Good to hear that you have recovered enough to dive into f.o.m. again. How appropriate to make your public reappearance on Scott’s post about recovering from a procedure called corneal cross-linking.

  64. Joshua Zelinsky Says:

    Harvey Friedman #53 “An arithmetic sentence can imply the nonexistence of a large cardinal, but no arithmetic sentence is equivalent to the nonexistence of a large cardinal.”

    Can you expand on why this is? The first part is clear, but the second isn’t obvious to me.

  65. Scott Says:

    dualmindblade #61: One central difference is that most Muslims—like most adherents of every major religion, but unlike most socialists—are what they are because they were born into it.

  66. Kodlu Says:

    Eric Cordian, #57: Do you mind sharing the link to the paper?

  67. James Gallagher Says:

    #Scott 40

    This is probably the first time in human history that a programmable quantum computer was used to do something that isn’t feasible classically.

    Oh come on, when did the goal posts move? If all this is proving is that they’ve achieved something that is not achievable classically, then why is that Quantum Supremacy? The outcomes of Bell Test experiments aren’t quantum supremacy are they? I mean isn’t Quantum Supremacy supposed to be about about factoring million digit numbers or doing database searches in sqrt N time and similar?

    Quantum Random sampling algorithms may certainly be doing something new and non-classical, like using Nature’s random number generator in a way that’s obscure because of all our confusion with QM “Interpretations” – but come on, really, this is how you want “Quantum Supremacy achieved” announced to the world?

  68. Scott Says:

    James #67: Because simulating it on a classical computer appears to take ~250 time. And the task is well-defined, and you can vary it just by changing the programming of the device, so computational power really is the sole bottleneck.

    That’s the difference from Bell experiments and the other examples you mentioned, which demonstrated quantum mechanics but not quantum computational supremacy.

    And if you, a commenter on my blog, don’t care about this, fortunately it doesn’t matter, because others do and will. Nature, which embargoed the paper, understands perfectly well that it’s dealing with one of the major science stories of the decade.

  69. Eric Cordian Says:

    Kodlu #66:

    Scott #59:

    The paper was published on NASA’s Website, and Google later removed it and has declined comment on the reasons why. I’m not sure the best word to describe this seq

  70. Eric Cordian Says:

    Kodlu #66:

    Scott #59:

    The paper was published on NASA’s Website, and Google later removed it and has declined comment on the reasons why. I’m not sure the best word to describe this sequence of events is that the paper was “leaked.” Those who got the paper while it was up got the whole thing, so the research isn’t really “dribbling out piecemeal,” as far as I can tell.

    The IBM result I referred to wasn’t a quantum device, but the simulation of a quantum device on a classical supercomputer.

    There is much grumbling on Twitter by physicists and cryptographers over the quantum supremacy claim. It will be interesting to see what the final consensus of the academicians turns out to be.

    The news media is going nuts, proclaiming everything from the end of cryptocurrency to Google being able to break “all cryptography.” Now might be a good time for a press release from a highly regarded quantum computing expert explaining what this paper, even if correct, doesn’t imply.

  71. Scott Says:

    Eric #69: Were you looking for the term “facepalm”? “World-historic public relations self-own”? “Neil Armstrong flubbing his line after stepping onto the surface of the moon”? 😀

    In fairness, it looks like this was the fault of NASA’s paper review process, not directly of Google.

    Also in fairness, everyone was confused/misinformed about what the Wright Brothers had or hadn’t accomplished between 1903 and approximately 1908, when they did their first public demonstrations. This will get cleared up faster than that! 🙂

  72. dualmindblade Says:

    Scott #65: I don’t see how that’s relevant to this analogy, unless you also think that a convert to Islam running for president should have to vigorously and explicitly denounce Islamic terrorists in order to be eligible for our consideration.

  73. Scott Says:

    dualmindblade #72: It would depend entirely on whether Islam was part of the candidate’s policy platform. In the US, for all the many ways our political system is broken, imposing the faith of one’s birth usually isn’t an explicit part of a candidate’s policy platform—not even Rick Santorum’s, not even Mike Pence’s. And to whatever extent it is, it shouldn’t be.

  74. asdf Says:

    Sanders isn’t running as a Marxist, he’s running as a self-described democratic socialist, which seems to basically mean a throwback to FDR. I figure if Fox News and the DNC are all so terrified of that, there must be something to like ;). And if we could elect Ronald Reagan as president, I don’t see what’s stopping Sammy Davis Jr. (besides being dead of course). But I wouldn’t try to hold Davis responsible for Netanyahu’s excesses.

    Fwiw, the UK Labour Party is labelled as democratic socialist in Wikipedia though I don’t know if they call themselves that. The biggest party in Sweden is the Social Democrats, but (as with the Judean People’s Front vs the People’s Front of Judea) the word order seems to matter.

  75. dualmindblade Says:

    Scott #73: A person’s religion, if they take it seriously, is bound to have some kind of influence on their world view. For a certain type of politician you, to put it mildly, don’t have to squint too hard at their policies to see a clear imprint of religious ideology. On the other hand, as asdf pointed out, Bernie’s policies aren’t tied to any particular brand of socialist theory, and certainly nothing that has anything to do with the soviet union. There are a vast number of very different strains of socialism, the relationships between them are complex, and in general they aren’t even necessarily ancestrally related. We don’t even know what Bernie’s exact political influences are, he doesn’t talk about it. Really, as candidates go, he’s one of the more policy oriented, putting aside what you actually think of his policies.

  76. asdf Says:

    Dualmindblade “We don’t even know what Bernie’s exact political influences are, he doesn’t talk about it”, Sanders very often credits Eugene Debs as a big influence. As mayor of Burlington VT, Sanders had a picture of Debs in City Hall.

    If it’s ok to post links to the NASA preprint, the supplemental materials are here:

    There is a Hacker News discussion here:

    It is of mixed quality.

  77. Craig Says:

    My understanding of the leaked Google paper is that they did a sampling computation in 3 minutes on a QC that would take the best classical computer today ten thousand years to do. That is great but how can we know that the QC did the computation correctly? Why can’t they do what Scott talked about in his third lecture in the last post which was to run a calculation that takes a few microseconds on a qc and takes a few weeks on the best classical computer? That would convince skeptics like myself that I was wrong.

  78. Mateus Araújo Says:

    I’m a bit mystified by the fact that the best classical simulation algorithms (such as those used by Google now) are strong simulation algorithms (i.e., explicitly calculating the amplitudes of the quantum states). Intuitively I would expect weak simulation (i.e., just sampling from the probability distribution) to be more efficient, due to the fact that not even quantum computers can do strong simulation of quantum computers.

  79. Jr Says:

    dualmindblade #51: Well, I would certainly think it is great if they did so reflect. That we don’t demand it of them is largely for pragmatic reasons. Generally speaking, people attach great value to keeping their religious identity, but as long as they can call themselves Muslims/Jews/Buddhists/whatever and perform a few symbolic actions they can often be willing to empty it of all real meaning. Thus it is (arguably) better to not question too much the claim that Islam is against violence, because the people who make that claim are helping to change Islam in the right direction. (While thinking they are stopping others from changing Islam.) And successfully convincing a Muslim that Islam actually is violent is as likely to lead him to endorse violence as to abandon Islam.

    People don’t have nearly the same attachment to political labels and they are much more willing to stop calling them socialists/nationalists/feminists if they come to reject the assumptions on which the ideology is based.

  80. Ted Says:

    Scott #27: I’m not at all sure about this, but I was under the vague impression that Gil Kalai’s hypothesis isn’t that noisy quantum computing is impossible, but rather that realistic noise is spatially correlated enough to significantly violate the assumptions of the error-correction theorem, so that quantum error correction will never be practical? If I’m right (which, again, I may not be), then I don’t think that this NISQ computation refutes that hypothesis.

  81. Pete Says:

    I find IBM’s reaction to this to be particularly petty and unprofessional. Dario Gil is out there saying this result is not significant at all; meanwhile if IBM did it we’d have commercials during the US Open saying how it’s going to cure cancer. They may say they don’t like the term Quantum Supremacy (the definition of which is pretty widely accepted), but what they really don’t like is Google Supremacy. With this, it’s become clear that IBM has officially moved from being a technical organization to being a marketing one.

  82. jonathan Says:

    @asdf 74:

    The biggest party in Sweden is the Social Democrats, but (as with the Judean People’s Front vs the People’s Front of Judea) the word order seems to matter.

    I would hope so! Otherwise Rick Santorum (a social conservative) would be a conservative socialist!

  83. jonathan Says:

    @Craig 77

    My understanding of the leaked Google paper is that they did a sampling computation in 3 minutes on a QC that would take the best classical computer today ten thousand years to do. That is great but how can we know that the QC did the computation correctly?

    My understanding is that their algorithm was simulating a physical (quantum) experiment, and thus they validated the algorithm’s accuracy by comparing it to the experimental data; but I’m an amateur in this area and could be mistaken. I assume Scott will describe the verification process when he discusses the paper, since (as you point out) it is essential.

  84. Job Says:

    Craig #77, probably because that requires higher quality bits.

    A quantum supremacy experiment involving random sampling will mostly address the kind of skepticism D-Wave faced early on, surrounding the quantumness of their device.

    IMO it’s not meant to address more fundamental type of skepticism involving QM and the computational limits of a physical system.

    That requires more than a piece of cheese, to use Scott’s terminology.

    But it is setting the stage for that type of debate to finally move forward in a meaningful way.

  85. Scott Says:

    jonathan #83: No, that’s not it at all. Verification is done using a brute-force classical computation. You can directly verify a speedup by a factor of a million that way—that might not be said explicitly in the draft of the paper that leaked, but it’s true. The factor-of-a-billion speedup, by contrast, depends on extrapolating the error rate from circuits that can be efficiently simulated classically.

  86. Accessible challenge Says:

    Craig #77: I agree. Talk of correlated errors and several other concerns (like in Gil Kalai’s blog today) can be put to rest with accessible public challenges. The SI in Google’s paper mentions the capability of harnessing smaller “patch” circuits; why not, simultaneous with publication, set up an accessible public challenge that uses an appropriately small patch?
    A weaker alternative would be to characterize, using the elided circuits mentioned in the SI, the extent of correlation in control and readout errors for at least some subsets of the full circuit.

  87. Scott Says:

    Ted #80: Gil went further than that, and explicitly conjectured that no quantum computing speedups are possible, with or without error correction. Don’t let him wiggle out of it now! 🙂

  88. Scott Says:

    Mateus #78: The fastest weak simulation of the circuits is a weak simulation (the more noise, the greater a factor you can save). But strong simulation is needed for verification of the QC’s outputs.

  89. Eric Cordian Says:

    Pete #81: I’m unsurprised IBM is unimpressed by this result. I notice the “Wright Flyer” talking point being repeated by others in response to suggestions that this isn’t a major milestone. Basically that the Wright Flyer has now been demonstrated, and the field will now progress double exponentially until we quickly arrive at the Airbus A380 of quantum computing. So clearly the proponents of this project anticipated pushback, and discussed clever rejoinders to pitch at their critics.

    Physicist Youtuber Sabine Hossenfelder opined back in June that quantum computing would be like fusion, in that “it will remain forever promising but never quite work.”

    Google: Behold! This turnip is simulating a turnip faster than a classical computer can simulate a turnip.

    IBM: Ho hum.

    Google: But the turnip is programmable!

    IBM: It’s only programmable in a number of limited ways related to turnip simulation with no practical application.

    Google: Grrrrrrrrr.

  90. Harvey Friedman Says:

    Re comment #64. I wrote “no arithmetic sentence is equivalent to the nonexistence of a large cardinal.” (btw the notion of equivalence here is provability in ZFC). Let A be so equivalent. Then notA is equivalent to the existence of the large cardinal and notA is still arithmetic. That is impossible. I might as well make this posting more useful: Let B be arithmetic.
    THEOREM 1. Suppose ZFC + B proves there exists a weakly inaccessible cardinal (the weakest large cardinal hypothesis). Then ZFC proves notB.
    Proof: Assume the supposition. Then ZFC + B proves its own consistency since V(lambda) is a model of ZFC + B (using that B is arithmetic). By Goedel’s Second Incompleteness Theorem, ZFC + B is inconsistent, and hence ZFC proves notB. QED
    THEOREM 2. Suppose B is arithmetic and ZFC proves B is equivalent to the existence of a green large cardinal. Then ZFC proves that green large cardinals do not exist.
    Proof: Assume the supposition. By Theorem 1, ZFC proves notB. Hence ZFC refutes the existence of a green large cardinal. QED
    Postings #847,848,849 should be on the FOM email list 9/24/19,

  91. John Smolin Says:

    Scott #59

    “When I last looked at IBM’s materials on the web, there were no technical specs whatsoever”

    Try looking at which has a lot of information on the public devices.

    Also, if you are logged into IBM Q Experience and look at “your backends” on the right, you can download up-to-date (daily) calibration data for all the devices (T1s, T2s, 1- and 2-qubit gate errors for each gate, readout errors, etc.). Developers can access that same information directly in QISKit.

    If anyone wants the data for the non-public devices, I can make them available as well.

  92. Scott Says:

    John #91: Thanks so much!! Extremely helpful.

  93. adamt Says:

    Scott #87, “Gil went further than that, and explicitly conjectured that no quantum computing speedups are possible…”

    To what extent does Gil being wrong about this one hurt his other conjectures about realistic noise and error correction? Are they orthogonal? Correlated? How much?

  94. climater Says:

    Scott #50: it is not clear to me that nuclear energy is the right way to go. I think it will only further increase our energy consumption and serve to reduce the impetus to find more sustainable sources by delaying the point at which we run out of non-renewable sources of energy. This position reminds me of Steven Pinker’s chapter on the environment (which I think is the weakest link of the otherwise brilliant book), where he fantasises how a massive and cheap source of energy would solve everything.

    I feel the real revolution we need is in our consumption habits. The current ‘solutions’ to climate change all suffer from wishful thinking that we (by this I primarily mean the Western civilisation) can continue leading our happy, consumerist lifestyles thanks to future technological innovations and scientific discoveries. This does not, however, take into account that such radical solutions, if found, would again revolutionise our consumption habits (for which, alas, I don’t think there is a reasonable upper bound). This wishful thinking I described is not even a conscious and acknowledged thought, it is more like an instinctual assumption that is never questioned because we simply do not want to give up our luxuries.

    Further, anyone bringing up this aspect is easily dismissed as a Luddite, as though that accusation ends all arguments.

  95. Jay Says:

    adam #93,

    Gil agrees this is a big deal that would go against his predictions. However he guesses that there is something wrong and the results will get retracted. See his blog for the detailed reasons he provides. But you might as well just wait and see who retracts first.

  96. GA Says:

    I’m trying to understand the chain of inference from Google’s leaked result of quantum supremacy to theoretical computer-science “hardness” of the computation.

    Computing the exact probabilities of a random quantum circuit is proven hard, but computing the exact probability of a random algorithm is also an open problem, so what you really care about is approximation of computing the probability (up to epsilon), or even weaker, just sampling from a probability (also up to epsilon under some metric of comparing distributions).

    Their computer implements Random Circuit Sampling, and their cited “theoretical” hardness results are your paper from 2017, of QUATH => HOG, and as far as I understood from your paper, proving that approximation / sampling from a (random) quantum computer/circuit is hard is still an open problem (Am I wrong here? I’m not up to date with everything), and a difficult one. But you did make a compelling argument that even if QUATH was solvable, it will lead to new insights.

    Their actual benchmark uses cross-entropy benchmarking, called xeb in their paper, and defined as 2^n* [P(x_i)] _i-1 (Can’t type brackets). I could not find any ‘theoretical hardness’ paper at all using this benchmark, some results talk about different XEB using log but they prove these are not strong enough and can be reached classically.

    Are there any hardness results for their benchmark? I wonder why they would use that instead of the proven HOG, even for smaller input sizes, I would see more value in a benchmark which has theoretical roots. I feel intuitively like their benchmark is much more similar to the log variation of XEB than to HOG, but didn’t think it through completely.

    As for their gates, I understand they are not general random quantum gates, but instead they have a variation of iSWAP and controlled phase CZ. The hardness results that do exist also don’t address the limited gates, in how it changes the distribution of random circuits. Are those two gates at least universal, so that we have hope that this could be proved? Their statement was “but reliably generating a target unitary remains an active area of research”, so I assume they aren’t universal. I would love to see some heuristic argument as to why those two in particular are hard, especially given results like Gottesman–Knill theorem, it seems like some surprising gates do have classical simulation. iSWAP is just swap and phase gates, and CZ is phase gate only on the 11 state. Doesn’t feel like it could be universal to me but maybe I’m wrong.

    I probably missed some things, so I’d love it if you could point to papers filling the gaps between their results and a real theoretical statement. I don’t have the intuition to tell which gaps are important and which are not. I also don’t know which papers/results already exist and I can’t really search as I am not an academic, and don’t have full access to many papers, and you probably know the state of the art results.

  97. climater Says:

    STEM Caveman #45: To some extent I agree with Scott #46.
    It looks like religion has evolved to be a belief system that is most effective at ensuring its own survival. This means that the methods of religion you mention (scaremongering and propaganda, among others) are among the ‘best’ ways to organise large masses of people around a cause. This is why these landmark historic movements (which in many cases were also nonviolent) tend to have parallels with religion. Does that lessen the impact the movements have had? No. Are there alternatives (short of ultraviolent imposition) that have worked in the past? If so, I would love to hear of them.

  98. fred Says:

    ” I urge the climate strikers to keep their eyes on things that will actually make a difference (building new nuclear plants, carbon taxes, geoengineering)”

    There is no engineering solution to this – the earth simply can’t be sustained with over 7 billion humans.

  99. fred Says:

    What fraction of their budget/resources is Google spending on this quantum supremacy breakthrough/effort?

  100. Jacob Says:

    I have to say Dario Gil’s response is pretty disappointing. I have had a great experience working with Qiskit and the IBM Quantum Experience but IBM’s sour response makes me lose a bit of confidence.

    Scott, would it be correct to basically say that, no, this is not ‘universal’ computing on 53 qubits (it cannot perform any unitary algorithm that takes in 53 qubits), but that it is still a programmable computer on 53 qubits that can handle a much larger class of problems than any previous quantum computer could? Is there a name for the ‘noisy compatible’ class of problems?

    Just trying to narrow down the exact difference b/w this and D-Wave for my arguments with some skeptics. Is it just basically that D-Wave couldn’t even really be programmed to calculate anything else even in theory? Or is that D-Wave could only provide a speed up over classical computers on a very small (arguably zero) class of problems compared to googles computer.

  101. fred Says:

    When it comes to quantum supremacy… I’m torn (I’m hoping to get corrected).

    If it’s indeed the case it’s been proven already with just 53 qubits, it could be quite a bummer, actually.
    It depends on whether it’s linked to a breakthrough in scaling things up.
    If not, proving quantum supremacy was a competition in itself… maybe it would have been better for it to drag on for an extra decade or two, having the big corporate monsters pump resources into it just for bragging rights, until we get much closer to a practical QC.

    But now because the next milestone (building an actual practical QC) could still be so much more difficult/expensive, there might not be any clear “short term” return on investment to keep all the corporate monsters interested (unlike some more obvious thing like AI).

    After all, it’s not like Google/Facebook/… have been rushing to tackle other tough expensive engineering challenges that could make a huge difference (like building experimental Tokamaks).

    I understand that for someone who’s devoted to theoretical quantum computation, that’s neat. But even Scott said a few times that not being able to prove quantum supremacy could have been even more interesting (it would have required a re-examination of QM)… I have a feeling we’re now in the same situation as finding the Higgs Boson… nice! But it was expected, so, what next? Spend 10 times more building a even larger LHC?

  102. Robert Michaels Says:

    Israeli TCS guy: Sorry, but quite obviously, there was enough hard evidence for Israeli Attorney General Avichai Mandelblit to announced his decision to consider indicting Prime Minister Benjamin Netanyahu with multiple counts of graft. Now he will be duly charged, arrested, and face a jury of his peers.

  103. asdf Says:

    Jacob #100, I think the problem DWave’s “QC” solved was also efficiently solvable on a classical computer, unlike this new thing.

  104. White Trashionalist Says:

    “My daughter Lily, age 6, is old enough to understand the basics of what’s happening and to worry about her future.”

    Is she scared of any specific harm coming to her future self or is it a more general “the world being warmer will be bad?”

    JimV #17: “Population size is in fact the driver on that and many other bad effects. The Earth will support just so many humans, and we are already exceeding our budget on renewable resources like fresh water (using up stores faster than they replenish).”

    Non-renewable freshwater is a rounding error, easily solvable by more irragation projects with renewable freshwater. The Earth can only support just so many humans, but the limit is way higher than our current and projected populations. Overpopulation is a myth.

    fred #101: “I think it will only further increase our energy consumption and serve to reduce the impetus to find more sustainable sources by delaying the point at which we run out of non-renewable sources of energy.”

    Which is a bad thing why? I always thought that the problem was carbon emissions and if you could get rid of them, you’d solve the problem, but it seems that for a lot of people, certain solutions(solar and wind energy and reducing consumption) are good for their own sake and it’s somehow “cheating” to reduce emissions without them.

  105. sofa Says:

    maybe stick to computers.
    your politics is horrific and evil.

  106. Job Says:

    D-Wave’s machine did not show a meaningful improvement over classical algorithms.

    If i remember correctly, it was just better at solving different instances than the classical version. And then the classical algorithm was updated.

    Plus, wasn’t it also an adiabatic QC, basically running quantum annealing for solving optimization problems? E.g. using quantum tunneling, which is not even well established?

    That’s very different from what Google is going for with random sampling, which (as cheesy as it is) is on stronger theoretical ground.

    In the sense that, unlike optimization problems, we know that a QC can easily sample the output of a random quantum 50ish qubit circuit, whereas no existing classical machine can.

    It will be harder to argue against a quantum supremacy result since it’s unlikely that there is a trivial change to a classical algorithm that will bring it close to what a QC is able to do.

    IMO you’d have to show that the set of random circuits used in the supremacy experiment have some property that can be exploited by a classical simulator – like, the circuits can be implemented using a non-universal gate set, or using sufficiently fewer gates/qubits to make the simulation easier.

    So as with D-Wave there could be some back and forth, but Google starts off at a much stronger position.

    That’s my understanding, please correct if i’m mistaken.

  107. Scott Says:

    sofa #105: So that I can better serve you in the future, could you clarify which part of what I said here was the evil part? I’m genuinely stumped. I’m not even sure whether I’m evil for being too far to the left or not far to the left enough.

  108. Scott Says:

    adamt #93:

      To what extent does Gil being wrong about this one hurt his other conjectures about realistic noise and error correction? Are they orthogonal? Correlated? How much?

    Those would be great questions for Gil himself, come to think of it.

    I see that he’s now dug in his heels and predicted that the Google result “will not stand,” which certainly suggests that he sees “no quantum supremacy” as a central and non-optional part of his worldview.

  109. Scott Says:

    fred #99:

      What fraction of their budget/resources is Google spending on this quantum supremacy breakthrough/effort?

    A minuscule fraction. Couldn’t be more than a hundred million or two.

  110. Scott Says:

    Jacob #100: It’s “universal” in the sense that you have a reconfigurable and fully universal set of 2-qubit gates. The only sense in which it’s not “universal” is that you’re extremely limited both in the number of qubits (53) and in the depth (about 20). No, I don’t think there’s any clean characterization of the class of problems solvable with those resources—it’s just some messy finite truncation of BQP (or rather SampBQP).

  111. asdf Says:

    Scott #107, I think Sofa #105’s comment was directed at White Trashionalist #104.

  112. Markant kvantegennembrud: Google har opnået ‘quantum supremacy’ | Ingeniøren | michaltheil Says:

    […] dagen før artiklen i Financial Times skrev han på sin blog dette:Luk […]

  113. Gabriel Says:

    Regarding Greta’s ridiculous alarmism. Here’s potholer54 arguing that it’s important to represent science accurately, and that hyperbole in the public discussion does more damage than good, because once you start exaggerating, people stop believing anything you say. In this video potholer54 is addressing AOC, not Greta, but it’s the same thing.

  114. Mateus Araújo Says:

    Scott #88: Thanks for the answer, I stand (gladly) corrected, as this is what I thought should be true.

    But now I’m confused about why one would need strong simulation to verify the output of a quantum circuit. If you don’t trust the weak simulation code, why should you trust the strong simulation code? Or are they afraid of estimating the wrong probabilities due to statistical fluctuations?

  115. Scott Says:

    Jay #95:

      Gil agrees this is a big deal that would go against his predictions. However he guesses that there is something wrong and the results will get retracted. See his blog for the detailed reasons he provides. But you might as well just wait and see who retracts first.

    History suggests a third possibility: that many QC skeptics will never, ever admit defeat, but will simply become increasingly irrelevant, much like the people who still search for loopholes in the Bell inequality experiments.

  116. Scott Says:

    GA #96: Sorry for the delay in answering you. You’re absolutely right that, for problems like “spoof the linear cross-entropy test,” our complexity-theoretic understanding is in an extremely unsatisfactory state right now. In practice, just like with applied cryptography, what’s going to convince the community is simply if enough time passes, and lo and behold, no one does manage to find some amazingly fast classical spoofing algorithm. (Including, e.g., IBM, which has done excellent work in the past on classically simulating random quantum circuits, and which now has an enormous motivation to puncture Google’s balloon.) Indeed, the community would still want that sort of empirical confirmation, even if we had complexity-theoretic hardness arguments much stronger than what we have.

    Having said that, it’s absolutely trivial to modify the “QUATH=>HOG” hardness reduction in my and Lijie’s paper to talk directly about linear cross-entropy, rather than about the slightly different HOG test that Lijie and I considered there. Let me know if you’d like me to write that out for you.

  117. Scott Says:

    Jacob #100: Indeed, the response from IBM seemed extremely petty to me. Quantum supremacy is not a sufficient condition for doing anything useful with a QC, but it’s obviously a necessary condition. So the right thing to do would’ve been to congratulate the Google group on its accomplishment (if indeed it holds up), and then simply explain how IBM is more focused on other important milestones X, Y, Z.

    D-Wave’s program, I think, was done in by multiple issues: their qubits weren’t nearly good enough, their Hamiltonians (until very recently) were purely stoquastic, their temperature was too high compared to the spectral gap, and even if all those issues were resolved, it’s still never been clear at a theoretical level whether to expect any practically important speedups from adiabatic optimization (other than the Grover speedup). The hard part–one that I could imagine occupying future historians of quantum computing–will be to disentangle which of these factors were more important than the others.

  118. Scott Says:

    fred #101:

      But it was expected, so, what next? Spend 10 times more building a even larger LHC?

    Fortunately, in this case, as I said in response to Q15 in the other post, we have at least two obvious and compelling “what nexts” (quantum simulation and useful error-correction).

  119. Scott Says:

    White Trashionalist #104:

      Is she scared of any specific harm coming to her future self or is it a more general “the world being warmer will be bad?”

    I mean, she knows that smoke coming out of cars and factories and so forth is making the world hotter—noticeably hotter than it was for her parents and grandparents—and that that can’t go on for much longer. Without being prompted with the ideas, she asked why people don’t solve the problem by riding bikes instead, or inventing new kinds of cars that don’t emit the smoke.

  120. Scott Says:

    Mateus #114:

      But now I’m confused about why one would need strong simulation to verify the output of a quantum circuit. If you don’t trust the weak simulation code, why should you trust the strong simulation code? Or are they afraid of estimating the wrong probabilities due to statistical fluctuations?

    Tell me, how do you use one sampling procedure to verify another one? They’re both just outputting samples, and you’ll have to wait an exponential amount of time before you ever even see them output the same sample.

    All the known procedures for verifying the outputs of a sampling device, involve calculating the theoretically predicted probabilities for the samples that were observed, and then doing statistics with those probabilities. Or in other words: strong sampling.

  121. Scott Says:

    Everyone: I’m going to close down this thread, because it’s too much for me to deal with this one at the same time as the supremacy FAQ one. Please get in any final comments today.

  122. Raoul Ohio Says:

    Unlike Gil Kalai, I have little advanced knowledge on QC related topics, but I do have a rather wide knowledge of CS, Math, and Physics.

    I have been making fun of controlled fusion since about 1970, even as CF breakthrough after breakthrough occur, but I still have to pay my electric bill. I don’t predict that the same thing will happen with QC, but it certainly seems plausible.

  123. sofa Says:

    scott #107: “So that I can serve you better..”

    You should not serve any master.

    People are free (or should be). All should live free.
    Also, no one should (i) steal property from others, (ii) force others at gunpoint to comply with their wishes. Denying life, liberty, and property at gunpoint- That is taking slaves.
    Or 51% wolves outvoting 49% sheep, on what’s for dinner.

    Yet, the candidates you publicly support, speak openly about their desire to do those evil things. [You publicly support this on your blog post, so i ask about it.]

    I urge you to re-think a position that would have you force people against their will, to do what you want them to do, at gun point. It is evil to suggest such a thing. Openly supporting slavery – Well that is bad.

    Both D and R both support many aspects of that. And both claim that the spectrum is linear. Yet, Liberty is not along their line: Liberty is orthonormal to their attempts at slavery.
    The particular candidates you mentioned- are openly seeking to enslave others using deadly force of the state.

    Please think about your support for the national socialist democratic party (nsdp) philosophy.
    Maybe, choose liberty, rather than slavery.
    Or not.

    Free men get to choose.
    And from time to time, men choose to discuss and contemplate fundamentals.

    [reasoned thought in evidence on the blog- makes me think that you just haven’t had a chance to contemplate the fullness of the slavery offered by those candidates, yet.]

  124. Scott Says:

    sofa #123: Alright, evil because I’m not libertarian. That clarifies it—thanks!

  125. sofa Says:

    [assigning labels= excuse for not thinking it through at this time]

    Be free. Think for yourself.
    Do not compel others, at gunpoint via the state, to follow your orders.
    Do what you want, in a responsible manner that also lets others be free.
    -or- be a slaver. and continue to revel in it. just take responsibility for the future you create.

    the foundations of “Liberty” are now ‘double-plus-ungood’ in government school training, so you may not have been exposed to or thought through some topics.
    But rational people discover it, in time.

    in time then. hopefully.
    “reason be unto you.”