My Tomassoni-Chisesi Prize talk
Update (Sep. 21) Video of Philip Kim’s and my talks is now available! (But not streaming, just a giant mp4 that you can download.)
On Thursday, I had the incredible honor of accepting the 2018 Tomassoni-Chisesi Prize in Physics at Università “La Sapienza” in Rome—“incredible” mostly because I’m of course not a physicist. (I kept worrying they’d revoke the award when they realized I could barely solve the wave equation.) This is not the first time quantum information was recognized; the prize has previously gone to Serge Haroche and Alain Aspect. This year, for the first time, there was both an under-40 and an over-40 award; the latter went to Philip Kim, a quantum materials researcher at Harvard who I had the privilege to meet on this trip (he’s the taller one below).
I’m unbelievably grateful, not only to the committee, and its chair Giorgio Parisi (whose seminal work on phase transitions and satisfiability I’d long known, but who I met for the first time on this trip), but to Fabio Sciarrino, Paolo Mataloni, Fernanda Lupinacci, and everyone else who graciously hosted me and helped make my hastily-planned visit to Europe a success.
The department I visited has a storied history: here are the notes that Enrico Fermi left, documenting what he covered each day in his physics class in 1938. The reason the last squares are blank is that, when Fermi and his Jewish wife left for Stockholm on the occasion of Fermi’s Nobel Prize, they continued directly to the US rather than return to an Italy that had just passed the racial laws.
On my way to Rome, I also gave two talks at a “quantum computing hackathon” in Zurich, called QuID (Quantum Information for Developers). Thanks so much to Lidia del Rio for arranging that visit, which was fantastic as well.
To accept the Tomassoni-Chisesi prize, I had to give a 40-minute talk summarizing all my research from 2000 to the present—the hardest part being that I had to do it while wearing a suit, and sweating at least half my body weight. (I also had a cold and a hacking cough.) I think there will eventually be video of my and Prof. Kim’s talks, but it’s not yet available. In the meantime, for those who are interested, here are my PowerPoint slides, and here’s the title and abstract:
Three Questions About Quantum Computing
Scott Aaronson (University of Texas at Austin)
I’ll discuss some of my work in quantum computing over the past 18 years, organizing it in terms of three questions. First, how can we demonstrate, using near-future hardware, that quantum computers can get any genuine speedups at all over classical computers (ideally useful speedups)? Second, what sorts of problems would be hard even for quantum computers, and can we turn the intractability of those problems to our advantage? Third, are there physically reasonable models of computation even more powerful than quantum computing, or does quantum computing represent an ultimate limit?
If you’re a regular reader here, most of the content will be stuff you’ve seen before, with the exception of a story or two like the following:
Last night I was talking to my mom about my grandfather, who as it happens came through Rome 73 years ago, as an engineer with the US Army. Disabling landmines was, ironically, one of the safer ways to be a Jew in Europe at that time. If you’d told him then that, three-quarters of a century later, his grandson would be back here in Rome to accept an award for research in quantum computational complexity … well, I’m sure he’d have any number of questions about it. But one thing I clearly remember is that my grandfather was always full of effusive praise for the warmth of the people he met in Italy—how, for example, Italian farmers would share food with the hungry and inadequately-provisioned Allied soldiers, despite supposedly being on the opposing side. Today, every time I’m in Italy for a conference or a talk, I get to experience that warmth myself, and certainly the food part.
(Awww! But I meant it. Italians are super-warm.)
There’s a view that scientists should just pursue the truth and be serenely unaffected by prizes, recognition, and other baubles. I think that view has a great deal to be said for it. But thinking it over recently, I struck the following mental bargain: if I’m going to get depressed on a semi-regular basis by people attacking me online—and experience shows that I will—well then, I also get to enjoy whatever’s the opposite of that with a clear conscience. It’s not arrogance or self-importance; it’s just trying to balance things out a bit!
So again, thanks so much—to the physics department of La Sapienza, but also to my family, friends, mentors, readers, colleagues at UT Austin and around the world, and everyone else who helps make possible whatever it is that I do.
Follow
Comment #1 September 15th, 2018 at 8:26 am
“But one thing I clearly remember is that my grandfather was always full of effusive praise for the warmth of the people he met in Italy—how, for example, Italian farmers would share food with the hungry and inadequately-provisioned Allied soldiers, despite supposedly being on the opposing side.”
This has to do with the particular circumstances of the Italian War. By July 1943, when the Allies invaded Sicily, the Italian public was tired of the war and tired of Mussolini. He was deposed and the new government tried to make peace with the Allies but the Germans occupied the majority of Italy and installed Mussolini as the head of a puppet state. (The new government continued to function in the south.) So many Italians viewed the Germans as occupiers and the Allies as liberators.
Comment #2 September 15th, 2018 at 8:41 am
Maybe they created the under-40 category to remind you that it’s not too late to become a physicist.
Comment #3 September 15th, 2018 at 10:13 am
The image by “here are the notes” isn’t working
Comment #4 September 15th, 2018 at 11:18 am
Way to go Scott, congratulations, you’re on your way to getting the Nobel Prize in Physics 🙂 But with your luck, on your return flight from Stockholm after getting your Nobel, you get arrested and handcuffed at the airport for impersonating a theoretical computer scientist 🙂
Comment #5 September 15th, 2018 at 11:40 am
avi #3: Working for me. Others?
Comment #6 September 15th, 2018 at 11:54 am
Michael #1: Thanks for the interesting historical context!
The other thing I know, of course, is that Italy managed to save half its Jews from extermination—not nearly enough, and not as impressive as Denmark, but a hell of a lot better than most of Nazi-occupied Europe. According to Hannah Arendt, the Italians’ main tactic was just to keep buying time, giving the increasingly-enraged Germans elaborate excuses for why they hadn’t yet rounded up this or that Jewish community but would surely get around to it next week.
My grandfather said that he met some of the Jews who were being hidden in the Vatican (but also that the American soldiers at the front, even the Jewish ones, had no idea of the scale of the Holocaust until close to the end of the war). He said that, in Italy, as the war was ending, he met Jewish resistance fighters who were headed to Israel, or what would soon become Israel. They urged my grandfather to join them, since the new state formed from the surviving remnant of Jews would need every experienced soldier it could get. My grandfather considered the offer but decided to return to his former life in Philadelphia, and shortly thereafter got married and started a family. He was done fighting.
Comment #7 September 15th, 2018 at 11:56 am
William Hird #4: Don’t you mean impersonating a physicist? 🙂
Comment #8 September 15th, 2018 at 1:51 pm
The “here are the notes” image isn’t working for me either. Great post, and congrats!
Comment #9 September 15th, 2018 at 1:59 pm
@Scott #7:
It’s a funnier joke (IMHO) my way because with the prestige the Nobel in physics gives you, the cops can only bust for trying to go back to your “old job” as a TCS. 🙂
Comment #10 September 15th, 2018 at 2:51 pm
Congratulations, Scott! This is wonderful news. I first got into physics (my background is mathematical logic/philosophy) through your interdisciplinary work with people like Lenny Susskind and I have loved watching the story unfold since the first responses to AMPS started. I am very inspired by the way the quantum information community has been coming together as a collective whole, slowly been developing away from physicists and computer scientists to quantum information scientists that genuinely are interdisciplinary. I think both from the sociological implications for academia as well as just the scientific implications, having more tools and the better ability to understand problems in a new light, what is happening is very, very good. So, I am glad that you have been recognized as a major contributor to the knowledge and progress on these topics.
P.S. are you planning any sort of AMA any time soon? I have a question that is theoretical computer science-y (non technical, in the sense that it more or less asks for your opinion on something) but I doubt it’ll ever be completely relevant to a post you make.
Comment #11 September 15th, 2018 at 3:23 pm
Peter #10: Thanks! Definitely no AMAs till after November 2 (the STOC deadline). 🙂 But go ahead, special for you, ask your question here.
Comment #12 September 15th, 2018 at 4:54 pm
Scott #11: Ah, right, I completely forgot about that post you made, sorry!
So my question I guess can be stated generally as: do you think that concepts from higher computability theory (admissible set theory, study of the Turing degrees in general) and descriptive set theory can have any sort of impact on every day computer science, something that your average software engineer or hardware engineer might care about?
To motivate my question I’d like to contrast it with computational complexity. Coming to computability theory as a logician, I always viewed the central ideas of computability as something like “we study the structure of subsets of the natural numbers”. The Turing degrees let us talk about a hierarchy of increasingly complex subsets of natural numbers, Post’s theorem lets us describe that hierarchy via the complexity of the formulae in the language of arithmetic that represent those sets, and the concept of oracles lets us generalize the idea of “definable with parameters from a given set” to “computible with parameters from a given set” and lets us move through that hierarchy while still retaining the main formalism of computability.
But of course, oracles also let us talk about much more practical questions when we talk about computational complexity. It seems pretty obvious that a computer engineer would care about something like the polynomial hierarchy, or at least they would care more about the fate of that hierarchy than they would probably care about the analytic hierarchy and the complexity of Borel sets, for instance. And it seems obvious why it is the case that they’d care about computational complexity at least a little bit, even if we are talking about EXP for example, that is still within the bounds of computable functions and oracles only serve to speed up the computation, not to allow an entirely new class of subsets of natural numbers to be computed. And additionally, problems in EXP and of course NP as well come up all the time in their work (although to be fair, the halting problem comes up as well, they just know they can’t write an algorithm for it).
So again just to restate my question, is there any aspect of the more esoteric regions of higher recursion theory that you think could be useful to an every day computer engineer to be familiar with, or that they might actually care about just in general? Is there any particular area of that section of the field that you think might result in some sort of big change in the general way engineers go about their business if it became widely known? Or do you think that region of the field is so divorced from practical questions than anything outside of “we found something that violates the Church-Turing thesis” would never reach anyone who uses applied computer science in an every day setting?
Your recent paper “PDQP/qpoly = ALL”, I believe, comes close to a positive answer, in the sense that I believe results like this might interest every day programmers but probably wouldn’t change how they operate at all. Maybe there is something in applied cryptography that would care when the discussion of computation with an oracle comes up? Of course it does when computational complexity type oracles come up and I guess Turing degree oracles are too impractical (impossible) to make a difference to an engineer.
I know it’s hard enough to teach CS undergrads just the basics of computability theory when they’re focused on becoming applied engineers (at least that’s what I’ve heard my software engineer friend’s say when I talk to them about their experience in those classes, haha) , so I don’t really have high hopes for descriptive set theory to creepy into any sort of curriculum, haha, but I think that it’s an area that doesn’t get as much interfacing with the applied community as it should. Even the results about computing sets of reals that I’m aware of come from logicians or theoretical computer scientists like the late Feferman who are motivated by questions of predicativity or similar concepts, although I’m sure I believe that those are not the only people working on those issues.
Comment #13 September 15th, 2018 at 4:56 pm
Scott #5:
Broken here too. It appears to be behind some Google thing.
Comment #14 September 15th, 2018 at 5:30 pm
Peter #12: Computability theory has long been a source of inspiration for real-world software developers: LISP was born as an instantiation of lambda calculus; programming books like Structure and Interpretation of Computer Programs are shot through with computability, etc. Having said that, it’s surely quite rare that higher computability is directly relevant to real-world programming, beyond the level of inspiration. After all, as you pointed out, complexity theory is “closer to earth,” but even it is rarely used in that way, outside of crypto and maybe one or two other domains. If there are programmers who use higher computability theory on a day-to-day basis, then they’re surely the same ones who also go on and on about type theory and categories and formal verification and all those other things that I’ve never really grokked. So probably the real answer to your question is that you should ask one of them!
Comment #15 September 15th, 2018 at 5:31 pm
Sniffnoy #13: OK, I’ll look into it after my plane lands in Austin.
Comment #16 September 15th, 2018 at 6:10 pm
(gasp) When I pasted in the image, it retained a URL involving my private email account! That seems really, really stupid of WordPress—especially since it creates a problem that’s invisible to the blog’s owner, giving a false impression that everything’s OK. By default, why doesn’t it put a local copy of any pasted image into your WordPress directory? In any case, should be fixed now.
Comment #17 September 16th, 2018 at 10:33 am
Congratulations, Scott! Your prize is well earned and I’m glad to see that the prize committee took an inclusive view regarding the scope of physics research. It’s better to focus on quality than on disciplinary boundaries.
Comment #18 September 16th, 2018 at 11:28 pm
[…] Aaronson recently won the Tomassoni-Chisesi Prize in Physics (yeah Scott!). In his post (here) about it he makes a passing […]
Comment #19 September 17th, 2018 at 1:16 am
[…] Aaronson recently won the Tomassoni-Chisesi Prize in Physics (yeah Scott!). In his post (here) about it he makes a passing […]
Comment #20 September 18th, 2018 at 9:46 pm
Congratulations, Scott!
Happy you weren’t arrested!
Comment #21 September 18th, 2018 at 11:56 pm
#12 and #14
What about functional programming Scott, where programming is treated as ‘the evaluation of mathematical functions’? Seems like a pretty practical application of computability?
I’ve come up with a new definition of cognition. And I have a way to relate this definition to mathematics and computer science. Here’s my definition:
‘Cognition is the integration of two different modes of modeling , where abstract (high-level) and concrete (low-level) models are combined in order to generate procedural knowledge for achieving goals’
So I think at the fundamental root of a mind in the most general sense (Cognition), there’s 3 different modes of thought – abstract models (let us call this ‘Far’ mode), concrete models (let us call this ‘Near’ mode), and practical ‘how-to’ algorithms (let us call this ‘Procedural’ mode).
Near, Far and Procedural.
And then my ‘Interpretation’ for connecting (mapping) math to cog-sci is that any given domain of mathematics can be decomposed into these 3 categories, by ‘re-interpreting’ the given domain as ‘modes of cognition’. These modes of cognition are ‘levels of modeling abstraction’.
Now lets look at Computability based on the’ Geddes Interpretation’ 😀
As I suggested in previous post, there seems to be a ladder of abstraction, where I can indeed split the field of computational logic into 3 levels. This is speculative (because frankly, I really doubt that *anyone* really groks what all this type theory/categories/verification business is about yet), but the ordering below seems intuitively very plausible:
Near Mode – Modal Logic
Procedural Mode – Functional Programming (and Type Theory?)
Far Mode – Formal Language Theory
So the idea is that the practical ‘how to’ stuff of functional programming (procedural mode) is somehow generated by integrating or *balancing* two dual theoretical models (near and far modes), which I’m guessing to be modal logic+formal language theory.
A neat way of looking at this is that there’s an ultimate aesthetic meta-principle of the ‘Golden Mean’, where all cognition is about trying to balance two opposites (a generalization of the mathematical notion of ‘duality’ perhaps?)
Then I can think of the 3 sub-fields above as a ‘see-saw’ with ‘Formal Language Theory’ at one end, and the opposite or dual ( ‘Modal Logic’ ) at the other end. And then ‘Functional Programming’ can be interpreted as the balancing of the two ends (‘the golden mean’).
See recent Scott Alexander story ‘In The Balance’, which is actually a good metaphor for what I’m proposing:
http://slatestarcodex.com/2018/09/12/in-the-balance/
So I’m making the big bold claim that all cognition is Near modes, Far modes and the ‘golden mean’ (balance) between them (Procedural Modes)!
If I’m right, then functional programming (and type theory) are somehow reducible to modal logic, as well as formal grammars.
A bit of quick research using Goggle does indeed unearth some previous attempts to create ‘Modal Type Theories’.
Comment #22 September 19th, 2018 at 10:45 am
the actual article
https://www.nature.com/articles/s41467-018-05739-8
Comment #23 September 19th, 2018 at 1:18 pm
fred #21: I had a long discussion with Renato (as well as John Preskill) about this work a couple months ago, when we all lectured at UC Boulder. To make a long story short: I find this “new paradox” interesting, but would absolutely not describe it using the language Renato does (“quantum theory can’t consistently describe the use of itself”). In some sense, the new paradox just amounts to the “Wigner’s-friendification” of Hardy’s paradox. That is, it’s precisely what you get by munging together those two previous paradoxes, and promoting the qubits or particles in Hardy’s paradox to two Wigner’s-friend-like conscious brains that happen to be in an entangled superposition state.
In my interpretation, the paradox then gets all its mileage by reasoning about what one Wigner’s friend is certain that another Wigner’s friend is certain of, etc., but with these certainties applying to a world where the Wigner’s friends are not measured in strange bases (e.g., |Thought1⟩+|Thought2⟩, |Thought1⟩-|Thought2⟩)—even though, in order to produce the paradox, the Wigner’s friends do have to be measured in strange bases. But I don’t regard that as legitimate (“unperformed measurements have no results”)! So for me, anyway, the argument falls apart, not because of any of the assumptions that Frauchinger and Renner explicitly enumerate, but because of a background assumption that they barely even mention.
Comment #24 October 21st, 2018 at 5:54 am
The link to the mp4 on the garr.it site says “deleted” but since October 4th it has been available on YouTube: https://www.youtube.com/watch?v=TM-MwQRM-hE
Comment #25 October 5th, 2021 at 2:51 pm
[…] honor to get to know Parisi three years ago, when he was chair of the committee that awarded me the Tomassoni-Chisesi Prize in Physics, and when I visited Parisi’s department at Sapienza University of Rome to give the prize […]