Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

news.ycombinator.com

Post reply on HN
Print view View original

331–340 of 373 posts

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#331

Post by ScottAaronson »

drostie wrote: post #41

Hi Scott, I first stumbled across your blog while I was across the pond doing my Master's in Delft; it looks like you've been relatively successful since then. I was wondering how you feel that success/celebrity has affected you. Does it actively drive you to something other than research -- say, are you viewing it as a building block to maybe publishing a book or so? Or does it feel like a distraction from research…

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 shrieking and throwing their panties at me ... oh god, the women are so persistent! Don’t they realize I’m married?

But I do try hard to “keep it real”—or better, “keep it complex”—by setting aside some quality time just for me and some pen and paper. As I like to say, it’s all about the amplitudes.

(Seriously: I do have a book, Quantum Computing Since Democritus! And I have been approached by people asking me to sign it. But typically only in a few highly selected places, like Cambridge, MA or Berkeley, CA. :-) )

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#332

Post by ScottAaronson »

adrianN wrote: post #37

When do you think will we have the first quantum computer that can solve useful problems faster than the classical competition, for example in quantum chemistry?

I hope in 5-10 years, but really I don’t know, and no one else does either.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#333

Post by ScottAaronson »

glifchits wrote: post #7

In my opinion, you're one of the most entertaining and approachable writers on mathematical topics like QC. How did you get good at writing?

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 of yourself, practice, and more practice.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#334

Post by beefman »

beefman wrote: post #227
beefman wrote: post #148

Will the power of 2^72 complex numbers working for me cause gravitational collapse? Has anyone calculated holographic bound limitations on quantum computers?

