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.
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.
thanks for a reference about James Randi! Now I reliazed that indeed if the claims survives exteremely sofisiticated scrutiny, then it really does not matter if it was a fraud or not, and one would need to accept one lives in a world where one is predictable in one way or another.
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.
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.
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.
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.
