1
First they came for the Iranians
Action Item: If you’re an American academic, please sign the petition against the Immigration Executive Order. (There are already more than eighteen thousand signatories, including Nobel Laur…
Scott Aaronson
I'm Schlumberger Centennial Chair of Computer Science at The University of Texas at Austin , and director of its Quantum Information Center . My research interests center around the capabilities and limits of quantum computers, and computational complexity theory more generally.
- Popular posts
- 50
- Total points
- 10,542
- HN comments
- 4,956
- Rank
- #73 personal
Visit scottaaronson.com → On Hacker News May 2009 – Jan 2021
Science & Space 26Math & Algorithms 26Society, Policy & Culture 15Life, Learning & Writing 9Software Engineering 8AI & Machine Learning 7
2
Scott’s Supreme Quantum Supremacy FAQ
You’ve seen the stories—in the Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, or elsewhere—saying that a group at Google has now achieved quantum computation…
3
The Kolmogorov option
Andrey Nikolaevich Kolmogorov was one of the giants of 20th-century mathematics. I’ve always found it amazing that the same man was responsible both for establishing the foundations of …
4
Knuth on Huang's Sensitivity Proof: “I've got the proof down to one page” [pdf]
The Sensitivity Conjecture, which I blogged about here, says that, for every Boolean function f:{0,1}n→{0,1}, the sensitivity of f—that is, the maximum, over all 2n input strings x∈{0,1}n, of…
5
Eigenmorality
This post is about an idea I had around 1997, when I was 16 years old and a freshman computer-science major at Cornell. Back then, I was extremely impressed by a research project called CLEVER, wh…
6
P vs. NP
For those who just want the survey itself, not the backstory, it’s here. (Note: Partly because of the feedback I’ve gotten on this blog, it’s now expanded to 121 pages!) Upda…
7
Google, D-Wave, and the case of the factor-10^8 speedup
Update (Dec. 16): If you’re still following this, please check out an important comment by Alex Selby, the discoverer of Selby’s algorithm, which I discussed in the post. Selby querie…
8
I will not log in to your website
Two or three times a day, I get an email whose basic structure is as follows: Prof. Aaronson, given your expertise, we’d be incredibly grateful for your feedback on a paper / report / gr…
9
How Shor's Algorithm works (2007)
I’ve been talking a lot recently about how quantum algorithms don’t work. But last week JR Minkel, an editor at Scientific American, asked me to write a brief essay about how quantum al…
10
NSA in P/poly: The Power of Precomputation
Even after the Snowden revelations, there remained at least one big mystery about what the NSA was doing and how. The NSA’s classified 2013 budget request mentioned, as a priority item, R…
11
Quantum supremacy: the gloves are off
Links:Google paper in NatureNew York Times articleIBM paper and blog post responding to Google’s announcementBoaz Barak’s new post: “Boaz’s inferior classical inferiority FA…
12
D-Wave: Truth finally starts to emerge
Wrap-Up (June 5): This will be my final update on this post (really!!), since the discussion seems to have reached a point where not much progress is being made, and since I’d like to oblige …
13
Your yearly dose of is-the-universe-a-simulation
Yesterday Ryan Mandelbaum, at Gizmodo, posted a decidedly tongue-in-cheek piece about whether or not the universe is a computer simulation. (The piece was filed under the category “LOL.…
14
What does the NSA think of academic cryptographers?
Brighten Godfrey was one of my officemates when we were grad students at Berkeley. He’s now a highly-successful computer networking professor at the University of Illinois Urbana-Champaign, …
15
Who Can Name the Bigger Number?
[This essay in Spanish] [This essay in French] [This essay in Chinese] In an old joke, two noblemen vie to name the bigger number. The first, after ruminating for hours, triumphantly announces "Eighty-three!" The second, mightily impressed, replies "You win." A biggest number contest is clearly pointless when the…
16
Quantum supremacy, now with BosonSampling
Update (12/5): The Google team, along with Gil Kalai, have raised questions about whether the results of the new BosonSampling experiment might be easier to spoof classically than the USTC team tho…
17
On the destruction of America’s best high school
[C]hildren with special abilities and skills need to be nourished and encouraged. They are a national treasure. Challenging programs for the “gifted” are sometimes decried as “eli…
18
Quantum mechanics as a generalization of probability (2007)
There are two ways to teach quantum mechanics. The first way -- which for most physicists today is still the only way -- follows the historical order in which the ideas were discovered. So, you start with classical mechanics and electrodynamics, solving lots of grueling differential equations at every step. Then you…
19
My biology paper in Science
Think I’m pranking you, right? You can see the paper right here (“Synthetic recombinase-based state machines in living cells,” by Nathaniel Roquet, Ava P. Soleimany, Alyssa C. Fer…
20
Grading Trudeau on quantum computing
Update (4/19): Inspired by Trudeau’s performance (which they clocked at 35 seconds), Maclean’s magazine asked seven quantum computing researchers—me, Krysta Svore, Aephraim Steinb…
21
The 8000th Busy Beaver number eludes ZF set theory (2016)
I’ve supervised a lot of great student projects in my nine years at MIT, but my inner nerdy teenager has never been as personally delighted by a project as it is right now. To…
22
Review of Steven Pinker’s Enlightenment Now
It’s not every day that I check my office mailbox and, amid the junk brochures, find 500 pages on the biggest questions facing civilization—all of them, basically—by possibly the …
23
Memrefuting
(in which I bring this blog back to the “safe, uncontroversial” territory of arguing with people who think they can solve NP-complete problems in polynomial time) A few people have aske…
24
My Conversation with “Eugene Goostman”
If you haven’t read about it yet, “Eugene Goostman” is a chatbot that’s being heavily promoted by the University of Reading’s Kevin Warwick, for fooling 33% of judges …
25
Matrix multiplication in O(n^2.373)
For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n2.376) steps. Last year, though, in his PhD thesis, Andrew Stot…
26
Can computers become conscious?: My reply to Roger Penrose
A few weeks ago, I attended the Seven Pines Symposium on Fundamental Problems in Physics outside Minneapolis, where I had the honor of participating in a panel discussion with Sir Roger Penrose. T…
27
The destruction of graduate education in the United States
If and when you emerged from your happiness bubble to read the news, you’ll have seen (at least if you live in the US) that the cruel and reckless tax bill has passed the House of Representat…
28
What I believe II
Unrelated Update: To everyone who keeps asking me about the “new” P≠NP proof: I’d again bet $200,000 that the paper won’t stand, except that the last time I tried that, it d…
29
Once we can see them, it’s too late
[updates: here’s the paper, and here’s Robin’s brief response to some of the comments here] This month Robin Hanson, the famous and controversy-prone George Mason University econo…
30
Pseudonymity as a Trivial Concession to Genius
Update (6/24): For further thoughts and context about this unfolding saga, see this excellent piece by Tom Chivers (author of The AI Does Not Hate You, so far the only book about the rationalist co…