- Inspired by my survey article, John Pavlus has now published an article on Busy Beaver for Quanta magazine.
- This week, I flitted back and forth between two virtual conferences: the Institute for Advanced Study’s Online Workshop on Qubits and Black Holes (which I co-organized with Juan Maldacena and Mark Van Raamsdonk), and Q2B (Quantum 2 Business) 2020, organized by QC Ware, for which I did my now-annual Ask-Me-Anything session. It was an interesting experience, switching between Euclidean path integrals and replica wormholes that I barely understood, and corporate pitches for near-term quantum computing that I … well, did understand! Anyway, happy to discuss either conference in the comments.
- For anyone interested in the new Chinese quantum supremacy claim based on Gaussian BosonSampling—the story has developing rapidly all week, with multiple groups trying to understand the classical difficulty of simulating the experiment. I’ll plan to write a followup post soon!
- The Complexity Zoo has now officially moved from the University of Waterloo to complexityzoo.net, hosted by the LessWrong folks! Thanks so much to Oliver Habryka for setting this up. Update (Dec. 12): Alas, complexityzoo.com no longer works if you use https. I don’t know how to fix it—the Bluehost control panel provides no options—and I’m not at a point in life where I can deal again with Bluehost SSL certificate hell. (How does everyone else deal with this shit? That’s the one part I don’t understand.) So, for now, you’ll need to update your bookmarks to complexityzoo.net.
- In return for his help with Zoo, Oliver asked me to help publicize a handsome $29 five-book set, “A Map that Reflects the Territory,” containing a selection of the best essays from LessWrong, including multiple essays by the much-missed Scott Alexander, and an essay on common knowledge inspired by my own Common Knowledge and Aumann’s Agreement Theorem. (See also the FAQ.) If you know any LW fans, I can think of few better gifts to go under their Christmas tree or secular rationalist equivalent.
This entry was posted
on Friday, December 11th, 2020 at 11:54 am and is filed under Announcements, Complexity.
You can follow any responses to this entry through the RSS 2.0 feed.
Responses are currently closed, but you can trackback from your own site.
Follow
Comment #1 December 11th, 2020 at 12:31 pm
Do you have any opinions on the paper claiming to replicate Google quantum primacy¹ experiment on a classical computer (paper at https://journals.aps.org/prx/pdf/10.1103/PhysRevX.10.041038) ?
¹ Thanks Scientific Armerican for this better name.
Comment #2 December 11th, 2020 at 12:45 pm
Scott, Please invent a complexity class beginning with a J.
Comment #3 December 11th, 2020 at 12:59 pm
B. #1: We already discussed it in last week’s thread on the USTC experiment.
Comment #4 December 11th, 2020 at 2:35 pm
Thank you Scott and glad to help keep the Complexity Zoo up!
If you have any questions about LessWrong, our hosting, or the book set, happy to answer them here.
Also, here are some images of the books that broke the post above but seemed decent to post here (sorry for abusing your LaTeX to do this! :P) .
$$ \require{HTML} \newcommand{\mypic}[4][]{ \style{ display: inline-block; background-image: url(#4); background-size: cover; #1 }{\phantom{\Rule{#2}{#3}{0px}}}} $$
$$\mypic{400px}{400px}{https://res.cloudinary.com/lesswrong-2-0/image/upload/v1606805322/w_1966_jahgq7.png}$$
$$\mypic{400px}{450px}{https://res.cloudinary.com/lesswrong-2-0/image/upload/v1607143400/w_1900_ev6b0r.png}$$
Comment #5 December 11th, 2020 at 5:00 pm
Oliver Habryka and the folks at LessWrong: Thanks for supporting the complexity zoo! The books look great—I just bought two sets!
Comment #6 December 11th, 2020 at 5:19 pm
The URL “complexityzoo.com” is not working for me on Firefox. It’s warning me about an expired security certificate.
Comment #7 December 11th, 2020 at 5:36 pm
Itai Bar-Natan #6: Shoot! It’s working for me. Is anyone else having that problem?
Comment #8 December 11th, 2020 at 5:54 pm
I’m getting “this connection is not private” message for “complexityzoo.com” on safari. Presumably the same issue that Itai is having, ie expired certificate.
Comment #9 December 11th, 2020 at 6:24 pm
I don’t think you have SSL setup for your complexityzoo.com forwarding, so http://complexityzoo.com is fine but https://complexityzoo.com triggers cert warnings.
Comment #10 December 11th, 2020 at 10:08 pm
Scott,
Instead of “Quantum computers need ~√N queries to search a list of size N”, will it not be better to have the older more ‘in words’ description? Because the kind of people who would pause to read the above (kind of) sentence would already know it. (I remember a long time back the supposed nerd in our company explain Quantum Computation to us the wrong way, and rather confidently.)
Comment #11 December 12th, 2020 at 12:31 am
Chrome warns me on complexityzoo.com but is OK with complexityzoo.net
I haven’t checked in for a few years, but the current setup looks a LOT BETTER than I recall, so whoever is doing the hard work to make that happen, keep it up!
Comment #12 December 12th, 2020 at 9:37 am
I await the next episode of Forcing with more excitement than the Mandalorian.
Comment #13 December 12th, 2020 at 9:47 am
Ashley Lopez #10: Agreed!
Comment #14 December 12th, 2020 at 9:54 am
Scott, I think this documentation page explains how to fix the HTTPS problems. If that doesn’t work, contact me if you like and I’d be happy to help fix it.
Comment #15 December 13th, 2020 at 12:13 pm
I’ve noticed that the Complexity Zoo appears to use a definition for “nondeterministic polynomial-time Turing machine”, which it calls an “NP machine”, that is non-standard, or at least non-universal.
Some (perhaps most ?) sources define a non-deterministic Turing machine as the specific type of machine used in defining the class NP: essentially a machine that can launch an unbounded number of P-time computations and return true if at least one of those computations reaches the accept state, otherwise returning false. I believe that this is the only definition which is equivalent to the common alternate definition of NP problems as those having solutions that can be verified in P-time by a deterministic TM. Note that this definition is extremely brittle. Adding just about any other processing step to it, such as inverting the final answer, breaks the equivalence of the two definitions, as well as the distinction between the classes NP and co-NP.
The Complexity Zoo in contrast appears to define an “NP machine” as a machine that allows arbitrary post-processing on the set of accepted computations (ie. inversion, counting, etc.). It then defines different complexity classes by restricting the type of post-processing that the particular type of “NP machine” associated with each class can do.
I think t would be helpful in avoiding confusion if this point were explained somewhere on the site.
Comment #16 December 14th, 2020 at 5:55 am
I am not very regular reader of your blog, but I lurk here quite often nonetheless since years. Especially as I see another claims on quantum computers and quantum supremacy my instinctive reaction is to see what you have to say about that. So I’ll waiting for your comment on Chinese claim of quantum supremacy with eagerness.
Comment #17 December 14th, 2020 at 8:07 am
Please publish the next article in the series on the continuum hypothesis – the suspense is killing me!
Comment #18 December 14th, 2020 at 10:19 am
@Ashley Lopez #10: Yeah, now that the election mess and vaccine stuff is less urgent, now is a good time to change it back. Or maybe prune it down to the main part – “Quantum computers don’t work by trying every solution at once” – so that you can put it alongside whatever other quotes you want to put there.
Comment #19 December 14th, 2020 at 11:51 am
https://www.reddit.com/r/programming/comments/kcwqij/every_single_google_service_is_currently_out/gftgdic/?context=1
Comment #20 December 14th, 2020 at 12:33 pm
Happy Chanukah! Someone I know quoted Al Franken’s podcast: “So, a lot of people don’t know this, but I’m a Jew. There. I said it. We are celebrating Hanukah, and so we are giving our grandchildren underwear, socks, and slacks, just like my parents gave to us.”
Comment #21 December 14th, 2020 at 4:24 pm
Wojciech Kowalski #16: Did you try scrolling down to see my whole post about it from 2 weeks ago? 🙂 (A followup post is coming soon.)
Comment #22 December 15th, 2020 at 3:59 am
Happy Chanukah Scott
I got a Chanukah card from my daughter (10) that included “I love you more than BB(a billion billion billion…..)” so I guess you have had some sort of impact on my family!
Comment #23 December 15th, 2020 at 3:17 pm
Busy Beaver question: Can we say that no reversible n-state TM can output zero in LB(x) operations, where x >= n?
The idea is that, otherwise, the inverse TM, starting with an empty tape, would be an n-state BB machine that runs for LB(n) operations.
If that’s true, then any n-state TM that outputs zero in LB(x >= n) operations would have to be non-reversible for one or more inputs, else we have a contradiction.
Comment #24 December 15th, 2020 at 4:07 pm
Scott: Hah, right, I didn’t do that and I feel embarrassed now. When I heard about this I went to your blog, read most recent post, read that you plan to write something about that and I assumed that it will be your first post about that. It felt strange that you didn’t write about Chinese claims, so it makes more sense now when I understand that it will be follow up.
Well, I will dig into that post then. Thanks.
Comment #25 December 17th, 2020 at 7:00 pm
Job #23:
1. I think you get a contradiction without even mentioning “reversible” or inverting the TM.
That is, suppose any n-state TM outputs zero in LB(x) operations, where x >= n. (I assume by “outputs zero” you mean “ends with a blank tape”, and that you mean in *exactly* LB(x) operations.)
Then pad it to an x-state TM, and observe that it halts after exactly LB(x) steps — contradiction. (I guess we also didn’t need to know what it output.)
2. Note that when you invert a reversible n-state TM, you might get a TM of more than n states, since the primitive operations (that define the allowed states) are not themselves time-symmetric.
Comment #26 December 18th, 2020 at 1:27 am
Bruce #25,
That’s right, but i should have just left it at x=n to avoid the contradiction you mentioned.
I see, thanks for confirming.
What happens if we consider only BB machines that use time-symmetric primitives? E.g. the TM equivalent of Toffoli gates.
Assuming that things remain mostly the same, in the sense that we’ll still have a set of BB/LB values for these reversible BB machines, can we at least say that:
No n-state (time-symmetric) reversible TM can output 0 (empty tape) in exactly reversible-LB(n) operations?
Basically, I’m wondering if we can extend LB(n) to something that’s closer to a typical TM.
Like, replace the empty-tape requirement with reversibility, or something else.
Comment #27 December 18th, 2020 at 10:33 pm
Job #26:
That contradiction happens even with x=n, because (by definition) LB(n) is an impossible exact runtime for an n-state machine. (You ought to know, since you defined it! Are we misunderstanding each other somehow?)
Yes, but you can say the same thing for “output X” (for any X) rather than “output 0”, again just by the definition of reversible-LB(n). And you can say it without ever *using* reversibility — you could say it for any other variant definition of TMs, and a corresponding variant definition of LB.
I don’t understand this comment.
I do think it might be interesting to think about reversible TMs, though.
Comment #28 December 19th, 2020 at 2:09 am
It’s an impossible run time for an n-state Busy Beaver machine though, not just any Turing Machine?
An n-state TM starting with a non-empty tape would correspond to an (n+c)-state BB, where c is however many states it needs to initialize the tape, and an (n+c)-state BB is allowed to run for LB(n) operations, for c > 0.
But I defined LB(n) as applying to BB machines, not TMs in general. For example, a TM would be able to start with LB(n) as input on the tape and then just run for that long?
That’s why i’m wondering about reversible n-state TMs.
Reversible n-state TMs would be able to start out with an arbitrary input value on the tape, including an LB(x), but presumably would still be unable to terminate after LB(x) operations (for x>=n) while leaving an empty tape.
They would only be able to run for LB(x) if they leave a non-empty tape. Does that make sense?
It’s not really an intuitive result, which is why i’m asking about it.
Comment #29 December 20th, 2020 at 9:52 pm
Job #28:
I now understand that you are talking about runtimes of TMs allowed to have arbitrary input, rather than required to start on a blank tape.
Yes, in that case, if a reversible TM takes any input to a blank tape output, then the inverse of that TM (by definition) takes a blank tape to that input.
If you could also modify the definition of TM so that every TM has an inverse with the same number of states and (when reversed) using the same number of steps, and if you redefine LB to be about that kind of TM, then LB(n) is an impossible runtime for an n-state TM which tries to either “take blank input to arbitrary output” or (equivalently, due to reversibility) “take arbitrary input to blank output”.
But that is obvious from the setup — it’s basically what reversibility means, once we presuppose the existence of inverse TMs with those properties — so it doesn’t seem interesting to me.
It’s also important to note that it doesn’t seem easy to redefine TMs to have those properties. If by “reversible TM” we just mean “an ordinary TM whose time evolution function (the function which a single step performs on its complete state (machine state + tape contents + tape position)) is a reversible function”, then I think redefining TMs to have those properties is either impossible, or requires relaxing that definition to let the inverse machine take more steps to simulate the reversal of each single step of the original machine. There are probably artificial ways to fix this, but I can’t think of a natural way. (Probably there is much more known about that than I know — I haven’t looked into what’s published about reversible TMs.)
There is another issue with reversible TMs which I only noticed just now — how does the inverse TM know when to halt? One answer could be “when it first gets back to the designated starting state”. But then, it’s not obvious to me that an ordinary TM whose time evolution happens to be a reversible function, always corresponds to a “reversible-by-construction TM” in this sense. This makes me sure that I wouldn’t want to spend much time on questions about reversible TMs without first finding out how other people have defined them.