Ask Me Anything: Apocalypse Edition
So far, I confess, this pandemic is not shaping up for me like for Isaac Newton. It’s not just that I haven’t invented calculus or mechanics: I feel little motivation to think about research at all. Or to catch up on classic literature or films … or even to shower, shave, or brush my teeth. I’m quarantined in the house with my wife, our two kids, and my parents, so certainly there’s been plenty of family time, although my 7-year-daughter would inexplicably rather play fashion games on her iPad than get personalized math lessons from the author of Quantum Computing Since Democritus.
Mostly, it seems, I’ve been spending the time sleeping. Or curled up in bed, phone to face, transfixed by the disaster movie that’s the world’s new reality. Have you ever had one of those nightmares where you know the catastrophe is approaching—whether that means a missed flight, a botched presentation at your old high school, or (perhaps) more people dying than in any event since WWII—but you don’t know exactly when, and you can do nothing to avert it? Yeah, that feeling is what I now close my eyes to escape. And then I wake up, and I’m back in bizarro-nightmare-land, where the US is in no rush whatsoever to test people or to build ventilators or hospitals to cope with the coming deluge, and where ideas that could save millions have no chance against rotting institutions.
If nothing else, I guess we now have a decisive answer to the question of why humanity can’t get its act together on climate change. Namely, if we can’t wrap our heads around a catastrophe that explodes exponentially over a few weeks—if those who denied or minimized it face no consequences even when they’re dramatically refuted before everyone’s eyes—then what chance could we possibly have against a catastrophe that explodes exponentially over a century? (Note that I reject the view that the virus was sent by some guardian angel as the only possible solution to climate change, one crisis cancelling another one. For one thing, I expect emissions to roar back as soon as this new Black Death is over; for another, the virus punishes public transportation but not cars.)
Anyway, I realized I needed something, not necessarily to take my mind off the crisis, but to break me out of an unproductive spiral. Also, what better time than the present for things that I wouldn’t normally have time for? So, continuing a tradition from 2008, 2009, 2011, 2013, 2015, and 2018, we’re going to do an Ask Me Anything session. Questions directly or tangentially related to the crisis (continuing the discussion from the previous thread) are okay, questions totally unrelated to the crisis are even okayer, goofball questions are great, and questions that I can involve my two kids in answering are greatest of all. Here are this year’s ground rules:
- 24 hours or until I get bored
- One question per person total
- Absolutely no multi-part questions
- Self-contained questions only—nothing that requires me to read a paper, watch a video, etc.
- Scan the previous AMAs to see if your question is already there
- Any sufficiently patronizing, hostile, or annoying questions might be left in the moderation queue, 100% at my discretion
So ask away! And always look on the bright side of life.
Update (March 19): No more questions, please. Thanks, everyone! It will take me a few days just to work through all the great questions that are already in the queue.
Update (March 24): Thanks again for the 90-odd questions! For your reading convenience, here are links to all my answers, with some answers that I’m happy with bolded.
- Could non-biological entities be conscious? (Short answer: presumably)
- Is online teaching here to stay, even after coronavirus passes?
- Would a parliament of randomly-chosen high SAT-scorers be better than the current US government? (Short answer: probably. Low bar!)
- Am I optimistic about NISQ algorithms like QAOA? (Short answer: no)
- Have I tried sitting under an apple tree? (Answer: No, only laying under the covers)
- Something something about radical bio-isolationism to defend against engineered super-plagues?
- Will the corona crisis help teach people about climate change?
- Will the crisis make academics reevaluate the need for so many conferences?
- How should we teach undergrad Theory of Computation?
- How do I feel about the progress in TCS over the last decade? (Short answer: good)
- Is MIP*=RE evidence for quantum being stronger in general? (Short answer: no)
- Should voters be blamed, or only politicians? (Short answer: voters)
- Could quantum computing help with future pandemics? (Short answer: conceivably but let’s start with masks and ventilators)
- What’s my estimate for the number of COVID victims?
- Will Trump’s debased response to the pandemic make him lose the election? (Short answer: I hope so!)
- What recently-read books do I recommend?
- What are my daughter’s favorite fashion games?
- Are there quantum size-depth tradeoffs for problems in NC or RNC?
- How do I combat the feeling that the pandemic makes all my research useless? (Short answer: my research was useless already!)
- Is time already involved at the commutator level in QM?
- What potential use of QCs brings me the most joy? (Short answer: disproving people who claimed QCs were impossible!)
- Why aren’t I more terrified of the flu than of coronavirus? (Short answer: Do you live in a frigging cave?)
- Why are physicists so ignorant of theoretical CS, if all their experiments rely on computers?
- How much economic cost should we bear to flatten the curve?
- Which two historical figures would I like to watch debating the human condition? (Answer: Bertrand Russell and Jesus)
- Is CRISPR being used to help search for coronavirus vaccines?
- Have I ever grown a beard? (Short answer: sadly, yes)
- Why are hard-to-simulate Mikado sticks not “Mikado supremacy”?
- What advice would I give a postdoc who dreams of pursuing big questions? (Short answer: do it!)
- What recent research idea did I have that didn’t pan out?
- How will QCs help advance materials science? (Short answer: no one knows)
- Are Parity Games in P?
- Boxers or briefs?
- How do I know I retain transtemporal identity?
- What positives will come out of this pandemic?
- Will I try Beeminder?
- Am I worried about dysgenic fertility trends?
- How do you know if something’s conscious? (Short answer: you don’t)
- What non-political decree would I issue as king?
- Do Borel determinacy and the measurability of projective sets have metaphysical truth-values? (Short answer: dunno)
- Why haven’t we previously seen lots of viruses with asymptomatic spread?
- How is Gil Kalai faring now that his worldview has been shattered? (Short answer: he’s fine)
- Have things gotten so awful that we should stop working on fundamental questions?
- Do non-physical realms exist?
- Is consciousness a quantum phenomenon?
- Can one separate the completeness and soundness aspects of MIP*?
- Why do I still feel the need to bring up Amanda Marcotte? (Short answer: Because ironically, she showed the world why my teenage fears weren’t completely delusional)
- How would I apportion money to different research areas?
- Can one end music infringement lawsuits by putting 68 billion computer-generated melodies into the public domain?
- What’s the second piece of information people should take from this blog?
- How likely am I to win a Nobel Prize?
- What research area would I choose were I starting today?
- Will my math lessons for my daughter be made more widely available? (Short answer: That’s the plan!)
- How should Turing-universality be defined for dynamical systems?
- Has the coronavirus crisis inspired me to take existential risks in general, including AI risks, more seriously? (Short answer: yes)
- Why do world leaders say we’re now in a war? (Short answer: because we are)
- Why doesn’t chemistry get more respect?
- What other catastrophes do I worry might hit us in the next decade?
- Have I ever experienced “true free will”?
- Why do many top PhD programs now expect applicants to already have research experience? (Short answer: arms race)
- Do I believe in telepathy? (Answer: no)
- Is what’s mathematically possible a strict subset of what’s logically possible?
- What do I think of the Law of the Excluded Middle? (Short answer: 100% for, 0% against)
- What do I think of bounded arithmetic and proof complexity?
- Who are leading candidates for the next Turing Award?
- Could an infinite amount of computation be done just before a Big Rip?
- What is quantum discord and is it useful for anything?
- What do I think of academics having to write diversity statements? (Short answer: for diversity, against mandatory statements)
- What’s my frank opinion of geometry-from-entanglement, and what does the new replica wormhole result tell us?
- What do I think of Sabine Hossenfelder’s view that impossibility theorems are only about theories, not about nature itself?
- Do I own a gun, or have I considered getting one? (Short answer: no and no)
- Are the asymptotically best quantum error-correcting codes likely to be stabilizer codes?
- What was the flavor of the last piece of cake I ate?
- Why is it called computer science if we don’t do experiments? (Short answer: for starters, we do do experiments)
- Is there such a thing as non-maximal entanglement? (Short answer: yes)
- At what fatality rate do you order shelter-in-place?
- Are logistics and optimization promising applications of QC?
- What problems in quantum complexity do I think will be solved next?
- What changes would I (and my kids) make to elementary education in the US?
- What do my kids think that my wife and I do at work?
- Do I think Theory A and Theory B will join forces to tackle the P=?NP problem? (Short answer: No, I think Theory A will tackle it, while Theory B explains how it could’ve been tackled more elegantly)
- What’s a good quantum computing project idea?
- What’s the role of error-correcting codes in the PCP Theorem?
- Is the Blum Speedup Theorem true? (Answer: yes)
- Which type of entanglement better captures the real world: tensor-product or commuting-operator?
- Is Ewin Tang’s algorithm practical?
- What motivates me to get out of bed? (Answer: Dana yelling at me to come help with the kids)
- Would George Washington’s descendants, ruling as kings, be preferable to Trump?
- What big question would I love to solve?
- Am I planning a revision of Quantum Computing Since Democritus? (Short answer: no)
Follow
Comment #1 March 18th, 2020 at 4:10 pm
Do you think that non-biological machines of any sort will ever become conscious?
Comment #2 March 18th, 2020 at 4:11 pm
Do you think that most major universities moving their teaching online for the rest of this semester will cause (or accelerate) any major or structural changes in higher education?
Comment #3 March 18th, 2020 at 4:13 pm
Hi Scott,
Don’t have a question but I will bring up one positive thing unrelated to this crisis: you may have saved my life by replying to an email I sent you a few months ago.
In addition, youd reply mentioned excitement about quantum supremacy in the future. Looking at it now, your wish came true.
Best regards,
Filip
Comment #4 March 18th, 2020 at 4:13 pm
Not a question, but one thing I like about the news coverage of the epidemic is that the phrase “exponential growth” is being used accurately for a change.
Comment #5 March 18th, 2020 at 4:14 pm
Imagine a form of government that works like this:
Everyone takes the SAT at 18. Mostly this test is used for admissions and employment purposes. However, the pool of the top 30000 is also used to select a parliament of 300. This parliament is selected through sortition, using some publicly-verifiable astronomical source of randomness. Do you think this would be better or worse than what we have now?
Comment #6 March 18th, 2020 at 4:34 pm
Saw this on Hacker News recently: Engineers crack 58-year-old puzzle on way to quantum breakthrough (HN thread, arXiv preprint). Sounded cool, but could use more interpretation for us laymen. Have you heard about this discovery, & if so, any comment? Could it accelerate the development of quantum computing?
Comment #7 March 18th, 2020 at 4:36 pm
James Cross #1:
Do you think that non-biological machines of any sort will ever become conscious?
Yeah that’s a tough one (especially for my first question!). 😉
Not only could the answer depend on what we choose to regard as “conscious”—something that’s probably not entirely within the scope of scientific investigation—it could even depend on what we count as “non-biological.” But certainly I see no principle to rule this out (indeed, what could such a principle even look like, if it had to be compatible with a broadly scientific worldview?). I even think the possibility of it happening in our lifetimes should be seriously considered. (My views on that have shifted over the past decade, partly because of the astonishing advances in machine learning that we’ve witnessed—things have turned out to work that just totally didn’t have to, given what we knew 10 years ago.)
Comment #8 March 18th, 2020 at 4:37 pm
This always cheers me up. The random Wodehouse quote generator website. Just want to share it with everyone here. It is not a paper or video, so if that still meets your requirements, please tell me which one is your favorite. Refresh page to get a new quote.
http://www.drones.com/pgw.cgi
Comment #9 March 18th, 2020 at 4:37 pm
Do you feel optimistic about any NISQ applications for classical problems, e.g. Maxcut via QAOA or generative modeling of classical datasets via QBMs?
Comment #10 March 18th, 2020 at 4:38 pm
Have you watched the Avatar cartoon?
Comment #11 March 18th, 2020 at 4:38 pm
Have you tried sitting under an apple tree?
Comment #12 March 18th, 2020 at 4:40 pm
Do you expect that millions of deaths would make it easier to promote radical bio-isolationism and the treating of breathing unprocessed, shared air as equivalent to unprotected sex, in preparation for the inevitable engineered super-plagues, or harder, as it will create the impression among the survivors that even the “most devastating” modern plagues are still civilizationally survivable?
Comment #13 March 18th, 2020 at 4:40 pm
Lyle Cantor #5:
Might be worse. Consider:
1. SAT score correlation with various types of intelligence is iffy at best.
2. More importantly, a lot of ultra high scores would probably go to people on the near end of the asperger spectrum that are very good at some things but have very little common sense.
Comment #14 March 18th, 2020 at 4:48 pm
Do you think this is a “teachable moment” that, by drawing parallels between people’s responses to the corona virus and climate change, climate change under-panic’ers could be convinced to take it more seriously?
Its seems to me that there is a lot of demographic overlap between people that took the corona virus seriously based on early evidence and those that take climate change seriously and vice versa, those that dismissed and continue to dismiss the corona virus threat as overblown and who treat climate change in the same way.
The accelerated timeline of the corona virus, compared to climate change, and the whiplash of people saying as recently as last week that it’s no big deal vs. “shelter in place, shut everything down” this week seems like an opportunity to get people to trust scientific predictions and mathematical models and expertise more broadly, and that waiting until things become unignorable problems and assuming technology will advance fast enough to bail us out is not a good strategy.
Comment #15 March 18th, 2020 at 4:51 pm
Lev Reyzin #2:
Do you think that most major universities moving their teaching online for the rest of this semester will cause (or accelerate) any major or structural changes in higher education?
Like, I don’t think many university presidents are going to slap themselves on the foreheads and say, “whoa, so this whole time we never needed a physical campus!” I think most students and faculty will be right back on campus, probably with big celebrations, as soon as they’re able to.
At the same time, tens of millions of people are going to get their first taste of online classes (on both the student and teacher sides). In that sense, the coronavirus might accomplish more than 10,000 marketing agents for EdX and Coursera ever could. And I’d be shocked if that didn’t have a noticeable effect.
I personally bought out of my teaching this semester (mostly, I thought then, to participate in a quantum computing semester at the Simons Institute in Berkeley!). So I’m not faced with the mad scramble to the cloud that many of my colleagues are right now. Coincidentally, though, I was planning to offer my intro to quantum information course through UT’s online masters’ program, starting this coming academic year. We’ll see how it goes!
Comment #16 March 18th, 2020 at 4:55 pm
Do you think COVID-19 will cause a permanent move away from large in-person scientific conferences?
Comment #17 March 18th, 2020 at 4:58 pm
What are the most important points to make in an undergrad Theory of Computation course? (Or, what should we do differently than what we now do in the traditional TOC course?)
Comment #18 March 18th, 2020 at 4:58 pm
How do you feel about progress theoretical computer science has made over the last 10-20 years? (In the sense of has there been too little, what has been most remarkable about it, etc.)
Comment #19 March 18th, 2020 at 4:59 pm
Raoul Ohio #12.
SAT is just a stand-in for any g-loaded test, swap it with Raven’s or whatever if it helps the thought experiment.
Comment #20 March 18th, 2020 at 5:00 pm
Filip #3: It made my day to learn that corresponding with me “may have saved your life” (!). Wow, thank you for telling me.
Tell you what, let’s try to save another life right now.
Everyone, stop reading Shtetl-Optimized and go wash your hands! 😀
Comment #21 March 18th, 2020 at 5:04 pm
Should we consider the MIP*=RE result, together with the zero-gap MIP* result as evidence that quantum computers may be stronger than we’d otherwise expect, or at least that our intuition is not nearly as reliable on them as we’d like? My naive response from this is to reduce my confidence in some things I’d otherwise consider highly likely; for example I would otherwise say that I’m pretty confident that NP is not contained in BQP/poly . Have these results reduced your general credence that we have a good understanding of how quantum complexity classes behave?
Comment #22 March 18th, 2020 at 5:07 pm
Simon Gay #4:
Not a question, but one thing I like about the news coverage of the epidemic is that the phrase “exponential growth” is being used accurately for a change.
I remember that after the Economist ran a credulous story about D-Wave back in 2007, they printed three letters of complaint: an on-point rebuttal from Umesh Vazirani, one letter that I don’t remember, and one letter complaining about everyone nowadays overusing “exponential.” The author of the third letter seemed to have a very high estimation of his own wit … and no concept of the possibility of “exponential” literally meaning “exponential,” let alone of what was actually wrong with the article.
Comment #23 March 18th, 2020 at 5:09 pm
Do you think in a democracy the voters should never be blamed, only the politicians they vote for? (I can see you rather bash Trump only, while other commenters blame also his voters.)
Comment #24 March 18th, 2020 at 5:10 pm
Lyle Cantor #5:
Imagine a form of government that works like this:
Everyone takes the SAT at 18. Mostly this test is used for admissions and employment purposes. However, the pool of the top 30000 is also used to select a parliament of 300. This parliament is selected through sortition, using some publicly-verifiable astronomical source of randomness. Do you think this would be better or worse than what we have now?
Your system strikes me as an improvement over what we have now. But also, “improvement over what we have now” strikes me as a depressingly low bar…
Comment #25 March 18th, 2020 at 5:14 pm
greetings from Philly! What is the most distant horizon that you somewhat regularly ponder for quantum computing, or what is the most far out thing that you can see people achieving through use of quantum computers.
bonus q: if this pandemic happened 5-9 years later, what way could you envision a qc being able to assist?
Comment #26 March 18th, 2020 at 5:15 pm
What are your daughter’s favorite fashion games?
Comment #27 March 18th, 2020 at 5:20 pm
Scott Comment #19,
A ringing endorsement. Now I just need to figure out which astronomical source of randomness has the best kabbalistic connotations.
Comment #28 March 18th, 2020 at 5:22 pm
Deepa #7: That was some powerful stuff, thanks!!! Asking me to pick a favorite Wodehouse quote is like asking me to pick a favorite chocolate truffle from the box—I can’t even try to answer the question without gorging myself more than I probably should right now.
Comment #29 March 18th, 2020 at 5:25 pm
What is you best bet (with associated scientific reasoning) for the final number of COVID-19 related deads.
Comment #30 March 18th, 2020 at 5:29 pm
Pranav #8:
Do you feel optimistic about any NISQ applications for classical problems, e.g. Maxcut via QAOA or generative modeling of classical datasets via QBMs?
To be honest, not so much!
On the other hand, I certainly think the question merits a lot more investigation (both theoretical and empirical), since certainly we know nothing to rule out such a speedup, which itself is an interesting fact.
Comment #31 March 18th, 2020 at 5:29 pm
How likely do you think it is that Trumps morally and intellectually debased response to the pandemic will lead to him losing the upcoming election?
Comment #32 March 18th, 2020 at 5:30 pm
Hello Scott,
Any books you have read recently that you’d like to recommend?
–
I also add for other readers:
https://scottaaronson-production.mystagingwebsite.com/?p=3679 [30 of my favorite books]
Comment #33 March 18th, 2020 at 5:33 pm
For problems already known to be in NC/RNC, do we know if quantum provides asymptotic improvements in work, e.g., for directed reachability/perfect matching (problems that we know how to parallelize in polylog depth using a lot more gates than the fastest sequential algorithm)?
I would love to get your feeling for how fleshed out the QNC landscape is, compared to NC/RNC. Stay safe!
Comment #34 March 18th, 2020 at 5:34 pm
Vampyricon #9:
Have you watched the Avatar cartoon?
Do you mean the James Cameron movie (which I guess I found as stunning as did the next person), or something else?
Comment #35 March 18th, 2020 at 5:35 pm
Jon Awbrey #10:
Have you tried sitting under an apple tree?
Not that I recall! I’ve tried laying under the covers, though.
Comment #36 March 18th, 2020 at 5:38 pm
When you feel, all the work you are doing for years so passionately is useless in the face of this pandemic, you become terribly hopeless. How do you combat that ?
Comment #37 March 18th, 2020 at 5:42 pm
In quantum mechanics, the order by which operators are applied matters. Does this mean that _time_ somehow is involved already at the commutator level of the formulation of QM?
Comment #38 March 18th, 2020 at 5:43 pm
what potential use of quantum computers brings you the most joy?
Comment #39 March 18th, 2020 at 5:52 pm
Scott, Why aren’t you terrified of the flu season every year, when influenza has killed 16,000 Americans this winter versus 100 for coronavirus?
Comment #40 March 18th, 2020 at 5:56 pm
Dear Scott,
why do so many physicists seem to misunderstand basic facts of CS theory such as the halting problem? I find this rather irksome, as physicists that deem basic computability theory results as irrelevant to their work seem to be oblivious to the problem posed by the following observation: the validation of their theories essentially depends on complex computational devices – sometimes all hardware, sometimes a stack of hardware and software – being certified to be producing meaningful measurements in their experiments.
All the best from Melbourne!
Comment #41 March 18th, 2020 at 6:06 pm
How much economic cost do you think we should bear in order to flatten the curve by shutting down economic and social intercourse? For example, if the shut down would lead to a major depression on the order of the 1930s, do you think it would still be worth it?
Comment #42 March 18th, 2020 at 6:14 pm
Which two (historical) figures would you like see debating the human condition? (Could be from different centuries!)
Comment #43 March 18th, 2020 at 6:23 pm
Scott, Do you know if they are using CRISPR technology in their search for a vaccine for the corona virus?
Comment #44 March 18th, 2020 at 6:30 pm
Have you ever tried growing a beard for an extended amount of time?
Comment #45 March 18th, 2020 at 6:35 pm
Honest question to overcome my ignorance about Google’s quantum supremacy: If you take a bundle of 1,000 Mikado sticks and let them drop to the ground, their distribution and orientation on the floor will be probabilistic but comply with a certain non-uniform probability distribution. By varying the height, the falling angle, the speed in which your hand releases the bundle etc., the Mikado drop even becomes “programmable”. I bet any classical computer would have a hard time sampling from the Mikado distribution on the ground. How is that not “Mikado supremacy”?
Comment #46 March 18th, 2020 at 6:50 pm
What advice do you have for someone who always dreamed of pursuing the “big questions” in science (and hasn’t given up about that dream), but found himself doing a postdoc in a technical (and somewhat esoteric) area of pure mathematics instead?
Comment #47 March 18th, 2020 at 6:55 pm
What’s a recent research idea that you’ve had but that didn’t pan out?
Comment #48 March 18th, 2020 at 7:01 pm
How much is materials science expected to advance with mass availability (for industry) of practical quantum computers? Are we looking at possible room temp superconductors in our lifetimes in terms of R&D speedup?
Comment #49 March 18th, 2020 at 7:34 pm
This, AFAIK, needs guessing, but that’s the fun of the question 😉 :
are parity games solvable in polynomial time? What would be an intuitive argument behind the guess?
Cheers.
Comment #50 March 18th, 2020 at 7:35 pm
Boxers or briefs?
Yes, this is comic relief but that’s what we need right now. Plus, answers!!!
Comment #51 March 18th, 2020 at 7:38 pm
At every single moment of your life, how do you know that you are Scott Aaronson without having to hold all at once in your consciousness every single biographical fact of Scott’s life?
For example, the very first moment we wake up in the morning, as we open our eyes and emerge from nothingness, hardly anything pops up in our mind at all besides a very subtle sense of “familiarity”.
Aren’t we most of the time in a constant state of amnesia, except we don’t realize it or care for it?
This can be contrasted with waking up after your first night in a hotel in a foreign city.
We really take for granted that sense of familiarity, but I’ve had a very strange experience during a seizure where made-up random memories were rushing up in my mind and felt totally familiar even though I knew they were glitches (it was as if I was suddenly remembering all at once dozens of strange dreams I had forgotten), and at the same time things that I knew I should know seemed totally unfamiliar (like the source code I had been working on for weeks).
Did you ever experience something like that?
Comment #52 March 18th, 2020 at 7:40 pm
Scott #6
My specification of non-biological machines was to rule out the argument that biological organisms are just machines which some people (maybe not you) could make.
I would say if consciousness actually depends on the organic molecules and structures in brains then that would rule out non-biological consciousness. We might still be able to construct it artificially but the machinery would look more or less like an organic brain. That certainly seems possible since there are properties to carbon itself and its ability to construct complex molecules that cannot be duplicated with other material. Certainly those properties are critical to life so it wouldn’t seem to me to be a stretch to imagine they might be critical to consciousness.
Comment #53 March 18th, 2020 at 7:58 pm
What positives do you think will come out of this pandemic?
Comment #54 March 18th, 2020 at 8:21 pm
NuclearSpaceHeater #11:
Do you expect that millions of deaths would make it easier to promote radical bio-isolationism and the treating of breathing unprocessed, shared air as equivalent to unprotected sex, in preparation for the inevitable engineered super-plagues, or harder, as it will create the impression among the survivors that even the “most devastating” modern plagues are still civilizationally survivable?
I don’t know, because what you describe as “radical bio-isolationism” sounds totally impracticable to me, both to sell and to implement, and both before and after the current coronavirus catastrophe. Or rather: it seems to me that, by the time one should talk about such radical isolation to escape “engineered super-plagues,” one should simply talk about having passed the technological singularity with whatever else that entails.
Comment #55 March 18th, 2020 at 8:44 pm
Hi Scott! Could I convince you to try some clever commitment devices — like Beeminder of course, but to not be quite so self-promotional I’ll link to a list of all our competitors I know of: https://blog.beeminder.com/competitors — as a way to make the way you spend your time match your dispassionate assessment of how you’d rationally/optimally spend your time?
Seems like it could be especially valuable right now!
Comment #56 March 18th, 2020 at 8:51 pm
Pat #13:
Do you think this is a “teachable moment” that, by drawing parallels between people’s responses to the corona virus and climate change, climate change under-panic’ers could be convinced to take it more seriously?
That would be great if it was!
On the one hand, people throughout history have shown a near-infinite ability to compartmentalize—while you can very occasionally teach them a lesson, you can never make them apply that lesson in full generality.
On the other hand, we’re about to get the most powerful, costly, and horrific demonstration of our lifetimes of the value of experts and expertise and openness and facts. To most readers of this blog, those values might be obvious, but the very fact that Trump and Bolsonaro and so forth are in power implies that the values aren’t universally shared. Indeed, why not just indulge whatever feels the best to believe, or most raises your status, as long as nothing actually matters and you and all of your friends and loved ones will be healthy and fed under truth or lies alike?
Of course the answer—of which civilization is now getting one of its first great reminders since WWII—is that lies can’t be contained. A lie about Barack Obama being born in Kenya metastasizes, over the years, into a lie about a disease that might kill your parents, and how it’s totally under control.
At the least, one could reasonably hope that this deadly remedial lesson, which the human race is about to endure, will destroy the anti-vax movement for a generation (as polio and smallpox did in their time). But yes, we can dream that it might go even further, and raise the whole cultural standing of “elitist, eggheaded technocrats with their science-laden warnings and plans,” back to what it was in (say) the 1940s or 1950s. That strikes me as the central cultural prerequisite to bending the arc of climate change.
Comment #57 March 18th, 2020 at 8:57 pm
Since I mentioned it in the last post — compared to other civilizational threats we’re facing, how do you rate dysgenic fertility trends (basically smarter/more education people having fewer kids)?
Comment #58 March 18th, 2020 at 9:10 pm
Follow-up to #1, which was “Will non-biological machines become conscious?”
Your reply was “It depends upon what you mean by conscious, but it’s possible, even likely.” (I hope this is an accurate paraphrase.)
My question is “How would you know, either way?” Feel free to supply the definition of consciousness (i.e., what you mean by conscious) upon which your response depends.
Comment #59 March 18th, 2020 at 9:14 pm
Dave Lewis #15:
Do you think COVID-19 will cause a permanent move away from large in-person scientific conferences?
I find such things hard to predict, but I guess my answer is similar to my answer in comment #14.
In the short term, I expect the vast majority of conferences to go back to in-person as soon as it’s safe for them to do so. Indeed, they’ll probably reconvene with all the more gusto, for being unable to for the whole preceding year or two. (Perhaps like the scientific conferences that restarted after WWII?)
For the longer term, though … well, a large fraction of academics are about to get their first-ever direct experience with virtual conferences—how such conferences work, and that they’re feasible at all. And on reflection, I do hope that this shared experience will lead to a broader conversation about whether we can move many in-person conferences from annual to once every 2 or 3 years, or in some cases do away with them entirely. For I’ve learned that the constant jetting around the world—in some cases, to give the very same talk to the very same colleagues who you saw a month ago on a different continent—is a strain on scientists’ minds as truly as it’s a strain on the planet.
Like, as long as we’re stuck in this equilibrium of conferences, conferences, conferences, each individual researcher almost has to attend at least 5 or 6 conferences per year (or at any rate, send their students and postdocs to them), if they don’t want to be left out of what’s happening. But sometimes a sufficiently dramatic event can jolt a system into a new and better equilibrium.
Comment #60 March 18th, 2020 at 9:18 pm
Jim Hefferon #16:
What are the most important points to make in an undergrad Theory of Computation course? (Or, what should we do differently than what we now do in the traditional TOC course?)
My teaching statement from way back in 2007 was about precisely those questions. And, while I probably wouldn’t have written that statement exactly the same way today, I still pretty much stand by it. 🙂
Comment #61 March 18th, 2020 at 9:28 pm
Silly question:
You’re temporarily king and can issue any one decree that will be followed to the extent that it’s physically possible. But it can’t be anything that is considered “political” (let’s say, if a majority of randomly surveyed American’s would agree that it is a political act).
What do you do with this very strange, temporary power?
Comment #62 March 18th, 2020 at 9:34 pm
In multiple posts (some on mathoverflow) you’ve described a belief that some questions are about the “real world” and thus have platonically true answers in some sense. In particular it seems like you’ve argued that True Arithmetic and some amount more is “true” is some metaphysical sense. While statements like the axiom of choice are fundamentally not about the real universe in the same way.
Does the space of metaphysically true statements extend into Borel determinacy and the measurability of concretely definable projective sets or does it end somewhere else?
Comment #63 March 18th, 2020 at 9:43 pm
Lyle Cantor # 27
That’s easy, the distribution of prime numbers 🙂
Comment #64 March 18th, 2020 at 9:55 pm
In terms of the natural selection process in the evolution of viruses, it seems like an obviously good adaptive trait to delay symptoms for several weeks so that the virus can spread well. So why haven’t we previously seen a lot of viruses with this feature?
Comment #65 March 18th, 2020 at 9:58 pm
Matjaz #17:
How do you feel about progress theoretical computer science has made over the last 10-20 years? (In the sense of has there been too little, what has been most remarkable about it, etc.)
Let me restrict the scope to the last 10 years to make this more manageable. In one sentence, I’d say TCS over the past decade has done less remarkably than we might’ve liked in the creation of new concepts and paradigms, but more remarkably than we had any right to expect in solutions to big open problems. Maybe both of those reflect a field that’s getting more mature and more sophisticated.
See, it’s like this: when I or others give talks extolling the “revolutionary new concepts” of TCS, we still generally like to talk about zero-knowledge proofs and PCP and inapproximability and Shor’s algorithm—i.e., all stuff that was new when it was discovered back in the 80s and 90s. Compared to that period, our foundational concepts seem to have reached an era of relative stability.
On the other hand, if you want the solutions to longstanding problems … holy crap, what a decade we’ve had! No, not P vs. NP, and not even the Unique Games Conjecture. But just to take a few unrepresentative examples close to my own heart:
– NEXP⊄ACC (Williams 2011) and related developments
– New separations between query complexity measures, resolving decades-old questions (various authors, ~2015), as well as refutation of the approximate log-rank conjecture
– Graph Isomorphism in quasipolynomial time (Babai 2016)
– Oracle separation between BQP and PH (Raz and Tal 2018, completing my program from 2009)
– Cryptographic method to prove the result of an arbitrary quantum computation to a classical skeptic (Mahadev 2018)
– Proof of the Sensitivity Conjecture (Huang 2019)
– MIP*=RE (Ji et al. 2020)
Every one of these felt to me like some amazing Christmas gift that we had no particular right to expect.
Comment #66 March 18th, 2020 at 10:04 pm
Hi Scott,
How is Gil Kalai faring now that his world view has been shattered ? 🙂 Will he recover before or after the Corona Diaries have faded from our consciousness :=)
Comment #67 March 18th, 2020 at 10:16 pm
Joshua Zelinsky #20:
Should we consider the MIP*=RE result, together with the zero-gap MIP* result as evidence that quantum computers may be stronger than we’d otherwise expect, or at least that our intuition is not nearly as reliable on them as we’d like?
That’s an interesting question, a question worth reflecting on, but I’d like to defend the view that the answer is basically “no.”
MIP* was always an extreme outlier among quantum complexity classes, in our inability to place any reasonable upper bound on its power (“not even computable!”). And the reason for that was sort of understood since the beginning: it’s because for MIP*, unlike for all those other classes, there was never any bound on how many qubits the provers might need to play their optimal strategy. And thus (again unlike with all the other classes), one was naturally led to consider Hilbert spaces of hyper-mega-exponential and even infinite dimension. So, as extraordinary as MIP*=RE is—it deserves every accolade being heaped on it—I haven’t yet seen any indications that it should lead to the discovery of new quantum algorithms down here in our “sublunary realm” of BQP and QMA and so forth.
Comment #68 March 18th, 2020 at 10:17 pm
Hi Scott. I have to preface this one by saying I’m wondering about it for real, and don’t have a conclusion myself. Have things gotten sufficiently awful/dangerous to humanity that those of us who work on long-range, “advancing human knowledge” type work should make the sacrifice of tackling less-interesting but more immediate-benefit problems?
Comment #69 March 18th, 2020 at 10:26 pm
Do you think the class of things (e.g. natural laws) which are mathematically possible is the same or smaller than the class of things which are logically possible?
(1+1=3 doesn’t seem to be a logical contradiction like “A and not A”; and “every natural number has a successor” doesn’t seem to be a logical truth like “A and not not A”. Yet 1+1=3 _feels_ very contradictory.)
Comment #70 March 18th, 2020 at 10:32 pm
Tamás V #22:
Do you think in a democracy the voters should never be blamed, only the politicians they vote for?
No, I’m happy to blame the voters as well. 🙂
Of course, each individual voter’s degree of culpability is many orders of magnitude less than that of the horrible leader they elected. That, combined with the practical need to engage those voters and try to change some of their minds, surely more than explains the moral focus on leaders rather than on voters.
(The exception that proves the rule here is of course Hillary in 2016, with the “basket of deplorables” into which she placed half of Trump’s supporters—being careful to exempt the other half. However accurate, that one unguarded remark plausibly tipped the scales and lost her the election.)
Comment #71 March 18th, 2020 at 10:41 pm
Do non-physical realms exist?
Or are things like life, thoughts, emotions, and consciousness perfectly described as emergent properties of Standard Model particles interacting in complex ways?
Comment #72 March 18th, 2020 at 11:08 pm
Vincent #24:
greetings from Philly! What is the most distant horizon that you somewhat regularly ponder for quantum computing, or what is the most far out thing that you can see people achieving through use of quantum computers.
bonus q: if this pandemic happened 5-9 years later, what way could you envision a qc being able to assist?
Greetings from Texas (but originally Philly)!
Since I specified one question per person, let me choose to field only your bonus question.
In a hyper-mega-optimistic scenario, one could imagine a quantum computer being used (for example) to help simulate the molecular constituents of candidate drugs or vaccines for coronavirus, as for pretty much any other disease. Notably, Summit—the largest supercomputer currently on earth—is apparently now being used for exactly those sorts of problems. Summit last showed up on this blog just a few months ago, when Google’s 53-qubit QC was beating it at random circuit sampling (albeit, not yet as decisively as we’d like). Long story short, we’d expect a QC to be helpful for biochemistry problems to whatever extent
(1) quantum many-body effects were actually important for the problems, and
(2) no classical shortcut could be found to handle those specific quantum many-body effects.
Having said that, even supposing these benefits are eventually realizable with a QC, it would be a much taller order to realize them within the next 5-9 years … especially since it doesn’t look likely that “truly scalable,” fault-tolerant QC will be achieved in that timeframe.
And even more to the point: there are so many prosaic things that we could be doing to mitigate the crisis but aren’t—testing, contact tracing, building millions more masks and respirators, clearer and earlier quarantines, more testing, huge cash prizes for successful interventions, overriding most of the usual scruples surrounding vaccine and drug development (controversial but I’ll stand by it), e.g. putting remdesivir in every CVS if experts merely think it will do more good than harm, still more testing…—there’s so much low-hanging fruit, I say, and even unpicked fruit that’s now rotting on the ground, that part of me feels like it’s obscene even to be talking right now about potential solutions as faraway and exotic as QC.
Comment #73 March 18th, 2020 at 11:21 pm
Scott #33:
Something else: https://en.wikipedia.org/wiki/Avatar:_The_Last_Airbender
Comment #74 March 18th, 2020 at 11:26 pm
egan #28:
What is you best bet (with associated scientific reasoning) for the final number of COVID-19 related deads.
If the disease continues to spread exponentially, unchecked by drugs or a vaccine, then easily half the world’s population could get it before herd immunity starts to kick in. And a 1% case fatality ratio seems like a reasonable splitting of the difference—on the one hand, data from the Diamond Princess and Hubei suggest CFR below 1% once you account for mild and asymptotic cases; on the other hand, data from Italy shows that CFR can go well above 1% once you run out of respirators.
Under the above assumptions, we’d be talking about ~40 million dead worldwide.
Of course, if our civilization’s historic though belated retreat from meatspace into cyberspace manages to “flatten the curve”—by which I really mean, buy enough time until a vaccine or effective treatments can be discovered—then the worldwide fatalities could be much less, even well below 1 million.
Conversely, though, if the virus mutated into something deadlier, or if (for example) the collapse of global supply chains led to famines or wars, the total dead could of course be even more than 40 million.
Comment #75 March 18th, 2020 at 11:29 pm
Mike #30:
How likely do you think it is that Trumps morally and intellectually debased response to the pandemic will lead to him losing the upcoming election?
Not as likely as I’d like! 🙂
Comment #76 March 18th, 2020 at 11:50 pm
eigen #32:
Any books you have read recently that you’d like to recommend?
Sure!
The Sins of Jesus by Richard Muller—yes, that Richard Muller, the well-known contrarian physicist at Berkeley
(fellow non-Christians: don’t be put off by the title! it’s basically an astonishingly plausible, page-turning, admiring yet 100% naturalistic fictionalized autobiography of Jesus, narrating step-by-step how, seeking to make people love their neighbors, he ends up starting a new religion despite not intending to. Muller was raised an observant Catholic, then became a doubter after studying physics, and this book is one of the most striking attempts to reconcile science and faith I’ve ever encountered)
In Defense of Elitism by Joel Stein.
This book is weirdly misnamed—Stein really means something more like “In Defense of Expertise.” But think of a now well-known genre—namely, the writer who crisscrosses America interviewing people from all walks of life, trying to figure out how Trump could’ve possibly won the election—but written in the comic style of Dave Barry.
Superforecasting by Philip Tetlock.
A classic of rationalism that I somehow hadn’t gotten around to, until I stayed at the home of the more famous Scott A. (the Slate Star Codex one), and made a note of everything on his shelf that I really needed to read. 🙂
Comment #77 March 18th, 2020 at 11:53 pm
Everyone: Thanks for the questions! With every one of them, I felt like a got a little bit more of my mojo back in this dark and depressing time. Having now fielded an even twenty, I’m signing off for the night, but will handle the remaining questions (including the one that requires Lily’s input) tomorrow.
Comment #78 March 19th, 2020 at 12:11 am
Is human consciousness a quantum phenomenon?
Comment #79 March 19th, 2020 at 12:14 am
So in this comment, Mateus Araújo pointed out that the MIP*=RE result isn’t really just using the set of quantum correlations, but also the fact that the provers are constrained to obey quantum mechanics. Can we separate these two factors, defining MIP-analogues with what correlations are allowed on one axis, and what constraints the provers have (don’t know enough to know what the appropriate formalization is here — Mateus?) on the other axis? And (hoping this doesn’t count as a second part) do you (or anyone else here 🙂 ) have any idea what the resulting classes would be equal to, or what we should expect them to be equal to?
Comment #80 March 19th, 2020 at 12:41 am
Why do you feel the need to bring up Amanda Marcotte’s name every now and then in a sort of self-righteous martyr kind of way? It’s unbecoming of you. Most people acknowledge that what happened to you after 171 was ridiculous, and don’t take the vapid writings of radicals like her seriously. Are you still not over it?
Comment #81 March 19th, 2020 at 12:45 am
As a policymaker what sort of algorithm (or even broad framework) should you use to apportion resources (money) to research into different problems, given the variation in probability, impact etc. ?
To clarify: Say, you are a top science funding czar (for US, or even for a global body like the Melinda Gates Foundation) how do you distribute your research money allocation into say {Pandemics, Global Warming, Quantum Computing, Asteroid Apocalypse defense, Malaria, Alzheimers etc. } Does this have to be just arbitrary, subjective etc. or can we come up with some (even vaguely) quantitative guidelines based on perceived risk, impact, horizon remoteness etc.
Comment #82 March 19th, 2020 at 12:57 am
A few weeks ago, there was press about some people who generated all 68 billion possible 12 note sequences out of the 8 notes above Middle C, turned it into a MIDI file and uploaded it to SoundCloud. Their stated motivation was to place all the melodies “in the public domain” so that no one could ever sue anyone else for copyright infringement on a melody (which is apparently a thing), so long as that melody was made after 2020 .
So my question to you, Scott, as a music lover, computer scientist, philosopher, and jurist, is this: once you are elevated to the Supreme Court, and this case reaches you, will this fly?
They say the reason they stuck to 12-long sequences of 8 notes was not wanting the file size to get too big. In your future ruling will you insist that it be a MIDI file, or can it be any set of instructions that generate that MIDI file in polynomial time? Or if you insist that compression is not allowed, will you permit them to upload a quantum state that is a superposition over all possible melodies?
link for reference: https://www.theatlantic.com/technology/archive/2020/02/whats-the-point-of-writing-every-possible-melody/607120/
Comment #83 March 19th, 2020 at 1:08 am
I only recently started reading this blog so maybe I have missed this but I really like your banner with the advice on taking one piece of information from this blog. What would be the second piece of information to take from this blog?
Comment #84 March 19th, 2020 at 1:51 am
What is your probability to obtain a Nobel Prize?.
Comment #85 March 19th, 2020 at 2:09 am
If you were to start your research journey from the beginning today, which area would you choose?
Comment #86 March 19th, 2020 at 2:25 am
Can I swap places with your daughter and get personalized math lessons from the author of Quantum Computing Since Democritus?
Comment #87 March 19th, 2020 at 2:54 am
Something that has bothered me for a long time…
Say we have a machine A which takes an input string, s_0, and produces an infinite sequence of output strings, s_1, s_2, … Things like this, cellular automata for example, are often considered universal computers because they can “simulate” a turing machine. This seems to mean we can provide an encoding function to map the input of a particular turing machine to s_0, and a decoding function which turns some of the sequence s_0, s_1, … into the intermediate or halting states of that machine. But turing this into a formal definition seems problematic. At one extreme, I don’t want a machine that simply stores a computer program and iterates a counter to be considered universal. If I somehow had a program that simulated my brain and I uploaded it into such a machine, I wouldn’t expect to experience anything. Yet I can provide E, D that turns the outputs of this into the states of a computer which actually computes the program. At the other extreme, I don’t want to insist that E, D be completely straightforward, I can think of cases of A where they are required to be a bit convoluted and in which I’d still expect to have a conscious experience if I were to upload myself into A. Can you answer the question, what is the maximal set of triples A, E, D that are universal in the sense I am trying to get at with the mind simulation thought experiment? If not, can you explain why this is a silly or malformed question caused by some simple misunderstanding so I can stop thinking about it?
Comment #88 March 19th, 2020 at 3:22 am
What do you think the COVID situation says about x-risk worries in general, and AI specifically?
I’m especially thinking along the lines of Yudkowsky’s argument in “No fire alarm”, which you’ve probably read, but a high level summary is: “there’s not going to be a fire alarm to tell us we *now* need to start worrying about AI”.
Comment #89 March 19th, 2020 at 4:11 am
Scott why the most of the world main leaders (presidents,PMs etc) say that we (population) are in a war?
Comment #90 March 19th, 2020 at 4:14 am
Quantum chemistry is a hard, relevant, and obviously, quantum, problem. Why do you think some great physicists are obsessed with subatomic particles and even exotic toy quantum field theories when this important quantum problem is just before our eyes? Why is chemistry not considered cool by so many cool people?
Comment #91 March 19th, 2020 at 4:18 am
Taking cue from covid, any other disasters that you think we are grossly under prepared for and should put more resources into?
And I mean near term Catastrophes eg say a immediate to 10 year horizon. Not things like global warming etc.
Comment #92 March 19th, 2020 at 4:45 am
Dear Scott,
My first time posting here! I discovered your blog a few months ago, got completely hooked, and even ended up reading your entire essay “ghost in the quantum turing machine”. Thank you so much for everything you opened my eyes to!
Now this question has been itching me ever since: Would you say that you, personally, have ever experienced true free will? And if so in what situation(s)?
I’ve asked myself this question while reading your essay, and to my despair couldn’t find any convincing example.
1) Whenever I have to take a big life-changing decision, I feel that I turn the question so much around my head, rationally balancing the pros and cons, that my eventual decision would in fact be entirely predictable given my past and current life, precisely because it *is* based on rational thinking
2) Whenever I have to chose between ordering a pizza with our without mushroom, I feel that I end up leaving this impossible choice to my current physiological state, which pretty much feels like throwing a biased dice in my brain, whose precise bias could probably be completely inferred from my current sugar level or whatnot
3) Faced with an abstract choice such as “blue box or red box”, the random dice feeling is even stronger. Sure I end up “choosing” a box, but if it is based on a completely arbitrary and random process, how is that *free*?
Pretty much anything else I ever do is sort of “following the flow”, with varying levels of self-awareness. Step n leads to step n+1 which leads to step n+2 … How to break out of this??
Comment #93 March 19th, 2020 at 5:18 am
Hi Scott!
Avi Wigderson says that he didn’t even know what research was when he was accepted at Princeton for grad school. He did many courses and no research at all in his undergrad. (Source: HLF interview)
Nowadays, an undergrad without some research progress (significant for an undergrad) seems to have a hard time getting accepted at a “tier-1” grad school. Seems like too much to expect from an undergrad.
Shouldn’t undergrad be for the deep study of a field (instead of research) (at least in fields like mathematics and theoretical CS)?
Feel free to argue against my premise or any implicit assumptions that you could detect.
Thanks! Stay safe!
Comment #94 March 19th, 2020 at 6:14 am
Do you believe in telepathy?
Comment #95 March 19th, 2020 at 7:09 am
I feel like I should have anticipated this AMA and thought a bit more about what question to ask you (I hope this isn’t the last AMA here).
My question is: what do you think about bounded arithmetic, proof complexity, and generally things around that circle of ideas?
Comment #96 March 19th, 2020 at 7:38 am
I feel that referring to COVID-19 as a new “Black Death” is completely inappropriate. The black death eradicated 1/3 of Europe’s population. In contrast, while the mortality rate of COVID-19 is mostly unknown yet, even the most pessimistic estimates do not put it above 4%. One should be careful with such things because it already looks like the panic generated by COVID-19 is going to be orders of magnitude more destructive than the disease itself.
Comment #97 March 19th, 2020 at 7:38 am
Who are the leading candidates, in your opinion, for the next Turing Award?
Comment #98 March 19th, 2020 at 7:42 am
Or, if you prefer, who are the ones most deserving the award?
Comment #99 March 19th, 2020 at 7:44 am
If the acceleration of the universe is itself accelerating and we’re heading for the Big Rip would the universe be capable of performing an infinite number of calculations? It seems to me that in theory you could extract useful work out of Dark Energy and at a exponentially increasing rate, so you could run your computer faster and faster, so even though the amount of time available would be finite the number of calculations might not be. Of course eventually the Dark Energy would start to tear your computer apart but even so….
John K Clark
Comment #100 March 19th, 2020 at 7:52 am
I’ve occasionally seen mention of a quantity called “quantum discord” that apparently quantifies quantum correlations that are not caused by entanglement. I’ve heard allegations that it can even be useful for quantum computing (the “Deterministic quantum computing with one qubit” or DQC1 model), which I’m very skeptical of. Could you discuss at a relatively non-technical level (either here or in a separate blog post) what “quantum discord” is and whether it’s actually useful for quantum computing?
Comment #101 March 19th, 2020 at 8:11 am
What do you think of academics having to write diversity statements as part of a job application?
Comment #102 March 19th, 2020 at 8:47 am
kind of a big fish, but worth a shot:
What is your frank opinion of the overarching geometry-from-entanglement, it-from-qubit program? If that’s too broad (or too close to home), here’s a very narrow subquestion: what is the replica wormhole result telling us?
Comment #103 March 19th, 2020 at 9:08 am
Ernest Davis #25:
What are your daughter’s favorite fashion games?
OK, I guess “game” rather than “games.” Lily tells me that right now, she’s into something called Fashion Famous on Roblox.
Great news, though! Lily and I have decided that I’m going to give her math and science lessons, and we’ll record them and try to make lecture notes! Think Quantum Computing Since Democritus, except with nothing allowed in unless I can literally explain it to a 7-year-old.
Comment #104 March 19th, 2020 at 10:15 am
What do you think of Sabine’s new essay on “Unpredictability, Undecidability, and Uncomputability” and her contention that, “In summary, mathematical impossibility-theorems are relevant in science, not because they tell us something about nature itself, but because we use mathematics in practice to understand observations, and the theorems tell us what can expect of our theories.”
Emphasis mine.
Comment #105 March 19th, 2020 at 10:17 am
Do you own a gun? If so, what kind, etc? If not, have you thought about getting one? Where I am, it’s easier to get a permit to purchase a gun than it is to renew a driver’s license.
Comment #106 March 19th, 2020 at 10:42 am
Do you think the (asymptotically) best quantum error correcting codes are likely to be stabilizer codes?
Comment #107 March 19th, 2020 at 10:45 am
What was the flavor of the last piece of cake you ate? (Mine was blueberry-chocolate)
Comment #108 March 19th, 2020 at 10:46 am
Are there examples of weak entanglements? Where if I measure one of two entangled particles as being in a certain state, I do not know for sure the state of the other, but I also know more about its state than by simple chance?
Comment #109 March 19th, 2020 at 10:48 am
Hi Scott, thanks so much for doing this.
Let’s say you have a very good estimate of the fatality rate for a disease about as infectious as COVID-19. At what fatality rate do you decide to order shelter-in-place restrictions (similar to the ones recently put in place in San Francisco, say)?
Comment #110 March 19th, 2020 at 10:54 am
How does logistics/optimization look among possible quantum comptuting applications? It may be low hanging fruit, but on what planet? On while we are on fruit, Is the work to program quantum comptuers likely to bear and interim fruit via simulation for logitstics/optimization on class computers?
Comment #111 March 19th, 2020 at 10:57 am
Richard at 64 asked: “In terms of the natural selection process in the evolution of viruses, it seems like an obviously good adaptive trait to delay symptoms for several weeks so that the virus can spread well. So why haven’t we previously seen a lot of viruses with this feature?”
Not that anybody asked *me*, but hey, it’s the Internet:
My reaction is that a virus is probably the simplest possible biological machine; if I recall correctly it only has about 20 genes worth of genetic material. It does not have a lot of scope for variation. Many bacteria have over 10,000 genes, and the total mass of bacteria outweighs the sum of all other biological creatures by about ten to one (quoting Stephan J. Gould from memory). Talk about a massively-parallel mutation process! Viruses don’t have the same evolutionary potential by a factor of at least 100,000. I’m just a layman, speaking from general knowledge, so there are probably other reasons also, but that one seems feasable to me. Evolution (and human progress also) works by trial and error: the more trials the better the chance of success.
I guess it might also be a factor that a super-virus that wiped out all the creatures it preys upon wouldn’t then have anything to prey upon.
Comment #112 March 19th, 2020 at 11:22 am
What unsolved problems in quantum complexity theory do you think are the most likely to be solved next?
Comment #113 March 19th, 2020 at 11:28 am
Elfnysien #33:
For problems already known to be in NC/RNC, do we know if quantum provides asymptotic improvements in work, e.g., for directed reachability/perfect matching (problems that we know how to parallelize in polylog depth using a lot more gates than the fastest sequential algorithm)?
I’m not aware of a better quantum size/depth tradeoff for problems like matching or reachability (if anyone else does, please chime in). Note that the quantum speedups that we know for such problems tend to be Grover-based, but Grover inherently requires large depth. Also, it would be a real breakthrough if you could do directed reachability in quantum logspace (BQL), which is related though not identical to what you’re asking. These are good questions though!
Comment #114 March 19th, 2020 at 11:32 am
What changes would you (and your kids) make to elementary education in the US?
Comment #115 March 19th, 2020 at 11:38 am
What do your kids think that you and Donna do at work?
There are some very funny videos of kids answering this type of question: https://www.youtube.com/watch?v=tHZTEDkZeHw
Comment #116 March 19th, 2020 at 11:38 am
Swadhin #36:
When you feel, all the work you are doing for years so passionately is useless in the face of this pandemic, you become terribly hopeless. How do you combat that ?
I’m trying to combat it right now through this AMA. 🙂
Besides that, eating good meals, playing with my kids, (soon) teaching them some math, but most of all, reminding myself that this pandemic didn’t make my research useless … my research was already useless! 😀
Comment #117 March 19th, 2020 at 11:47 am
In the following talk (https://youtu.be/d5BhIFumJXA?t=86) Professor Abramsky seems to imply that the unification of the two communities may be able to attack big problems like P vs NP.
What do you think about the chasm between Theory A and Theory B in theoretical CS?
Comment #118 March 19th, 2020 at 11:53 am
Martin #37:
In quantum mechanics, the order by which operators are applied matters. Does this mean that _time_ somehow is involved already at the commutator level of the formulation of QM?
I’m not sure I fully understand the question. Yes, in quantum mechanics you have operators that don’t commute. But as soon as you explain to me why that matters, in terms like “see, it matters because if you measure position first and then momentum, you get different results than if you measure momentum first and then position” … well then, hasn’t your explanation already presupposed the concept of time? Also, didn’t we already have plenty of non-commuting operations that we could do even in classical physics (albeit not measurements), like putting on underwear and putting on pants?
[Note: My warranty on the above answer does not extend to quantum gravity. Theorize there at your own risk. 😀 ]
Comment #119 March 19th, 2020 at 11:57 am
Vincent Paris #38:
what potential use of quantum computers brings you the most joy?
As I’ve said in dozens of my talks, the application of QC that brings me the most joy is refuting Gil Kalai, Leonid Levin, and all the others who said that quantum speedups were impossible in our world. 😀
Comment #120 March 19th, 2020 at 12:07 pm
What would you think is a good Quantum information and computing project idea will be for an undergraduate physics student whose knowledge about about Quantum information and computing comes from your book and some YouTube lectures?
Comment #121 March 19th, 2020 at 12:11 pm
Steve L #39:
Scott, Why aren’t you terrified of the flu season every year, when influenza has killed 16,000 Americans this winter versus 100 for coronavirus?
This one severely strains the saying about there being no such thing as a stupid question!
Coronavirus is on an exponential trajectory, with the number of cases doubling every 4 days or so. And unlike with the flu, there’s no vaccine. Absent heroic containment measures (of the sort many countries are finally doing, though too late), there’s no reason why this shouldn’t infect half the human race over the next couple of months, before herd immunity would finally push the r0 below 1. Furthermore, estimates for the case fatality rate are way higher than the flu’s—let’s say 1%, under super-optimistic assumptions about the world’s ability quickly to ramp up medical capacity.
If so, then we’d be talking 40 million dead this season. The last time the flu racked up numbers like that was in 1918, and that was terrifying.
Comment #122 March 19th, 2020 at 12:19 pm
Dear Scott:
At a high level, is the role of error correcting codes in the PCP theorem?
Comment #123 March 19th, 2020 at 12:58 pm
Is there a natural problem s.t. for any algorithm solving it within time complexity t(n), there is another algorithm solving it within time complexity t'(n) s.t. t is superpolynomial in t (i.e. for any polynomial p and n>>0, t(n) > p(t'(n)))?
Comment #124 March 19th, 2020 at 1:05 pm
Hey Scott, longtime lurker here. I have a lingering MIP*=RE related question I’ve been waiting for an opportunity to ask you. My understanding is that this means that the tensor-product and commuting operator models of entanglement are unexpectedly not equivalent.
It sounded to me like previously we had those two alternative models of entanglement that we thought were equivalent, at least in the limit, but that since we thought they were equivalent, we could say that we had a complete, correct understanding of entanglement (if not of all its consequences, of course). But if we now know they are not equivalent, can we still say that? Do we know which one is incorrect? Do we know if either is correct?
Comment #125 March 19th, 2020 at 1:40 pm
Hej hej from apocalyptic Sweden!
Do you know any implementations (open source would be great) of Ewin Tang’s recommendation system, and if/where the algorithm has been applied in industry?
Or what would be the reasons it wouldn’t be usable in practical applications, say like youtube’s recommendation system or something like that?
Comment #126 March 19th, 2020 at 2:03 pm
When you wake up in the morning, what motivates you to get out of bed?
Curious to know if you’re biologically straight-jacketed by Maslow’s universal human needs like the rest of us: http://scheff.faculty.soc.ucsb.edu/main.php?id=32.html
Comment #127 March 19th, 2020 at 2:49 pm
If George Washington became King in 1789 and his family ruled ever since, wold this be better than the current situation and Trump? The King could decide what the people needs without caring for stupid voters.
Comment #128 March 19th, 2020 at 2:49 pm
Hi Scott,
what’ the big question that you’d love to solve? Not talking about P vs NP here, but rather something more realistic 😉
Comment #129 March 19th, 2020 at 3:05 pm
Scott @116
Yes the number of cases is doubling every four days, but much of that reflects much more testing going on. More testing could mean more reported cases even if the actual number of cases is not changing. Until we can get a testing baseline, we do not know the actual rate of spread.
Comment #130 March 19th, 2020 at 3:16 pm
Dear Scott,
living in nearly locked down Germany, caring for a locked in kid, organizing virtual lectures and worrying about a challenged society I totally empathize with you. I therefore wanted to share, that the thing which currently keeps my mind up and occupied is reading your book (yeah, I am late, but nevertheless) and trying to follow your argumentation and getting all the puns. Thanks :).
My question: at the end of the intro you write “Here’s hoping that, in 2020, this book will be as badly in need of revision as the 2006 ecture notes were in 2013.”
-> do you plan a revision? I would be eager for buying it.
Comment #131 March 19th, 2020 at 3:41 pm
Everyone: please, no more questions! (Comments on previous questions and answers are fine.)
I’m grateful for all the questions, and I now have more than enough! I’ll get to the remaining ones over the next few days. Thanks again!
Comment #132 March 19th, 2020 at 3:47 pm
#122
Sorry, I have to make a correction:
At a high level, *what* is the role of error correcting codes in the PCP theorem?
Thank you for your insight.
Comment #133 March 19th, 2020 at 3:48 pm
Richard #64 – there are lots of such viruses. HIV, HPV, herpes all do that. Similarly with bacteria (e.g. syphilis).
More spectacularly, there are a whole lot of viruses which infected people (or animals, way back in history) and caused so little by way of symptoms that the immune system never bothered with getting rid of them; a non-trivial portion of the human genome looks likely to have come originally from viruses.
But in order for a virus (or any parasite, really) to be viable, it has to spread faster than it’s knocked out, either by the immune system or death of the host. That’s not trivial, and broadly there are two strategies that seem to work: one is hang around without causing much damage (to avoid immune system attention) and spread when there is close contact (e.g. sexual). HIV is broadly in this group, except it of course avoids immune system attention more aggressively.
The other is to find a way of spreading fast enough that the immune system and death of the host don’t keep up. But this isn’t all that easy; infected people do not in fact leave trails of virus behind them without some reason, and generally viruses find the outside environment to be fairly hostile. The standard approach here seems to be to cause enough damage that infected people tend to spray virus around, usually damage to nose / throat / lungs which causes droplets. This is more or less guaranteed to get the immune system interested. In evolutionary terms, overdoing it is a bad idea. Stuff like colds, which don’t cause much damage, stay around. Really nasty things, like Ebola or the Black Death, don’t in the long term. The Black Death is an extreme example: you still don’t want to catch the plague today, but even without modern medicine you stand a significantly better chance of surviving it than people 700 years ago, simply because the most susceptible were killed off.
So a virus doesn’t have much of a possibility of sitting around for a few weeks without causing obvious symptoms in order to spread. In particular, that’s true because viruses are very simple; they don’t really do things like ‘stage A, stage B’ except where the immune system forces them to (i.e. stage B is caused by the immune system response). There are, of course, more complicated diseases which do do something more subtle to spread; again, syphilis is a good example. Toxoplasmosis may have behaviour-altering effects which aid its transmission. Going to extremes, ophiocordyceps unilateralis is a fungus which infects ants: an infected ant changes behaviour radically in such a way as to maximise the chances of fungus spores infecting more ants.
Comment #134 March 19th, 2020 at 3:59 pm
A comment geared towards those who with MIP*-related questions. I’ve started a piazza forum for people who want to ask/answer/discuss questions related to MIP*: http://piazza.com/utoronto.ca/summer2020/mipre. To sign up, use the access code “quantum”.
It’s quite bare at the moment, but hopefully it will be a useful resource for interested folks!
Comment #135 March 19th, 2020 at 4:05 pm
You might want to record the discussions with your 7 yo, although that might take away their authenticity. If you can record the material you discuss, it would be a book eventually.
Comment #136 March 19th, 2020 at 4:14 pm
@116 and @129 — “doubling time” can be analyzed by looking at the log slope of the number of cases. The best resource for that that I’ve found is here:
http://nrg.cs.ucl.ac.uk/mjh/covid19/
It looks like with no intervention the log slope is ~1.35 (doubling time ~ 3 days), but with interventions common in the Western world the log slope is ~1.22 (doubling time ~4 or 5 days). More severe interventions and widespread PPE in South Korea and Japan seem capable of making the log slope shallower.
Comment #137 March 19th, 2020 at 5:08 pm
Miquel Ramirez #40:
why do so many physicists seem to misunderstand basic facts of CS theory such as the halting problem? I find this rather irksome, as physicists that deem basic computability theory results as irrelevant to their work seem to be oblivious to the problem posed by the following observation: the validation of their theories essentially depends on complex computational devices – sometimes all hardware, sometimes a stack of hardware and software – being certified to be producing meaningful measurements in their experiments.
I mean, we don’t necessarily expect the people working in one field to understand the central insights of a very different field. Like, I don’t understand Einstein’s field equation, or even Maxwell’s equations, more than superficially (I can surely state them and define each term with only minimal use of Wikipedia, but not much more… 🙂 ).
Having said that, while I’ve gotten enormous comedic mileage over the years from ragging on my physics friends for their CS howlers (“NP means Not Polynomial! BosonSampling is a #P-complete problem!”), I prefer to do so with a concrete example in hand of something that ignorance of CS caused them to get wrong.
And the fact that particle physics experiments rely on computers is not a good argument for why theoretical physicists need to learn theoretical CS. Like, would we also say that particle physicists need to be expert metallurgists, since so many components in the LHC experiments are made from metal?
A far stronger argument for why theoretical physicists should learn some CS theory—and conversely, for why CS theorists should learn some physics—is provided by the convergence between the fields epitomized by quantum computing and information, and even more recently by “It from Qubit.” And I’m delighted to report that this argument is working! I.e., the CS sophistication of the physicists who I talk to (and vice versa) has very noticeably increased over the last 10-15 years. So just give this one some more time!
Comment #138 March 19th, 2020 at 5:33 pm
Thanks very much for your answer, Scott, entertaining and intellectually challenging at the same time.
> the fact that particle physics experiments rely on computers is not a good argument for why theoretical physicists need to learn theoretical CS. Like, would we also say that particle physicists need to be expert metallurgists, since so many components in the LHC experiments are made from metal?
I don’t buy that argument when the research is such that it is formulated, articulated and pretty much running on algorithms to process ambiguous and very noisy observational data. For example, the current discussion about the value of the cosmological constant, and its implications on the assumed existence of yet to be observed fundamental particles that provide a rationale for estimated values.
> So just give this one some more time!
Probably you guessed who I was thinking about 🙂
In any case, I didn’t want to come across too negative, as you say, there’s great opportunity on convergence, not just on “big picture” problems such as what the f*ck the universe actually is and why latkes don’t grow on trees, but also on “pedestrian” problems such as programming quantum devices or optimizing and verifying the design of nanomechanical systems.
Comment #139 March 19th, 2020 at 5:50 pm
Neil #41:
How much economic cost do you think we should bear in order to flatten the curve by shutting down economic and social intercourse? For example, if the shut down would lead to a major depression on the order of the 1930s, do you think it would still be worth it?
The question of just how much economic pain this is worth is an extremely hard one—the coronavirus could cost millions of lives, but so could another Great Depression. As John Ioannidis points out, it’s a question that can only really be addressed with more data—data that we could have gotten by, y’know, massive early testing. In the absence of that data, it seems to me that we have no choice but to proceed on the assumption that this virus will kill >1% of the human population if not contained, which would suffice to justify a pretty massive response.
Comment #140 March 19th, 2020 at 6:00 pm
D. Al Ektick #42:
Which two (historical) figures would you like see debating the human condition? (Could be from different centuries!)
Bertrand Russell and Jesus.
Comment #141 March 19th, 2020 at 6:08 pm
richard horan #43:
Scott, Do you know if they are using CRISPR technology in their search for a vaccine for the corona virus?
According to my Google search just now, CRISPR is indeed (unsurprisingly) one of the tools now being used to study the virus—see for example here, here, here. But I have no idea whether this work will lead to a vaccine.
Comment #142 March 19th, 2020 at 6:10 pm
Nils #125: Tang addresses this question herself in her blog post “An overview of quantum-inspired sampling” (https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-inspired-sampling/), subsection “Implications -> For classical computing”. She is “cautiously optimistic about the implications of this work for classical computing. … If I had to guess, the best chance for success in dequantized techniques remains recommendation systems, since speed matters significantly in that context. I view the other algorithms as significantly less likely to see use in practice, though probably more likely than their corresponding quantum algorithms.”
(Does anyone know how to make hyperlinks in these blog comments?)
Scott #131: I would suggest editing the original post to say right at the top that you’re no longer accepting new questions. Your comment announcing closure to new questions is a little hard to find, and will only get harder as it gets buried deeper above new comments.
Comment #143 March 19th, 2020 at 6:41 pm
polylog #44:
Have you ever tried growing a beard for an extended amount of time?
Yes. For a few months, when I was 20, and working on the quantum lower bound for the collision problem. A friend said that it looked like a rabid animal attacking my face. I’m sure I have photos somewhere, but not sure if I should share them.
Comment #144 March 19th, 2020 at 6:44 pm
Boules #45:
Honest question to overcome my ignorance about Google’s quantum supremacy: If you take a bundle of 1,000 Mikado sticks and let them drop to the ground, their distribution and orientation on the floor will be probabilistic but comply with a certain non-uniform probability distribution. By varying the height, the falling angle, the speed in which your hand releases the bundle etc., the Mikado drop even becomes “programmable”. I bet any classical computer would have a hard time sampling from the Mikado distribution on the ground. How is that not “Mikado supremacy”?
It’s not because there’s no reason for the difficulty of the simulation to increase exponentially with the number of Mikado sticks. We don’t care what a classical computer would “have a hard time” doing, if it wouldn’t have an asymptotically hard time.
Comment #145 March 19th, 2020 at 6:54 pm
A set theorist #46:
What advice do you have for someone who always dreamed of pursuing the “big questions” in science (and hasn’t given up about that dream), but found himself doing a postdoc in a technical (and somewhat esoteric) area of pure mathematics instead?
Go pursue the big questions! Don’t wait for anyone to give you permission! That might mean pivoting your research to bigger questions (and from there to bigger ones, and so on). It might mean finding a way to relate your existing research to the big questions—i.e., to draw broader lessons from whatever you’ve done. Or it might mean starting a blog where—as it turns out—you can just spout directly about whatever big questions you want, with no quality control or anything! (Except for the reactions of whatever readers you attract.)
But also, as you do the above, you’ll need to make a living! That might mean getting a day job; your day job might (or might not) involve research on more technical and esoteric questions. If you go the latter route, at least try to arrange that the technical and esoteric questions are of personal interest to you!
Comment #146 March 19th, 2020 at 7:23 pm
Craig Gidney #47:
What’s a recent research idea that you’ve had but that didn’t pan out?
To be honest, not much lately—not because my success rate is so high, but simply because I’ve had so little time for research and (alas) became more conservative in what I’d work on at all!
A few years ago, though, Marijn Heule (a world leader in SAT-solving, then at UT Austin) got me interested in attacking the famous Collatz Conjecture using automated theorem-proving tools. I designed a string rewrite system whose behavior encoded the Collatz Conjecture, and then spent weeks trying to prove weaker properties of the system—competing against Marijn’s software tools to see what statements I could prove. Long story short, we got to where Marijn’s tools could beat me, but we never got to where they could prove Collatz, or indeed anything else of much mathematical interest. If we’d proven Collatz I promise you would’ve heard about it! 😀
Comment #147 March 19th, 2020 at 7:32 pm
Victor #48:
How much is materials science expected to advance with mass availability (for industry) of practical quantum computers? Are we looking at possible room temp superconductors in our lifetimes in terms of R&D speedup?
No one knows. Room temperature superconductors might not even exist. If they do exist, they might be impractical for other reasons than temperature. If they exist and are practical, they might just be too hard to find, a needle in an exponentially large haystack of possibilities—a problem that (crucially) even a quantum computer would only modestly ameliorate, via Grover’s algorithm. Where a QC would really help this, would be if you had a list of promising candidates for room-temperature superconductors, but couldn’t feasibly simulate them classically because of complicated many-body quantum effects. In that case, a QC could save you the trouble of testing every last candidate in the lab—it could identify promising ones in a much more automated way.
Comment #148 March 19th, 2020 at 7:37 pm
BLANDCorporatio #49:
are parity games solvable in polynomial time?
Yeah, so I’m totally not the person who you should ask this. Find someone who’s worked on parity games and who has at least a slight intuition for them!
I will say, though, that if being in P is like having the coronavirus, then being in NP∩coNP is like having a fever and a dry cough but no runny nose.
Comment #149 March 19th, 2020 at 7:47 pm
Math Boy #50:
Boxers or briefs?
Boxers. Tried them once when I was ~18, have never wanted to go back to briefs.
Comment #150 March 19th, 2020 at 7:52 pm
fred #51:
At every single moment of your life, how do you know that you are Scott Aaronson without having to hold all at once in your consciousness every single biographical fact of Scott’s life?
Uhh … because I remember what it was like to be me one minute ago, and that includes remembering what it was like to be me two minutes ago, and so on in a great chain stretching all the way back to at least my toddlerhood? I.e., “transtemporal identity,” also known as linked lists? 🙂
Comment #151 March 19th, 2020 at 8:11 pm
Victory Omole #53:
What positives do you think will come out of this pandemic?
Some of them are obvious (and have been touched on earlier):
A big boost to online education, teleconferencing, telemedicine, and delivery services.
A massive (albeit temporary) drop in pollution, emissions, and traffic.
Tens of millions of people who suddenly have huge stretches of time to play with their kids, or read great literature (or even write it), or learn a new skill, or “pull a Newton” and think deep thoughts under a tree.
Other diseases, besides the coronavirus, that will take a hit from half the human race going into quarantine.
But the biggest positives would be a huge boost to our preparedness for future (and possibly even deadlier) pandemics, applying the lessons learned from the catastrophic failures this time; the total humiliation of the anti-vax movement; increased trust placed in actual experts; and a new emphasis on reality and truth when selecting political leaders. Note that none of those positives are in any way guaranteed—they all depend on what happens next!
Comment #152 March 19th, 2020 at 8:13 pm
Do you think Newton had an advantage because he did not have unlimited internet access?
Comment #153 March 19th, 2020 at 9:16 pm
Scott@139
Thank you.
Comment #154 March 19th, 2020 at 9:34 pm
Daniel Reeves #55:
Hi Scott! Could I convince you to try some clever commitment devices — like Beeminder of course[…]? Seems like it could be especially valuable right now!
Yes, you could! I tried StickK years ago, sort of liked it, but eventually abandoned it, when I found that I was fudging my progress rather than authorizing donations to the George W. Bush Presidential Library. 🙂 I’ll be happy to try Beeminder—maybe, at first, for something nearly impossible to fudge like my weight (I lost almost 20 pounds over the summer, and have since been trying to keep them off and stay at a good weight).
At least, I’ll sign up for Beeminder just as soon as I get around to it! Now, if only there were some clever way to force myself to follow through…
Comment #155 March 19th, 2020 at 9:46 pm
jonathan #57:
compared to other civilizational threats we’re facing, how do you rate dysgenic fertility trends (basically smarter/more education people having fewer kids)?
I think that would eventually be an issue (the “Idiocracy” scenario). But I also suspet that, well before it happens, other factors will come into play—if not a literal AI singularity, then genetic engineering of the human germline, to make any newborn another John von Neumann if desired. (Incidentally, I think it would be a horrible irony if no one ever worked toward that goal for reasons of “ethics.” What about the ethical implications of not doing it?)
Or, if you’re in the mood for cheer, I think it’s entirely plausible that climate change and/or wars and/or pandemics will sharply reduce the human population, and replace the dysgenic trends you mentioned with something entirely different. Alas, what replaces those trends might look less like selection for greater intelligence (or empathy, conscientiousness, etc.) than selection for spear-throwing abilities!
Comment #156 March 19th, 2020 at 10:16 pm
Peter S. Shenkin #58:
Follow-up to #1, which was “Will non-biological machines become conscious?”
Your reply was “It depends upon what you mean by conscious, but it’s possible, even likely.” (I hope this is an accurate paraphrase.)
My question is “How would you know, either way?” Feel free to supply the definition of consciousness (i.e., what you mean by conscious) upon which your response depends.
The central and obvious difficulty is that you wouldn’t know. But Alan Turing’s famous point in 1950 was that that doesn’t mean all is lost. In particular, we regularly judge other people to be conscious, despite the metaphysical impossibility of knowing for sure, largely on the basis of their behavior. So it stands to reason that, if a machine could behave indistinguishably from a human, then regardless of whether it really, truly felt the pain and tasted the strawberries and cream, many thoughtful people would choose to regard it as doing so. And crucially, the question of whether such a machine can be built is no longer philosophical, but empirical! Science has traction with it!
Comment #157 March 19th, 2020 at 11:00 pm
Josh Brule #61:
You’re temporarily king and can issue any one decree that will be followed to the extent that it’s physically possible. But it can’t be anything that is considered “political” (let’s say, if a majority of randomly surveyed American’s would agree that it is a political act).
What do you do with this very strange, temporary power?
Uhh, a ban on car alarms? On websites like NSF’s “FastLane,” which take more than a half hour of aggravation just to log in to? Would those be sufficiently non-political? Or how about a huge national stockpile of respirators and masks, to be used in pandemics?
Comment #158 March 19th, 2020 at 11:10 pm
Josh #62:
Does the space of metaphysically true statements extend into Borel determinacy and the measurability of concretely definable projective sets or does it end somewhere else?
Yeah, those are tough ones. I’d be very interested in hearing arguments either way. I feel confident that statements in the arithmetical hierarchy are “down to earth,” in the sense that they’re ultimately phraseable in terms of finite computational processes, and we must have a clear conception of those processes if we’re engaging in mathematical reasoning at all. I feel equally confident that statements like AC and CH are “way up in outer space,” in the sense that one can give compelling accounts of the mathematical universe where either they or their negations hold. But statements in the Platonic stratosphere or mesosphere? Who the hell knows?
Comment #159 March 19th, 2020 at 11:22 pm
Richard #64:
In terms of the natural selection process in the evolution of viruses, it seems like an obviously good adaptive trait to delay symptoms for several weeks so that the virus can spread well. So why haven’t we previously seen a lot of viruses with this feature?
That’s an excellent question, and something I wondered about as well! Maybe designing viruses that spread aggressively and asymptomatically (I almost wrote “asymptotically”) is just a really hard engineering problem, since our immune systems are pretty good at responding to viruses and thereby causing symptoms. This problem has clearly been solved a few times in virus history. But for the old solutions we’ve had time to develop vaccines, and for the really old solutions we’ve had time to adapt evolutionarily.
If this is right, then
(1) we were lucky that nature failed to come up with totally new solutions to this engineering problem for quite a long time, and
(2) our luck just ran out.
Anyway, I’d love for any biomedical experts among my readers (Shtetl-Optimized must have some, right??) to correct me and/or add additional insights.
Comment #160 March 19th, 2020 at 11:37 pm
William Hird #66:
How is Gil Kalai faring now that his world view has been shattered ?
Why not go over to his blog and ask him??
I can tell you, though, that Gil has publicly taken the position that Google’s supremacy claim won’t stand—not because he thinks there’s a much faster classical simulation, but because he thinks there must’ve been some problem with Google’s experiment. (Gil’s thoughts about what the problem might be have repeatedly shifted, as several of his earlier objections were decisively answered.)
Comment #161 March 20th, 2020 at 12:01 am
David Karger #68:
Hi Scott. I have to preface this one by saying I’m wondering about it for real, and don’t have a conclusion myself. Have things gotten sufficiently awful/dangerous to humanity that those of us who work on long-range, “advancing human knowledge” type work should make the sacrifice of tackling less-interesting but more immediate-benefit problems?
That’s an enormous question that I can only answer for myself. I’ve absolutely had a sense of the world getting more and more “awful/dangerous,” as proudly ignorant demagogues take power and as science and expertise are increasingly spat upon. But that sense of dread has driven me in two diametrically opposed directions:
On the one hand, an urge to battle the encroaching darkness with whatever tools are at hand—jettisoning the intellectually interesting stuff entirely, unless it can pull its weight in the struggle.
But on the other hand, an urge to retreat even further into deep fundamental questions—in effect, giving up on the present and just trying to think or write for the ages, like some ancient who knows that he can’t save the collapsing Roman Empire but dreams that his scrolls will be rediscovered in a thousand years.
On some days one of these urges dominates, on some days the other. Perhaps the clearest byproduct has been an increasing impatience for stuff that falls between the two extremes—i.e., that’s neither of immediate use to humanity nor of enduring interest.
Comment #162 March 20th, 2020 at 12:24 am
Eric Cordian #71:
Do non-physical realms exist?
Or are things like life, thoughts, emotions, and consciousness perfectly described as emergent properties of Standard Model particles interacting in complex ways?
Nothing that’s non-physical exists physically. It might, however, exist non-physically. 🙂
As a simple example, I’m totally fine uttering statements like, “a family of Boolean functions with superquadratic gap between randomized and quantum query complexities exists“—even though the type of “existence” that we’re talking about clearly isn’t physical (some would call it Platonic).
So, having granted that much, I’m at least open to the possibility that conscious experiences “exist,” over and above the subatomic particles in the brains that house them. Or even that tables and chairs “exist” over and above the particles—perhaps in the Kripkean sense that the tables and chairs would still be tables and chairs, even supposing that we could change the laws of physics so that tables and chairs were no longer made of particles at all.
On the whole, though, I don’t lose a great deal of sleep over these questions, regarding them mainly as semantic disputes over what we want to mean by words like “exist.” I’ve read many ponderous debates about “reductionism vs. emergentism,” and don’t feel like I gained nearly enough insight to justify the time invested.
Comment #163 March 20th, 2020 at 1:13 am
Antoine Deleforge #92
you may like this mini-series:
https://wiki.lesswrong.com/wiki/Free_will_(solution)
if you’re in a hurry you can try reading the last few, or even just the last one; conversely if you’ve got time there’s plenty other stuff on that site I enjoyed reading
Comment #164 March 20th, 2020 at 1:43 am
” So why haven’t we previously seen a lot of viruses with this feature?”
Some thoughts in addition to Scott #159:
Imagine a virus identical to Covid-19 entering the human pool say 50 years ago. Would the increase in mortality have been as noticeable?
First, mobility being lower the spread could be slower and the virus could be perhaps naturally squelched. Second, baseline longevity was itself lower. So conceivably a large fraction of the victims of Covid-19 would be already dead of other causes. Finally, with the lack of screening and data collation possibly many such deaths would have been attributed to “unknown causes” or “old age” etc.
So perhaps humanity has indeed seen such viruses but just not on a scale or perceptiveness that we see today.
Comment #165 March 20th, 2020 at 2:45 am
Polylog #44, hey yeah, I saw the episode where Scott had a beard in the mirror universe! He was a despotic planetary ruler who ran around cracking a whip and shouting “quantum computers try all the possible answers in parallel!” He was much more interesting than Spock, who had a beard in the same episode but was just doing some dumb thing on a star ship.
Comment #166 March 20th, 2020 at 4:10 am
Scott #159 and Richard #64 re why viruses don’t wait around to spread before causing symptoms:
I’m not an expert but my “interested bystander” understanding (similar to my understanding of quantum complexity) is that this is indeed a hard problem for viruses, and there are several solutions. A virus doesn’t have a metabolism, and it is kind of a very simple “one-shot” entity that does its thing when it enters a cell, so multiple stage infections are hard for them, because they require more complexity and thus a larger genome, which is disadvantageous because a small genome can be reproduced faster and stored in capsids (virion shells) that are smaller and thus more robust environmentally.
The normal way viruses work, which is basically “smash and grab”, is the lytic cycle, which is invade, reproduce zillions of progeny, explode the host cell, repeat.
To lie low is more tricky. The most common solution is to finesse it by simply causing mild symptoms that aren’t severe enough to prevent transmission; that is the normal evolution towards a less virulent virus.
But the other main “engineering” solution to delaying the effects of the virus is to integrate the genome of the virus into the DNA of the host cell, and then going dark, waiting for the cell to reproduce some potentially indefinite number of times, before suddenly waking up (often based on environmental cues) and entering the lytic cycle. There are two forms of this, depending on whether the virus is DNA or RNA based; a DNA virus can directly splice itself into the host genome, but an RNA virus has to use reverse transcriptase to first convert it’s RNA to DNA.
For DNA viruses, that is normally called the lysogenic cycle. Herpes viruses are this type of virus, and that’s why they are chronic, lie low for long periods of time, and are practically impossible to cure (think both oral/genital Herpes and Shingles). For RNA viruses that do that, they are called retroviruses (of which HIV is one); I’m not sure if RNA viruses are classified as lysogens or not.
About 8% of the human genome consists of ancient copies of retroviruses that have become disabled by evolution so that they can’t enter the lytic cycle or move anymore (they can also move around in the genome), but the acquired genes have become indispensable, since the syncytium, which forms the blood barrier around the placenta in placental mammals, requires that genetic machinery.
Comment #167 March 20th, 2020 at 6:20 am
If you have 10B$ to spend in one single research project which one would you choose and why?
Comment #168 March 20th, 2020 at 8:00 am
Scott #156
But wouldn’t it make a big difference in how the machine was treated under the law?
We could easily treat non-conscious machines as slaves or send them to the trash heap if we tired of them. We wouldn’t hold them accountable for crimes but would treat them as defective products and the responsibilities of their manufacturers.
I would argue that for us to assume the machine was conscious, we would have to design into the machine something we understood that would make it conscious. Mere behavior suggesting consciousness wouldn’t be sufficient. That would require our understanding consciousness more than we understand it at this time.
Comment #169 March 20th, 2020 at 8:03 am
Scott #159
I think most viruses do eventually mutate into less virulent forms and thereby maximize their long-term reproductive success.
Comment #170 March 20th, 2020 at 8:54 am
Addendum to comment 166: My pedantic instincts compel me to add that there are other ways to integrate a virus genome into the host DNA than just those two ways; virus diversity is vast and mind-boggling, so there are bizarre oddballs like the hepadnaviridae, which have a partially single-stranded, partially double-stranded DNA genome, which for some bizarre reason first converts its genome to RNA, then uses reverse transcriptase to turn that back into DNA, and then finally integrating that into the host DNA.
Comment #171 March 20th, 2020 at 10:31 am
Scott #154:
> I found that I was fudging my progress rather than authorizing
> donations to the George W. Bush Presidential Library
Eek, yeah, that’s one reason Beeminder doesn’t do anti-charities! https://blog.beeminder.com/anticharity (nor good charities, mostly, though we do have that option in one of the fancy premium plans).
Anyway, I’m excited you want to try Beeminder! In fact, I intend to do my best to solve Beeminder’s bootstrapping / catch-22 problem by personally holding you to what you’ve said here! 🙂
Comment #172 March 20th, 2020 at 10:38 am
Brooks #78:
Is human consciousness a quantum phenomenon?
I would say: clearly not, or rather, not in the sense that tunneling and Bell inequality violation and the quantum Zeno effect and so forth are “quantum phenomena.”
By which I mean: even if quantum mechanics turned out to be implicated somehow in a good explanation for consciousness, which is a possibility that I don’t rule out … even so, quantum mechanics is a specific framework that makes specific (extremely successful) predictions for how physical systems behave, and nothing in our present understanding of that subject gives you even a toehold on the hard problem of consciousness, or even on explaining the information processing activity of the brain, and the specific attempts to claim otherwise that I’ve seen have typically been forehead-banging bullshit.
Comment #173 March 20th, 2020 at 11:40 am
Sniffnoy #79: Yes, absolutely, one can separate out the completeness and soundness sides of MIP*, producing a whole zoo of possible complexity classes. I believe that what happens when one does that was explicitly discussed as one of the open problems in the MIP*=RE paper. Since Henry Yuen is here on this thread, maybe I’ll defer to him if he wanted to add anything!
Comment #174 March 20th, 2020 at 12:12 pm
The chosen one #80:
Why do you feel the need to bring up Amanda Marcotte’s name every now and then in a sort of self-righteous martyr kind of way? It’s unbecoming of you. Most people acknowledge that what happened to you after 171 was ridiculous, and don’t take the vapid writings of radicals like her seriously. Are you still not over it?
When the occasion warrants (e.g., when someone like you brings it up 🙂 ), I imagine that I’ll continue to mention not just her but also Arthur Chu, the “Dr. Nerdlove” guy, and all the others who put ideology over humanity during one of the defining events of my life.
Like, I’m gratified you feel that their attacks on me were “ridiculous,” and I’m gratified that countless others (including the overwhelming majority of people who I respected for other reasons) agreed with you! But do you realize that the attacks on me, by Marcotte and others, may have attracted more eyeballs and social media shares than everything else I’ve done in my entire career? Not only my research but all my popular articles and courses, on the order of a thousand posts on this blog, the interviews with John Horgan and Lex Fridman and Hacker News etc., the big numbers essay, the P vs. NP survey, “Why Philosophers Should Care About Computational Complexity,” “The Ghost in the Quantum Turing Machine,” all of it? Do you have any idea how that feels?
Even more fundamentally, though, the reason why I sometimes bring up Marcotte and the others is that, in an unironic and unintended way, they did me a great favor, by dramatically illustrating what I had tried to explain about why I spent so much of my life in suicidal depression and fear. It was because of them—or rather, because of every other bully with the same mindset, every nerd who opportunistically sided with the bullies, everyone who cynically co-opted the language of social justice to secure their own place in some high-school cafeteria pecking order. Given what happened to me, after I once cautiously opened up about my experiences deep in this comment section, no one can ever pretend that I only feared some bogeyman inside my head.
Comment #175 March 20th, 2020 at 2:06 pm
Hi Scott, first of all, I have to say I loved your book and read it many times, also for delivering QC lectures. I’m a physicist and I’m trying to look into some QC applications in my field.
So, all in all: congratulations for a great piece of work: QC since Democritus is a great book.
Now the question: do you think quantum annealing will have some real impact in practical applications? d-wave is the only one looking into this or are there other companies working on this? Or you think it is hopeless given the “exponentially small gap” argument? I’m also recluded with my family and can understand your feelings, I guess. Good luck! LK.
Comment #176 March 20th, 2020 at 3:07 pm
The consensus in biology is that parasites evolves towards low virulence, but that is the opposite of the consensus among people who actually study the evolution of virulence. In particular, I believe the consensus is that both theory predicts and measurement proves that parasites evolve greater virulence after changing hosts. This is a common problem: modern science doesn’t actually work to propagate ideas of specialists. I would say that 90% of biologists don’t even understand evolution.
For the evolution of virulence, I recommend Paul Ewald. Here is a survey summing up his career. In fact, he is most famous for explaining the distribution of virulence and he provides arguments for why respiratory infections are generally not virulent. So that provides hope.
Claiming that parasites should evolve towards low virulence is a group selection argument because individuals within one host are competing with each other. It’s more plausible than most group selection arguments because transmission between hosts is important and is a sharp break, so an infection is sort of like an organism. But it is mainly wishful thinking.
Comment #177 March 20th, 2020 at 3:37 pm
Suppose one day QC is fully implemented, and every company in the world has a supply of quantum computers and people to program them. There might then be demand for a mainstream “quantum programming language,” which in addition to for loops and if statements and whatever, has some additional constructs that let people take advantage of the full power of QC without necessarily understanding much about how the underlying quantum mechanics work.
Can you speculate on whether this is a reasonable hypothetical, and if so, what these constructs might be?
(Thanks Scott!)
Comment #178 March 20th, 2020 at 3:45 pm
Maybe we should treat every flu epidemic as a massacre. It appears to me that the Japanese government response to this coronavirus is even more lackadaisical than the American. Yet it has slower growth (though still exponential), apparently due to Japanese society’s habits for dealing with flu season, such as masks and medical attention for fevers.
Comment #179 March 20th, 2020 at 3:56 pm
Antony #167, LK2 #175, and Greg Bodwin #177: Sorry, I had said no more questions—so if I answered yours, it wouldn’t be fair to everyone else. But I decided to leave your questions up anyway, in case someone else would like to field them!
Comment #180 March 20th, 2020 at 4:38 pm
Rahul #81:
As a policymaker what sort of algorithm (or even broad framework) should you use to apportion resources (money) to research into different problems, given the variation in probability, impact etc. ?
To clarify: Say, you are a top science funding czar (for US, or even for a global body like the Melinda Gates Foundation) how do you distribute your research money allocation into say {Pandemics, Global Warming, Quantum Computing, Asteroid Apocalypse defense, Malaria, Alzheimers etc. } Does this have to be just arbitrary, subjective etc. or can we come up with some (even vaguely) quantitative guidelines based on perceived risk, impact, horizon remoteness etc.
Yeah, that’s a hard one. Spend a lot on mitigating threats to human civilization, and then plow whatever is left into quantum computing and computational complexity? 🙂
More seriously, if you’ve seen how the sausages get made, even to the tiny extent that I have, the idea that there’s some rational algorithm for allocating funds is laughable. Mostly, there’s
(1) bottom-up pressure—e.g., scientists who get excited about some particular new direction and advocate for it, combined with what the NSF calls “proposal pressure” (allocating funds to a given area based on how many grant proposals that area got the previous year),
(2) top-down pressure—e.g., some Congressman gets a particular type of cancer, so pushes the NIH to put more money into curing that cancer. Or they read someplace that China is beating the US in the race for quantum computers, which explore all answers at the same time and have major national security implications. 🙂
(3) some individual program manager at a granting agency has an idea for something support and successfully advocates for it (especially common, I think, at DARPA and the other military agencies).
But you were presumably asking how it should be done, in a rational world? If so, let me set aside the difficult political questions of balancing immediate societal needs against blue-sky research, etc.—it will certainly be hard to find an algorithm for that!—and just talk about allocating funds within basic science, or even just a specific area of basic science.
I think it matters a lot on whether we’re talking about
(a) experiments at any significant scale, or
(b) theory (or tiny experiments and explorations doable by a single investigator).
For (a)—and not only for LHC, LIGO, the Hubble Space Telescope, etc., but even for much smaller projects—you obviously do need planning commissions with input from the relevant research communities to figure out how best to allocate resources.
For (b), by contrast, I’m of the radical opinion that our current system of grant proposals is a gigantic waste of time. Rather than maintaining the huge fiction of “research projects,” with goals, timelines, deliverables, milestones, etc. etc.—and forcing theorists to write “proposals” either for work that they’ve already done, or work that they have no idea how to do—what you want to be doing instead is placing bets on people. In other words, the granting agency would simply identify the individuals with the most outstanding track records, and agree to support them (along with a certain number of students and postdocs of their choosing) for life, or perhaps with 10-year renewals. Or the granting agency could simply give lump sums to the top departments to distribute to their researchers and faculty.
The system of betting on people is how it worked in the age of Galileo and Newton. It has a superb track record. It would free up a huge amount of time for actual research. For the type of science that’s driven by individuals, it seems just clearly superior to the system that we have now.
Comment #181 March 20th, 2020 at 4:55 pm
Adam Brown #82:
A few weeks ago, there was press about some people who generated all 68 billion possible 12 note sequences out of the 8 notes above Middle C, turned it into a MIDI file and uploaded it to SoundCloud. Their stated motivation was to place all the melodies “in the public domain” so that no one could ever sue anyone else for copyright infringement on a melody (which is apparently a thing), so long as that melody was made after 2020 .
So my question to you, Scott, as a music lover, computer scientist, philosopher, and jurist, is this: once you are elevated to the Supreme Court, and this case reaches you, will this fly?
LOL! This strikes me as a fully general reductio ad absurdum of copyright law. That is, if we let it fly, then why not grant someone else a copyright on each and every element of the set {0,1}* that isn’t already copyrighted? Such a person could then sue anyone who publishes anything for infringement—or choose to place all new books, music, films, and everything else into the public domain.
It’s like, who cares if the filer can’t perform the stunt of explicitly listing every element of {0,1}*? Why shouldn’t the copyright office let people submit regular expressions?
One way out of this would be to put a limit of (say) 10,000 on how many copyrights any one person can have. Or better yet, the copyright office could say to the people who did the SoundCloud thing: sure, absolutely, you can have copyrights on all 68 billion possible 12-note melodies. That will just be a $50 filing fee for each one, thank you! 🙂
If I were a Supreme Court justice … well, like, I’d probably be disbarred within a few hours, for blurting out “who cares what the existing rules say? let’s just figure out whether this country should have a copyright regime in the first place, and if so how it should work!” (Can Supreme Court justices be disbarred?)
Anyway, I’ll be extremely interested to see how the real legal system deals with this—not having the mind of a lawyer, I find it almost impossible to predict.
Comment #182 March 20th, 2020 at 5:10 pm
Zach #83:
I only recently started reading this blog so maybe I have missed this but I really like your banner with the advice on taking one piece of information from this blog. What would be the second piece of information to take from this blog?
As you might have seen, just yesterday I changed my one piece of information to “BUILD MORE VENTILATORS.”
So I guess my second piece of information would be “Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.” 😀
Comment #183 March 20th, 2020 at 5:15 pm
mark #84:
What is your probability to obtain a Nobel Prize?
Given that there is no Nobel Prize for CS (or for math), I suppose the prize would need to be in…
Physics, for the foundations of quantum supremacy experiments?
Economics, for my complexity-theoretic Aumann agreement theorem?
Literature, for various posts on this blog?
Peace, for my moral courage in standing up for the humanity of STEM nerds?
In none of these cases do I consider the probability especially high. 😀
Comment #184 March 20th, 2020 at 5:18 pm
Tony #85:
If you were to start your research journey from the beginning today, which area would you choose?
I feel like I’d be drawn to theoretical computer science for the same reasons why I was 20-25 years ago, but honestly I don’t know.
Comment #185 March 20th, 2020 at 5:21 pm
Jesper #86:
Can I swap places with your daughter and get personalized math lessons from the author of Quantum Computing Since Democritus?
Also, Deepa #135:
You might want to record the discussions with your 7 yo, although that might take away their authenticity. If you can record the material you discuss, it would be a book eventually.
Good news! I did decide to record my discussions with her, with the eventual goal of turning them into something that anyone could benefit from.
Comment #186 March 20th, 2020 at 5:55 pm
Scott #181
> let’s just figure out whether this country should have a copyright regime in the first place, and if so how it should work!
From a TCS and morality perspective, having some copyright law makes sense. Inventing art or doing engineering/science work is a computationally expensive process and someone benefiting by cloning/reusing the output without paying the computational cost is not fair.
Unfortunately, it’s hard to prove how much computation you did and how original you are, as well as how original everyone’s thought processes are anyway 🙂 In my opinion, being practical and focusing on intentions is more important than some obscure & verbose rules.
Comment #187 March 20th, 2020 at 5:59 pm
Hi Scott, it appears you have skipped my question (#69). Just wanted to know whether this was accidental or my question was bad.
Comment #188 March 20th, 2020 at 6:06 pm
Hi Sniffnoy #79. There is indeed a whole zoo of different MIP classes, depending on what kind of correlations you allow the provers to use.
Prover correlations: classical, non-signaling
Complexity: MIP = NEXP
———
Prover correlations: quantum, finite-dimensional (but no upper bound on dimension)
Complexity: MIP* = RE
——–
Prover correlations: quantum, T qubits of entanglement (where T may be function of input size)
Complexity: NTIME[2^T]
——–
Prover correlations: quantum, commuting operator correlations (denoted by the class MIP^co).
Complexity: Not currently known. It is contained in coRE, and we conjecture that it is *equal* to coRE.
———
Prover correlations: non-signaling, 2 players
Complexity: MIP^ns[2 players] = PSPACE
——-
Prover correlations: non-signalling, poly(n) players
Complexity: MIP^ns[k players] = EXP
——
For an “intermediate” number of players (say log n), I think the complexity of MIP^ns[k players] is not known, somewhere between PSPACE and EXP.
——
There are more wild classes that one can consider: one can consider provers that *almost* obey quantum mechanics; for example their measurements *almost* commute with each other. It turns out that this class has a decidable upper bound (see Coudron-Vidick, https://arxiv.org/pdf/1510.00102.pdf).
As Scott mentioned one can consider cases of each where there is no gap between soundness and completeness, in which the corresponding MIP class can become more difficult than RE! (this is a follow-up note I have with my students Hamoon Mousavi and Sajjad Nezhadi: https://arxiv.org/abs/2002.10490).
Comment #189 March 20th, 2020 at 6:47 pm
dualmindblade #87:
Something that has bothered me for a long time…
Say we have a machine A which takes an input string, s_0, and produces an infinite sequence of output strings, s_1, s_2, … Things like this, cellular automata for example, are often considered universal computers because they can “simulate” a turing machine. This seems to mean we can provide an encoding function to map the input of a particular turing machine to s_0, and a decoding function which turns some of the sequence s_0, s_1, … into the intermediate or halting states of that machine. But turing this into a formal definition seems problematic. At one extreme, I don’t want a machine that simply stores a computer program and iterates a counter to be considered universal. If I somehow had a program that simulated my brain and I uploaded it into such a machine, I wouldn’t expect to experience anything. Yet I can provide E, D that turns the outputs of this into the states of a computer which actually computes the program. At the other extreme, I don’t want to insist that E, D be completely straightforward, I can think of cases of A where they are required to be a bit convoluted and in which I’d still expect to have a conscious experience if I were to upload myself into A. Can you answer the question, what is the maximal set of triples A, E, D that are universal in the sense I am trying to get at with the mind simulation thought experiment? If not, can you explain why this is a silly or malformed question caused by some simple misunderstanding so I can stop thinking about it?
I’ll tell you what: to make your question a little more tractable, can we leave the hard problem of consciousness out of it, and just talk about universality? 😀
If so, then there’s certainly no misunderstanding. The exact definition of computational universality for dynamical systems like cellular automata is a subtle question, and one that aficianados have argued about for decades. I recall that it was even an issue with the $25,000 prize that Stephen Wolfram awarded, for a proof of the universality of a 2-state 3-symbol Turing machine. The proof required some very convoluted encodings of the input and output.
In deciding whether or not to accept a given universality argument, the question that I ask myself is whether the model being shown to be universal, if I bought it at a store and used it as my own personal computer, would actually improve my life in any way—or whether merely to encode the inputs to that computer and decode its outputs, I’d have to do just as much work as the computer was supposed to save for me anyway.
Translated to more technical terms, this is saying that the encoding and decoding algorithms, used in the universality reduction, should be implementable within a “small” complexity class: in this case, something much, much smaller than the set of all computable functions. And universality proofs can be judged as better, the smaller that complexity class is.
For more on this theme, see Section 6.1 of my Why Philosophers Should Care About Computational Complexity essay.
Comment #190 March 20th, 2020 at 7:50 pm
James Cross #167
Human attribution of consciousness? Yes, it matters a great deal. “Actual” consciousness, on the other hand, wouldn’t affect this at all.
That doesn’t work, because we have a moral imperative to assume consciousness whenever it is in doubt.
Comment #191 March 20th, 2020 at 8:37 pm
Scott #189:
Scott, thanks for answering my question, and I’m relieved to now know that I haven’t been wasting a bunch of my brain time on an obvious misunderstanding of the definition of universality, that’s 90% of what I wanted to get out of asking you this. So, I won’t be disappointed if you don’t re-respond, and don’t expect you to do so, maybe someone else in the comments could chime in, but the whole reason of bringing consciousness into the equation was to avoid the answer you just gave, it’s an attempt to cut past the subtlety you’re referring to, and the only way I can think of to do so. I happen to believe that if I could simulate my brain with the fidelity required to also simulate normal seeming human behavior on a standard computer, that that brain would be conscious in the same sense that I am. Of course, this is disputed, but I’m fairly sure you also hold the same opinion when you’re in the mood to have an opinion at all. I additionally believe that if this uploaded brain were to generate responses more and more slowly over time, perhaps exponentially so, that it would still have the same level of experience. Now, I’m not so sure you feel the same way actually, I think you might not, but if you take this as a given, then I think the consciousness thought experiment becomes useful, as it side-steps your idea of asking whether we’d find such a computer useful. No, we would not if it were exponentially slow or even worse, from the outside, but were we to upload ourselves into one, we might find it useful indeed, we wouldn’t care how slow it is as long as it keeps computing us forever. Given this allowance, the issue of deciding whether the complexity of the decoder is “small” becomes more difficult, it seems to me that time complexity is no longer sufficient. Give me any time-based complexity class, and I can devise a machine which meets the requirements of computing my brain properly, but foils the decoder by, say, padding it’s output with the required amount of extraneous garbage. So, what I’m trying to get at is, under all of my admittedly controversial assumptions, can we find a nice way to decide where the bulk of the computation lies, in the machine or the decoder, or is it hopeless to try and separate them? The point of bringing consciousness into the equation is for clarity. Would my uploaded brain have an experience before the decoding function is applied, or only after? Or is it some bizarre in-between?
Comment #192 March 20th, 2020 at 9:57 pm
Douglas Knight #176
I’m not seeing any conflict here. Of course, if a parasite is changing hosts, its selection pressures will be different from the ones affecting a parasite that isn’t changing hosts. If you meant a new host organism, the survival of the old host is no longer valuable to the parasite, and may even be counterproductive since the old host is a competitor to the new one.
If you meant a new host species, the selection pressures would presumably depend on which species it is infecting at the moment.
Comment #193 March 20th, 2020 at 9:58 pm
Henry Yuen #188:
I think you missed the point of my question.
In the previous thread, there was a lot of discussion of this in terms of the set of correlations. Specific sets of correlations were considered: Classical (or none which is the same?), quantum (finite dimensional), quantum (arbitrary commuting), arbitrary non-signalling. (Also arbitrary? That’s different from non-signalling, I gather?) These particular sets of correlations form a chain under inclusion.
But, the complexity classes you seem to get do not form a monotonic sequence; as has been much discussed, you’d expect it to be monotonic decreasing, but it doesn’t. Instead you get NEXP, RE, (conjectured) coRE, PSPACE, PSPACE.
But if we take what Mateus was saying, this suggests that the reason it’s not monotonic is because really we should be making a table, with one dimension being the correlations they’re allowed to use, and the other dimension being some sort of constraint on them (I’m not very clear on this part); and this table would be monotonic decreasing in one direction, and monotonic increasing in the other. And then the reason that our original sequence mysterious fails to be monotonic is just because it’s something like the diagonal in this table rather than a row or a column.
Does that idea make sense? Can we construct this table?
Comment #194 March 20th, 2020 at 10:05 pm
dualmindblade #191:
Universality is generally defined in terms of reductions (preserving the i/o behavior of the reduced program), not simulations (preserving the internal structure). So the universal program presumably wouldn’t preserve consciousness anyway.
Comment #195 March 20th, 2020 at 10:35 pm
Edan Maor #88:
What do you think the COVID situation says about x-risk worries in general, and AI specifically?
I’m especially thinking along the lines of Yudkowsky’s argument in “No fire alarm”, which you’ve probably read, but a high level summary is: “there’s not going to be a fire alarm to tell us we *now* need to start worrying about AI”.
I’m sure I could invent a clever reason why it shouldn’t change my views about anything, but if I’m being honest? It does cause me to update in the direction of AI-risk being a serious concern. For the Bay Area rationalists have now publicly sounded the alarm about a looming crisis for the human race, well before it was socially acceptable to take that crisis too seriously (and when taking it seriously would have made a big difference), and then been 100% vindicated by events. Where previously they were 0 for 0 in predictions of that kind, they’re now 1 for 1.
Comment #196 March 20th, 2020 at 10:43 pm
Lo$pietato #89:
Scott why the most of the world main leaders (presidents,PMs etc) say that we (population) are in a war?
Because we are, even if not everyone realizes it yet. Of course, it’s a war not against an enemy tribe, but against a different, even more lethal kind of foe that humans have also faced throughout their history: namely, a self-replicating snippet of code.
Comment #197 March 20th, 2020 at 10:45 pm
@Sniffnoy #193. I see where you’re coming from. I would explain it like this, however: the choice of correlations that the provers can use is both a power *and* a constraint for them — there is no need to introduce a separate axis.
I think what you’re trying to get at, though, is the following: the complexity of a multiprover interactive proof system is determined by two competing forces: one is the power that the provers have to try to “cheat” the verifier (so in this case, access to a bigger set of correlations gives the provers more power to “cheat”), versus the power that the verifier has over the provers (so in this case, access to a bigger set of correlations *potentially* gives the verifier the ability to ask the provers to exhibit fancier correlations).
If the “cheating” power is stronger, than the complexity lessens; if the verifier can demand the provers to do stronger things, than the complexity increases. How those two forces play out depends very sensitively on the specific correlation sets you consider — not just whether it’s bigger or smaller than some other correlation set.
I would say that the reason that there is a non-intuitive and very interesting pattern of complexity classes (NEXP, RE, PSPACE, etc…) corresponding to MIP, MIP*, MIP^ns[2], etc, is because of the *specific mathematical structure* of the different correlation sets: the first is convex combinations of deterministic functions, the second has to do with linear operators on Hilbert spaces, the third can be expressed as a linear program.
Hopefully this comes closer to answering your question.
Comment #198 March 21st, 2020 at 1:02 am
Scott #162
>Nothing that’s non-physical exists physically. It might, however, exist non-physically.
We’ starting to shut down here in NZ too. I’m using the time of endless solitude at home to develop my ultimate theory of metaphysics 😀
*Summary of my latest metaphysical speculations about realms of existence
Punch-line: ‘Reality Is a Globe of Conceptual Knowledge defined by Complexity Classes’
*Existence is a matter of degree quantified by a complexity measure
I’m thinking that ‘existence’ is a matter of *degree*, which can be qualified in terms of some sort of complexity measure. That is to say, I’m thinking that concepts that are very simple only exist objectively to a *low degree*, and moving in the direction of increasing complexity is the direction of ‘increasing solidity’, in the sense that such concepts have a higher *degree* of existence
*There are two poles of existence – mathematical and physical
If we think of all knowledge (everything that is knowable), as an abstract *conceptual space* (a landscape), then I postulate that mathematics and physics are at opposite poles in that landscape. That is to say, I do think both mathematical (abstract) and physical ( concrete) objects objectively exist (platonism & physical realism), and they are in some metaphysical sense, opposites
*Epistemology works differently for mathematics and physics
Physics is reductionist. The direction of increasing generality of explanation is the direction of *decreasing* abstraction – you increase your understanding by breaking everything into smaller and smaller locally interacting parts, *zooming in* on the conceptual landscape. Bayesianism works well here – understanding is built from the ‘bottom-up’ – updating based on observations.
But mathematics doesn’t work like this at all ! The direction of increasing generality is the direction of *increasing* abstraction – you increase your understanding by unifying disparate concepts, *zooming out* of the conceptual landscape- understanding actually works ‘top-down’ – mathematics is at the ‘opposite pole’ in the conceptual landscape. Bayesianism won’t work for mathematical reasoning- I think you need some kind of many-valued logic – my guess is fuzzy modal logic.
*Cognition is the mapping language between mathematics and physics and works via reflective equilibrium
I think cognition (mental existence) is the mid-point between the two poles of existence (mathematics & physics) on the conceptual landscape. That is to say, it is the center point of mid-level abstraction. And cognition is the mapping language that translates between the different levels of abstraction. Cognition establishes a language that tells you how to translate high-level (abstract) concepts into low-level (concrete) ones
Therefore, for cognitive science, I think epistemology works differently from both math and physics The way I think it works is neither top-down, nor bottom-up Instead, I think it works by *reflective equilibrium*, whereby high- and low- level models are integrated to find the *mid-level* of abstraction
Both Baysesian Inference and Logic break down for cognitive science I think – they are unified by *computational complexity theory*
*Epistemology is Computational Complexity Theory !
Complexity classes define ‘existence’
At the last the punch-line to metaphysics is laid bare! Something exists *exactly to the degree that it could in principle be cognitively understood*, via it’s classification as a complexity class ! The highest degree of existence is at the exact center of all levels of abstractions, the point of maximal complexity in the conceptual landscape. And that’s cognition. As you move out from the center of the conceptual landscape towards the poles, the objective existence of concepts is becoming weaker and weaker (the ‘degree of existence’ gets lower and lower). At the poles themselves (pure math at one end, pure physics at the other), existence winks out – these are the points of minimal complexity in the conceptual landscape.
Both Bayesian inference and Logic are unified by computational complexity theory. They work perfectly at their respective poles of existence (Bayes = Pure Physics, Modal Logic = Pure Math), but begin to break down as you move towards the mid-level points of abstraction At the exact center of the conceptual landscape (the core of mental existence), both Bayesian Inference and Logic have been unified as complexity classes !
Comment #199 March 21st, 2020 at 1:49 am
Henry Yuen #197: I see! So the definition of these classes really is just a generic thing that you could plug any set of correlations into (there’s no second implicit axis that we’re also varying when we switch from classical to quantum or from quantum to non-signalling, it really is just the set of correlations that’s changing), and it really is just non-monotonic then. Huh. A little disappointing, I must admit…
Comment #200 March 21st, 2020 at 5:12 am
Joan#90:
“Why is chemistry not considered cool by so many cool people?”
Here’s my take: To a lot of geeks (the sort that gravitate to Physics, Maths or even CS) patterns and rules are the big attraction. It’s all like a puzzle waiting to be solved. But the rules need to be clear. It’s like a game of chess they love.
Chemistry, unfortunately, has a bit of fuzziness to it (reflecting our lack of understanding of the rules as well as we do in say Physics). The rules exist but with too many exceptions and special cases (which is why some of us love it!)
In my opinion that’s the reason for the perception of a lack of “coolness”.
PS. In India we have a very competitive post-school test for admission to the technical universities and although Math, Physics and Chemistry are the three subjects on the test, I consistently hear from the test toppers that they didn’t like Chemistry as much as Math or Physics.
Comment #201 March 21st, 2020 at 7:15 am
Joan #90:
Quantum chemistry is a hard, relevant, and obviously, quantum, problem. Why do you think some great physicists are obsessed with subatomic particles and even exotic toy quantum field theories when this important quantum problem is just before our eyes? Why is chemistry not considered cool by so many cool people?
There’s a certain romance that draws people to the study of the most fundamental laws and constituents of physical reality. And there are deep mysteries there: what caused the Big Bang, what happens at a black hole singularity, what’s the dark energy, how are QM and GR reconciled?
At the other end of the reductionist hierarchy, there’s also a romance that draws people to the study of complexity and networks and brains and societies. And there are deep mysteries there as well: how does consciousness arise? Does P=NP? Why do people so often choose evil and stupidity, and can we get them to choose otherwise?
But chemistry? Many people might have the impression—perhaps mistaken—that this is a middle layer in the reductionist hierarchy that “in principle” has been completely understood since the 1930s, by which we mean that there are no fundamental upheavals left in the subject, but “only” the (no doubt important) working out of the details of innumerable special cases.
To repeat, I’m not saying that the above is true, only that it’s a perception that might exist. 🙂
So then, what would I do if I were a PR man for chemistry, with a mandate to get more of the most intellectually curious people into the field? Well, of course I’d talk up the fundamental conceptual mysteries that remain in chemistry, if I knew of any. But if I didn’t…
Then I think the first thing I’d do would be to talk about psychedelic drugs. I might hand out copies of Alexander Shulgin’s remarkable book “PiHKaL”, which Scott Alexander reviewed and which I recently started reading. Shulgin, a chemist, did something incredible in the 60s and 70s that probably could never have been done before or since: namely, to synthesize hundreds of new psychedelic compounds, apparently more-or-less legally, try each of them out on himself and his willing friends, and then write down everything that happened. Remarkably, Shulgin is often able to trace the chain of causality (very convincingly) all the way from the physical properties of a given molecule (e.g., that it has or lacks a particular carbon bond), to its binding or not binding to some class of receptors, to the subjective experience that he and his friends had, and the thoughts about the universe that they were thereby led to.
Anyway, if that didn’t work, the other thing I’d do would be to talk up how both the coronavirus crisis, and the even larger climate crisis, underscore that practical knowledge of the everyday physical world and how to manipulate it remains of the utmost importance to the survival of civilization! If you want to build a drug that attacks the coronavirus, that’s chemistry, and if you want to invent an energy-efficient way to capture and sequester atmospheric carbon, that’s also chemistry. Depending on my mood, I might also talk up how quantum computers and simulators might eventually lead to revolutionary capabilities for such problems … and how any young person who was ready to exploit those capabilities to tackle the biggest societal challenges, might live to be hailed as the next Jonas Salk or Norman Borlaug.
Good luck! 🙂
Comment #202 March 21st, 2020 at 7:35 am
Anon #91:
Taking cue from covid, any other disasters that you think we are grossly under prepared for and should put more resources into?
And I mean near term Catastrophes eg say a immediate to 10 year horizon. Not things like global warming etc.
Since 10 years is already a pretty long time horizon for prognosticating catastrophes, let me give you a more immediate one!
One of the things that terrifies me the most right now is the possibility that Trump, whose shamelessness knows no bounds, will quickly pivot from denying and minimizing the corona crisis to exploiting it, to make himself more like an actual dictator rather than merely an aspirational one. (Trump’s friend, Bibi, is already clearly attempting that in Israel. Putin achieved the transition in Russia even well before the crisis.)
Trump’s “making himself an actual dictator” could mean a range of things, from asserting the emergency power to jail any journalist who criticizes him, to his commandeering or shutting down Amazon or any other entity whose competence during the crisis threatens him, to his calling off or postponing or blatantly falsifying the November election. If he did these things, I think there’s an excellent chance that the Republicans in the Senate (excepting Mitt Romney), along with a 5-4 majority on the Supreme Court, would go along with all of it.
Comment #203 March 21st, 2020 at 8:34 am
Scott #150
Obviously I was talking from an experiential point of view.
(but I can’t say I’m surprised by your type of answer).
Comment #204 March 21st, 2020 at 8:45 am
Antoine Deleforge #92:
Now this question has been itching me ever since: Would you say that you, personally, have ever experienced true free will? And if so in what situation(s)?
I would say that I exerted the “maximum amount of free will” (at least, the maximum that I’ve experienced) in those rare cases when I did something not because the people around me wanted or expected me to do it, or because it was the natural thing to do for someone in my situation, but simply because I wanted to and damn what people around me thought.
Here are some examples:
– In 1994, when I pushed my parents and the administrators at Hong Kong International School to let me start skipping grades.
– In 1996, when I left home at age 15, to attend a program at Clarkson University that I’d literally learned about from a mass-mailed brochure.
– In 2000, when I set up a website called “In Defense of NaderTrading” to try to prevent the election of George W. Bush. (Had I exerted my free will some more, and gotten more attention for the site, maybe we would’ve gotten just 539 more vote-swaps in Florida…)
– In 2001, when I dropped everything else I was doing to work on a ridiculously ambitious problem, one that even Andris Ambainis hadn’t solved: namely, lower-bounding the quantum query complexity of distinguishing 1-to-1 from 2-to-1 functions
– In 2002, when I decided to waste a month building a huge zoo of complexity classes, and another month reading and reviewing Stephen Wolfram’s book (despite being a totally unknown grad student)
– In 2005, when I started a blog called (of all things) “Shtetl-Optimized”
– In 2006, when I asked my boss, Ray Laflamme at the Institute for Quantum Computing in Waterloo, if I could teach a crazy course called “Quantum Computing Since Democritus”
– In 2009, when I spent a whole weekend in a difficult, contentious, incredibly personal email exchange with some postdoc in Princeton who I barely knew, then accepted her invitation to take the train there to continue arguing in person. (Over the next 3 years, that postdoc would become my girlfriend, fiancee, wife, then mother of my first child.)
With these examples in mind, I can finally explain something that seems to have perplexed many people: namely, why I reacted to SneerClub and its fellow travelers, not merely as some annoying nobodies shitposting on social media, but as an existential threat, a coronavirus of the mind. And this despite the fact that, at least 3/4 of the time, I’m politically closer to the sneerers than to those they attack.
The reason is that, with laser precision, the sneerers target the urge to “exercise one’s free will.” Like, they spend hours perfecting and refining mental kryptonite against the impulses of nerds like me to say what they’re thinking or do what they want, and damn the disapproval or the quizzical looks of those around them. The sneerers’ worldview, even when one happens to agree with them, is poisonous to the little hothouse flower of nerdian freedom that led to almost everything that was good in my life.
Comment #205 March 21st, 2020 at 8:46 am
Scott #202
It’s pretty striking that you mention the US, Israel, and Russia when it comes to their position on the dictatorship scale,
but then, like most, you have that gigantic blind spot regarding China, which is pretty much now the de-facto top economy in the world.
Hey, there’s really nothing anyone can do about it!… The CCP say they’re benevolent, so let’s all play along and pretend they are!
Too bad for the Uyghurs, too bad for Tibet, too bad for their push on AI to control 1.5 billion Chinese who have no freedom whatsoever anyway.
Hopefully all that will stay within China, just like their viruses!
Comment #206 March 21st, 2020 at 8:51 am
#190
What is “actual” consciousness? What is “non-actual” consciousness for that matter?
Your moral imperative would need to include animals down to snails or slugs at least. Our society sees no such imperative for many types of animals – chicken, cows, pigs, sheep, etc – which certainly show signs of consciousness.
Still with animals we are talking about naturally evolved organisms with nervous systems that work in a similar fashion to the human nervous system. This is quite different from an artificial machine where there would be no reason to assume consciousness unless we designed it into the machine.
Comment #207 March 21st, 2020 at 9:13 am
Scott, maybe I should’ve done my due diligence on stack-overflow rather than bring it to your level, but why is the distinction between hard and easy problems posed as the difference between exponential vs polynomial time solvable, and not super-linear and linear time solvable?
Comment #208 March 21st, 2020 at 9:30 am
Harsha #206: I said no more questions. But see e.g. my P vs. NP survey, or (indeed) StackExchange.
Comment #209 March 21st, 2020 at 9:36 am
fred #205: Yes, of course the CCP is terrifying! Although if we’re interested in the deltas, they’ve already been terrifying for generations, and they’re notably less terrifying now than they were under Mao. This is a warning: don’t impute views to me that I never even hinted at holding.
Comment #210 March 21st, 2020 at 9:45 am
dualmindblade #191
> I happen to believe that if I could simulate my brain with the fidelity required to also simulate normal seeming human behavior on a standard computer, that that brain would be conscious in the same sense that I am
I’m not following all the details of your questions but it seems to me that the questions you are asking should lead you to reconsider this belief.
What if you “uploaded” yourself not to a machine but to a stack of paper in a room with a guy in it executing your algorithm by hand ? The notion that such a process would lead to the existence of a new and distinct conscious entity to me seems not only absurd, but maximally absurd (ie. at least as absurd as as any belief anyone has ever expressed).
This is the main reason why I do not believe either of the following claims:
1. That information processing is a sufficient condition for consciousness.
2. That a deterministic machine can ever be conscious.
Comment #211 March 21st, 2020 at 9:46 am
Varun R. #93:
Nowadays, an undergrad without some research progress (significant for an undergrad) seems to have a hard time getting accepted at a “tier-1” grad school. Seems like too much to expect from an undergrad.
Shouldn’t undergrad be for the deep study of a field (instead of research) (at least in fields like mathematics and theoretical CS)?
The issue is an arms race. PhD programs at MIT, Berkeley, and even here at UT Austin are quite competitive; they can accept only a small fraction of applicants. So from the admissions committee’s perspective, if you can fill the incoming class with students who already have at least some research experience, then why should you take a chance on students who don’t, absent compelling evidence (e.g. from rec letters) that the latter are truly exceptional? Or do you think PhD admissions should be based exclusively on something like GRE scores? (Grades vary too much from one institution to another to be especially useful.)
Comment #212 March 21st, 2020 at 10:02 am
Anon #94:
Do you believe in telepathy?
No.
Comment #213 March 21st, 2020 at 10:19 am
Maximilian #69:
Do you think the class of things (e.g. natural laws) which are mathematically possible is the same or smaller than the class of things which are logically possible?
(1+1=3 doesn’t seem to be a logical contradiction like “A and not A”; and “every natural number has a successor” doesn’t seem to be a logical truth like “A and not not A”. Yet 1+1=3 _feels_ very contradictory.)
Sorry for skipping your question!
If a purely arithmetical statement—for example, that a certain Turing machine halts—can be disproved from the axioms of ZF set theory, or from some other axiom system whose arithmetical soundness I believe in, then I’m totally fine to call that statement a “logical impossibility.” In the sense that I’d then regard the statement as false not merely in “our” universe, but in any conceivable universe.
Having said that, one can indeed usefully distinguish between statements can be disproved using trivial propositional reasoning—for example, “P=NP iff P≠NP”—and statements that can be disproved but only by delving much deeper—for example, “xn+yn=zn has a positive integer solution with n≥3.” This is not a sharp dichotomy, but a sliding scale, graded by
(1) the strength of the logical system and
(2) the granularity of knowledge about the statement in question
that one needs to use for the disproof.
(To illustrate what I mean by “granularity of knowledge”: to disprove the statement “P=NP iff P≠NP,” one doesn’t even need to know what P and NP are.)
Comment #214 March 21st, 2020 at 10:36 am
Scott #213
> Having said that, one can indeed usefully distinguish between statements can be disproved using trivial propositional reasoning—for example, “P=NP iff P≠NP”—and statements that can be disproved but only by delving much deeper—for example, “xn+yn=zn has a positive integer solution with n≥3.”
Doesn’t your first proposition here rely on the principle of the excluded middle ? Meaning it’s non-constructive (and hence not something you could trivially prove in Coq, for example). Don’t you think constructive proofs have higher epistemic status than non-constructive ones ?
Comment #215 March 21st, 2020 at 11:47 am
Gerard #210
That’s a famous thought experiment, and the idea that a pen/paper calculation could hold a consciousness doesn’t strike me as absurd at all, at least no moreso than the idea that a physical process could do the same, something which I do consider to be remarkable.
Comment #216 March 21st, 2020 at 12:21 pm
Bennett Standeven (192),
It is commonly claimed that parasites are out of equilibrium and we should generically expect them to evolve towards lower virulence. This is wrong. Parasites evolve quickly compared to their hosts and should generally be assumed to be in equilibrium. Smallpox has been highly virulent for at least a thousand years and has been infecting humans for at least 3k years. Vivax malaria has been infecting humans for 35k years and remains highly virulent. Falciparum malaria is even more virulent, but that’s not because it is younger, only 7k years of infecting humans, but because it has a different niche.
A narrower claim is that when a parasite switches hosts that it is not adapted to its new host. This is not about malaria bouncing between mosquitoes and humans. This is about a permanent switch, such as when malaria switched from gorillas to humans, or when this coronavirus switched from bats to humans. When it switches hosts it is out of equilibrium, because it is adapted to the old host and it will evolve to be adapted to the new host. This is correct. This is one time you should expect a parasite to be out of equilibrium. But it is widely claimed that it is highly virulent because it is not adapted. This is backwards. Generally its virulence in the new host gets higher over time as it adapts to the new niche.
Comment #217 March 21st, 2020 at 12:53 pm
Maximilian #69:
I don’t think you can draw a distinction between logic and mathematics. The way I see it mathematics is built from logic. 1+1 = 3 is very much a logical contradiction once you’ve defined the natural numbers and what addition means.
On the other hand I think that different areas of mathematics don’t all have the same degree of solidity, given that paradoxes like the Liar Paradox or Tarski’s Paradox are troubling.
To me the theory of finite sets probably has the highest epistemic status within mathematics and should definitely be paradox free. The next highest level would be allowing constructive inductive definitions of infinite sets, such as the natural numbers.
Comment #218 March 21st, 2020 at 1:07 pm
Scott #209
“Yes, of course the CCP is terrifying! Although if we’re interested in the deltas, they’ve already been terrifying for generations, and they’re notably less terrifying now than they were under Mao.”
Uhh…given the current power of China, the CCP is more terrifying than ever!
They make our struggle against the USSR look like a walk in the park.
The CCP has managed to use capitalism to their advantage, making most of the world dependent on China, now holding most nations by the balls on way or another, mostly through debt or supply chain black-mail (last year the CCP was threatening the US through their monopoly over rare earths, now it’s over basic medical goods).
Domestically the CCP has unlimited access to vast riches, they can directly control every single one of their corporations (e.g. Jack Ma losing all control over Alibaba, overnight).
We’re not talking about Mao era farms here, but cutting edge technology industries.
They’re aggressively pushing to secure monopolies where it matters, it started with the solar power industry 10 years ago (through dumping they totally killed the US solar power industry), and now electric cars, AI, robotics, military or consumer level (drone tech, 3d printing tech), you name it.
Since the 90s, they’ve used the blind pursuit of short term profit of western corporations to their advantage, by twisting the rules of the free market… Airbus, Google, Apple, Microsoft, Facebook (and, indirectly, many in the academia, who rely on those corporations to “cash out” at some point) are all ready to give up on the values of western democracies for a share of the Chinese pie, giving away to the CCP technological know-how on how to control 1/5 of the world.
The CCP has now fully realized the nightmare predictions of Orwell.
There is no longer any hope of dissent within China. Within the CCP, Xi took total control, proclaiming himself ruler for life and putting in place a new Mao style cult of the personality on the people. And he’s using social media to make the West be okay with it: the idea that things are now much better in China than in the old days… how the CCP lifted millions out of poverty (you’ve heard this anywhere lately?), when in fact it was the CCP that put all those Chinese in poverty in the first place.
The CCP has refined to an art their soft-power tactics, how to control the West through social media, influence of politicians (direct or indirect corruption, by for example putting them on the executive board of Chinese companies), acquisition of national assets, debt (Belt and Road initiative), …
Politically, the CCP always side against the US, on Venezuela, Syria, Iran, …
they use blackmail of western corporations to push their views on Taiwan, the South China Sea, HK.
They use NK as their attack dog, giving them access to nuclear military tech to destabilize Asia whenever it suits them.
Comment #219 March 21st, 2020 at 1:38 pm
dualmindblade #215
Well consciousness is certainly a profound mystery. As such I expect that its source must lie in something we don’t understand. An algorithm contains no place to hide any such mystery, we know every detail of it. The same cannot be said for physical matter. We still don’t have a fully self-consistent theory of physics.
Hence I think the materialist view that consciousness emerges from physical systems remains conceivable while the view that it emerges solely from the abstract processing of information to me is wholly inconceivable.
That said, I am not a a materialist and I think one of the following views is more likely:
1 – Some form of panpsychism with a form of base consciousness being a fundamental property of matter and where certain physical systems can amplify this base consciousness into what we recognize as our own conscousness.
2 – What is, or at least used to be, called spiritual monism. Consciousness and the mind exist a priori and what we perceive to be the physical world is simply a mental construct which arises from it but which has no independent existence of its own.
Of these I tend to lean toward (2).
Comment #220 March 21st, 2020 at 2:23 pm
Hi Scott,
I’m one of your students. I’m very much depressed by the COVID situation and the political situation triggered by COVID.
Can we help each other and get out of such depression
Comment #221 March 21st, 2020 at 2:32 pm
Gerard #214:
Doesn’t your first proposition here rely on the principle of the excluded middle ? Meaning it’s non-constructive (and hence not something you could trivially prove in Coq, for example). Don’t you think constructive proofs have higher epistemic status than non-constructive ones ?
If we just want to establish what’s true, then I’m totally, 100% fine (and 0% not fine 😀 ) to use the Law of the Excluded Middle. In that context, the whole obsession with constructive proofs is a thing that I never understood in the slightest. It’s like, why not drop any of the other self-evident rules of propositional logic, and see how far you can get that way? What’s so special about Excluded Middle?
I agree that constructive proofs can be useful in other contexts, beyond establishing the bare truth of some proposition. For example, very often we want an algorithm (better yet, an efficient algorithm) to find an object, rather than just a proof that the object exists.
Comment #222 March 21st, 2020 at 2:41 pm
Douglas Knight #216: To whatever extent a virus is optimizing for anything when it mutates, it’s optimizing for making as many copies of itself as possible. All else equal, a mutation that increased a virus’s r0 would of course seem extremely bad. On the other hand, it could also be good, if it turned out that the way to make more copies of yourself was to make your hosts only mildly sick, ideally asymptomatic, rather than sending them to the ICU and/or killing them. So it could go either way; more info is needed about the mutation’s effects.
(Here on Shtetl-Optimized, armchair epidemiology is always free of charge 😀 )
Comment #223 March 21st, 2020 at 2:53 pm
Andrei #95:
My question is: what do you think about bounded arithmetic, proof complexity, and generally things around that circle of ideas?
I’m strongly in favor of them … as long as they maintain at least a 6ft distance from me! 😀
More seriously: I’ve always been fascinated by logic and model theory and proof complexity, but more at the abstract level (i.e., the level I tried to get across in Quantum Computing Since Democritus) than at the level of actually rolling up my sleeves and doing anything original. Despite some valiant attempts (see e.g. this by Pavel Pudlak), so far there’s been relatively little connection between proof complexity and quantum computing, or any other parts of CS theory where I have actual working expertise. Of course it will be extremely interesting to see if that changes!
Comment #224 March 21st, 2020 at 2:55 pm
Scott #221
I take it you aren’t a fan of Coq and the Calculus of Constructions then.
What is your preferred approach to formal proofs ?
Comment #225 March 21st, 2020 at 3:00 pm
Gerard #214
> Doesn’t your first proposition here rely on the principle of the excluded middle ? Meaning it’s non-constructive (and hence not something you could trivially prove in Coq, for example). Don’t you think constructive proofs have higher epistemic status than non-constructive ones ?
Disproving “P=NP iff P≠NP” means proving “~ (P=NP iff P≠NP)”, and that can be proved constructively using principle of non-contradiction. Here is a proof in a language called “Idris” (sorry, I don’t know how to do code formatting):
not__p_iff_not_p : Not ((p -> Not p), (Not p -> p))
not__p_iff_not_p (g, h) = g (h $ \x => g x x) (h $ \x => g x x)
Even without being able to prove either implication, we can prove (easily, in agreement with Scott’s point) that they can’t both be true.
Comment #226 March 21st, 2020 at 3:16 pm
Yovel #97-98:
Who are the leading candidates, in your opinion, for the next Turing Award? Or, if you prefer, who are the ones most deserving the award?
The literally next Turing Award has so much stochasticity in it that, unless one has inside info, there’s no point in even speculating about it. Who deserves to be in line to eventually get a Turing Award is a somewhat better question. Certainly quite a few Turing Awards that were given during my career (e.g. Yao, Valiant, Goldwasser and Micali, RSA, Diffie and Hellman, Judea Pearl, Vint Cerf, Leslie Lamport, Tim Berners-Lee, Hinton and the other deep-learning guys, recently Ed Catmull from Pixar) had the property that, long before they were awarded, the thought had crossed my mind, “wow, that person’s contributions to CS seem extremely impressive, such that it would not be out of place for them to get something like a Turing Award!”
If, without delving into details, I simply ask myself who gives me a similar feeling today … I dunno! Satoshi, except that he’s presumably disqualified on the grounds of no one knowing whether he even exists or is a single individual at all? 🙂 Other cryptocurrency pioneers like Buterin? Brin and Page, for PageRank? Or, if one preferred somebody who had the same basic ideas at the same time but didn’t become a gazillionaire from them, then Jon Kleinberg? Hassabis (or others at DeepMind), for AlphaGo and AlphaZero? Luis von Ahn, for CAPTCHAs and DuoLingo?
It’s actually not such an easy question, without being on the committee and seeing a full slate of nominations.
Comment #227 March 21st, 2020 at 4:26 pm
Gerard #214:
No, one absolutely does not need excluded middle to show ¬(A⇔¬A). A⇔¬A is just the conjunction of A⇒¬A and ¬A⇒A. Note that A⇒¬A is just the same thing as A⇒(A⇒⊥), i.e., (A∧A)⇒⊥, i.e., A⇒⊥, i.e., ¬A. Meanwhile, ¬A⇒A would in particular imply ¬A⇒¬¬A, which by above is the same thing as just ¬¬A. And, by the principle of non-contradiction, one cannot have both ¬A and ¬¬A.
Maybe there is a better way to demonstrate this, I’m not an expert in constructive logic. Regardless, absolutely nothing non-constructive is required to show ¬(A⇔¬A).
Gerard #216:
Why on earth should one be bothered by the liar paradox, which relies on statements that can’t even be expanded out, and so can’t even be formalized in any reasonable version of mathematics?
Comment #228 March 21st, 2020 at 4:40 pm
Scott #221,
“ If we just want to establish what’s true, then I’m totally, 100% fine (and 0% not fine ???? ) to use the Law of the Excluded Middle. In that context, the whole obsession with constructive proofs is a thing that I never understood in the slightest. It’s like, why not drop any of the other self-evident rules of propositional logic…”
HOLY MOLY!!! Wow, wow, wow!
Now this hit me like a lightning bolt and has me very excited 🙂 Why? Because Scott, my friend, I think you have grossly over-relied on your intuition here and for once it has led you astray. I suspect you are are going to be delighted to be shown wrong.
I contend there are truths (important ones too!) that are only evident with specifically *excluding* the Law of the Excluded Middle. Truths that can not be arrived at or understood without neglecting this “self-evident” rule. Frankly, I am shocked that you did not already know this. It seems you esteem western logics above and beyond others for no other reason than habit and familiarity!
Let me marshal my thoughts and will get back to you with the actual case!!
Comment #229 March 21st, 2020 at 4:43 pm
Scott #221:
If you are looking for a more pragmatic use of intuitionistic mathematics and generally constructive ideas, check out the “proof mining” program of Ulrich Kohlenbach (see e.g. his survey for ICM 2018). In short, this program focuses on analyzing proofs in ordinary mathematics (e.g. nonlinear analysis, commutative algebra, etc.) using proof-theoretic tools in order to extract additional information which is not immediately apparent, for example a rate of convergence from a convergence theorem (or, in cases where such a rate can be shown to be potentially non-computable, weaker information like a “rate of metastability”).
Disclaimer: I am one of the contributors to this program.
Comment #230 March 21st, 2020 at 5:18 pm
John K Clark #99:
If the acceleration of the universe is itself accelerating and we’re heading for the Big Rip would the universe be capable of performing an infinite number of calculations? It seems to me that in theory you could extract useful work out of Dark Energy and at a exponentially increasing rate, so you could run your computer faster and faster, so even though the amount of time available would be finite the number of calculations might not be. Of course eventually the Dark Energy would start to tear your computer apart but even so….
Point #1: In the standard ΛCDM cosmology, the one that’s fit all the data since 1998, there will not be any Big Rip. There will merely be an accelerating, exponential expansion that continues forever, just like what’s happening right now (except somewhat faster after there’s a lower density of matter to counteract the expansion gravitationally). To get a Big Rip, you’d need something different and exotic.
Point #2: If you believe in the ΛCDM model, together with the Bekenstein bound from black hole thermodynamics, then there’s an upper bound of about 10122 on the number of bits or qubits that can ever be involved in any computation that takes place in our universe—assuming that the results of the computation have to be readable in a single place. Notably, this is true even if the universe is infinite: regions more than 40 billion light years away or something are receding too quickly from us for the results of any computations done there ever to reach us.
With those points out of the way:
Frank Tipler famously proposed a scenario much like what you describe, where an infinite amount of computation gets done in a tiny fraction of a second before the universe ends (in his case, via a Big Crunch). Well, he didn’t just propose it—he claimed to be able to derive a priori that the future had to be that way, and even connected it to his religious beliefs! Observation was not kind to these ideas: if the dark energy discovered in 1998 is indeed a cosmological constant, then there won’t be a Big Crunch, let alone one where we all get to live forever (subjectively speaking) in a computer-simulated paradise.
I have no idea whether something like Tipler’s scenario could be resuscitated in a (to be clear, totally hypothetical) Big Rip cosmology—I suppose it could depend on the details of the latter, and possibly on unknown features of quantum gravity. Is there anyone here who knows cosmology and GR and who’d like to field this one?
Comment #231 March 21st, 2020 at 5:31 pm
Sniffnoy #227
> Why on earth should one be bothered by the liar paradox, which relies on statements that can’t even be expanded out, and so can’t even be formalized in any reasonable version of mathematics?
I don’t follow you.
Isn’t the counterexample that is used to prove the uncomputability of the halting problem basically just a formalized version of the liar paradox ? Also according to Wikipedia Godel’s first incompleteness theorem also uses such a construction: https://en.wikipedia.org/wiki/Liar_paradox#Applications.
I was, of course, referring to such a formalized version.
Comment #232 March 21st, 2020 at 5:41 pm
Ted #100:
I’ve occasionally seen mention of a quantity called “quantum discord” that apparently quantifies quantum correlations that are not caused by entanglement. I’ve heard allegations that it can even be useful for quantum computing (the “Deterministic quantum computing with one qubit” or DQC1 model), which I’m very skeptical of. Could you discuss at a relatively non-technical level (either here or in a separate blog post) what “quantum discord” is and whether it’s actually useful for quantum computing?
I confess that I can never remember the definition of quantum discord! You can look it up here. It’s some mutual-information-based measure of the “quantumness of correlations” in a bipartite system. It coincides with the entanglement entropy for pure states, but it can be nonzero even for certain separable (that is, completely unentangled) mixed states.
OK then, but if I know that a bipartite mixed state has nonzero discord, what can I do with that fact? What concrete protocols are powered by quantum discord, the way quantum teleportation and superdense coding and Bell inequality violation are powered by entanglement? I’ve asked several colleagues that question over the years, but never once got an answer that was simple enough (or maybe connected enough to things I cared about?) that it stuck in my head.
I can say that, in 20+ years of working on many aspects of quantum computing and information, I’ve never once needed the concept of quantum discord for anything that I personally cared about, including DQC1. And I’ve seen quantum discord invoked in ways that made me cringe (“while we can’t articulate the point of our experiment, or anything of broader interest that our system does, it has nonzero quantum discord, ergo our paper should be published in PRL”).
However, it’s entirely possible that discord is useful and needed in other parts of quantum information, besides the ones that I’ve worked on. Does anyone here have insight to share?
Comment #233 March 21st, 2020 at 6:16 pm
Hi Scott,
I just wanted to thank you for keeping this blog and for doing this, even when so much seems to be crumbling around us.
Reading this AMA has helped me cope with my current dread. Not because its particularly optimistic, but because your reasoning is always so refreshingly *clear*.
I know this will not just “blow over”. But being stuck at home gives me the choices of being pessimistic and optimistic. Neither will make a shit difference to the world right now, given that the only possible course of action is just to stay home. But being optimistic, right now, helps us navigate these crazy times with less panic and dread (and maybe keep our immune systems a little stronger!), helping us to come out on the other side better and stronger for us, our children, and the rest of the world which will sorely need our help.
Stay safe =)
Comment #234 March 21st, 2020 at 7:12 pm
Gerard #231: No, Tarski’s Theorem (on the indefinability of truth) is a straightforward formalization of the liar paradox, but Gödel’s and Turing’s theorems are not. They both modify the liar paradox in crucial ways. With Gödel’s theorem, you look at an encoding, not of “This sentence is false,” but rather of
G(F) = “This sentence can’t be proved in the formal system F.”
The crucial advantage of G(F) over the original liar sentence is that, as Gödel showed, it can “compiled down” to a pure statement of arithmetic—you don’t need the unformalizable concepts of “truth” and “falsehood.” On the other hand, unlike the liar sentence, G(F) is not an outright paradox or contradiction! Everything works out, for example, if G(F) is simply true yet unprovable in F.
With Turing’s theorem, you consider a hypothetical program P that’s purported to be able to analyze the behavior of an arbitrary input program, and then you set things up in such a way that P is run on itself, and forced to do something different from what it does. That would be a contradiction, but the contradiction is resolved simply by P never existing in the first place. So this is again different from the liar paradox, even though it shares a self-referential character.
Comment #235 March 21st, 2020 at 7:15 pm
Daniel #233: Thank you so much. The fact that at least person (hopefully more? 🙂 ) who I like and respect is reading this, and that it’s helping them cope, makes my day and makes the whole exercise feel worth it to me.
Comment #236 March 21st, 2020 at 7:48 pm
The r0 if a virus is as much a function of the social interactions among humans than a property of the virus itself. E.g. social distancing makes the r0 drastically smaller.
Comment #237 March 21st, 2020 at 8:39 pm
Scott #232: I know of one possible example of a quantum protocol that’s “powered by” quantum discord: according to https://arxiv.org/abs/1312.3332, the “quantum illumination” protocol that Seth Lloyd proposed in 2008 in https://science.sciencemag.org/content/321/5895/1463. (Please correct me if I’m wrong, but the idea seems to be that for a system that used to be entangled, but whose subsystems have decohered, there remain correlations that survive the decoherence process and are stronger than would be possible in a system that was never entangled in the first place, and these correlations can be useful for sensing. The quantum discord quantifies these correlations that preserve a “memory” of the initial entanglement.)
While not a computing protocol, quantum illumination appears to have been experimentally demonstrated to beat classical bounds for applications in quantum communications and sensing in https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.111.010501 and https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.114.110506, respectively. This does seem to me to be a non-hyped situation in which quantum discord can deliver a demonstrable improvement over purely classical protocols, but please let me know if you disagree.
Comment #238 March 21st, 2020 at 9:01 pm
Gerard #224:
What is your preferred approach to formal proofs ?
I confess I don’t have one, as someone who (so far) has had no need to work with fully formalized mathematics on a day-to-day basis. At a conceptual level, I’m totally fine with (say) first-order logic and ZFC. And I’m also totally fine with any “higher-level programming language” that anyone else wants to use for mathematical reasoning (for example, category theory, type theory, Voevodsky’s stuff…), just so long as that higher-level language can ultimately be “compiled down” to first-order logic plus ZFC, possibly with some large cardinals thrown in, or some similar system that I fully understand and that’s clear.
Comment #239 March 21st, 2020 at 11:36 pm
Scott #230
I really hope the universe does turn out to be a Zeno machine. That would make for a universe that is far more interesting from our point of view, because there would always be the potential for more and more interesting and complex things to happen forever. It would be in keeping with the ‘Infinite In All Directions’ philosophy of Dyson and Deutsch.
Of hope me hoping that it’s like that, doesn’t make it so. But I think there’s still enough doubt about the nature of dark energy, that there’s still a decent possibility that the universe is a Zeno machine. No one knows how the dark energy works. Perhaps it doesn’t even exist at all, or perhaps it’s not a constant. I refuse to believe that the amount of computation possible is bounded!
Instead I would go back to my idea of reality as a ‘Sphere Of Information’, a ‘conceptual space’ where all concepts that can in principle be known are located, as outlined in post #198 above. (Note, I think it’s actually a 3-Sphere (a hypersphere), because I think there’s 3 different dimensions of abstraction)
So I think the hyper-sphere of information has a really weird property. The surface is the points of minimum complexity. The center is the point of maximum complexity. As you move towards the center, you find the space expanding without bounds , like the TARDIS in Doctor Who! It seems finite on the outside, but you move towards the center, the geometry stretches out more and more, so that in fact, paradoxically, you have to cover an infinite distance to reach the center – in the limit that you reach the center, the complexity reaches infinity !
As I implied in #198, I think the external poles of the hyper-sphere would represent the bottom of the physics and math hierarchies , respectively (basic algebra for math, and quantum mechanics for physics). And you move towards the center, you’re moving up the math and physics hierarchies, towards ever more complex systems.
At the core (the exact center), I think, is, in effect, ‘the mind of God’ (inifinitely complex cognitive system). So we see that math gets ‘closer to closer’ to cognition as we move up the math hierarchy towards the center of the hyper-sphere.
What I’m saying is that, I think reality is like an onion with infinite amount of layers to be peeled off. Infinite at the center! The surface of that hypersphere is ‘The Beginning Of Infinity’
Comment #240 March 22nd, 2020 at 2:56 am
Scott #95:
> For the Bay Area rationalists have now publicly sounded the alarm about a looming crisis for the human race, well before it was socially acceptable to take that crisis too seriously (and when taking it seriously would have made a big difference), and then been 100% vindicated by events.
That’s my impression as well (though I was on the “we need to worry about x-risks” bandwagon before, so my views haven’t changed).
Btw, I’d even go one bit further than you – the two biggest issues that x-riskers have been talking about, or at least that’s my impression, is rogue AIs, and a (probably human manufactured) super virus. Without even looking at the rationality-sphere’s reaction to Coronavirus specifically, the fact that one of the two main issues we’ve been harping on about all this time is a super-virus, and that we now have a great live example of a non-super virus, just a regular virus, causing this much damage, just makes me double down even more on saying that the threat of a *real* super-virus is just as big as we’ve been worrying about.
Off topid – here’s a question for the AMA – is there any way to get notified if someone replies to me on this blog? I know I can just set notifications on when submitting a comment (or I though tthat was an option – don’t see it now), but that tends to fill up my inbox too quickly 🙂
Comment #241 March 22nd, 2020 at 6:52 am
b #101:
What do you think of academics having to write diversity statements as part of a job application?
I think diversity is a value worth pursuing, even over and above intellectual excellence, which already produces many kinds of diversity when you optimize for it alone. I’m strongly in favor of applicants, if they choose, talking about what they did or want to do to reach out to underrepresented populations as part of their teaching statements. That’s what was done for decades—when I applied in 2007, to take one example, I talked about the volunteer math and CS outreach I’d done at high schools that heavily served underrepresented populations. If I were on the job market today, I might talk about how proud I was to have hosted a weekly quantum information group meeting at UT Austin that’s regularly included trans people (most famously Ewin Tang), African-Americans, Hispanics, Iranians, Chinese, Indians, self-taught folks from the Austin community, and even a few experimentalists. 🙂
Having said that, I also think that separate, mandatory diversity statements, particularly the way they’ve apparently been implemented by the University of California system, are a moral travesty.
For those who haven’t been following, apparently this year UC life sciences not only required all faculty applicants to submit diversity statements, but rejected 75% of applicants purely on the basis of those statements, with no consideration given to their research or teaching.
This raises an obvious question: how do you reject 75% of applicants purely from their diversity statements, when nearly 100% of those statements affirm that diversity is great, the applicant values diversity, he or she has been privileged to work with diverse students and collaborators and hopes to continue doing so, etc. etc.?
Part of what’s going on, apparently, is that UC wanted a way to get race and gender quotas into faculty hiring, as they’re forbidden from doing overtly by California state law. That’s actually the part that I find less troubling. The worse part is that, to whatever extent the statements weren’t just a backdoor way to consider the applicant’s own sex and skin color, they functioned as a blatant ideological litmus test. It wasn’t enough to value diversity or to want to treat all people with equal respect. Instead, the only way to get a high score, and thereby advance to having your research considered, was to parrot the specific formulations of modern social-justice ideology that you might find (for example) on woke Twitter. So in particular, the applicant would need to know the right codewords—which could have the extremely ironic effect of punishing applicants from outside the Anglo countries, where those codewords are more widely understood.
Anyway, what happened next was that Abigail Thompson, the chairwoman of the math department at UC Davis (and a longtime friend of Shtetl-Optimized guest blogger Greg Kuperberg), wrote a short piece for the Notices of the American Mathematical Society that exposed the situation for what it was, opposed it, and explicitly made an analogy with the anti-Communist “loyalty oaths” that UC faculty were forced to sign in the 1950s on pain of firing.
In response, a mathematician named Chad Topaz at Williams College collected ~600 signatories on a letter condemning Thompson (I can no longer find it online, but see here), and there were loud demands that Thompson step down as department chair. But Thompson, who emerges as a heroine in this story, declined to apologize or step down, and a counter-petition (see here for signatories) circulated in the math community supporting her right to express her views. As someone liable to get depressed about these things, I found it inspiring that between the two petitions, virtually every mathematician of whatever race or gender who I’d personally known or respected, or even heard of in a mathematical context, was on the second petition rather than on the first.
Anyway, even as I write this, I wonder whether the whole tempest has been rendered irrelevant by events. It’s like: refusing to consider a brilliant biologist, because she’s pro-diversity but not in exactly the right way or with exactly the right codewords, is a sort of luxury that you can afford only if you think of biology jobs as basically just spoils or sinecures to be divvied up. These woke signaling games become a lot costlier as soon as you actually need the best biologists—for example, to help stop pandemic diseases. Going forward, I could imagine that we’re going to see a lot more emphasis on serving a diverse population that’s also alive and not hooked up to ventilators.
Comment #242 March 22nd, 2020 at 8:05 am
Scott#181
“Can Supreme Court justices be disbarred?”
A Supreme Court justice can be impeached but constitutionally he doesn’t even have to be a lawyer.
John K Clark
Comment #243 March 22nd, 2020 at 8:27 am
Thanks for this I’ve enjoyed reading questions and responses.
I have 2 daughters (4 and 8) who we’ll be home schooling for coming period. If you do teach your daughter about some of your work and put this on the internet that would be amazing. I have plenty of colleagues and friends who’d love it too.
Comment #244 March 22nd, 2020 at 8:49 am
Everyone: I apologize for my slowness in working through the list of nearly 100 questions! Short-answer questions are one thing, but many of these questions effectively require a blog post or essay in themselves to answer. And it turns out that it’s not so easy to produce dozens of new blog posts on command! I’ll get to everything soon, though, I promise.
Comment #245 March 22nd, 2020 at 10:05 am
Not a question but a comment. Your state of mind is not helpful to you, your family, or anyone else. Everyone in the world is anxious about the state of the world right now. Talking about an “apocalypse” is not doing your own mental health any good.
Be glad that you have your family with you. Be glad that you are still healthy.
And focus on social distancing and on something to take your mind off and be productive!
(And for the record, I live in Canada, where at least so far my provincial and federal governments are taking COVID-19 seriously and acting to try and “flatten the curve” i.e. mix of suppression and mitigation of infections. Whether their efforts are enough to make the difference is up to all of us, and we won’t know if it is until several weeks after the effects were implemented back on March 13).
Comment #246 March 22nd, 2020 at 10:28 am
Aaron G #245: Your outlook might be a bit different if you lived in the US, where during the crucial weeks, the president pursued a policy of “don’t test, don’t tell”—i.e., obfuscate the truth about how many people are being infected, because as soon as it gets out the stock market will crater. This policy may have consigned millions of people to their deaths—although if we’re lucky, the WWII-level mobilization that’s finally starting despite the president’s delay might still reduce that to tens or hundreds of thousands, at a staggering cost.
As I mentioned in an earlier thread, I’m extremely worried in particular about my parents, both of whom have compromised immune systems. I have no expectation that ICUs will be available if they need that.
So no, this isn’t the apocalypse. But it’s arguably the closest thing to an apocalypse that I, and most other human beings below the age of 80, have ever experienced.
If you met me in person (which I don’t advise right now 🙂 ), I think you’d be pleasantly surprised by how well I’m holding up, given the above! Mostly I’m just sheltering at home like I’m supposed to, eating, sleeping, and spending a huge amount of time with my family. And blogging, of course.
Comment #247 March 22nd, 2020 at 3:46 pm
Scott 222,
I’m not sure how important it is, but parasites are not optimizing R0. Rather, they are optimizing reproduction per unit time. So speeding up the progression of the disease, which is pretty much what virulence is, can improve fitness, even if it reduces R0.
The group selection / prisoner’s dilemma is a ratchet making it easier to evolve higher virulence than to evolve lower virulence. If two variants exist in different hosts, the one with higher fitness will outcompete the one with lower fitness, tautologically. But when the divergence first appears, both variants are in a single host. The more virulent one moves faster and outcompete the less virulent one within the initial host. It will make the host sick, triggering the immune system and social distancing and the less virulent one may not escape the host at all, and thus never have a chance to have its fitness tested in the full inter-host reproductive cycle.
Comment #248 March 22nd, 2020 at 10:55 pm
clayton #102:
What is your frank opinion of the overarching geometry-from-entanglement, it-from-qubit program? If that’s too broad (or too close to home), here’s a very narrow subquestion: what is the replica wormhole result telling us?
I’ve been a member of the It from Qubit collaboration since the beginning. I wouldn’t have joined if I didn’t genuinely think it’s one of the more exciting things now happening in fundamental physics! Having said that, my reasons for being excited might be slightly different from those of other collaboration members. I have no attachment to string theory being true as a fundamental description of nature, let alone string theory in 5-dimensional supersymmetric AdS space or whatever. But it seems to me that over the past ~20 years, AdS/CFT has emerged as a playground for much broader questions about quantum gravity, and it’s led to striking insights about those questions that are clearly clues to something.
OK, if I tried to do this justice—even the small fragment that I’ve worked on and sort of understand—this would become a whole essay, and I still have twenty-odd questions to go. In one paragraph, though: if we accept the celebrated discovery of Bekenstein and Hawking from the 1970s, that every black hole has an entropy that scales like the surface area of its event horizon in Planck units, then a question arises of how to reconcile that discovery with the rest of physics, without giving up on even more basic principles like the unitarity of quantum mechanics. Once you try to take that question seriously, you’re led (for example) to the holographic principle, to the idea that there needs to be some mapping between the stuff that an observer outside a black hole sees pancaked on its event horizon, and the radically different view of the same stuff that an infalling observer sees. And this mapping, by its nature, can’t respect spatial locality; it has to scramble information, like an error-correcting code. And trying to understand the mapping better leads you to questions about entanglement, and error-correction, and even circuit complexity … yeah, as I said, it’s a long story! 🙂 But astonishingly, it’s a story much of which is told in an extremely simple language of qubits and quantum gates and so forth—a language that (unlike the languages of QFT and string theory) I actually know. And it’s repeatedly led to new questions in quantum complexity theory that I’ve been able to play with, and that would be interesting to me even if you removed the quantum gravity motivation, and where I’ve been able to tell the physicists a couple things that they didn’t already know.
Now as for the new replica wormhole thing: yeah, I don’t even pretend to understand it. Having said that, Daniel Harlow did spend an hour explaining it to me on my recent visit to MIT (one of my last trips before the coronavirus made travel inadvisable). And I can try to summarize what Daniel told me, with thanks to him but with all errors my sole responsibility.
Hawking’s original derivation of the existence of Hawking radiation relied on the Euclidean path integral—i.e., a piece of dark witchcraft that has no general reason to work in quantum gravity, and that sometimes definitely doesn’t work, but that often enough does work (in the sense “spitting out an answer that you have independent reasons to like”). In one sentence, the essence of the new discovery seems to be that, to whatever extent you accept that dark witchcraft, the same dark witchcraft, when combined with additional dark witchcraft involving “replica wormholes,” can also be used to derive the famous Page curve. I.e., you can “derive” the statement that the Hawking radiation is not completely thermal, but really does encode the quantum state of the infalling matter.
This means, in particular, that you can “solve the black hole information loss problem,” but only in the sense that you’ve “derived” from the dark witchcraft the bare statement that you wanted (and that you probably believed for other reasons anyway). You still don’t get a microscopic description of what a black hole’s entropy consists of, so you still haven’t “solved the information loss problem” in that stronger sense.
Comment #249 March 22nd, 2020 at 11:21 pm
AdamT #104:
What do you think of Sabine’s new essay on “Unpredictability, Undecidability, and Uncomputability” and her contention that, “In summary, mathematical impossibility-theorems are relevant in science, not because they tell us something about nature itself, but because we use mathematics in practice to understand observations, and the theorems tell us what can expect of our theories.”
I specifically asked for no questions that require me to comment on any linked paper or document! So I hope you’ll forgive me for confining myself to the following remark:
Sabine’s wordsplitting conclusion reminds me a lot of Niels Bohr’s (in)famous maxim that “physics is not about nature; it’s only about what we can say about nature.”
To which my reaction was always: OK, wonderful, and appropriately wise-sounding. But the whole reason why we care “what we can say about nature” is that ultimately, knowing the answer to that question does tell us a lot about nature itself!
As one example, we’ve learned that we have to talk about nature in the language of quantum mechanics. But there’s a reason why we have to talk about it that way, and I’d summarize the reason by simply saying that nature is quantum-mechanical! But however you want to describe the reason, it’s clearly not just some language convention, but one of the greatest discoveries about nature itself that was ever made.
And I’d say exactly the same about uncomputability (to take one of Sabine’s examples). Yeah, sure, whatever, computability and uncomputability are properties of theories rather than properties of the universe. But it seems obvious that the question we really care about is, “can the universe be appropriately described by a computable theory? Or can it only be described by uncomputable theories?” And the latter is not only a question about the universe itself; it’s one of the biggest such questions that I can imagine asking.
Comment #250 March 22nd, 2020 at 11:27 pm
Nick #105:
Do you own a gun? If so, what kind, etc? If not, have you thought about getting one?
No, I’ve never owned a gun and never wanted one. If I ever felt like I needed one to protect my family, then I expect that my first instinct would not be to buy one but to move.
Comment #251 March 22nd, 2020 at 11:32 pm
Zeb #106:
Do you think the (asymptotically) best quantum error correcting codes are likely to be stabilizer codes?
It seems plausible that they would be, by analogy to the classical case (especially if you don’t care about efficient decoding!). But you should totally ask someone who knows quantum error-correction better than me. Is there such a person here?
Comment #252 March 22nd, 2020 at 11:34 pm
Jim #107:
What was the flavor of the last piece of cake you ate? (Mine was blueberry-chocolate)
Today I had some chocolate birthday cake, baked by my wife Dana and daughter Lily, to celebrate my son Daniel’s third birthday. (At Lily’s insistence, the cake was assembled from three successively smaller layers, like a wedding cake. It leaned to the side like the tower of Pisa.) Happy birthday Daniel!
Comment #253 March 23rd, 2020 at 2:47 am
@Douglas Knight:
Thanks! Now your argument makes sense to me. I did assume you were talking about parasites jumping between two host species (or moving within a single species).
Comment #254 March 23rd, 2020 at 4:39 am
Happy birthday Daniel!
Comment #255 March 23rd, 2020 at 6:47 am
Scott #234
> With Gödel’s theorem, you look at an encoding, not of “This sentence is false,” but rather of
> G(F) = “This sentence can’t be proved in the formal system F.”
My understanding is that Coq and the Calculus of Constructions replaces assertions about truth or falsity with assertions about provability. Since it appears that most, if not all, of mathematics can be formulated in this way perhaps the difference between those two points of view isn’t all that important ?
As for the original Liar’s Paradox it seems like it’s not “really a paradox” either. It seems like it’s only a paradox if you insist that all sentences be assigned a truth value. But clearly it makes no sense to assign a truth value to many sentences. What is the truth value of “Take out the garbage.” or “What is the capital of Austria ?” ? Also even sentences that have the form of a proposition don’t necessarily have a truth value because they may depend on external context. For example to assign a truth value to the sentence “The river is wide.” you would first need to specify which river it’s referring to and how you define “wide”. The Liar Paradox sentence seems a bit like this later case in that by referring to itself it seems to be referring to something that is “on the boundary” between internal and external context.
In any case my point in bringing up paradoxes wasn’t to get into a technical discussion of these particular issues but rather that mathematics seems to have certain limits or flaws where it seems to break down in unexpected ways. Some examples of this are Godel’s Incompleteness Theorem, the Halting Problem and the Banach-Tarski Paradox (this is the Tarski Paradox I meant, not the logic related one).
A question I find very interesting is whether there exists a way of doing mathematics that retains it’s interestingness (and especially it’s practical relevance) while avoiding these problems, whether that involves limiting oneself to finite sets or constructive proofs.
Comment #256 March 23rd, 2020 at 9:41 am
Gerard #255,
“My understanding is that Coq and the Calculus of Constructions replaces assertions about truth or falsity with assertions about provability. Since it appears that most, if not all, of mathematics can be formulated in this way perhaps the difference between those two points of view isn’t all that important?”
Moreover, both Coq and similar proofing systems are not Turing-complete, *always* halt, and do not include the Law of the Excluded Middle in them at all. This is not by mistake.
“But clearly it makes no sense to assign a truth value to many sentences. What is the truth value of “Take out the garbage.” or “What is the capital of Austria ?” ? Also even sentences that have the form of a proposition don’t necessarily have a truth value because they may depend on external context.”
But that is *exactly* what is wrong with the Law of the Excluded Middle and was noted by none other than Aristotle when he drew back from using it based on the problem of future contingents. Any logical system that uses LEM as an axiom will necessarily not deal with these types of propositions.
“A question I find very interesting is whether there exists a way of doing mathematics that retains it’s interestingness (and especially it’s practical relevance) while avoiding these problems, whether that involves limiting oneself to finite sets or constructive proofs.”
I don’t know how to account for *interestingness*, but there are strongly normalizing languages that do not break down like Turing machines and the halting problem. The simply typed lambda calculus – which is the internal language of Cartesian Closed Categories and therefore super interesting! – is strongly normalizing. Any program written in it will necessarily halt.
Comment #257 March 23rd, 2020 at 10:18 am
We know how to solve the following:
given positive integers a,b, find integers x,y that minimize ax + by > 0
and while the decision problem version is in P, it is not known to be P-complete, and it appears difficult to parallelize.
Now consider:
given positive integers a,b,c, gcd(a,b,c)=1, find integers x,y that minimize ax^2 + bxy + cy^2 > 0
This also can be solved through a sequence of operations, and feels very “euclidean” like.
Recently an acquaintance of yours, Bram Cohen, had a contest you promoted on your blog, which in essence challenged people to solve this problem as quickly as possible with access to a beefy GPU and many CPU cores. No one really used the parallel resources (besides I think a guess and use-a-backup type algorithm using 2 cores).
Unfortunately, not a single entrant even analyzed this from a computer science perspective.
So that is my question to you:
Is it possible to show that the second problem “reduces” to the first, in the sense that if we could efficiently use parallel resources to solve the second problem, that it means we could then solve the first using parallel resources efficiently as well?
Sorry if I worded that weird, but hopefully the question is clear.
Comment #258 March 23rd, 2020 at 11:48 am
Scott,
Someone rings your doorbell and claims to be representative and fully connected to all knowing/powerful God, but you feel skeptical. What question would you ask that would be both easy enough check in short time (few hours) and convince you 100%?
Comment #259 March 23rd, 2020 at 12:12 pm
According to Stoicism, whenever you think that you’re in a bad situation, it’s useful to imagine how things could actually be way worse.
So if you’re a fan of fairly realistic scifi and are feeling down, I recommend reading “Seveneves” by Neal Stephenson, it shows what a real apocalypse could be like, and how humanity can endure, no matter what.
That book actually helped me deal with stage 4 cancer!
Comment #260 March 23rd, 2020 at 12:23 pm
Nick Nolan #257: As I said several times, no more questions. Thank you!
Comment #261 March 23rd, 2020 at 1:00 pm
Nick Nolan #257
I’ll give you my answer even if Scott won’t.
I think it all comes down to your definition of what an all-knowing/all-powerful god is. If the power to grant you delights beyond your wildest dreams or suffering beyond what any human being has ever imagined for as long as the stars have fuel to burn suffices then I would argue that all you need to be convinced of is that they have access to a really fast NP oracle (ie. being able to solve some convincingly hard billion+ variable SAT instances in a few seconds, for example).
Comment #262 March 23rd, 2020 at 4:55 pm
I tried to respond to a comment above, my browser locked up, nevermind probably for the best since my thoughts seem against the entire world. My family and me are ok, all locked up in 4 rooms in London UK, we all had flu symptoms and seem ok now.
If I had been on time to ask a question (haven’t been over the years, lol) I would have asked “Why is it called Computer Science when you don’t do any experiments?”
Comment #263 March 23rd, 2020 at 5:23 pm
James Gallagher #261: I said no more questions, but that’s not even a real question, it’s a snark. 🙂 So here’s one answer: more than half of what you’ll find in a typical CS department is experimental, involving (e.g.) experimental assessments of the performance of systems or algorithms that you or others designed. Even I have a few experimental papers, especially from earlier in my career … which is more than many of my theoretical physics colleagues can say!
Comment #264 March 23rd, 2020 at 5:31 pm
lewikee #108:
Are there examples of weak entanglements? Where if I measure one of two entangled particles as being in a certain state, I do not know for sure the state of the other, but I also know more about its state than by simple chance?
Yes, absolutely—as long as I interpret “I do not know for sure the state of the other…” to mean “the other particle is in a superposition that’s moderately biased toward |0⟩ or |1⟩.” (A superposition of |0⟩ and |1⟩ is itself a definite state! You just don’t know in advance the outcome of measuring it in the |0⟩,|1⟩ basis.)
An example would be the 2-qubit state
[ |0⟩ (0.8|0⟩ + 0.6|1⟩) + |1⟩ (0.6|0⟩ + 0.8|1⟩) ] / √2.
As you can see, measuring the first qubit gives you some information about the second qubit, but less than the maximal amount. This state is non-maximally entangled.
Comment #265 March 23rd, 2020 at 5:42 pm
Jair #109:
Let’s say you have a very good estimate of the fatality rate for a disease about as infectious as COVID-19. At what fatality rate do you decide to order shelter-in-place restrictions (similar to the ones recently put in place in San Francisco, say)?
It depends on a hell of a lot more than the infection and fatality rate! For starters:
– How much of a toehold the disease has established in the community
– How well people are sheltering voluntarily
– How the fatality rate is expected to change as the hospitals fill up
Comment #266 March 23rd, 2020 at 5:52 pm
Jack Vaughan #110:
How does logistics/optimization look among possible quantum comptuting applications? It may be low hanging fruit, but on what planet? On while we are on fruit, Is the work to program quantum comptuers likely to bear and interim fruit via simulation for logitstics/optimization on class computers?
Let me address the first question only (I specified no multi-parters). For logistics and optimization problems, we generally expect only modest speedups from a quantum computer, from algorithms related to Grover’s algorithm (which solves a huge range of combinatorial search and optimization problems in roughly the square root of the number of steps needed by the best known classical algorithms). Alas, no one has any idea how to realize Grover-type speedups anytime soon—they seem to require very high-depth quantum circuits, which in turn would require a full fault-tolerant quantum computer.
I hate to be the bearer of bad news, but if anyone told you otherwise (e.g., that quantum computers will give huge speedups for logistics/optimization in the next few years), that person was almost certainly either lying or misled by somebody else.
Comment #267 March 23rd, 2020 at 6:01 pm
Kevin #112:
What unsolved problems in quantum complexity theory do you think are the most likely to be solved next?
If you’d asked me in the summer or fall, for sure I would’ve said MIP*=RE, since I had inside info that it was on the verge of being solved (and the authors weren’t even particularly secretive about it). But now I don’t have inside info and I don’t feel like speculating. QMA=QMA1, a classical oracle separation between QMA and QCMA, and quantum copy-protection of point functions under plausible crypto assumptions all feel to me like they should be doable, but who knows?
Comment #268 March 23rd, 2020 at 6:40 pm
Justin #114:
What changes would you (and your kids) make to elementary education in the US?
Answering for myself:
– Abandon the rigid separation of students by age (“first grade,” “second grade,” etc.). Just let students advance through each topic at their own pace, often joining teacher-led study groups that bring together students of different ages. (In other words, basically the way universities work, and the way extracurriculars work even in elementary school.)
– Don’t start at an absurd hour like 7:45am (when the public elementaries in Austin start).
– Don’t get all Nazi about it if students are sometimes late to school, or miss school for a trip with their families, etc. School should be a resource for kids (and their parents) to benefit from, not a prison that compels their attendance. Like preschool.
When I asked Lily this question, she said:
– In kindergarten, the classroom was full of toys. This should be extended to first through sixth grades.
– Likewise, kindergarten had more recess time. This should also be extended to the higher grades.
Comment #269 March 23rd, 2020 at 6:47 pm
Laurel #115:
What do your kids think that you and Donna [sic] do at work?
Excellent question!
Lily (age 7) says:
Some days, mommy and daddy teach classes. Other days, they try to figure out things that nobody in the world knows. And daddy also does blogs.
Daniel (age 3) says:
Get money! And go to school!
Pretty damned accurate. 😀
Comment #270 March 23rd, 2020 at 7:34 pm
Nick Palladinos #117:
In the following talk (https://youtu.be/d5BhIFumJXA?t=86) Professor Abramsky seems to imply that the unification of the two communities may be able to attack big problems like P vs NP.
What do you think about the chasm between Theory A and Theory B in theoretical CS?
Actually, I think one of the fundamental ways to explain the chasm is that Theory B isn’t oriented around clearly-stated “big questions” like P vs. NP at all. Instead it’s about inventing and studying languages—i.e., expressive formalisms (category theory, type theory, functional programming languages…) for describing things that were otherwise known. So it’s not obvious to me that the Theory B folks are going to join the struggle to prove P≠NP—they’re welcome to, but they also might just sit it out, and tell the Theory A fighting the battle how they could’ve fought it more elegantly! 😀
(I did, once, get super-fascinated about some Theory B problems, when Joel Ouaknine told me about them in Oxford. But that was because they were basically Theory A computability and complexity questions that happened to have Theory B origins!)
Comment #271 March 23rd, 2020 at 7:42 pm
Leul #120:
What would you think is a good Quantum information and computing project idea will be for an undergraduate physics student whose knowledge about about Quantum information and computing comes from your book and some YouTube lectures?
Sorry, but as a general rule I don’t propose projects to students until I’ve gotten to know them, and seen something firsthand about their knowledge base, interests, and style of thinking.
I can, however, recommend the following algorithm: peruse the quant-ph arXiv every single weekday, as well as the lists of talks at QIP, the Simons Quantum Wave workshops, and any other events that interest you. Just by reading the titles and abstracts, make a list of works that are of potential interest to you. Narrow your list down to 5 or 6 by reading further into the papers. Then, in the papers you like the best, look at the open problem sections! Or any obvious shortcomings in the works that you think could be remedied, or other directions you can think of taking the ideas. And then there’s your project.
Comment #272 March 23rd, 2020 at 7:48 pm
Anon #122:
At a high level, [what] is the role of error correcting codes in the PCP theorem?
In some sense, the PCP Theorem is an error-corrected version of the Cook-Levin Theorem. Error-correction is built into what you want: you want that, even if an assignment satisfies only (say) 99% of your constraints rather than all of your constraints, you can still read out from that assignment the solution to some “exact” SAT instance of interest to you. So it’s totally unsurprising that error-correcting codes would show up, although many more ideas are needed as well (so that, e.g., the verifier only needs to make a few queries, or equivalently each constraint involves only a few variables).
Comment #273 March 23rd, 2020 at 7:57 pm
Vanessa Kosoy #123:
Is there a natural problem s.t. for any algorithm solving it within time complexity t(n), there is another algorithm solving it within time complexity t'(n) s.t. t is superpolynomial in t (i.e. for any polynomial p and n>>0, t(n) > p(t'(n)))?
Yes!! This is precisely (a special case of) the Blum Speedup Theorem. (Also discussed in Quantum Computing Since Democritus.)
Comment #274 March 23rd, 2020 at 10:19 pm
I guess my question was too boring, but I’m surprised it didn’t even make it out of the moderation queue 🙁
Oh well. Glad to hear you and the family are doing well.
My governor just implemented lockdown, so I guess I’m going without pay for … who knows how long. Part of me wishes we’d just admit that the hope for containment has long since passed, so we should just infect all the people of low risk now, and then in a couple weeks we’ll be close to herd immunity.
Comment #275 March 23rd, 2020 at 11:01 pm
Peng #274: Extremely sorry about that! I must have missed your comment. I just put it up (as #257, so as not to ruin the numbering). Alas, it’s too detailed/technical, and violates my rule about not requiring me to read some document elsewhere. But I’m happy to leave it up in case someone else has anything useful to say.
Comment #276 March 24th, 2020 at 10:43 am
AreWeThereYeti #124:
Hey Scott, longtime lurker here. I have a lingering MIP*=RE related question I’ve been waiting for an opportunity to ask you. My understanding is that this means that the tensor-product and commuting operator models of entanglement are unexpectedly not equivalent.
It sounded to me like previously we had those two alternative models of entanglement that we thought were equivalent, at least in the limit, but that since we thought they were equivalent, we could say that we had a complete, correct understanding of entanglement (if not of all its consequences, of course). But if we now know they are not equivalent, can we still say that? Do we know which one is incorrect? Do we know if either is correct?
Yes, one corollary of MIP*=RE is to solve Tsirelson’s problem in the negative: there are correlations that you can get from commuting-operator entanglement that you can’t get from tensor-product entanglement.
If you want to go beyond math and talk about actual physics: I’d say that the commuting-operator model is a good match for quantum field theory, which inherently involves infinite-dimensional, non-tensor-product Hilbert spaces. But we know that quantum field theory can’t be the final truth about nature, because it neglects gravity. And while there’s not yet an accepted theory of quantum gravity that describes our world, the famous discoveries of Bekenstein and Hawking from the 1970s suggest that any such theory would need only a finite number of qubits (that is, a finite-dimensional Hilbert space) to describe any bounded region of the universe. If so, then tensor-product entanglement would ultimately be a better match for physical reality.
Comment #277 March 24th, 2020 at 10:50 am
Nils #125:
Do you know any implementations (open source would be great) of Ewin Tang’s recommendation system, and if/where the algorithm has been applied in industry?
Or what would be the reasons it wouldn’t be usable in practical applications, say like youtube’s recommendation system or something like that?
To add to what Ted #142 already wrote: I know of a couple efforts to implement at least parts of Ewin’s algorithm, but unfortunately the algorithm is not yet practically relevant, for a variety of reasons:
– Huge polynomial dependence on the rank and condition number (although that’s now improving)
– The assumed data structure is not a great match for how data would really be organized at a place like Netflix or Amazon (to put it differently: a large reorganization would be necessary)
– I don’t really know, but I’m told that most services no longer do recommendations in this simple linear-algebraic way anyway
Comment #278 March 24th, 2020 at 10:56 am
John McAndrew #126:
When you wake up in the morning, what motivates you to get out of bed?
Alas, these days I often lay in bed for an hour or more after waking up—mostly answering emails, reading the latest coronavirus news, and getting depressed. What motivates me to get up is mostly Dana yelling at me to come help with the kids.
Curious to know if you’re biologically straight-jacketed by Maslow’s universal human needs like the rest of us: http://scheff.faculty.soc.ucsb.edu/main.php?id=32.html
Yes 🙂
Comment #279 March 24th, 2020 at 12:36 pm
Thanks, Scott, for the reply. That actually sounds pretty exciting, it sounds like this result has taken something we thought we understood and made it an open problem again, one that is perhaps related to the bigger question (from some perspectives!) of quantum gravity, if I understand you correctly. That sounds right up the alley of the ER=EPR, people, perhaps. I know you probably won’t respond at this point, but thanks again, that’s fascinating.
Comment #280 March 24th, 2020 at 12:53 pm
How harmful regulations obstructed US coronavirus response: CDC prevents private companies from manufacturing tests; telemedicine is illegal; some states have laws limiting the number of beds in hospitals; bureaucratic red tape prevents doctors from moving from state to state.
The Trump administration is easying some of these silly regulations, but they started doing this too late. John Stossel: https://youtu.be/v_2omrmqPNs
Comment #281 March 24th, 2020 at 3:08 pm
#263 Scott
haha, you’re a good sport to respond to my dumb question. Maybe you could record a simple Q&A session with your children where they ask similarly silly questions for fun. 🙂
Hope you and all readers here are doing well during these difficult times, I’m hoping to learn General Relativity properly over the next week or so, since I only learnt how to answer the exam questions at university all those years ago
Comment #282 March 24th, 2020 at 5:28 pm
TobiasM #127:
If George Washington became King in 1789 and his family ruled ever since, wold this be better than the current situation and Trump? The King could decide what the people needs without caring for stupid voters.
That’s too enormous of a historical hypothetical to answer, for reasons of the butterfly effect. A few thoughts, though:
On the one hand, if we could bring George Washington back from the dead, it seems obvious that he’d be a vastly better president than our current one—assuming we could modernize Washington’s views on a few minor issues such as slavery. (Although Washington would no doubt be startled that these space-age beings from hundreds of years in the future were asking him, a farmer and musketeer, for his guidance.)
On the other hand, while democracy is a profoundly flawed system, the track record of monarchy is not spotless either, to put it mildly. One of the few things even more horrible than Trump is someone with Trump’s disposition and zero democratic institutions to restrain him—and there’s no reason think that Washington’s descendants k times removed, sharing only a 1/2k fraction of Washington’s genes, couldn’t be like that (indeed, even for tiny values like k=1 or k=2—there’s plenty of precedent there).
More fundamentally, Washington stands to this day as a symbol of civic virtue in large part because he became president only with great reluctance, then left after two terms to go back to his farm. In a world where he’d agree to become a king, in a certain sense he’d no longer be Washington.
Comment #283 March 24th, 2020 at 5:34 pm
Anthony #128:
what’ the big question that you’d love to solve? Not talking about P vs NP here, but rather something more realistic
(1) How to do NISQ quantum supremacy where you can efficiently verify the answer
(2) Oracle separation between QMA and QCMA
(3) Whether QMA(2) is contained in EXP
(4) Aaronson-Ambainis Conjecture
(5) Quantum copy-protection of arbitrary functions under cryptographic assumptions
Comment #284 March 24th, 2020 at 5:39 pm
barbara #130:
My question: at the end of the intro you write “Here’s hoping that, in 2020, this book will be as badly in need of revision as the 2006 ecture notes were in 2013.”
-> do you plan a revision? I would be eager for buying it.
No, I have no plans at this time to do a revision of QCSD. I do, however, have plans to do something even more exciting: a brand-new, truly popular-level book about exponentials and infinity and information and complexity and quantum mechanics and more, fully illustrated! (Which actually directly relates to the suggestion of Deepa #135.)
Comment #285 March 24th, 2020 at 5:40 pm
And that’s all, folks—after a full week, I believe I’ve finally gotten to the end of the queue!
Thanks for the questions everyone—I hope at least some of you found it interesting.
I’ll leave the thread open for a little while longer just in case someone wants to comment on one of the answers.
Comment #286 March 24th, 2020 at 5:53 pm
Scott #283: thanks for sharing!
Comment #287 March 24th, 2020 at 7:32 pm
This was fascinating, Scott! Thank you so much. I eagerly await your next book!
Comment #288 March 24th, 2020 at 8:35 pm
@Scott #241:
“I think diversity is a value worth pursuing, even over and above intellectual excellence, which already produces many kinds of diversity when you optimize for it alone.”
Why is diversity of gender/skin colour/ethnic origin worth pursuing over and above intellectual excellence when hiring someone to do research and to teach the next generation of scientists? I’m genuinely curious what benefit you think this particular type of diversity (which is apparently optimized for in diversity statements) provides that is worth the trade off with respect to intellectual excellence in this context.
Comment #289 March 25th, 2020 at 12:15 am
some girl #288: Honestly? If we want society to continue to support academic research—something that’s not at all a given—then it helps if as many segments of society as possible feel a shared stake in the enterprise. And if we want them to feel such a stake, then it helps if they have meaningful opportunities to participate. And so to whatever extent we can improve along that dimension with little or no harm to intellectual excellence, it seems to me that we should.
Note that this view would also militate in favor of looking for more opportunities for, e.g., poor white boys from West Virginia or the Bible Belt to join the academic enterprise. I embrace that implication.
On the other hand, I firmly oppose mandatory social-justice statements used to pre-screen faculty applicants, precisely because you can’t have such things without seriously harming intellectual excellence.
I hope you understand that the above views put me well to the right in contemporary academia—indeed, I expect to be (re-)denounced on social media when and if the relevant folks find this thread—even while they put me well to the left among the broader US public. But that’s a position that I’m used to occupying by now! 🙂
Comment #290 March 25th, 2020 at 4:41 am
Scott#289:
“Note that this view would also militate in favor of looking for more opportunities for, e.g., poor white boys from West Virginia or the Bible Belt to join the academic enterprise. I embrace that implication.”
From the utilitarian viewpoint “society to continue to support academic research”, why not use “poverty” as the sole surrogate for identifying and correcting under-representation instead of diversity?
i.e. If we adopted a policy like that how different would that be at correcting under-representation? Are there significant non-poor cohorts that are underrepresented?
Comment #291 March 25th, 2020 at 5:06 am
Scott #284 – do you think it *does* need a revision? I’ve just started reading it, but from a cursory glance the only thing that seems wildly out of date is MIP* = RE vs MIP* \subseteq NEXP as is in the book! But I am basing this off the introduction as opposed to the later sections…
Comment #292 March 25th, 2020 at 7:44 am
#232: Quantum discord could be useful for noisy versions of the tasks you mentioned, Scott – quantum teleportation, superdense coding and essentially all unidirectional, bipartite, memoryless quantum communication [1]. Unfortunately, it is NP-complete to compute [2].
[1] V Madhok, A Datta – International Journal of Modern Physics B, 2013
[2] Yichen Huang 2014 New J. Phys. 16 033027
Comment #293 March 25th, 2020 at 9:33 am
Rahul #290: I’m not sure. But I’m certainly open to the possibility that there are ways certain groups of people’s lives can suck, in systematic ways, that are completely orthogonal to being poor.
Comment #294 March 25th, 2020 at 9:42 am
Eric #291: I mean, I think it could benefit from an update, but it wouldn’t change anything in any deep way—it would just (1) fix various errata and (2) add comments about various things that were discovered in the past 7 years (such as MIP*, BQP vs. PH, Urmila Mahadev’s protocol, complexity growth in AdS/CFT…).
Comment #295 March 25th, 2020 at 10:50 am
Scott:
Back to the Covid topic; quick comment: Originally (now – 15 days), I was one of those thinking these lockdowns are a overreaction; covid will not be so bad etc. Your posts were the wake up call. Thanks for that! Coming from a person like you they were credible and forced me to analyse deeper and I reached the same conclusions as you: Drastic actions like lockdowns were needed.
However, I am sitting in India and now the country is in a complete lockdown. Now I am having second thoughts. Will the disruption in the essentials supply system and resultant incidental potential casualties (due to starvation, civil unrest etc.) be worse? I think this needs very careful analysis.
Have you given this closer thought? Is such a drastic lockdown just a knee-jerk reaction in hindsight? Are we taking this too far? Is the solution worse than the problem?
I don’t have the answers, but just wondering what you (and others on the blog) think?
Comment #296 March 25th, 2020 at 12:29 pm
Rahul #295
> However, I am sitting in India and now the country is in a complete lockdown.
Is the lockdown really complete ?
I find it hard to believe that any nation could survive for long with a complete shutdown of the economy. Somebody has to keep power plants running, water distribution systems operating, food production and shipping going or everyone who isn’t a farmer with their own offgrid solar array is going to be be in serious trouble very quickly.
Here in New York there is a detailed list of “essential” businesses that are exempt from the shutdown. The set of businesses considered essential is quite extensive. For example I know of an IT equipment supplier that is considered essential because they supply products to healthcare related and other essential businesses. I think the shutdown mainly only applies to consumer facing businesses that don’t serve basic needs. I haven’t seen a breakdown but I would suspect that at least 50% of workers in the state are in the essential category.
Given this (and it really couldn’t be done any other way) I wonder if the shutdown will have it’s intended effect. People probably get the majority of their interpersonal exposure at work and if half of them are still working the spread of the virus may be slowed a bit but probably not enough to prevent it from soon reaching just about everyone.
I wouldn’t be surprised if when the history of this event is written the consensus will be that millions of deaths were inevitable once January had passed without action and that the economic consequences of these shutdowns were an “own goal”. That said it does seem like a Kobayashi Maru scenario at this point.
Comment #297 March 25th, 2020 at 3:49 pm
Gerard:
Update from India: Even here there’s exceptions for essential services carved out. But that’s in theory.
It’s all about the quality of systems and governance: In practice, here those exceptions are proving to be incredibly difficult to carve out and enforcement is quite ham handed. Perhaps we just live in a low trust, low initiative society. Looks like that middle ground between life-as-usual and full-lockdown is not easy to achieve in practice.
Come to think about it, to make this work is effectively akin to an overnight transition from a market economy to a command and control system.
The end result is what seems like a full blown lockdown on the ground with access to even essentials proving out to be quite difficult to impossible. We are still at the start, so perhaps systems will improve.
We will see how things go. Can only be positive for now.
Comment #298 March 26th, 2020 at 6:32 am
Rahul,
Regarding “potential casualties due to civil unrest”; when people are restricted from movement the chance of riots evolving would be very much lesser, right? I am no police officer, but I would imagine that before riots people come together, distribute weapons, etc. and then it breaks out.
(Which part of India are you in, if you don’t mind me asking? You mentioned difficulties with essential supplies.)
Comment #299 March 26th, 2020 at 12:03 pm
I’m confused by this article:
https://www.eurekalert.org/pub_releases/2020-03/thni-ebi032420.php
Being the engineer that I am, it seems to me that physics is mistakenly conflating identity with equality. If two particles are identical in every way, they are still distinguishable by virtue of their positions in space. So are they still identical? Or just equal? And did Java forever ruin my ability to understand physics?
Comment #300 March 26th, 2020 at 12:24 pm
Darrell Burgan #299: I haven’t read that article (and have no plans to) but I can answer your question. In QM, two electrons (for example) are indeed distinguished by their position in space and/or their spin state. But they’re “identical” in the sense that if you switch them around, then you get back exactly the same state you had before—in fact, there’s no experiment that can possibly tell you whether the electrons were switched or not, if you weren’t looking and if whoever switched them left no other trace.
Furthermore, and crucially, we know this is true. That is, we know that even in the far future, no properties will be discovered by which the one electron could be distinguished from the other one after all. How do we know that? We know it because one can see quantum interference between paths where the two electrons switch places, and paths where they don’t. And in QM, one never sees interference between paths unless they lead to final states that are literally identical in all respects.
Comment #301 March 26th, 2020 at 1:30 pm
Darrell Burgan #299
I would add that the indistinguishability of fundamental particles is probably among the most important concepts in physics. You get different statistical behavior from particles that are distinguishable (as they were assumed to be in classical physics) versus indistinguishable. There are two kinds of statistics particles can obey in quantum mechanics: Fermi-Ditrac and Bose-Einstein. In the former the wave function is anti-symmetric under exchange of two particles (ie. doing so multiplies it by -1) while in the later it is symmetric. Particles that obey these two types of statistics are called respectively fermions and bosons and both their microscopic macroscopic behaviors are very different. Fermions, for example, as a result of their antisymmetry, obey the Pauli Exclusion principle, which is ultimately responsible for the “solidity” of matter. If particles were distinguishable they would obey a third type of statistics and it has been verified for many years that this is not the case.
As an aside there’s also a relationship between the type of statistics a particle obeys and it’s spin, with fermions having half-integer spins while bosons have integer spins.
Comment #302 March 26th, 2020 at 2:23 pm
Scott #300: “we know that even in the far future, no properties will be discovered by which the one electron could be distinguished from the other one”
I don’t think we actually know this. Sure, we know that the particular electrons in the interference experiments that have been done are identical. But – to pick a random example – we don’t know that electrons produced in Earth’s gravitational field are identical to electrons produced in interstellar space – unless someone has actually done some sort of experiment involving interference between cosmic rays and terrestrial electrons. Sure, there’s no reason to think they aren’t identical, but that’s not the same as knowing for sure that they are.
Comment #303 March 26th, 2020 at 4:36 pm
Radford #302: OK, but even by your standards, we know that the photons arriving from hundreds of millions of light-years away are the same kind as photons on earth, right? Otherwise (e.g.) astronomy based on interferometry wouldn’t work.
Note also that, for the electrons light-years away to be non-identical with electrons here, one would need to revise the Standard Model itself to have multiple electron fields—one with excitations here but not there, and another with excitations there but not here. And it’s very plausible that doing so would lead to predictions that conflict with known observations (if it can’t already be ruled out on theoretical grounds within QFT). Would any physicists like to chime in?
Comment #304 March 26th, 2020 at 5:12 pm
Just noticed that I missed something:
Jonathan Dowling #152:
Do you think Newton had an advantage because he did not have unlimited internet access?
Undoubtedly.
Comment #305 March 26th, 2020 at 5:19 pm
Niche question: could a problem be shown to be BQP-complete under logspace reductions? Assuming P=BPP, then there are such problems for BPP. Actually, maybe even allow completeness under quantum logspace reductions?
Comment #306 March 26th, 2020 at 5:34 pm
Richard #305: Yes. Not only that, but probably most or all of the known BQP-complete promise problems could be shown to be complete under logspace reductions. I don’t know if anyone has cared enough to confirm that, but could be a good student project!
Comment #307 March 26th, 2020 at 11:32 pm
Radford: The idea that there are different electrons is a layperson’s understanding of what Quantum Field Theory tells us. And it tells us, rather clearly, that THERE ARE NO PARTICLES. That’s right, particles are not a fundamental object in quantum physics. It’s all fields, which are themselves excitations of vacuum. Particles are a no-interaction flat-space approximation of the fields. So the question “are the two electrons identical?” does not even make sense in quantum physics, not as stated, anyway. Are two excitations of vacuum identical? Well, the only difference between two excitations are the values they have, such as what field they are excitations of, their position, momentum, spin direction… There is nothing “intrinsic” to these excitations that we call particles, like “identity”. it’s all a bunch of numbers and nothing else.
Similarly, there is no “wave/particle duality”. Waves and particles are just the familiar macroscopic ideas, and the field excitations can sometimes be measured as waves or particles, if the experimental setup is configured a certain way.
Comment #308 March 26th, 2020 at 11:56 pm
Scott #300: thanks! A little pseudo Java code, then:
public class Particle {
. . . private int spin;
. . . private int someOtherProperty;
. . . private SpatialPosition position;
. . . public Particle(int spin, int someOtherProperty, SpatialPosition position) {
. . . . . . this.spin= spin;
. . . . . . this.someOtherProperty= someOtherProperty;
. . . . . . this.position = position;
. . . }
. . . // typical definition of hashcode() and equals() goes here
. . . // considers spin and someOtherProperty but does NOT consider position
}
public class DoIGetThisRight {
. . . public void hmmm() {
. . . . . . SpatialPosition position1 = (somewhere);
. . . . . . SpatialPosition position1 = (somewhere else);
. . . . . . Particle p1 = new Particle(1, 2, position1);
. . . . . . Particle p2 = new Particle(1, 2, position2);
. . . . . . // equality tests – note that the position has no bearing on equality
. . . . . . // my sense is this is similar to what physics is calling “identity”
. . . . . . assertTrue(p1.equals(p2));
. . . . . . assertTrue(p2.equals(p1));
. . . . . . // identity tests – my sense is this is what we mean when we say
. . . . . . // two particles are equal but not identical
. . . . . . assertFalse(p1 == p2);
. . . . . . assertTrue(p1 == p1);
. . . . . . assertTrue(p2 == p2);
. . . }
}
Comment #309 March 27th, 2020 at 12:23 am
Darrell Burgan:
I’d say the most fundamental mistake you’re making is imagining that the universe is made of objects — things with identity, history, position, etc. But almost certainly the universe is not, at a fundamental level, made of such things, that respect our intuititions about ojbects If we trust QFT — which cannot be a complete picture of reality, but let’s go with it for now — then it’s made of a dozen or so fields, and particles are just certain patterns within those fields. So any notion of identity simply makes no sense. Again, QFT is not the final answer here, but I think we should expect that the correct theory of everything will necessarily also have this property, that the most fundamental things in the universe will not match our intuitions about objects.
Comment #310 March 27th, 2020 at 5:46 am
Intriguing long-answer on ‘It from Qubit’ (#248)
I was sceptical, and was all set to dismiss the program, but now suddenly the idea has roared back in a big way for me!
I realized in the end that if one wants to grant objective reality to both mathematical and physical objects, and if one wants to avoid dualism, then taking reality to be information seemed to be the only way to do this. I’ve reached a conclusion.
What is reality ? My answer is that it’s a 3-sphere of information (Qubits). But this is *not* a physical space. It’s more general. It’s a *conceptual* space, as I outlined in post #198. My 3 dimensions of the conceptual hyper-sphere should not be confused with physical dimensions – it just so happens that I think that there are 3 different dimensions of abstraction. So this is not physical space, but rather, physical space is embedded (or encoded) within this.
I believe I know what physical and mathematical objects really are, as well as resolving the nature of cognition. I think these are simply different *views* of the information in the hyper-sphere. Physics is the low-level view of ‘information’ where you’ve zoomed into the conceptual landscape, mathematics is the high-level view of ‘information’, where you’ve zoomed out of the conceptual landspace. And cognition is the mapping language between the 2 views (which is itself also embedded in the hypersphere)
I think we’ll all be hearing much more about ‘It From Qubit’ in the years ahead. Many books could definitely be written exploring ideas along these lines!
Comment #311 March 27th, 2020 at 7:59 am
Radford #302, Scott #303: Not a physicist, but I’ll pitch in. The Pauli exclusion principle depends on the interference effect between different electrons. If there were more than one type of electron, each atomic orbital would be able to hold at least four electrons rather than just two. This drastically changes the chemical properties of the element, and makes the lowest energy state lower than it would be with only one type of electron. If an object made out of electron-A were to collide with an object made out of electron-B, the electrons would flood from one object to the other to equalize the types of electrons in each object, probably making a big explosion. Now we can make the same sort of argument as when people argue that there aren’t any antimatter planets or antimatter galaxies: There’s no evidence for this explosive interaction, or of the new form of atomic matter that would arise from multiple electron types, anywhere in the solar system or the universe. That said, unlike in the case of antimatter galaxies, I don’t know if anyone’s looking.
Comment #312 March 27th, 2020 at 11:00 am
#308 Darrell Burgan:
You’d do much better by defining a series of multi-dimensional arrays, one for each fundamental particle (or rather: fundamental field), with functions to calculate successor states of those arrays, with some accessors to return the “particles” that can be interpreted from a given region for backwards compatibility with legacy apis.
Comment #313 March 27th, 2020 at 11:05 am
Darrell Burgan #308:
Your Java code analogy won’t work (object reference vs instance). You know how we can write 4, 2+2 2^2 and they all refer to the same object? You can distinguish them by your notation but once you evaluate them on a calculator it’s just 4. Now, the amazing thing about nature is that the observation is such a calculator. Pure magic. You can track different objects with same values in Java by some internal id in the memory allocator but not in real life. And NOT because you don’t have access to that internal id field, but because such an id doesn’t exist and the whole concept of a classical object whose identity you can track through space and time is an illusion.
Comment #314 March 27th, 2020 at 1:13 pm
Scott #211: Thanks for the reply (to the question regarding grad school “arms race”). I’m afraid I don’t have a “better” way to do it. If only someone implemented a stable matching algorithm for grad school applicants and grad schools…
I do have another question though: what should a TCS PhD student in, say, India (at a place like TIFR), do to increase their chances of producing world-class research output and having a successful research career? What *is* a successful research career?
Comment #315 March 27th, 2020 at 1:34 pm
Shmi #307: It’s all very well to say that “Are all electrons identical?” is not a well-formed question from the advanced standpoint of QFT, but this doesn’t resolve the question of whether or not in an actual experiment one would see interference between an electron produced in Earth’s gravitational field (say, by some pair production process) and an electron that was produced in the weaker gravitational field of interstellar space (to take one example of different situations that could conceivably produce different “kinds” of electrons).
Itai #311: Yes, the failure to observe such phenomena is certainly a reason to think that there are not different kinds of electrons in (say) different galaxies. But that’s sort of my point – you need to actually look for this, not just say that you’ve already established that they’re all identical. (Well, you don’t really have to look for this, if you think other avenues of research are a lot more promising, but if you’re wondering about it…)
Also, I suspect that one could modify the Pauli Exclusion principle if necessary. It’s sort of like the “proofs” that special relativity shows that faster-than-light communication is impossible, which just assume that the any new phenomenon allowing FTL communication must satisfy the principle of relativity, when of course we only have evidence that presently-known phenomena satisfy this principle, not as-yet-undiscovered phenomena.
Comment #316 March 27th, 2020 at 2:09 pm
Scott #273:
Blum’s theorem does prove such a problem exists, but AFAICT the problem constructed in the proof is very contrived. I am curious to know whether there is a *natural* problem with this property. It’s like, Ladner’s theorem says that if P=\=NP then NPI is non-empty, but it would still be interesting to have natural examples like graph isomorphism (ofc we only suspect graph isomorphism is in NPI). Of course, “natural” is not formally defined but IMO the question is still interesting.
Comment #317 March 27th, 2020 at 2:34 pm
Vanessa #316: There might be natural examples, but I don’t think any are known.
Comment #318 March 27th, 2020 at 3:04 pm
Radford Neal #315
“It’s sort of like the “proofs” that special relativity shows that faster-than-light communication is impossible, which just assume that the any new phenomenon allowing FTL communication must satisfy the principle of relativity, when of course we only have evidence that presently-known phenomena satisfy this principle, not as-yet-undiscovered phenomena.”
The problem with FTL communication is much deeper than that.
One of the assumptions underlying all of physics is the principle of causality. We consider causal relationships between events to be absolute. If event A is seen as the cause of event B by one observer then the same will be true for all observers.
If there exists a phenomenon allowing FTL communication then it is possible for two events separated by a spacelike interval to be causally related. However the temporal relationship between those events (ie. whether A occurs before B or vice versa) depends on the reference frame of the observer.
Now it could be that the principle of causality is wrong, but that would profoundly alter our understanding of physics and of reality itself, it would be far more than just discovering some new phenomenon.
Comment #319 March 27th, 2020 at 3:19 pm
Scott #317: Btw, I had the impression that matrix multiplication might be like this, only for weaker speedup. That is, it might be that for every alpha > 2 there is an algorithm with complexity O(n^alpha) but there is no algorithm of complexity O(n^2). Is that really a likely possibility or am I confused?
Comment #320 March 27th, 2020 at 3:31 pm
Radford #315: I think what the other commenters were trying to be get at is that, while the idea that some electrons are distinguishable can’t be logically refuted, QM and QFT let us push the idea firmly into realm of “off-base enough so as not to deserve further thought.” An analogy would be the guy who thinks there are little men moving around behind his TV screen, so then a friend explains fiber-optic cables, LCD displays, etc. etc., and the guy says he understands all that but still there must be at least a few little men behind the screen? The point is that, after you’ve learned that all electrons are just excitations in a fermionic field, saying “but still they might be distinguishable…” is a speculation of a similar character.
Comment #321 March 27th, 2020 at 7:17 pm
Gerard #318: The arguments that FTL communication would violate causality assume that the means of FTL communication obey the principle of relativity – so that if you can (say) communicate instantly in one reference frame, then you can communicate instantly in any other reference frame as well, since whatever phenomenon allows instant communication obeys the principle of relativity. But the argument fails to rule out a means of communicating that is instant in one particular reference frame. (The speed of communication in other reference frames differing in velocity could be worked out from this, and wouldn’t be instant.)
I have little hope (fear?) that FTL communication is possible, but neither do I think it’s completely implausible. After all, there is an obvious universal reference frame around – that of the cosmic microwave background radiation.
Comment #322 March 27th, 2020 at 11:28 pm
The paucity of testing has left us with a muddled idea of the number of infected. But can we assume that more tests would give a simple scale factor to the estimate of infections. In this way, can we trust estimates of the growth of infections?
Comment #323 March 28th, 2020 at 8:27 pm
Vanessa #319: Your speculation about the complexity of matrix multiplication is widely accepted as a plausible conjecture. It would be true if the exact complexity of matrix multiplication was Theta(n^2 log(n)), for instance, but it currently seems plausible that the complexity is not O(n^2 log(n)^k) for any fixed k, but is O(n^(2+epsilon)) for every epsilon > 0.
Comment #324 March 29th, 2020 at 11:31 am
Scott,
Can I request you to post more vigorously during this crisis? You are a very smart guy and lots of very smart people frequent this blog.
I think the solutions are going to come from some very out of the box thinking applied to this problem.
At the same time, the dunning Kruger effect means that the smartest of us, the ones most likely to come up with some smart idea, are the least likely to think that we will be of any use.
Hence I think we really need you to make more posts. The covid mitigation strategies are going to need all sorts of smart ideas and not just medical or virology ones. I suspect that going ahead bigger inputs will be needed about logistics and supply chains and people trAcking all of which could squarely fall within the expertise area of the people on thia blog.
Hence a humble request to start blogging and posting agressively. I know how hard it can be in these times. But I sincerely feel that some smart ideas may really come from readers of blogs like this one.
Comment #325 March 29th, 2020 at 9:10 pm
If a virus is composed of protein and nucleic acid (DNA/RNA), it is not alive. Therefore, it cannot be killed. Of what good, then, are sanitizers, disinfectants, or fumigation? Viruses mutate. Hand washing will physically brush it off of the skin, but will not kill it. It may be the case that we must helplessly wait until it changes form and thereby cannot hook onto lung cells.
Comment #326 March 30th, 2020 at 3:37 am
Hans Wurst #325:
This is seriously stupid. You are trying to make an argument about reality based on definitions of words. The words used to describe it do not matter! It doesn’t matter whether a virus is “alive” according to someone’s definition. It doesn’t matter whether you call it “killed” or insist on calling it “inactivated” or something else. The fact is that the novel coronavirus, like most other viruses, can have its structure disrupted, in a way that renders it permanently harmless, by the application of many common sanitizers such as alcohol, chlorine bleach, or hydrogen peroxide. Moreover, soap has the same effect on it, as is the case for a number of other viruses as well. There is no means by which one can validly conclude that this is not so because a virus is not “alive”!
If one expands out your argument, gets rid of such terms as “alive” and “kill”, this becomes obvious. The reason viruses are often considered not to be “alive” is because they do not metabolize. “It doesn’t metabolize, therefore sanitizer is useless against it” — that doesn’t follow! And, in this case, it’s wrong.
I feel like I’m basically obligated here to suggest you read Eliezer Yudkowsky’s 37 Ways that Words Can Be Wrong.
Comment #327 March 30th, 2020 at 11:23 am
Hans #325
“it is not alive. Therefore, it cannot be killed.”
Same with my toaster!
Comment #328 March 30th, 2020 at 11:25 am
Fresh research on how long ppl can transmit corona after their symptoms disappear
https://www.sciencedaily.com/releases/2020/03/200327091234.htm
Comment #329 April 1st, 2020 at 3:25 pm
I’m with Radford Neal.
Scott, you introduced an extreme question of “even in the far future, no properties will be discovered,” but then you backed off to what current theory says. The double slit experiment is very powerful and it greatly restricts any possible future theory. But there is a limit to what it says, which RN correctly identifies.
Comment #330 April 2nd, 2020 at 5:50 pm
scott #201:
“what would I do if I were a PR man for chemistry, with a mandate to get more of the most intellectually curious people into the field? ”
while any field can always use more, there are already plenty of intellectually curious people in chemistry; certainly as many as there are in theoretical physics or computer science. the disparaging attitude that chemistry is ‘merely’ applied physics is held only by those with no knowledge or understanding of chemistry (eg., Dirac) and who think that ‘pure’ is ‘deeper ‘than ‘applied’. that attitude is of course, nonsense.
Comment #331 April 8th, 2020 at 6:33 am
[…] last bits are from Scott Aaronson’s answers in his post “AMA: Apocalypse Edition“: here are his thoughts on the It from Qubit idea in fundamental physics (the whole spacetime […]
Comment #332 April 17th, 2020 at 4:23 am
Hi Scott,
Tang’s quantum-inspired recommendation algorithm, can this now be implemented on a classical computer and outperform classical standards ? If not, why not ?