My ACM TechTalk on quantum supremadvantage
This Erev Yom Kippur, I wish to repent for not putting enough quantum computing content on this blog. Of course, repentance is meaningless unless accompanied by genuine reform. That being the case, please enjoy the YouTube video of my ACM TechTalk from last week about quantum supremacy—although, as you’ll see if you watch the thing, I oscillate between quantum supremacy and other terms like “quantum advantage” and even “quantum supremadvantage.” This represents the first time ever that I got pushback about a talk before I’d delivered it for political reasons—the social-justice people, it turns out, are actually serious about wanting to ban the term “quantum supremacy”—but my desire to point out all the difficulties with their proposal competed with my desire not to let that issue overshadow my talk.
And there’s plenty to talk about! While regular Shtetl-Optimized readers will have already heard (or read) most of what I say, I make some new comments, including about the new paper from last week, the night before my talk (!), by the USTC group in China, where they report a quantum supremacy experiment based on random circuit sampling with a superconducting chip, this time with a record-setting 60 qubits and 24 layers of gates. On the other hand, I also stress how increasing the circuit fidelity has become a much more urgent issue than further increasing the number of qubits (or in the case of BosonSampling, the number of photons), if our goal is for these experiments to remain a couple steps ahead of classical spoofing algorithms.
Anyway, I hope you enjoy my lovingly handcrafted visuals. Over the course of this pandemic, I’ve become a full convert to writing out my talks with a stylus pen rather than PowerPointing them—not only is it faster for me, not only does it allow for continuous scrolling rather than arbitrary divisions into slides, but it enforces simplicity and concision in ways they should be enforced.
While there was only time for me to field a few questions at the end of the talk, I later supplied written answers to 52 questions (!!) that I hadn’t gotten to. If you have a question, please check to see if it’s already there, and otherwise ask away in the comments!
Thanks so much to Yan Timanovsky for inviting and organizing this talk, and to whurley for hosting it.
Follow
Comment #1 September 15th, 2021 at 7:29 pm
“convert to writing out my talks with a stylus pen rather than PowerPointing them”
The lore says that Amazon got so successful because they banned PowerPoint slides in meetings. Instead people are encouraged to just write out notes as a free-form text and give out print-outs to participants.
Comment #2 September 15th, 2021 at 9:01 pm
Do you mind an extremely ignorant question about counterfactual quantum computation? How does the complexity class of the problem affect the resources you need in the counterfactual setup? Do you need exponentially many more measurements to answer problems in EXP vs P?
Comment #3 September 15th, 2021 at 9:39 pm
Scott McKuen #2: In “counterfactual computation”—something people make a much bigger deal about than it is—you still have to invest at least as much time and space to do your computation as you would’ve needed ordinarily (somewhat more, actually). It’s just that, like with the Elitzur-Vaidman bomb (to which counterfactual computation is closely related), you can say that the branch of the wavefunction that ran the computation never had a large amplitude—the point being that it would have had a large amplitude if its output had been other than what it is. But this is a matter of perspective and interpretation, rather than of any savings in computational resources. Indeed, if you want “the total probability that your time-T computation was ever run” (for some definition of that phrase) to be ε, you’ll need to invest ~T/ε time.
Comment #4 September 16th, 2021 at 12:24 am
Perhaps the politically correct term you’re looking for is “classical inferiority”.
Comment #5 September 16th, 2021 at 4:10 am
> This represents the first time ever that I got pushback about a talk before I’d delivered it for political reasons—the social-justice people, it turns out, are actually serious about wanting to ban the term “quantum supremacy”
Can you say a bit more about this? Don’t want to sound like poking the wasp nest too much, but I’m genuinely curious about your experience here. Did you receive complaints after submitting the abstract? Did you receive them afterward? Where did the pushback come from?
Comment #6 September 16th, 2021 at 4:57 am
Tommaso G #5: My contact person at ACM and my department chair both relayed to me that they’d heard/received complaints about it, although both were sympathetic and neither ordered me to do anything differently. To my ACM contact, I proposed to give a completely different talk (about shadow tomography of quantum states and differential privacy) — I even sent them the other title and abstract — explaining that I didn’t trust myself to speak for an hour about quantum supremacy without ever slipping up and saying the term “quantum supremacy.” He replied no, it was fine, I should just use the original title. So I did, but I added the prologue that you can listen to.
Comment #7 September 16th, 2021 at 7:43 am
I lol’d at 13:00: “So I drew these galaxies to give you a sense…”
Doodling is another advantage of handwritten notes!
Comment #8 September 16th, 2021 at 7:51 am
Nick #7: Glad you liked that! 🙂 In moving to handwritten talks, I was partly inspired by Roger Penrose, who hand-draws spectacular illustrations for his every book and lecture that are like direct windows into his brain. I can’t draw nearly so well, and there’s less in my brain than there is in his, but maybe I could provide such a window anyway.
Comment #9 September 16th, 2021 at 9:32 am
Scott:
This represents the first time ever that I got pushback about a talk before I’d delivered it for political reasons—the social-justice people, it turns out, are actually serious about wanting to ban the term “quantum supremacy”
If I were you I would react to such comments like a lead brick reacts to a fruit fly.
Comment #10 September 16th, 2021 at 11:44 am
I am not a social-justice people, but I really don’t like the term “quantum supremacy” because of its connotation. I read on this blog (in the comments) and elsewhere the proposal of “quantum primacy” which sounds very fine. I think this would be a great workaround. That being said, it is of course unacceptable that you (or others) be intimidated for using a scientific term that is the consensus!
These are actually two distinct issues:
1. It is perfectly normal for an individual to use the term that is agreed upon in the community.
2. It is a good idea for the community as a whole to question the terms chosen and evolve them, if necessary.
Comment #11 September 16th, 2021 at 4:23 pm
> the social-justice people, it turns out, are actually serious about wanting to ban the term “quantum supremacy”
Wasn’t this a Monty Python sketch ?
Comment #12 September 16th, 2021 at 6:06 pm
From Jeff Bezos 2017 letter:
We don’t do PowerPoint (or any other slide-oriented) presentations at Amazon. Instead, we write narratively structured six-page memos. We silently read one at the beginning of each meeting in a kind of “study hall.” Not surprisingly, the quality of these memos varies widely. Some have the clarity of angels singing. They are brilliant and thoughtful and set up the meeting for high-quality discussion. Sometimes they come in at the other end of the spectrum.
In the handstand example, it’s pretty straightforward to recognize high standards. It wouldn’t be difficult to lay out in detail the requirements of a well-executed handstand, and then you’re either doing it or you’re not. The writing example is very different. The difference between a great memo and an average one is much squishier. It would be extremely hard to write down the detailed requirements that make up a great memo. Nevertheless, I find that much of the time, readers react to great memos very similarly. They know it when they see it. The standard is there, and it is real, even if it’s not easily describable.
Here’s what we’ve figured out. Often, when a memo isn’t great, it’s not the writer’s inability to recognize the high standard, but instead a wrong expectation on scope: they mistakenly believe a high-standards, six-page memo can be written in one or two days or even a few hours, when really it might take a week or more! They’re trying to perfect a handstand in just two weeks, and we’re not coaching them right. The great memos are written and re-written, shared with colleagues who are asked to improve the work, set aside for a couple of days, and then edited again with a fresh mind. They simply can’t be done in a day or two. The key point here is that you can improve results through the simple act of teaching scope – that a great memo probably should take a week or more.
https://www.aboutamazon.com/news/company-news/2017-letter-to-shareholders
Comment #13 September 16th, 2021 at 10:59 pm
A better solution would be if white-supremacy groups change there terminology to White-Advantage or White-Primacy.
Comment #14 September 17th, 2021 at 4:18 am
I am just waiting for them to attempt banning the word “supremum” in mathematics. I personally would never bow to such requests. +1 for the handwritten notes, it’s just a lot easier and convenient to create and can be as easily to read.
Comment #15 September 17th, 2021 at 6:29 am
Last post was sent prematurely. Sorry.
I just wonder when you will change the name of this blog since “shtetl” is offensive to some people. This madness must be stopped, and if people like you are not willing to fight because of their “desire not to let that issue overshadow m̶y̶ their talk” or whatever, the fight is lost.
Happy new year, Scott. שנה טובה
Comment #16 September 17th, 2021 at 8:03 am
Scott #6:
OK, look, either I give a talk about “quantum supremacy”, or about SHADOW TOMOGRAPHY OF QUANTUM STATES AND DIFFERENTIAL PRIVACY. Choose wisely.
This is brilliant XD
Comment #17 September 17th, 2021 at 8:05 am
Even if Quantum Supremacy is a thing, Classical Computations Matter.
Comment #18 September 17th, 2021 at 8:09 am
What bothers me with the term Quantum Supremacy is that “supremacy” suggests an overwhelming advantage across the board, but we all know very well that it’s simply not true.
Comment #19 September 17th, 2021 at 8:53 am
Tommaso G: I worked for a whole year on my and Guy Rothblum’s shadow tomography and differential privacy project, I’ve given many talks about it before, and I would’ve been happy to give my ACM TechTalk about it! It wasn’t in any way, shape, or form a joke proposal. But yeah, they chose quantum supremacy.
Comment #20 September 17th, 2021 at 9:26 am
fred #17, 18
I think only quantum supremacists would claim that quantum computers will always outmatch classical computers.
#ClassicalComputationMatters #NoVoiceToQuantumSupremacists ;- D.
Comment #21 September 17th, 2021 at 9:35 am
Scott, is there a definite complexity class for “simulating a quantum physical system”, at least if we consider “the hardest” of such instances?
It’s really hard to comprehend the number of states in superposition in a 2,000 or 2 million qubits QC.
We often hear that 2^2000 is more than the number of particles in the known universe.
But we can start to imagine that kind of number in a classical universe by considering what can be displayed on a typical 1920×1080 computer screen, where each pixel is only either black or white (state 1 or state 0).
We have ~2^2,000,000 possible distinct states.
Those states have to include every page of text ever written or that could ever be written by humanity and by any alien civilization (including all versions including every possible permutation of typo and grammatical error)…
and also every frame of every movie that was ever shot or could ever be shot (take any actual movie you know, and then imagine creating an near infinite number of sequels for it), and then additional versions of all these where any character’s face is replaced by every possible permutation of the faces of all the humans that ever existed (also consider the age as a permutation), and then additional versions including all the permutations of every character holding every possible small object ever invented by humans, then consider each character wearing all the possible permutations of every piece of clothing that was ever created, and on top of that every other imaginable near infinite list of arbitrary modifications.
And once you’re done accounting for all those variations, you still have only considered a ridiculously infinitesimal fraction of what could be displayed on that screen.
And the set of all those possible images is what a quantum computer with 2,000,000 qubits would be “manipulating” all at once.
Comment #22 September 17th, 2021 at 10:26 am
Thanks Scott, it’s a superb presentation, a very clear and honest assessment of the state of the art, I learned a ton!
Comment #23 September 17th, 2021 at 10:49 am
I don’t understand your handling of the word issue. IMO either give it up or don’t. Possibly still make your case (to protect your intellectual independence), but after that either stick to “supremacy” or “advantage”. Either keep the word or erase it, don’t strike it out so it’s still visible, and don’t make hybrid words or “oscillate”. If you’re worried you would slip up due to using “quantum supremacy” for too long, practice on 10 sentences and in the unlikely event of slipping up anyway, you can correct yourself on the spot (or not if you forget to). To me it came off as some kind of bad energy (contempt?) towards the issuers, for which a science talk probably isn’t a great place. And meanings, especially technical ones, like to have a single word for themselves. [that’s all my feelings and guesses, maybe you have a great reason for it all]
———-
Since this comment section seems to be dominated by the “supremacy” camp, for the sake of variety I’ll offer my thoughts on the object-level issue. For the record, my highest achievement in Quantum Anything is that I can maaybe define BQP 😉
I personally can’t help but find it very reasonable if someone feels uncomfortable with the phrase “quantum supremacy”. It’s not that there are bad uses of the word “supremacy”. The word “supremacy” is rare and the phrase “white supremacy” is common, and there is no other common phrase with “supremacy” in it (look here for some of the numbers) . This results in a strong association between the word and the phrase. Such associations are really no joke – they can even result in the swallowing of the common word in the phrase by the uncommon one, like with “conspiracy [theory]”. And “quantum supremacy” has the same structure as “white supremacy” (as opposed to, say, “military supremacy” which is between two militaries).
As for your “let’s reclaim it” argument, let’s remember that word reappropriation isn’t exactly an universally applied, uncontroversial practice. And this would be a rather atypical case of it, usually a derogatory term is reclaimed to take it away from its hateful users. Also, perhaps this is just a tactical error (i.e. you don’t really believe there is any reclaiming to do), but this argument seems to contradict any “words can’t go bad, this isn’t any issue at all” argument.
———-
Otherwise, great talk. Though I’m a little sad for the loss of the “Quantum Computing in one slide” slide. Though now that I can maybe define BQP, I’m not sure how accurate it was given the lack of mention of reversibility.
Comment #24 September 17th, 2021 at 10:55 am
Scott #19: yes, yes, I know 🙂 but still sounds funny
Comment #25 September 17th, 2021 at 11:15 am
fred #21: BQP was invented for exactly that purpose, to capture the set of problems that’s efficiently solvable using the resources of quantum physical systems. The one major limitation here is that BQP is a class of decision problems (languages) only. But we can easily remedy that by considering generalizations like FBQP for functional problems or SampBQP for sampling problems, or even classes of problems that involve preparing quantum states or applying unitary transformations. (Keep in mind, though, that the elements of complexity classes are not computations; they’re problems that you use computations to solve.)
Comment #26 September 17th, 2021 at 2:55 pm
JoshP #15:
I just wonder when you will change the name of this blog since “shtetl” is offensive to some people.
If the actual shtetls were offensive enough to be wiped out in history’s most infamous genocide, I wouldn’t be surprised if the word were “offensive to some people” as well.
This madness must be stopped, and if people like you are not willing to fight because of their “desire not to let that issue overshadow m̶y̶ their talk” or whatever, the fight is lost.
I followed probably the same thought process as many, many academics in deciding how to present some material:
(1) Can’t I just make a choice that will make everyone happy, including myself?
(2) No, I can’t?
(3) Then at least let me show everyone that I weighed all the relevant considerations and wasn’t oblivious to any of them!
Comment #27 September 17th, 2021 at 3:16 pm
Major QM and QIT milestone:
The first (?) “Numerical Recipes in Quantum Information Theory and Quantum Computing” book was published this week.
Modestly surprised that the code is in Fortran. In the venerable “Numerical Recipes” tradition, there might be Pascal and C versions coming soon.
Comment #28 September 17th, 2021 at 4:52 pm
> The lore says that Amazon got so successful
Funny, I always thought it was a mixture of regulatory capture, monopolistic anti-competitive practices (eg competing against their own clients), political lobbying, and campaign contributions.
Comment #29 September 17th, 2021 at 11:38 pm
Can we interpret the double-slit experiment as solving a black-box problem, like Simon’s?
In the experiment, I’m thinking the emitter would be the quantum black-box.
Then the secret value could be the wavelength of the particles emitted by the black-box?
The two slits would correspond to the quantum circuit, and the circuit’s output would be the position of the particle as given by the detector (e.g. on a number line).
The idea is that we’d figure out the wavelength by sampling outputs.
E.g. each particle position would tell us a little bit about the secret value, since they would exclude the interference bands.
We’d end up with a system of equations and then solve for the secret value, like in Simon’s algorithm.
On the other hand, since the interference pattern only shows up depending on the length of the gap between the slits (IIUC), i’m guessing we’d also need to put the system into a superposition of all possible gaps?
I can sort of visualize Simon’s algorithm as sampling from a superposition of double-slits.
E.g. one double-slit per output value in Simon’s 2-to-1 black-box function.
Does this make sense?
Comment #30 September 18th, 2021 at 5:53 am
Job #29: I’d think of the double-slit experiment as much more closely analogous to the Deutsch-Jozsa algorithm: you have two branches and are interested in the relative phase of the amplitudes contributed by both. (To complete the analogy, we’d imagine that you vary the relative placement of the slits, rather than closing one of them, then use the interference pattern to deduce something about where the slits were placed.) Simon’s algorithm, though of course it also comes down to 2-term interference at the end, involves a function with exponentially large domain and range and a secret periodic structure, which is a lot of additional structure that’s not present here.
Comment #31 September 18th, 2021 at 8:38 am
Scott,
Can you please, *please*, start using the term Quantum Pikachu instead? You might get some flak from PETA about appropriating the historical exploitation of Pokemon; but otherwise I feel like the best way to deal with the polarized excesses of the right or left is to unite all the proverbial dogs with their coveted cars ad absurdum.
This both illustrates the arbitrary Tinkerbell nature of language which could mean anything if we believe in it hard enough, and also a glimpse what a post-woke supremacy world might look like left to its own devices. Very practically, it’s likely to take some of the steam out of this bikiest of sheds debates, get some comic relief, and let serious (not to be confused with people who take themselves too seriously) people get back to work. Those not in on the take will piece it together from the context, another wonderful aspect of language known as pragmatics.
Comment #32 September 18th, 2021 at 9:25 am
Ebigram #31: Thanks! I might try that out the next time there’s a quantum pikachu experiment to blog about, or a new development in the theory of quantum pikachu.
As for how likely people are to understand me, though: when I commented in the talk that claims of revolutionary near-term applications of quantum computing to machine learning were “>95% BS,” I got a slew of earnest questions about what “BS” stood for.
Comment #33 September 18th, 2021 at 10:30 am
Very nice talk Scott. I really do like the continuous format as opposed to the typical power point format – it worked very nicely in your talk.
Comment #34 September 18th, 2021 at 2:42 pm
Scott #30,
With Deutsch-Jozsa the secret value is a single bit (constant vs balanced), plus a single bit of output.
So the detector would just beep when it detected a particle.
That seems fine, but Deutsch-Jozsa’s algorithm also puts the output bit into a superposition.
What would be a good analogy for that step?
I see the emitter as starting out in an even superposition (corresponding to the first set of H gates plus the black box).
Then the double-slit would correspond to the second set of H gates.
With Deutsch-Jozsa, the detector should be silent if the black-box is constant and beep if it’s balanced.
Comment #35 September 18th, 2021 at 2:43 pm
Scott #32: Really? Everyone knows that’s Boson-sampling, or at least that’s what my quantum GPT-3 intelligent NLP assistant tells me. But if I had to hold my breath, for fear of hypoxia, I’d sooner wager on “ML Inferiority” than Quantum Supremacy (no offense, more of an ML skeptic than a QC believer).
While I sense a generation gap has kept you from embracing my infantile millennial inclination to shoehorn pokemon into every topic, I still think satire, which you’ve shown to be one of your many strengths, is the way to go here. Since I’m already giving you my unsolicited suggestions: maybe “quantum-totally-better-than-classical-in-this-case-where-it’s-not-so-great-yes-even-spoofing” or shortened to just quantum TBTC eliding the more gratuitous part. Kinda has a PAC learning vibe to it.
Comment #36 September 18th, 2021 at 3:13 pm
On a more serious note, would just like to join the chorus in praise of your talk. it’s not my area, so most of what I know has been through your writings/presentations; so I hope you know that whatever pettiness from a vocal minority you have to countenance, there are many more like myself who have benefited from your platform who’d be hurt by measures to interfere with or muzzle it. I find that very real material virtue to be oddly absent from these discussions, which I believe there are far more discreet, gentler, respectful ways of resolving than invoking the full force of *Nature*. It’s the means here that are exactly what I find suspect here, even moreso than the ends, however dubious.
Comment #37 September 18th, 2021 at 3:38 pm
I guess a double-slit analogy for black-box problems fails to capture the fact that the answer is actually found by reading the input value, rather than the output?
E.g. for Deutsch-Jozsa, it’s not the detector that should stay silent when the black-box is constant. Instead, it’s the emitter that would be measured to be in some empty/null/zero/silent state.
I personally would need to know about more the emitter side of the experiment in order to make this analogy work.
Comment #38 September 19th, 2021 at 6:06 pm
Can I praise you for being willing to give a written talk despite (ahem) poor handwriting? Seriously, this is awesome. I like written talks, and my handwriting is bad, so it is good to see others do this. Many of the people who do written talks have intimidatingly good handwriting, so the contrast is nice. And it is totally readable!
Comment #39 September 19th, 2021 at 6:08 pm
matt #38: My handwriting isn’t quite as bad as it looks! 🙂 It’s just that I still don’t fully have the hang of writing on my laptop screen with a stylus pen.
Comment #40 September 19th, 2021 at 6:55 pm
Scott 39: tablets are much better for that. Screen lays flat and doesn’t wobble. At minimum, put something solid behind your laptop screen to stop wobbling.
Comment #41 September 19th, 2021 at 10:55 pm
RO two cents worth on “writing vs. typing presentations”:
There are a lot of issues.
One is speed. I can type MUCH faster than write, especially if I am trying to be readable. I think a speed bump of 5x for typing is a realistic estimate.
On the fly editing and formatting is nice.
And spell check. I hate misspelling words when I have an audience. Most spell checkers are pretty lame, but copy and paste into Google, get the correction, and paste back takes about 1.5 seconds.
Distinct fonts work a lot better with typing. This is essential for text interspersed with code examples. Achieving the distinction between Calibri and Courier New by hand ain’t gonna happen.
Beauty is in the eye of the beholder. How many of us behold our writing as better looking than typing?
The amount and type of math notation is a key consideration.
Given these issues, my preferred method for online lectures (in programming and math) is a MS Word doc with a font size around 16 to 24 or so. For MOST math, ALT++ (i.e., ALT key and + key) pops up Equation Editor. EE is very lame, but it mostly works OK as a WYSIWYG LaTeX editor. Unfortunately it does not understand matrices, etc., and you have to use the menus, which is painful. When done, save as a .pdf and post it.
Comment #42 September 20th, 2021 at 9:42 am
Scott
Is there a way to describe the superiority of the Quantum Fourier Transform over the classical DFT in terms of purely classical inputs and outputs or is the superiority of the QFT only exploitable when used as a component of another quantum algorithm, like Shor’s ?
Comment #43 September 20th, 2021 at 10:48 am
Gerard #42: The difficulty with that question is that the QFT takes a quantum state as input and produces another quantum state (corresponding to the DFT of the first state) as its output. So, while you could call the QFT “exponentially faster” than the classical DFT, as a function of the size N of the vector being Fourier-transformed, really it’s not solving the same problem, and should be seen as different and incomparable. Like you said, only when the QFT is used as a subroutine in some larger quantum algorithm with classical inputs and outputs, such as Shor’s algorithm, does a direct quantum vs. classical comparison make sense.
Comment #44 September 22nd, 2021 at 9:08 am
American “social-justice” people are highly sensitive to the connotations of the s-word, while they continue to designate themselves with the name of a whole continent, oblivious to the existence of three dozen fellow nationalities. Interesting contradiction.
Comment #45 September 22nd, 2021 at 10:37 am
Marcelo #44: I confess that I’m not sure which continent you’re talking about!
Comment #46 September 22nd, 2021 at 12:56 pm
People from the USA call themselves American. But Marcelo just called us American too. I’m not sure what to make of that.
Comment #47 September 22nd, 2021 at 5:55 pm
Well people from the USA *are* American. It’s just that ~two-thirds of Americans aren’t from the USA.
Comment #48 September 23rd, 2021 at 7:14 pm
Given the obvious (though unfortunate) linguistic link between “quantum supremacy” and “white supremacy,” it seems to me it’s worth some effort thinking of a better name, even for the purely selfish reasons that for essentially zero cost it removes a negative connotation from an important scientific advance and potentially makes the field more welcoming to students in underrepresented minorities. If you buy that premise, then the two arguments against changing the name — (1) institutional inertia, and (2) linguistic implications of quantum computing overtaking classical computing — are really weak arguments. For (1), you are a leader of the field, you are surely someone who actually can make an influence in changing the language. I’m not even sure I can take (2) seriously as an argument… it almost sounds like you are saying that “quantum supremacy” is the *unique* string of 2-3 English words that captures your meaning. What about “quantum ascendancy” or “quantum superiority” or “quantum primacy” or “quantum leadership” or “the next wave of quantum computing” or “the next stage of quantum computing” or “the quantum frontier”? If (1) and (2) are really your arguments, it reads to me much more like you would rather use your privilege as a powerful person in this field to mock people who point out issues that affect underrepresented minorities if they don’t affect you directly, rather than trying to use your position to make a positive change, *at literally zero cost.*
Just my 2 cents.
Comment #49 September 23rd, 2021 at 10:40 pm
As much as I would love to see terminology that tweaks the noses of the Perpetually Aggrieved (quantum sexism and imperialism sound fun), “quantum supremacy” is a mediocre term. It has the exaggerated sci-fi/fantasy chest beating feel of talk about Princes Of The Universe or Galactic Uber-Centurions, as though it is beyond ordinary concepts of supremacy, it is QUANTUM supreme, man! Quantum computing’s killer apps are too wonky to that get drunk on the hyper super duper power of it all.
“Quantum speedup” is precise and matches the language used elsewhere.
Comment #50 September 24th, 2021 at 11:59 am
> banning the word “supremum” in mathematics.
Broke: ban the word “supremum”
Woke: ban the *concept* “supremum”
This is a serious suggestion and would have good effects. I explained some of the reasons in the Busy Beaver discussion with Scott in the stricter situation of integer Max, but it applies to any type of extremal quantity (max, sup, lim sup, ess sup) and the language habit of metaphorically conjuring such a quantity into existence just by talking as though it is out there in the universe somewhere, like the winning strategy in chess or the number of neurons in Biden’s brain. The problem isn’t only that this is nonconstructive, but that its a “category error” — something that is naturally only an estimate, a target for inequalities, is treated as a number.
Comment #51 September 24th, 2021 at 12:55 pm
STEM Caveman #50
I have similar feelings about the concept of infinity. I suspect that mathematicians throw it around far too freely and that therein lies the root cause of the paradoxes that have plagued mathematics and logic since Russell, Gödel, etc.
Note also that no engineer will ever need a mathematics of infinity. For practical purposes it will always suffice to restrict ones analysis to some finite N that is “large enough”.
These are just my intuitions though, it’s not like I have a complete theory of how to redo all of mathematics without infinity.
Comment #52 September 24th, 2021 at 1:39 pm
Gerard #51: You have it exactly backwards! Russell and Gödel were part of the early 20th century movement that finally clarified things, that explained how we’re able to use formal systems that sensibly talk about or refer to infinity, even while we ourselves only ever manipulate finite strings of symbols.
Comment #53 September 24th, 2021 at 3:39 pm
Scott #52
> Russell and Gödel were part of the early 20th century movement that finally clarified things, that explained how we’re able to use formal systems that sensibly talk about or refer to infinity, even while we ourselves only ever manipulate finite strings of symbols.
I don’t see how you can make that claim when the major result of that work, Gödel’s Incompleteness Theorem, states almost the exact opposite, ie. that you can’t have a complete and consistent theory of infinity based on a finite formal system.
Comment #54 September 24th, 2021 at 3:52 pm
Gerard #53: Why would you ever have expected there to be a complete theory? Of course some people did expect that, but it’s not just that they were wrong—it’s that, with hindsight, it’s completely obvious why they had to be wrong. (Most great discoveries are completely obvious with hindsight.) Once that’s cleared up, you can understand the infinite hierarchy of theories—PA, ZFC, ZFC with large cardinal axioms, etc. etc.—that let you make more and more true statements about infinite sets, with no one of them exhausting all the true statements.
(And while opinions can reasonably differ on the definiteness of statements about higher cardinals, for me, life is way too short for any view that refuses to make sense of a statement like “there are infinitely many prime numbers” as just straightforwardly true—true as surely as I’m sitting here.)
Comment #55 September 24th, 2021 at 4:18 pm
Scott #54
I’m not saying you can never make any sensible statements about unbounded sequences. I think you definitely need to be able to do inductive proofs, for example. Otherwise you’d be stuck analyzing every single case, which wouldn’t be at all practical if N were say the size of Avogadro’s Number.
But I think there is a line that gets crossed somewhere that involves an excessive reification of the concept of infinity. Once you cross it you start arriving at conclusions that make no sense, like the Banach-Tarski Paradox. I’m not sure exactly where that line is, but yeah I’d bet it’s this side of Cantor’s transfinite cardinals.
Comment #56 September 24th, 2021 at 4:36 pm
Scott #54
> Why would you ever have expected there to be a complete theory? Of course some people did expect that, but it’s not just that they were wrong—it’s that, with hindsight, it’s completely obvious why they had to be wrong.
Yes I agree with you there. Even an ancient philosopher should have been able to tell you that the finite can never fully describe the infinite.
But if you can’t have a complete theory of infinity, (ie. there are facts about it that will remain unknowable unless you choose to assert them as true) then in what sense is it a valid object of study ?
Comment #57 September 24th, 2021 at 7:52 pm
@Scott,
you don’t need any concept of infinity to talk about the infinitude of prime numbers, or analytic number theory, or any concrete infinite set used in mathematics. Euclid did not have a notion of infinite object when proving, rather finitistically, the infinitude of primes, nor did Euler’s approach using the zeta function or Riemann’s extension of it, involving anything more infinitary than “this process can always be done for the next value of N”.
I think the result that Peano Arithmetic is equivalent to the set theory of finite sets (ZF with “all sets are finite”) is robust enough to assert that PA is a reasonable proxy for fully general infinity-free reasoning. PA is much stronger than needed to develop all mathematics likely to ever find a use in science. If you really want to use it as a system for writing out theorems and proofs then all sorts of syntactic shortcuts that don’t change the proof theoretic strength would be needed, but that’s just user-interface, not OS. This or the same with weaker systems (e.g. primitive recursive arithmetic) could be seen as one version of Gerard’s point if I understand him correctly.
The problem with infinity, as Gauss pointed out, is “actual infinity”, where you not only denote certain constructs (e.g., unending sequences) as “infinite”, but reason about them like sharply apprehensible finite objects that can be taken in hand and spread out before your eyes and examined for whether they do or don’t have any property you like — the Twin Prime conjecture, for example. Using language and thinking of this type leads to pseudo-problems like the Continuum Hypothesis.
Comment #58 September 24th, 2021 at 8:32 pm
STEM Caveman #57: So let me give you a concrete challenge. For down-to-earth, non-metamathematical reasons in quantum computing theory, I need to know that given a finite universal basis of quantum gates, there exist unitary transformations that can’t be generated exactly using those gates. That observation is what leads us to consider the approximability of unitary transformations in the first place. But by far the simplest way to see why it’s true, is that there’s an uncountable infinity of unitaries but only some countable subset of them can be generated using my gates. So now, if you censor notions like “countable” and “uncountable” from math, enjoin me from using them, then how am I supposed to say the thing I just said? If the answer is that I could say it, but only via some complicated, awkward circumlocution whose only purpose is to satisfy you, then we’re finished, this discussion is over, we’ve proven that this philosophy of mathematics is not the one for me. 🙂
Comment #59 September 24th, 2021 at 9:13 pm
> if you censor notions like “countable” and “uncountable”
Why would they be censored? “Infinite” has Euclid’s meaning, the ability to always produce one more. “Countable” has the usual meaning, parametrization by N. There’s nothing to stop you from defining and using “uncountable” as the negation of countable, but something even more useful that leads to better-stated theorems and maybe marginally shorter proofs is to name and utilitize the stronger notions of uncountable that actually appear in practice, such as one-to-one parametrization by 2^N or by R. And then do whatever you have already been doing.
For instance, if your proof that there are uncountably many unitaries boiled down to embedding 2^N into U(n), then literally the same Cantor diagonal argument you had in mind applies. It would actually be shocking to see a non-contrived example from normal mathematics that requires “actual infinity”.
As in our discussion of Max(S) for Busy Beaver, you seem to be under the impression that this is a question of censorship, rather than accurately expressing what you’re doing with the available materials — an activity that leads to greater directness, not circumlocution. The Busy Beaver paper would have been slightly shorter and clearer at each point where the issue comes up.
Comment #60 September 24th, 2021 at 10:56 pm
STEM Caveman #59: In that case, what if anything should I ever do differently from what I do now, when I do math? And if I should never do anything differently, then what if anything is the daylight between your position and mine?
Comment #61 September 24th, 2021 at 11:37 pm
It’s like the difference between having God in your system and not. We both know, since neither of us ever developed the habit of arguing based on super-beings, that anything you can derive with the God idea you can also trivially and easily express without it, using no more than small superficial changes that are basically automatic and simplify things (remember my example in the BB thread, of Revered Wright and what “God damn America” means to him versus to seculars like Obama and Oprah). But a believer might be shocked and resistant to changing the language he is used to and fear a loss of the Precious, simply because repeated use has accustomed him to treating some words as describing real things.
Consider, simpler than BB(n), the Ramsey number R(10,10), which is defined as solution of a discrete, finite extremal problem. Mankind will probably never know this number or its last digit or two. There isn’t any metamathematical debate about its existence in terms of common logical objections like the axiom of choice, excluded middle principle, actual infinity, predicativity, etc. But I claim that there is no value, some loss of clarity and realism, and some just plain mysticism, in operating as though there is a pre-existing integer R(10,10) whose properties we discover through the lower- and upper-bound constructions that are found over time. A sophisticated consumer knows that “R(10,10) > 97” is an abbreviation to say we have a construction with certain parameters, and “R(10,10) < 75619567562" an abbreviation for an algorithm with some other parameters. If you did want R(10,10) to be a full-fledged object in your theory instead of a syntactic construct, you could talk about it as a set of values, or rather an interval, which we could potentially and very improbably narrow down to a single point.
It's actually a very interesting exercise to notice and unlearn the habit of talking in terms of pre-existing objects we can't actually find, and the little changes of phrasing that allow you to speak in a backwards-compatible way, i.e., to be fully understood by the 99 percent who retain the habit. The interesting thing is that it makes your statements and thinking clearer both to yourself, and to them; it makes you better at the mathematics.
Comment #62 September 25th, 2021 at 12:01 am
> talk about it as a set of values, or rather an interval
By the way, once the discussion moves to real numbers rather than integers, then in the case of “supremum”, talking about a set of values rather than its hypothetical “sup” tends to be a tangible improvement. We care about whether the Sup is attained, which is a statement about the set that goes beyond knowing the value of the Sup, and inequalities involving Sup or Max (let alone more complicated things like limsup and ess-sup) unwind to unnatural statements compared to talking directly about the set.
Comment #63 September 25th, 2021 at 1:08 am
(@Scott) Another example, that I had meant to post in the BB thread.
Everywhere in your paper that you prove a growth estimate on BB(n), the argument has 3 steps.
-Translate from the integer BB(n), to a machine witnessing that halt time.
-Construct a larger, slower machine, n’ states that runs f(BB(n)) steps
-Translate into a statement on BB(n+1)
Since I view the concept of an integer-valued function BB(n) as mystical, and prefer to talk in terms of the machines themselves, the first and last step are deleted. For the middle step, perform the same construction, and say that “an n-state machine that runs B steps is transformable to an n’-state machine that runs f(B) steps” (where transformation means function that preserves halting and nonhalting of machine runs). I might use “lives” rather than “runs” to avoid confusion with the notion of runtime as a pre-existing quantity, where a machine is defined to live K steps if it does not halt within (K-1) steps. Privately I would say “runs” to myself to mean exactly the same thing, since the idea of an unobservable a priori runtime doesn’t play a role in my thinking, but “lives” is fine for communication. Finally, I would observe that none of your proofs require the uncomputable notion of halting because they only use whatever state the machine is in at state K when it has lived K steps, for some K (that happens to be the halting time, but doesn’t need to be).
So we get a direct and more general description of what your proof really does, by not fitting it into the mystical frame of BB(n) as a genuine integer, and avoiding the uncomputability associated with halting. Of course you could talk about halting machines only, but since the set of halting machines is a bit vague (no membership test), intuitively we might expect that reference to this set doesn’t do real work in the proof, and that turns out to be the case.
Comment #64 September 25th, 2021 at 5:58 am
STEM Caveman #61
> We both know, since neither of us ever developed the habit of arguing based on super-beings, that anything you can derive with the God idea you can also trivially and easily express without it
What exactly do you mean by that ? It seems obvious that people who believe in God often use arguments based on that belief to arrive at conclusions that are quite mystifying to the rest of us.
Perhaps you consider such conclusions to be inherently logically flawed, which is probably true if you’re talking about belief systems like Young Earth Creationism. But what of more serious thinkers, like Descartes, who derived from his concept of God that the world we observe could not fundamentally be a delusion, a result that is unreachable for many of us ?
In fact I would argue that the God Concept, at least as most theists understand it, is truly all powerful in that it can be used to prove any claim whatsoever, ex falso quodlibet, precisely because it is inherently logically contradictory.
Comment #65 September 25th, 2021 at 12:35 pm
STEM Caveman #62, #63: I’m actually really happy that we’re now not debating metaphysics, but just a straightforward falsifiable empirical claim. The claim is that if I train myself to talk about math in a more constructivist way, it will help my research. I confess I’m skeptical of this claim, firstly because I can’t think of a single accomplished mathematician or theoretical computer scientist who ever told me that such a thing was true in their experience, secondly because … I mean, I’m not confused about what people mean when they say they have upper and lower bounds on R(6,6), and thirdly, because, well, what if some future advance did pin down R(6,6) exactly? Wouldn’t you then be somewhat in the position of Auguste Comte, who argued at length why the composition of the stars was a metaphysical unknowable as an important part of his philosophy, only for spectroscopy to be invented a few years later and resolve the stars into mostly hydrogen and helium?
Comment #66 September 26th, 2021 at 11:32 am
Incidentally, Gerard #56:
But if you can’t have a complete theory of infinity, (ie. there are facts about it that will remain unknowable unless you choose to assert them as true) then in what sense is it a valid object of study ?
Almost every object of study is like this! In physics, we might never be able to answer the questions of why a universe exists at all, why it’s this way rather than various other ways, or why we consciously perceive it. But none of that makes physics an “invalid object of study”!! With both physics and infinity, the question is: can we learn anything reliable, surprising, and profound? And in both cases the answer is yes, we can. So then the goal simply becomes to learn as much as possible.
Comment #67 September 26th, 2021 at 1:46 pm
Scott #66
I believe that the questions of why a universe exists and why we are conscious of it are probably fundamentally unanswerable by physics or any other science, at least according to the current western understanding of that concept.
Apart from that however I do think that physics works under at least the hope of being able to fully understand the workings of the universe as it appears to us. Moreover, unlike mathematics, that understanding would be anchored in repeatable experiments rather than some list of axioms that we just have to keep adding to and which anyone can choose to accept or reject as they please. In fact the logical result of that process would seem be the creation of not a single mathematics representing objective truth but rather an unbounded number of different “mathematics”(plural) from which one could choose.
Comment #68 September 30th, 2021 at 2:28 pm
Scott – huge fan of the blog. I wanted to understand the intersection of cryptocurrencies and QC…you said proof of stake, but I wonder if you meant accelerating proof of work systems.
Comment #69 September 30th, 2021 at 11:21 pm
I am a bit late the discussion between Scott and STEM Caveman here, but here is my two-cents on the not-at-all deep or eternal question of the nature of infinity.
Most of the discussions or debates (between mathematicians) about how to handle infinity that I have come across fall somewhere within or around the following descriptions.
— A dispute over the ontological status of infinite sets, one position being that it is not on the
same level as “the number 2” for example.
— A dispute over the existence of mathematical objects that cannot be constructed, even in
principle.
— A dispute over the use of the axiom of choice.
Each of these debates is, in its own way, a debate about mathematics (what it is, what it should be, etc) as it is about infinity. I find that most of the time when people argue on things like this they are not in agreement on what version of mathematics they are talking about. “Versions of math” I frequently see in these discussions include, but are not limited to:
— Math as a collection of undeniable, completely agreed-upon and indisputable truths about things like the natural numbers
— Math as a completely invented formal system, with no necessary correspondence to anything true, whatever that means
— Math as a very useful formal system, motivated by things like the physical universe and things like it, but by no means restricted to it
So far I think these conceptions of “math” are defensible, and each may permit its own attitude towards infinites. I do think that debating a preference for one over the other is below Aaronson’s Beach Boys Threshold. Which brings me to the following:
— Math as whatever it is people in math departments who call themselves mathematicians talk about, and how they talk about it.
Which is where the debate usually ends up, and seems to be where this one ended up. I am not going to try to change your mind, STEM Caveman, as I am deeply sympathetic to your general position and attitude, but I want to tell you why I think you won’t ever be able to affect meaningful change in “math” as described above.
The real line is one of the most central objects in modern mathematics. Speaking personally, it is my favorite mathematical object. It is also in many ways a preposterous and extravagant object, with no obvious physical correlate. Borel’s Normal Number Theorem is my favorite theorem about the real line. It is such a beautiful idea, and gives us a small glimpse into the depth and richness of the continuum. It is also meaningless, preposterous, and extravagant in the sense that it is saying that if you pick a number at random, with probability 1 it is will a number that does not exist in nature, and you could not compute, even in principle. So why carry on with a mathematics that not only permits but embraces such statements? I think the reason is part practical (as Scott mentioned that it makes communication easier), but largely romantic. I remember when I was young and learned for the first time that “point nine repeating was equal to one,” I was stunned and intoxicated by the idea that you could even ask and answer a question like that. I think that feeling of intoxication is why I (and perhaps others?) stick with the real line, and Borel’s Normal Number Theorem, and the rest of it, even if they are bad for me. 🙂
It is a personal anecdote, but maybe partially explains the lack of success in getting professional mathematicians to stop talking about their favorite things. In any case, my advice for a “pro constructivist warrior” would be to focus their efforts here:
— Math as whatever it is math departments teach undergrads.
It is this version of math where I think there is real ground to be gained. I think a concerted effort to get professors to seriously acknowledge that there is ongoing debate amongst professionals about how best to really do mathematics, what certain people object to and why, serious criticisms of things like the axiom of choice, our present model of the continuum, etc. It is here where I am firmly in your camp– this version of math should change.
Comment #70 October 3rd, 2021 at 3:59 pm
Matt Baker #68: Sorry for the delay in answering you. No, I meant what I said: in this talk, I was talking specifically about generating cryptographically certified random bits, which could conceivably be useful for proof-of-stake cryptocurrencies like the next-generation Ethereum. The use of quantum computers to attack proof of work, mine bitcoins, etc, is another whole topic in its own right. For more about it, see eg this survey article.
Comment #71 October 5th, 2021 at 6:55 pm
@Tu #69
Interesting remarks, I enjoyed reading. Scott is adding blog posts faster than I can add blog comments, so I will say something quickly now and try to return later to add more.
I don’t think this has to do with “nature of infinity”, airy metaphysics or even “constructivism” (well, maybe it is related to some parts of some arguments for the latter). In a view like Scott’s, questions about infinity and shades of distinction about it matter but that’s only from reifying these things to begin with rather than treating them as figures of speech.
The normal number theorem is a good example. You talk about random individual real numbers, but even in orthodox, classical, infinitistic mathematics that is recognized as a poetic figure of speech for prosaic calculations with measures of total mass 1. I think this language could use some modernization to better capture the intuition, and a lot of basic probability gets around that by building a second formalism from the prosaic unit measures and then speaking the second language, but that’s a topic for another time. The point is that the usual standard framework embraces the idea of a linguistic figure of speech, what used to be called a macro command, for this; why not use that idea more generally for “supremum” and other concepts where it more accurately captures what you’re already doing, than reified talk about Actual Objects?
Comment #72 October 26th, 2021 at 6:33 pm
Some time ago, in another comment, I linked to a report on g-tummo experiments published in Plos One, in which the authors found that the neurocognitive component of said meditation/yoga practice actually raises core body temperature into the fever zone and maintains it there: Neurocognitive and Somatic Components of Temperature Increases during g-Tummo Meditation: Legend and Reality. The original research, that of Harvard’s Herbert Benson, was published in Nature back in 1982: Body temperature changes during the practice of g Tum-mo yoga. This is also related to the Wim Hof, aka “Iceman”, phenomenon and the big question that’s been burning up my mind is, where does the energy come from?
Okay, so looking into that, I recently found a very interesting paper from 2019 reporting on some quantum thermodynamics experiments, in which the authors, well, from their abstract:
“Heat spontaneously flows from hot to cold in standard thermodynamics. However, the latter theory presupposes the absence of initial correlations between interacting systems. We here experimentally demonstrate the reversal of heat flow for two quantum correlated spins-1/2, initially prepared in local thermal states at different effective temperatures, employing a Nuclear Magnetic Resonance setup. We observe a spontaneous energy flow from the cold to the hot system.”
Reversing the direction of heat flow using quantum correlations
What I found most interesting is from their Discussion:
“Furthermore, numerical simulations show that reversals may also occur for a spin interacting with larger spin environments which induce thermalization. Hence, an anomalous heat current does not seem to be restricted to microscopic systems.”
If you put that together with the 2007 research from biophysicist, Huping Hu, and medical doctor, Maoxin Wu, published in Medical Hypotheses, then you have a highly plausible mechanism for explaining the g-tummo and Wim Hof thermodynamics: they are pulling heat from the colder surroundings.
Spin-Mediated Consciousness: Theory, Experimental Studies, Further Development & Related Topics
“We found that applying magnetic pulses to the brain when an anaesthetic was placed in between caused the brain to feel the effect of said anaesthetic as if the test subject had actually inhaled the same. We further found that drinking water exposed to magnetic pulses, laser light or microwave when an anaesthetic was placed in between also causes brain effects in various degrees. Additional experiments indicate that the said brain effect is indeed the consequence of quantum entanglement.”
At this time I do not know of any other plausible explanation. These monks and nuns have contests in which they sit basically naked in the freezing snow, the equivalent of bedsheets soaked in freezing river water draped over their torso, and they generate enough heat to not only maintain core body temperature but also dry 3 sheets in succession, often taking several hours to do so. And they don’t lose appreciable weight, certainly not that required were they simply converting brown fat, as Benson conjectured. What does this say about quantum supremacy? Is it not a macro example?
Comment #73 October 27th, 2021 at 3:44 pm
Last night I was thinking about your “woke-folk” problem and about the first thing that popped into my mind, living in California, the first State to legalize medical marijuana, as I do, was the
ArtVI.C2.1.1.3 Supremacy Clause! I wondered what it would take to change the name of a Constitutional Clause, so I looked and it requires an Amendment! Good luck with that! I’m laughing out loud right freaking now!
But anyway, my thought was to replace the troublesome “quantum supremacy” with “classical emancipation,” emancipation meaning “the act or process of emancipating” and emancipating meaning “to free from constraint, control, or the power of another.” Let’s just use it in a sentence from your blog:
“[i]ncluding about the new paper from last week, the night before my talk (!), by the USTC group in China, where they report a classical emancipation experiment based on random circuit sampling with a superconducting chip, this time with a record-setting 60 qubits and 24 layers of gates.”
It sounds pretty damn good, doesn’t it? Its etymology is actually not too bad either:
“1620s, “set free from control,” from Latin emancipatus, past participle of emancipare “put (a son) out of paternal authority, declare (someone) free, give up one’s authority over,” in Roman law, the freeing of a son or wife from the legal authority (patria potestas) of the pater familias, to make his or her own way in the world;
[N]ot used by the Romans in reference to the freeing of slaves, the verb for this being manumittere. The English word was adopted in the jargon of the cause of religious toleration (17c.), then anti-slavery (1776). Also used in reference to women who free themselves from conventional customs (1850).”
Based on the Wikipedia entry, Criticism of the name, it’s curious that “ascendency,” a synonym for “supremacy,” is not used. But I like “classical emancipation,” largely because it implies a “freeing from a constraining power” rather than a “submission to a constraining power.”
What I personally worry about, with regards quantum computation and this trend towards automation in general, is the loss of labor: what happens in a consumption based economy when the vast majority of laborers are replaced by automation, robots producing without consuming and displaced workers no longer being able to consume? I’m not the only one worried about it:
Robots, Growth, and Inequality;
For the Benefit of All: Fiscal Policies and Equity-Efficiency Trade-offs in the Age of
Automation.