ScottAaronson

9 ms·

1.
by ScottAaronson 8y ago
Thanks! In theoretical computer science as a whole, authorship is only for those who made a direct intellectual contribution. It’s one of the things I like best about the culture of our field.
2.
by ScottAaronson 8y ago
No, I hadn't seen that paper; thanks! I don't want to comment on it without having studied it, except to mention that it doesn't make any reference to Forrelation.
3.
by ScottAaronson 8y ago
Pretty much any intro to QC (and in particular, any of the intros I've written, and linked to elsewhere on this thread) will make the point about Hilbert space (that's what it's called) having a dimension that grows exponenti
4.
by ScottAaronson 8y ago
Results from inductive inference show that you’re not going to converge in general . In the specific case of chess, however, my point was that we, because we know the complete list of rules, could plausibly look in from the outside and s
5.
by ScottAaronson 8y ago
Just as a quick followup: Avishay Tal has confirmed for me that, indeed, their proof still goes through if you replace the Fourier transform by any other unitary matrix with bounded entries.
6.
by ScottAaronson 8y ago
Knowing more math than most of the people who you pass on the street, but at the same time having vastly inferior social skills to them, is something that you sort of get used to in childhood. :-) You should keep in mind, also, that as a t
7.
by ScottAaronson 8y ago
I’m not sure I fully understand your argument, but if someone showed that they could perfectly predict the actions of the people around them, say hours or days into future, placing the predictions into a sealed envelope or a cryptographic c
8.
by ScottAaronson 8y ago
Short answer: not in any obvious way! Longer answer: whatever I have to say about possible implications of QC for the hard problem of consciousness, you can probably find in the following lecture https://www.scottaaronson.com&#x2
9.
by ScottAaronson 8y ago
No, I don’t think humanity is well placed to be responsible wielders of quantum computing. But the thing is, we’re even less well-placed to be responsible wielders of nuclear weapons, or climate-destroying combustion engines, or probably
10.
by ScottAaronson 8y ago
When the quantum computation is finished, you suck it up and you measure. The entire point of the quantum algorithm was to set things up in such a way that, even as the measurement destroys the superposition state, the right answer is obse
11.
by ScottAaronson 8y ago
If you mean, quantum computers that would exploit a nonlinear term in the Schrödinger equation to solve NP-complete and even harder problems in polynomial time (as studied by Abrams and Lloyd in 1998), then the central problem is that I don
12.
by ScottAaronson 8y ago
Honestly, almost all of the technical innovation in this breakthrough had to do with classical circuit complexity—-once you know my Forrelation problem, there’s almost no further input you need about quantum computation. (Well, a slight am
13.
by ScottAaronson 8y ago
Right, but even if chess were infinite, we could still imagine an algorithm that would output the smallest explicit rule set that was consistent with all the games it had seen so far, and that would quickly (though how quickly?) converge
14.
by ScottAaronson 8y ago
While I was on sabbatical: 7am - Wake up, eat breakfast, check email, help get daughter ready and walk her to school 9am - Back to sleep 2pm - Wake up again, shower, eat lunch, check email. Possibly coffee with friend or colleague. 4pm - T
15.
by ScottAaronson 8y ago
My favorite part of my sabbatical in Tel Aviv was having some actual time to do research. My second-favorite part was the hummus. Forrelation is not a “guiding light for quantum deep learning.” I’m not even sure if there’s such a thing
16.
by ScottAaronson 8y ago
I think that the teaching of QM has already been impacted by quantum information—and I hope it gets impacted more, regardless of if and when we get useful QCs! To my mind, it’s just infinitely clearer to start with the basic rules and
17.
by ScottAaronson 8y ago
If anything like that turned out to be true, and fundamental (rather than just an engineering limitation), I’d regard it as a shocking discovery that would overturn our current understanding of QM. After all, physics is local—each particle
18.
by ScottAaronson 8y ago
The reason why the running time of Grover’s algorithm involves sqrt(n) has to do with the Pythagorean theorem—or if you like, the fact that quantum mechanics is based on the 2-norm, in contrast to classical probability theory which is based
19.
by ScottAaronson 8y ago
There are at least two plausible solutions to the Dice Room, depending on whether you adopt SSA or SIA. I wish I knew something more insightful to say about it than that, but I still don’t know the right way to think about indexical probab
20.
by ScottAaronson 8y ago
It’s funny: when Philip Roth passed away recently, I was rereading some of his stuff, and thinking to myself, “why am I so terrible at writing?” If I have any tips, I guess they’d be bend-over-backwards honesty, willingness to make an ass o
21.
by ScottAaronson 8y ago
I hope in 5-10 years, but really I don’t know, and no one else does either.
22.
by ScottAaronson 8y ago
There’s no question that celebrity can get to your head in this line of work. Every single time I get off my private plane somewhere, I’m mobbed by quantum complexity theory groupies, not to mention the Hacker News paparazzi, and the women
23.
by ScottAaronson 8y ago
I confess I get annoyed when people make arguments about the interpretation of quantum mechanics using complicated thought experiments involving lasers and mirrors. Why not just talk about it in the modern way, in terms of qubits and state
24.
by ScottAaronson 8y ago
As far as I know, it would have zero effect on any of that ... unless you need to simulate quantum physics or chemistry, factor large integers, calculate discrete logarithms, or possibly solve some large optimization problems while doing yo
25.
by ScottAaronson 8y ago
No, it's an unknown known. :-)
26.
by ScottAaronson 8y ago
No, I wouldn't recommend that either. :-)
27.
by ScottAaronson 8y ago
On further thought, we should distinguish two problems: (1) "Induce" the rules, in the sense that after training on millions of played games, you now have a neural net or whatever that plays mostly or entirely according to the rul
28.
by ScottAaronson 8y ago
Actually, if you already have a classically functionally complete gate (say, the Fredkin or Toffoli gates), then you only need one other gate to get a functionally complete set for quantum computing. This one other gate could be the Hada
29.
by ScottAaronson 8y ago
I'd seen Fermat's Library but haven't used it. I hadn't heard of distill.pub before your comment. Honestly, I don't see scientific papers going away anytime soon. What's the alternative to an individual or gr
30.
by ScottAaronson 8y ago
Well, the "less partying" part sounds accurate. :-) In grad school, for example, I had some good friends, but very little "party life" and certainly very little dating life---not out of choice, just because I didn'

More ›