(can't edit) There's a related comment here[1]. The simpler version of the bound doesn't depend on mass or energy, just surface area (or radius for a Schwarzschild black hole). It seems to me that 2^72 of "storage" is already pushing it, but anyway I don't understand why the number of bits needed to "describe" the state isn't the relevant quantity. IIRC Bekenstein had at least one completely classical derivation of t…

Scott briefly discusses this issue in his book[1], where he cites a paper by Davies[2], which in turn cites one of Scott's talks[3]. I'm not sure about Davies' idea that the holographic bound should be formulated in terms of Kolmorgorov complexity instead of Shannon entropy, but the general question of holographic limitations on quantum systems deserves further study, it seems to me.

[1] https://www.amazon.com/dp/0521199565/

[2] https://arxiv.org/abs/quant-ph/0703041

[3] https://arxiv.org/abs/quant-ph/0507242

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#335

Post by omarchowdhury »

akavel wrote: post #257
omarchowdhury wrote: post #255

Earlier quoted context omitted.

As someone still trying to understand the essence of quantum computing, your analogy to me can be summed up as coherence only comes from coherence. Which to me is too general, and describes computing as a whole. How coherence is determined in the particular case of quantum computing as opposed to classical computing is the meat and potatoes that I'm looking for.

Sorry, don't think I can do more at this point; I once managed to understand the Shor's algorithm from some book; but I didn't reinforce it, and now I'm left only with a vague recollection of the main a-ha moment... Though I actually don't really get what do you mean by coherence here (esp. in the area of classical computing).

My coherence I mean something intelligible that can be acted on (ie. computer code and its results).

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#336

Post by ScottAaronson »

tomlemon wrote: post #171

In your mind what is the solution to the "Dice Room" paradox you describe in "PHYS771 Lecture 17: Fun With the Anthropic Principle" ( https://www.scottaaronson.com/democritus/lec17.html )? I take it you don't believe in the SIA? Is this paradox irreducible? Is the world going to end soon?

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 probabilities. Do you?

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#337

Post by ScottAaronson »

TrinaryWorksToo wrote: post #9

I'm halfway through the first chapter of Neilsen and Chuang's book. I'm enjoying reading about the subject and am at the quantum parallelism part. Can you explain why Grover's algorithm has a runtime of root N? It seems like the runtime should be log2(n) because of exponential qubits or 1 because there must be a way for all the qubits to interfere. Also, What resources do you reccomend for self study? Are there quant…

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 on the 1-norm. Classically, each time you pick one item out of N to query, you can add ~1/N probability to the marked item—so the probability of having found the marked item after T queries goes like T/N. Quantumly, you can add ~1/sqrt(N) amplitude to the marked item with each query, so the amplitude on the marked item after T queries goes like ~T/sqrt(N), and hence the probability of observing the marked item when you measure goes like ~T^2/N.

A fundamental result from the 1990s, called the BBBV Theorem, shows that not even a quantum computer can solve the unordered search problem any faster than Grover’s algorithm solves it. I won’t prove the theorem in this comment :-), but the intuition is simply that quantum mechanics is a norm-preserving and linear theory. So you actually need to do something to gradually put more and more amplitude onto the marked item; you can’t just instantly and magically give an amplitude of 1 to whichever branch of your superposition happened to hit the marked item.

I’m not sure if there are QC meetups in SF (does anyone else?). But certainly nearby Berkeley is one of the centers of the world for QC—home to Umesh Vazirani’s group, the Simons Institute for Theory of Computing, and now also the startup Rigetti.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#338

Post by ScottAaronson »

Leibniz0 wrote: post #84

Scott, I loved your book (QCSD). What are the chances that overcoming noise in quantum gate systems as they get larger is a practical impossibility beyond some threshold - for instance in the same way that inverting a gaussian convolution requires super-exponentially less noise above a given sampling density / stdev ?

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 couples mostly to its near neighbors—so there doesn’t seem to be any inherent reason why noise per qubit needs to keep increasing as you integrate more and more qubits.

For more, see my other answers on this thread about QC skepticism.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#339

Post by ScottAaronson »

nicklaf wrote: post #65

Hi Scott, If quantum computing ever becomes commonplace, and quantum computer programs widely written and understood, do you envision that the teaching of quantum mechanics itself will be significantly impacted? Or instead will we simply see quantum complexity theory begin to redefine the undergraduate computer science curriculum?

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 properties of QM—states, unitary transformations, measurements, tensor products, entanglement, density matrices, etc.—illustrated with the simplest systems to which those rules apply, namely collections of qubits (or more generally, finite-dimensional Hilbert spaces). This already lets the students fully understand no-cloning, quantum teleportation, quantum key distribution, basic quantum algorithms like Bernstein-Vazirani and Simon, and other cool things from quantum information, and it already lets them explore the conceptual questions (the measurement problem and so forth) that interest most of them. After this material has been mastered, and only after, one could see how it gets applied to real physical systems like the harmonic oscillator, the hydrogen atom, or a particle in a 1D potential well. So, all the mathematical complications of infinite-dimensional Hilbert spaces—which are not essential to understanding QM itself—could be deterred to this part of the course. This is the reverse of the historical order in which the ideas were discovered in the 1920s, but I think it’s the much more logical order in which to learn them—even if quantum information weren’t a big thing that people now care about.

If you want to see a recent text by a bona fide physicist that presents QM in exactly this way—what I think of as simply the “modern” way—then check out Lenny Susskind and Art Friedman’s remarkable “The Theoretical Minimum” series. Or you could look at pretty much any introductory book or course lecture notes about quantum information, including mine. We do it this way as well, except that we never do get to the harmonic oscillator or the hydrogen atom. :-) I can say from experience that the material is then totally accessible to any bright undergrad who’s done math up through linear algebra.

Re: I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA

#340

Post by wzeng »

TrinaryWorksToo wrote: post #9

I'm halfway through the first chapter of Neilsen and Chuang's book. I'm enjoying reading about the subject and am at the quantum parallelism part. Can you explain why Grover's algorithm has a runtime of root N? It seems like the runtime should be log2(n) because of exponential qubits or 1 because there must be a way for all the qubits to interfere. Also, What resources do you reccomend for self study? Are there quant…

There is a Bay Area Quantum Computing meetup (I'm one of the organizers!)

https://www.meetup.com/Bay-Area-Quantum-Computing-Meetup/

Next one will likely be at the end of July. Hope to see you there!

Post reply on HN