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.
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.
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 exponentially with the number of particles in your system. This is because every possible classical configuration of the system is its own orthogonal "direction" in Hilbert space, and the full state can be an arbitrary superposition (i.e., complex linear combination) of those directions.
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 say after some finite point: “ah yes, now the system has gotten all of them.”
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.
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 theoretical computer scientist, I spend a lot of my time hanging around people who are abnormal in more-or-less the same ways I am, and in many cases more so.
Besides QCSD, I’d try Mermin’s Quantum Computer Science: An Introduction for QC, or any of my 50 favorite books from this list
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 commitment and revealing them later, then to whatever extent fraud and the like had been ruled out as explanations (in the ordinary experimental ways, and possibly with the help of James Randi :-) ), I’d have to say that the person had successfully unmasked free will as an illusion.
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
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 even guns or fire! :-) So with all the more dangerous technologies out there, it would be weird to fret about quantum computers of all things: something that seems unlikely to do much harm (at least if we take care to upgrade our crypto), and that might even do significant good for the world, for example if quantum simulation lets us design more efficient batteries and solar cells.
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 observed with a high probability (since you used constructive and destructive interference to boost its amplitude, while suppressing the amplitudes of the wrong answers).
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’t believe such a nonlinear term exists. Experimental searches have put more and more severe upper bounds on its size, if it did exist. But the bigger problem is that such a term would completely break the structure of quantum mechanics, in even more “basic” ways than by making NP-complete problems easy. For example, it would genetically lead to faster-than-light communication and to violations of the uncertainty principle. So while it’s interesting to think about, and even worth searching for just in case, it almost certainly belongs to the category of “what if?” physics.
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 amount, since Raz and Tal had to modify Forrelation a bit to get their proof to go through.)
For an attempt at a popular summary of what the circuit lower bound innovations consisted of, see my blog post:
No, this doesn’t much change my priors about the power of quantum computation—for one thing, because we all (or at least I :-) ) were already pretty damn confident that Forrelation was not in PH. On the other hand, I was not expecting that the separation could be proved right now—certainly, not without first proving some weaker separations like BQP vs. AM.
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 on the correct rules in the case of chess, even if it would be up against undecidability when trying to do the same thing for a completely arbitrary game.
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 - Time to pick daughter up again!
4-6pm - Play with kids, eat more, check email
6-8pm - Read news and social media, get depressed
8-9:30pm - Help get kids ready for bed
9:30pm-4am: NOW it’s time to do some research!!! Tools: pen, paper, sofa, LaTeX editor, and sometimes web browser to look up papers (but this last tool is extremely dangerous and can lead to procrastination)
4am - Collapse
Being back in Austin and teaching will severely affect the above hours. But in any case, it’s not like I consciously decided on them, as part of some plan to maximize productivity (!!) - this is just what I fall into when I don’t have other obligations.
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 as “quantum deep learning” that’s sufficiently well-developed to deserve the name. You can use Forrelation as a separating example for some other quantum learning problems, e.g. k-means clustering, but so far that mostly just shows that you can artifically shoehorn an exponential quantum speedup into those tasks, rather than that the tasks will give us useful quantum speedups in “real life.”
In the Forrelation problem, I conjecture that the only thing that really matters about the Fourier transform is that it’s a unitary matrix all of whose entries have small absolute values. As such, it lets you relate two Boolean functions in a way that a quantum computer can notice, but that’s extremely “global” in nature and doesn’t show up locally. Raz and Tal may have used some additional technical properties of Forrelation in their proof (now that I write that, I’m actually not sure—I’ll need to check!). But if they did, then I conjecture that another proof could avoid the use of those properties.
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.
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.
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.
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?