Classifieds thread
In addition to the emails from journalists, I also get a large number of emails seeking interactions with me—a discussion of cryptocurrencies, help in planning a political campaign, whatever—that could probably be had just as well, or better, with some other reader of this blog. So inspired by Slate Star Codex, my lodestar of blog-greatness, I’ve decided to host Shtetl-Optimized‘s first ever classifieds thread. This is your place to post any announcement, ad, offer, proposal, etc. that you think would be of particular interest to fellow Shtetl-Optimized readers. As usual, I reserve the right to remove anything too spammy or otherwise unsuitable (“C@$H 4 G0LD!!!”), but will generally be pretty permissive.
Oh yes: Merry Christmas to those who celebrate it, from a spot roughly equal driving distance (about an hour 20 minutes) from Nazareth and Bethlehem!
Update: OK, let me start the ball rolling, or rather the photon propagating. Reader Piotr Migdal wrote to tell me about a quantum optics puzzle game that he created. I tried it and it’s excellent, and best of all clear: unlike virtually every other “quantum game” I’ve tried, it took me only a minute to figure this one out. (Admittedly, it’s less of a quantum game than an “optics game,” in the sense that the effects it teaches about also appear with laser beams and other many-photon coherent states, which you don’t really need QM for, even though QM provides their ultimate explanation. But whatever: it’s fun!) Piotr has lots of other great stuff on his website.
Follow
Comment #1 December 24th, 2017 at 3:45 am
Dear fellow Shtetl-Optimized readers, I’ve been thinking about Bell’s inequalities violations and came up with this analogy.
Suppose you have to write a computer program that outputs 0 or 1. Two copies of this program are run independently to play a cooperative game, where answers 0 (by the first copy) and 1 (by the second copy), or (1,0) count as a win, and answers (0,0) and (1,1) count as a loss. Now, if the program is purely classical, there is no way to win: its output depends only on the internal state, so both copies will produce the same result. When program has an access to random bits, the chances of winning increase to 0.5. And finally, if the program has an access to shared qubits of the |01> + |10> sort, it becomes very easy to win with 100% probability.
I would very much like to know if my analogy is correct, or am I missing something.
Comment #2 December 24th, 2017 at 4:27 am
Oleg #1: No, that’s wrong. The point of the Bell inequality is that entanglement lets you achieve something that would be classically impossible without faster-than-light communication, even supposing you had unlimited random bits pre-shared between the parties (in which case, your game would be winnable 100% of the time even classically). Also, there’s no requirement that both parties run the same program.
You can think of the Bell inequality as a game played by two separated programs, and that’s exactly how many of us do think of it. But the game, called the “CHSH game,” is more subtle than the one you describe; it has a classical win probability of 3/4 and a quantum win probability of cos2(π/8)~0.854. For more, see e.g. here or here.
Comment #3 December 24th, 2017 at 6:40 am
I will send a current version of https://arxiv.org/abs/1709.06711 to anyone who is willing to submit the new version to a JMathPhys-level refereeing. The new paper is already significantly better and has had the benefit of two readers, but even better would be even better. Acknowledgement in the text to the first ten people who take the task seriously (this is Shtetl-Optimized, and it’s the competition of the season, far superior to any crossword, so I’m expecting a hundred takes at least). In due course I will put a v3 on the ArXiv and submit the paper to JMathPhys.
Reading this paper will make you SMARTER!!!!! Well, at least it will give you a new way to understand a few curious aspects of quantum field theory.
Comment #4 December 24th, 2017 at 9:07 am
Thanks for the Merry Christmas wishes.
Visiting Israel is in my list of “things to do” before I die. From personal friends who have made the trip, particularly to the Christian Holy sites like those you mention, it’s a life altering experience.
I wish you a very Happy and Prosperous 2018!
Comment #5 December 24th, 2017 at 9:16 am
If you teach a quantum computing course, you might find my quantum circuit simulator Quirk to be a useful learning tool to show students.
Quirk is a drag-and-drop circuit editor that runs in web browsers. It’s free, open source ( github.com/Strilanc/Quirk ), and I host the latest version at:
algassert.com/quirk
Anyone can go to that link, start dragging gates onto the circuit, and the result displays will update in real time. You can even add state displays to the middle of the circuit.
Comment #6 December 24th, 2017 at 2:54 pm
Hi, I’m a AI Safety and Cybersecurity researcher looking for a new gig in the Chicago or Bay areas. I hold an MBA, have started 14 companies with 7 successful exits, and served for 4 years in the Air Force in cybersecurity.
I’m currently working on a contract to produce a thorough literature review on corporations as AGIs- if you’d like to fund more research along these lines, hire me as a freelancer for AI safety or Cybersecurity or starting a company, or just meet up for coffee, shoot me an email- pscheyer at gmail.
I’d like to expand the lit review into a couple of books’ worth of material- one, titled The People We Make, examining Corporations, States, and other extant AGIs, how to govern and assess them while maintaining democracies and a modern standard of living. I think this topic, and finding ways to make sure corporations actually do what they’re intended to, is critical to AI safety and generally maintaining civilization.
The other, Dragons, describes how high-net-worth individuals become consumed by their money. They act to protect and expand their wealth, and have forgotten or subsumed any other goals they have in favor of wealth-oriented actions. I’ve worked with many wealthy people, some with agency, most without, and i find this a fascinating topic.
If you’d like to help fund either work or just chat about the topics, please hit me up- pscheyer at gmail.
Comment #7 December 24th, 2017 at 3:48 pm
I’m writing a paper in which I derive a regret bound for one-shot (non-episodic) model-based reinforcement learning with a weak external “advisor” (my personal motivation is AGI safety although ofc other applications are possible.) I wonder whether anyone would be interested in reading a draft and commenting on it? (The draft should be ready in a month or so.) If you are, please contact me at (rot13 of) gbc.fdhnex@tznvy.pbz
Comment #8 December 24th, 2017 at 4:36 pm
Scott, I am so happy you mentioned the Quantum Game with Photons here! 🙂
For my defense – the initial goal was to create a simulation with a few particles, so to show Hong-Ou-Mandel interference, Quantum Key Distribution, quantum teleportation and perhaps quantum memory. In fact, the underlaying JavaScript engine is built to support tensor arbitrary products.
What turned to be challenging, is to provide a clear and intuitive visualization. Here even for a single photon there are quite a few things that players find confusing (visualization of polarization, measurement). Plus, creating a an interface that works, turned out to be much more time-consuming task than expected. Though, at the same time – it turned out that even with a single photon there is a lot of room for challenging task.
Yet, right now the only thing here that cannot be described by classical wave optics is measurement (so: Elitzur–Vaidman bomb tester).
Comment #9 December 24th, 2017 at 9:34 pm
My husband is a big fan of this blog and mentioned this ‘open classifieds’ post. As an early Xmas present I said I’d promote his film ’Digital Physics’ on his behalf.
‘Digital Physics’ is a fictional narrative that incorporates science ideas that many readers of this blog might be familiar with. He says you guys are ‘quantum people’ who might not agree with some of the ideas in the movie, but since the main character is kind of crazy and not necessarily portrayed in the most flattering light, you might find the story well-balance in that respect. If you’re looking for a computationally themed movie (and who isn’t?!?), give ‘Digital Physics’ a shot.
http://www.digitalphysicsmovie.com. (Available on Amazon Prime and Vimeo)
Comment #10 December 25th, 2017 at 3:39 am
I’d be remiss to miss this chance to advertise http://beeminder.com (we’re also one of the official advertisers on Slate Star Codex).
Maybe the most compelling endorsement for this audience is the multiple PhDs that various Beeminder users have told us probably wouldn’t have happened but for Beeminder. (Certainly my own is in that category, even though Beeminder as such didn’t exist back then. My then-girlfriend — now CTO of Beeminder / my spouse — called it the “Voluntary Harassment Program”. And later “Kibotzer” for “kibitzing robot”…)
Oh right, telling you what Beeminder is: It’s a quantified-self tool with commitment contracts attached. So you pick a metric, steps with Fitbit, time tracked via RescueTime, commits on GitHub, messages in Gmail, etc etc, and commit to some change in that metric over time. We plot your progress with a “yellow brick road” to follow and you agree to get charged actual money if you don’t keep your datapoints on track.
It’s very data-nerd oriented and we’re working on making it more accessible to non-nerds (without dumbing it down).
If you, a Shtetl-Optimized reader, try it out and run into anything confusing or frustrating, we’d be especially grateful to hear about it. Because there are already an overwhelming number of things about Beeminder that are overwhelming to normal humans. So anything throwing you fellow hypernerds for a loop will be top priority to fix!
PS: Thanks so much to Scott for permission to spam his audience, not to mention the brilliant and poignant blog!
Comment #11 December 25th, 2017 at 8:16 am
Will you be speaking while you are here?
or meeting with lesswrong tlv?
Comment #12 December 25th, 2017 at 9:25 am
daw #11: Yes, I’ve already spoken at TAU, Hebrew University, Weizmann, and Technion, and am scheduled to speak again at Weizmann and Technion (check the physics seminar calendars). And I came to a LessWrong tlv meetup, which I enjoyed tremendously, and would love to come again insofar as two small kids and traffic on the Ayalon freeway permit. Or shoot me an email if you’ll be near TAU or Neve Avivim and want to get coffee or something.
Comment #13 December 25th, 2017 at 1:52 pm
I just finished teaching the Graduate Complexity Theory class at Carnegie Mellon University. The lecture videos are on YouTube, and the course notes, homeworks, and tests can be found on the website here:
http://www.cs.cmu.edu/~odonnell/complexity17/
The course assumes you have studied Part III of Sipser’s book (“Computational Complexity”), and focuses on time complexity, circuit complexity, and randomness.
There are a few slightly ‘nonstandard’ topics/presentations in there that I hope may be of interest: the (nonrelativizing) “TIME(t) in SPACE(t / log t)”) theorem of [HPV77]; SAT not in time n^1.66 on RAM machines with sublinear space; a complete proof (with pictures) of Permanent being #P-complete (following Blaser’15); the Pitassi-Rossman-Servedio-Tan Switching Lemma; PP and Permanent not in Uniform-ACC [AG94]; and, a streamlined version of Williams’s NEXP not in ACC (doing EXP^NP in place of NEXP is a bit easier…).
Comment #14 December 25th, 2017 at 8:34 pm
To what extent is the Church-Turing thesis baked in to the current toolset of mathematical physics? Is there any even remotely straightforward way of even describing hypercomputation within present frameworks? As far as I am aware even Penrose doesn’t attempt to speculate in this area, his treatment of a noncomputable OR amounts to “here be dragons”.
Something that nags at me is the theoretical hierarchy of Turing oracles–the “unreasonable effectiveness” of mathematics at describing the physical world is a truism, but it seems to me that either hypercomputation is impossible, and this is a case of a true castle in the air with no practical consequence, or else…
~~~
You sometimes criticise people who try to argue against machine consciousness while gliding past the implications for the CTT, but aren’t you being similarly coy with your resolution to the firewall problem? You more or less dispose of mathematical realism by de facto extending quantum indeterminacy to the truth value of mathematical propositions.
You counter by pointing out that these propositions are so gargantuan and intractable that they’re impossible to calculate with the resources available within the physical universe, but as an old teacher of mine was fond of saying, “if you steal a penny you’re still a thief”.
The entire project of theroretical physics since Newton is grounded in the idea that mathematics can be used to describe the goings-on in the physical world. But if mathematical propositions can be contingent on physical reality then things get a bit odd. Right now the landscape of math may be solidly fixed out to some inconceivably far-off fringe of ludicrously arcane propositions, but was this always the case? Near the beginning of time the Universe was much smaller, and the resources avalable to computation presumably much less, so did that indeterminate fringe lie much closer in? If one writes down an equation to describe conditions near or at the big bang with, say, a variable that has “2” as a coefficient, is one justified in doing so?
Can one be sure that the existence of “2” or its properties were determitate at that point or were they part of some cloud of probabilites of other possible numbers succeeding “1” of other ways that “2” could behave? How could one ever hope to write down an equation describing such a cloud if all one has to work with are bits of present-time math that in some sense must presuppose the outcome?
Comment #15 December 26th, 2017 at 12:37 am
xyz #14: You’ve probably raised too many philosophical enormities for me to tackle them all in one comment! 🙂
The most basic thing I’d say, though, is that in different subjects, there are different statements that we question and different ones that we provisionally grant. This is the only possible way to make progress, and as long as we’re clear about which black boxes we’re opening at a given time and which ones we’re leaving closed, it’s not a problem.
So for example: in a discussion of firewalls and Harlow-Hayden, we’d normally just assume the (quantum polynomial-time) Church-Turing Thesis, because the rest of the discussion has enough moving parts already! In a separate discussion we can question the CT Thesis, and if it were ever rejected, then of course that could affect future discussions about firewalls (and hundreds of other “downstream” discussions besides).
Likewise, I don’t think we could even get started doing physics, if we couldn’t presuppose the reliability of our knowledge at least of elementary arithmetic, and of math that’s expressible in terms of arithmetic (which I’d argue is almost all the math one needs in practice)—even though a philosopher might find it interesting to question the latter.
Separately, though, I’d also argue that our knowledge of arithmetic is reliable—or rather, that it must be assumed to be reliable in order to have any coherent conversation whatsoever, including the conversation that you and I are having right now. (E.g. if 1+1=1 then there aren’t even two separate parties to this conversation, so how is it a conversation at all? 🙂 )
Comment #16 December 26th, 2017 at 2:09 am
I fear that journalists will use these open threads to exploit Scott. He can’t but stop and help someone in need. That’s his innate nature.
Comment #17 December 26th, 2017 at 2:26 am
Umm, not really a classifieds post but wanted to point out that the facebook likes and shares counts of the blog posts are always the same. Probably an easy fix or you could just remove the wrong count.
Comment #18 December 26th, 2017 at 5:52 am
venky #16: LOL
Aravind #17: Y’know, you’d think writing a plugin to count number of Facebook shares would be pretty straightforward, yet I’ve had endless trouble with that plugin, including the counts resetting themselves (in some cases, from over a thousand back to zero) and taking forever to load. Can anyone suggest a better plugin?
Comment #19 December 26th, 2017 at 5:53 am
I am a postdoc in logic somewhere in Benelux. If there are readers around the area who want to grab a coffee, drop me a line (rot13): srqrevpb.snebyqv@htrag.or
Comment #20 December 26th, 2017 at 7:38 am
Hey, you’re the one who stole the penny, not me… 🙂
Comment #21 December 26th, 2017 at 8:26 am
xyz #20: Welcome to my life. I spend my time answering people’s questions, even in threads that weren’t designed for that, and even when the thanks I get is replies as on-point and comprehending as “I know you are but what am I?” This “stealing a penny” thing seems pretty important inside your head, but if you have an argument against something I said about firewalls, then please spell it out explicitly, in a way that engages whatever it is that I said. I make no apologies for assuming the (quantum polynomial-time) Church-Turing Thesis when and if it’s potentially relevant to something else, as long as I tell you I’m doing it.
Comment #22 December 26th, 2017 at 9:38 am
Sorry if I caused offense.
The point I was trying to make is that you seemed to be skirting around the profound implications for physics of considering mathematics to be a physical phenomenon in much the same way that Strong AI skeptics so often skirt around the profound implications for physics of postulating physical entities that escape Turing equivalence. I suppose I was being a bit cheeky.
Comment #23 December 26th, 2017 at 10:35 am
xyz #22: There are many possible grounds on which you could dispute the Harlow-Hayden argument. But I really don’t think it depends at all on whether “mathematics is a physical phenomenon” (whatever that means), or any other such imponderable.
As far as math is concerned, all the HH argument (with my strengthening of it) really assumes, is that problems like inverting arbitrary injective one-way functions are indeed exponentially hard in our universe.
Now, setting aside the philosophical question of why such problems “should have” been exponentially hard, that they are hard seems empirically like a pretty plausible assumption. (Note that it’s the assumption on which we base essentially all modern encryption, so it’s apparently good enough for that! 🙂 ) All HH are saying is that, if you believe the other steps in their argument, then either that assumption is wrong, or else decoding the Hawking radiation (in the way the AMPS suggested would create a firewall) can’t be done within the black hole evaporation time, at least for a “normal, astrophysical” black hole that’s not pre-entangled with a reference system.
Comment #24 December 26th, 2017 at 2:21 pm
Hey,
I’m seeking to perform freelance software engineering services. If it helps, I have a smidgen of quantum computing experience (https://gist.github.com/JamesCropcho/286c4c17cd5861e87e9cfbd99409e82b), although fully expect most needs to be non-QC!
Could be New York-based, or remote.
Clicking on my name takes one to my LinkedIn profile. Kindly send me a message on there if you have a lead or directly need my expertise.
Sound good?
―James
Comment #25 December 26th, 2017 at 6:50 pm
Well, may as well repost what I posted on SSC’s classifieds thread about me looking for jobs (programming jobs, primarily, since the academic job search has not worked out thus far).
Then later I’ll make another post about some math problems because that’s more fun. 🙂 But first this! Original post follows:
I’m looking for programming jobs at the moment. Background is primarily in math (in which I have a PhD — pure stuff, not applied); not much experience programming professionally (<1 year) but I’ve been programming in one form or another for my own purposes since I was a kid (on a much lesser scale, obviously, but still). Since people always ask about languages… for my own stuff I usually use C or Haskell (a big part of my thesis was algorithmic, I implemented it in Haskell); and profesionally I’ve used MUMPS, C#, Javascript. But, c’mon — I’m a smart guy, I understand programming, I’ll pick up anything you throw at me. And with my background in math I’m good at making sure truly every case is covered and at spotting edge cases before they become a problem.
Also I realize like everything is web these days but I’m hoping to find something that avoids that; I guess that means I’m looking for what they call backend work. Basically — I like computation, taking a bunch of bytes and turning them into a specified other bunch of bytes. Precise things, where you can say for a fact whether you’ve gotten it right or not, you know? I am trying to avoid things that are too fuzzy, where correctness is a matter of guessing and judgment.
Currently living in Ann Arbor but willing to relocate. If you think I’d be useful to you or you want to know more, let me know; email address is unygzna@hzvpu.rqh (rot13’d to stop spam).
Alternatively, if you think you could use a mathematician (who to be clear has basically no knowledge of any applied math) for some other job, you can let me know about that as well!
[Actually, let me add something here, since people here do more math/CS than on SSC and might be interested in knowing what sort of math I do. Well, you can see my website, but basically I’ve got two projects going at the moment. One involves studying the complexity of computing natural numbers in some weak computational models, and a curious well-ordering phenomenon that results from such; and the other involves doing some computations with ordinals and well partial orders because why not it’s fun. Basically, everyone seems to think I’m a logician even though I know very little logic in the proper sense. I personally tend to think of myself more as a sort of weird combinatorialist (who has occasionally tried to pass himself off as a computer scientist for job application purposes 😛 ), but I’ll admit my work often doesn’t classify well, what can I say.]
Anyway, thanks to anyone who has anything for me!
Comment #26 December 26th, 2017 at 7:31 pm
Traditionally, optics had been classified under classical physics, but when mapping all knowledge, I decided that classification wasn’t correct, in the sense that it doesn’t cleanly ‘carve reality at the joints’. I ended up classifying optics as part of quantum physics. Surely it’s more useful to say that optics is indeed part of QM Scott?
My justification is that in terms of *practical* applications, applied QM is mainly about the manipulation of light and you need the principles of QM to understand it – Lasers, Holograms, Radar, Radio Waves etc.? Diffraction, refraction of light etc. are wave effects, and therefore shouldn’t light be considered a QM phenomenon?
—
#14, #15
Philosophy of mathematics again 😉 I’m trying to apply the ‘Sean Carroll’ test to philosophy from now on… I think Sean’s right….what really matters is whether the philosophy has *utility* , in the sense that it’s a *useful* aid to scientific understanding. Otherwise it’s not that important.
It does seem useful to broadly recognize 3 general classes of ‘things’ – mathematical, material and mental. Trying to define away or reduce these 3 to 1 in my view really impedes scientific progress , so recognizing the 3-level split passes the Sean Carroll test – it’s useful.
Now the relationship between these 3 classes is confusing, has been argued about by philosophers for millennia, and, I freely admit, is beyond my understanding to resolve. And it’s probably not necessary to resolve it if one is a scientist.
The 3 classes are closely related at the very least, and *may* all in some sense be *physical* (whatever that means). For each of the 3 classes, there’s various positions one could take along a scale from non-realist at one extreme to Platonist or outright dualist at the other.
In terms of philosophy of mathematics, a reasonable compromise is to grant that at least *some* mathematical objects are objectively real, but that these objects are somehow embedded in the physical world (weak realism).
My understanding is that you can arrange mathematical objects into a hierarchy, from least to most abstract, and as you start to move up the scale of abstraction, it gets less and less clear whether the mathematical objects are actually referring to something physical, or whether they’re just a useful language invented by us. So the question is where you draw the line?
The way I see it, geometry and topology are most concrete subjects, and then you move to the more abstract realms of algebra and number theory. At higher levels of abstraction, universal algebra kicks in, and then at even higher levels of abstraction , mathematical logic (set and category theory).
So there seems to a continuum of levels of abstraction thusly:
Geometry->Topology->Number Theory->Algebra->Universal Algebra->Set Theory->Category Theory
Is this the way you see it Scott?
In any event, for scientific purposes all that’s needed is to recognize that there does seem to be a hierarchy of levels of abstraction, and the actual ontological status of these things might not ultimately be that important, or even have a definite answer at all?
The philosophy is too hard for me to resolve, so I’m happy to leave it to the super-brains. I’m hoping that super-intelligences can clear all this up for us and explain it nicely.
Comment #27 December 26th, 2017 at 11:45 pm
mjgeddes #26: You might say that all physics is quantum physics! If we need to make a principled distinction, though: there’s the physics where we need to remember that the state of the world is a vector in Hilbert space, and then there’s the physics where we can approximate everything by fields and particles wiggling around in 3-dimensional space. Piotr Migdal’s game does a wonderful job teaching about interference, beamsplitters, and phaseshifters, all important for quantum optics—but on the other hand, one of the reasons why it actually works as a game is that it restricts itself entirely to the latter kind of physics.
Comment #28 December 27th, 2017 at 12:51 am
#27
Well yes, I think that’s right, *all* physics is indeed quantum physics in the sense that QM appears to be the fundamental (bottom) level. But again….we can still make useful divisions into various levels of abstraction.
I think the principled distinction I want to make is between the level where you see coherent behaviour (explicit quantum superposition effects) and the level where you don’t. So for instance, things like superconductivity or superfluidity I’d call quantum , whereas billiard ball motions not. Or perhaps, the most useful distinction is between the level where thermodynamics applies (classical) and the level where it doesn’t (quantum)?
To me, the distinction you made sounds like the one between mathematics and physics 😉 Vectors and Hilbert space , aren’t these *mathematical* objects? Here’s where philosophy is rearing it’s diabolical head again you see! Vectors and Hilbert space seem like they’re part of Algebra and Functional Analysis (branches of mathematics rather than branches of physics).
The difficulty is that no one seems to actually know what quantum physics is actually *referring to* (in the sense of the actual objective ontological entities involved).
So after me dissing philosophy, suddenly it’s come roaring back into the conversation lol, the old hoary question of how we should actually interpret the quantum mechanical wave function. Is there something *physical* to which the wave function is *referring*, is the wave function itself the actual reality? Or is it simply a mathematical device recording our state of knowledge?
Comment #29 December 27th, 2017 at 1:10 am
So since this apparently also a legitimate use of this thread, I’m going to use this to attempt to draw some attention to some math problems, falling outside my main research projects, on which either: (1) I’m basically stuck and don’t really expect to make further progress, or (2) I’m asking something that’s way beyond me and have not actually made any serious attempt to solve the problem but am asking anyway. These problems are likely hard, to be clear! Admittedly, the extent to which you should take “I find these problems hard” as evidence of “these problems are hard” is unclear. Still, my assessment is that these problems seem hard.
(Also, I don’t think any of these are well-known problems or have anything really out there written about them, but it’s not like I’ve tried to do much in the way of a literature search here; I could be wrong.)
I’m just going to write some short summaries here; details will be in links.
Problem 1: A greedy coloring of the natural numbers
This problem is due to Joshua Zelinsky. Here’s an old unsolved problem: Is there a finite coloring of the positive integers such that for all (n,m)≠(2,2), n+m and n*m get different colors? My understanding is that the expected answer is no.
Josh asks the following variant: Say we greedily color the positive integers so as to satisfy this constraint. I.e., are colors will be the positive integers, and we will color them in order, assigning each the lowest color we can so as to be consistent with what’s been assigned so far. Can we at least show that this particular coloring uses infinitely many colors?
I’ve written a little more about this problem here, in which I also describe some other patterns appearing in this coloring that I’d like to see proven.
Problem 2: Playing Snake on finite graphs
Let’s say we consider the game of Snake, but instead of playing on a grid, we play on an arbitrary finite graph. For which graphs does the player have a winning strategy?
Well, if H is a spanning subgraph of G, and H is winnable, then so is G. Therefore it makes sense to focus on the minimal winnables, thus that become unwinnable when any edge is removed. I’ve found three (or, depending on how you count, five) families of minimal winnables. And, on graphs of 8 or fewer vertices, I’ve manually verified that these are all. Unfortunately my method just becomes too difficult to carry out once you go up to 9 vertices.
Question: Are these really all the minimal winnables? Frankly, it seems ridiculous that they should be — there’s no way I’m calling the idea that they are a conjecture — but I don’t have a counterexample.
I’ve written more about this problem, and some other questions we can ask about Snake on graphs, here. (I also have more notes on this problem that I haven’t posted to the internet, if anyone is really interested…)
Problem 3: What if we redid homotopy theory?
This one’s an open-ended problem, and one I’m not remotely qualified to answer; this one falls under category (2) above. I’m just going to point to where I asked it on MathOverflow here.
Problem 4: The classical analogue of PDQP
This is one I can’t point you to a webpage for but have written about before in the comments here, so I’ll link to that. 🙂 I’ve also asked Scott, and Adam Bouland, about it before — so who knows, may want to talk to them, maybe they’ve done more with it that I don’t know about — but I feel like it’s worth publicizing again. 🙂
Basically: In this paper, Scott, Adam Bouland, Joseph Fitzsimmons, and Mitchell Lee introduced a model of computation where we imagine we have a quantum state we are working with, only in addition to being able to measure parts of it in the ordinary way, we are also allowed to do magical “non-collapsing measurements”. They pointed out that, among other things, in this model, all of SZK can be solved in polynomial time (SZK⊆PDQP), the collision problem can be solved in constant time, and the unstructured search problem can be solved in time O(n^1/3) while requiring time Ω(n^1/4).
In the comments on this post, I noted that we can define a classical analogue of this model, in which we work not with a quantum state but an ordinary classical probability distribution (on which we can perform magical “non-destructive samples” 🙂 ); and that much of what was in the paper above doesn’t actually depend on the quantum aspects and so is still true in this weaker model. In particular, even without the quantum aspects, SZK is still polynomial-time (thanks to Adam Bouland for that observation), and the collision problem is still constant-time.
But what about the search problem? I have an algorithm in this model that shows that it’s at most O(n^1/2). But can we get any corresponding Ω(n^1/k) lower bound?
What with me not really being a complexity theorist — this is another one from category (2) — I thought I’d post it here (again 😛 ).
(Maybe I should ask this one on cstheory.stackexchange? I hadn’t really considered that until now…)
Comment #30 December 27th, 2017 at 1:12 am
Quick edit: I said above that “these problems seem hard” but it seems likely to me that question #4 would not be that hard to a complexity theorist! But I can’t claim to know the area that well. Number 1 and 2 though, certainly seem hard based on my own experience and just the general hardness of arbitrary number theory/combinatoics problems (these are in category (1)), and #3 seems hard because hardly anyone answered when I asked it on MathOverflow. 😛
Comment #31 December 27th, 2017 at 1:15 am
Edit again: Argh, also I guess I misstated #4, seeing as we already know it has to be Ω(n^1/4) because that’s the lower bound when we do allow quantum stuff. So: Can we get a lower bound on the time that’s better than what we know how to get in the quantum case? That’s more like the question I intended…
Comment #32 December 27th, 2017 at 2:56 am
mjgeddes #28: I mentioned mathematical concepts only because they’re the language in which physics is written, not because of some ontological commitment about their physical reality. (Strangely, commenter xyz seems to have had the exact same confusion.) I’ve noticed that my physicist friends don’t even blink if you talk about the state of a physical system being a unit vector in Hilbert space.
Yes, superfluidity is a “quantum phenomenon,” but so is the solidity of ordinary matter (which is largely due to the Pauli exclusion principle)! So there’s a slippery slope here, where the “quantum” part of physics will keep threatening to swallow all of it. The way I draw the line is by saying: there are physical systems that we can efficiently simulate on a classical computer, basically just by keeping track of what’s happening at each point in 3-dimensional space. And then there are physical systems that we can’t simulate that way.
(Note that there are some systems that are clearly “quantum” even by my criterion, but that can still be simulated efficiently on a classical computer, by switching to a more clever representation. Stabilizer states are one example.)
Comment #33 December 27th, 2017 at 11:01 am
Scott #27, I quite expected that my #3 would languish, and indeed it has. No takers for me. But relative to your saying “that all physics is quantum physics!”, you could discover that quantum optics is also equivalent to a random field theory (in the sense that one can use a twist operation to construct a random field theory as a subalgebra of the algebra of raising and lowering operators of quantum optics) by letting me send you the prospective v3 of that paper. The quantum optics algebra of observables is obviously different from the random field theory’s algebra of observables, but the same Hilbert space supports representations of both algebras.
Or someone else. My e-mail address: peter[dot]w[dot]morgan[at]yale[dot]edu (so anyone at Yale especially welcome). Another day, another classified ad (the classified rates are very reasonable here, I must say).
Comment #34 December 27th, 2017 at 12:09 pm
The big paradox with the concept of physical reality:
Consciousness is what’s at the very bottom of our experience, but we assume that there is something even lower than consciousness, something outside of it, which we call physical reality (that’s a reasonable assumption, although humans don’t always agree with each other on what “reality” is).
But we can only perceive physical reality indirectly, as content in our sphere of consciousness.
And the content of consciousness is what comes about from the activity of the brain, as a physical construct sensitive to causal patterns between sensory data. “Looking for causality” is how the brain evolved as a means of survival/natural selection (predicting the future is always good!).
But then there was a leap from “causal” statistical analysis to “hard” logic and mathematics, which is very fruitful (aka physics), but it’s not entirely clear to me whether that leap is necessarily always valid.
Is it possible to imagine a general AI that is much more efficient at predicting the future than we are, yet it wouldn’t rely on logic and mathematics like we do?
Comment #35 December 27th, 2017 at 4:34 pm
Actually, Scott, a thing I just realized last night:
The computation model that’s used to define PDQP, it’s said that solving the collision problem is constant-time in it, and I repeated that statement above (applying it also to the classical analogue); but isn’t the algorithm for this actually logarithmic time, when you keep track of everything? Consider — the final step is to take the results of your non-collapsing measurements on the domain and compare them. But if the domain is of size n, its elements must be of size log n, meaning comparing them takes time log n. In fact really to my mind we ought to count the non-collapsing measurements themelves as taking log n time, seeing as how many bits they’re measuring simultaneously. But even if the model was defined in a way where that doesn’t count, the comparison definitely ought to count, right?
Comment #36 December 27th, 2017 at 6:20 pm
Sniffnoy #29, #35: I like your question about a lower bound for search in the classical analogue of the PDQP model! I conjecture that ~√n should be optimal, just as I conjecture that ~n1/3 is optimal for the quantum version.
Yes, you’re right, the gate complexity of the collision-finding algorithm in the PDQP model is O(log n); it’s only the query complexity that’s O(1).
Comment #37 December 27th, 2017 at 6:29 pm
Scott #36: I’ve written to you and Adam about this before, have you forgotten? 🙂
Oh yeah query complexity. Because the queries are a black box which notionally could take a long time so that’s a thing that it makes sense to look at. I keep forgetting that’s a thing that people care about. So many types of complexity…
Comment #38 December 27th, 2017 at 7:49 pm
Israeli Minister of Transportation Yisrael Katz has announced that a new high-speed rail station in the Old City of Jerusalem will be named after the second most admired man in the world, President Donald Trump.
In fact, since Trump recognized Jerusalem as Israel’s capital. a Trump naming frenzy has swept Israel, with plans to name a street and a park after Trump as well.
Since I get the impression you like Israel, but don’t like Trump, I was wondering what your thoughts were on all of this.
Comment #39 December 27th, 2017 at 7:52 pm
Scott #32
It seems to me that HH unavoidably pulls in the issue of mathematical realism–a mathematical realist would say that the result of the firewall calculation has a reality independent of whether it can actually be computed in the available time, and so the possibility of making the necessary observations should necessitate the firewall’s presence regardless.
The “monte carlo” objection seems to me to be an attempt to show that the reality of the result can’t be contingent on the difficulty one would expect to encounter in deriving it. I think my confusion arises from your observation that getting the result from a “monte carlo” procedure in the available time is of comparable unlikelyhood to the spontaneous appereance of a firewall. I took from this the implication that the two were somehow causally connected–otherwise I’m not sure how that actually answers the objection. Then it just seems like saying “no-one will ever collect the Powerball jackpot, because winning Powerball is less likely than being hit by lightning, so people will always be hit by lightning before they can redeem their ticket.”
Comment #40 December 27th, 2017 at 7:53 pm
@Fred #34:
“the big paradox with the concept of physical reality”
The Veda’s, the spiritual texts of India, say that the physical universe is essentially an illusion , they use the term maya. Which begs the question “what is real ” then. Maybe the weirdness of quantum mechanics is prima facia evidence that our physical realty is a real “illusion” and to try and make perfect mathematical sense out of it (physics, computer science, ect) may be the ultimate fools errand 🙁
Comment #41 December 28th, 2017 at 2:19 am
BTW, Scott, if you’d prefer a complexity-theoretic angle on my problem #2 above, note that if my hypothesis about which graphs are winnable is true (which, again, I expect it isn’t, because it’s ridiculous, but I’ve yet to find what a counterexample might look like), it would mean that the language of winnable graphs, naïvely just in PSPACE, is in fact in NP. 😛
Comment #42 December 28th, 2017 at 5:13 am
Sniffnoy #37:
I’ve written to you and Adam about this before, have you forgotten?
Yes. 🙂 Not because the question is uninteresting, but because my memory is poor and worsening.
Comment #43 December 28th, 2017 at 5:46 am
xyz #39: In that case, I think you just have a factual misunderstanding about how the AMPS paradox works. A firewall doesn’t get created merely because the result of a computation is perceived in someone’s mind, or stored in a computer memory somewhere—that would indeed be bizarre, even more so than what we’re actually talking about! 🙂
Rather, the reason the firewall forms is that an physical transformation was applied to the quantum state of the early Hawking radiation—and because of a holographic duality, that’s equivalent to applying a physical transformation to the quantum state of the black hole.
By using computational complexity, one can plausibly lower-bound the amount of time it would take to apply that physical transformation. But it’s still a physical transformation of an actual quantum state. (And interestingly, even if we assumed for example that P=PSPACE, we’ve been unable to show that applying the physical transformation would be easy. The implication, from HH decoding being easy to solving a computational problem being easy, currently only works in one direction.)
So at the end of the day, just like in any other physics, if you want to change a physical system you have to act on it, not just sit at home thinking about it or simulating it on your computer. It’s just that this particular system—i.e., a quantum black hole dual to its own Hawking radiation—is one of the weirdest ones that physics ever considered.
Comment #44 December 28th, 2017 at 6:03 am
fnord #38: As you’d imagine, I think it’s horrible, and an eternal disgrace that the Netanyahu government allowed it to happen, on top of the much more fundamental disgrace of the Netanyahu government supporting Trump in the first place for craven and short-term reasons.
Maybe I should comment that my feelings about Israel are as complicated as my feelings about the US. Both countries’ foundings are among the most important events in human history for me, Herzl and Ben-Gurion are my heroes along with Adams, Hamilton, Franklin, and Paine, and the survival of both countries is one of the things I most care about. But both countries clearly need to be defended not just against external threats but also against internal rot. Just like I know hundreds of Americans hardly any of whom support Trump, so I know hundreds of Israelis hardly any of whom support Netanyahu. But obviously my sample is biased, because (alas) quasi-democratic processes have brought these opportunistic strongmen to power in both countries.
Comment #45 December 28th, 2017 at 8:11 am
WANTED: Good surveys of interpretations of quantum mechanics. Seeking mid-level between popular and professional, eg Stanford Encyclopedia of Philosophy, any length, moderate math welcome. Must be team player suited to our fast-paced multidisciplinary environment. All submissions will be read with gratitude. EEOE (Equally Epistemic/Ontic Enquirer)
Comment #46 December 28th, 2017 at 8:17 am
I don’t have anything to publicize, but I’d like to take this opportunity to point out that Shtetl Optimized was responsible (at least partially) for my recently landing a job at a big research outfit in Research Triangle Park. I was asked an out-of-the-blue apropos-of-nothing “science geek” question and I drew on some of the discussions here to blow my interviewers out of the water. Thanks, Scott and everyone else!
Comment #47 December 28th, 2017 at 8:18 am
William #40
Yes, and it’s so interesting (lucky for us!) that Schrodinger was so fascinated by those questions
http://www.cortona-india.org/Storage/20101121-2Bitbol.pdf
Comment #48 December 28th, 2017 at 8:30 am
William Hird #40,
“Maybe the weirdness of quantum mechanics is prima facia evidence that our physical realty is a real “illusion” and to try and make perfect mathematical sense out of it (physics, computer science, ect) may be the ultimate fools errand”
This seems like the exact opposite lesson. The mathematicis of quantum mechanics has been enormously successful in understanding things on a small scale, with many modern technologies relying on that (e.g. anything with lasers and most modern electronics). If anything, this shows us that the use of mathematics to understand things taken together with empirical observation of the universe is a really good combination and much stronger than anything else.
I could easily imagine someone in 1700 just as people are really starting to realize that Newtonian gravity implies something like chaos for very long-term predictions of orbits saying something very similar to what you have said about gravity. I’m curious what you would say to that person.
Comment #49 December 28th, 2017 at 8:49 am
fred #34’s ‘causal statistical analysis’ reminded me of Scott’s proposal/challenge to develop a theory of causal computational learning from some time ago. Well, is there any status update on it, anyone?
Comment #50 December 28th, 2017 at 10:48 am
Bob Strauss #46: Awesome, enjoy your new job, and you’re welcome!!
Shtetl-Optimized: Helping people get jobs since … well, you may have actually been the first. (Or was that me?) 😀
Comment #51 December 28th, 2017 at 10:56 am
Ashley #49: Alas, nothing worth writing about. I had some ideas about learning an unknown circuit via “injection queries” (i.e., causal interventions), but I then discovered that I’d basically just recapitulated some of the 2006 work of Dana Angluin and her collaborators. Between writing about it and now, I also met Judea Pearl and had a lovely conversation, but we didn’t manage to discuss anything substantial about the prospects for “causal COLT.” In the meantime, the deep learning revolution has happened, and reminds us that learning theory is hopelessly behind practice even just in understanding, explaining, and predicting the successes of non-causal kinds of machine learning. Which, of course, presents an opportunity for ambitious theorists.
Comment #52 December 28th, 2017 at 2:16 pm
@ William Hird #40
Please note that “beg the question” doesn’t mean “raise the question.” It means “presuppose or assume the premiss of an argument.”
Comment #53 December 28th, 2017 at 2:57 pm
@Joshua # 48:
Sounds like you are forgetting that no one can give a simple explanation for the double slit experiment and that no one can give a simple explanation of why two magnets attract or repel each other (action at a distance, see the Richard Feynman YouTube video where he says he cannot give a simple explanation of why magnets work). If one of the greatest physicists of the 20th century cannot give a “laymans” explanation of action at a distance, then I “don’t have to” explain anything about physics to someone from the 1700’s 🙂
Comment #54 December 28th, 2017 at 3:48 pm
Joshua #48
“The mathematics of quantum mechanics has been enormously successful in understanding things on a small scale […] the use of mathematics to understand things taken together with empirical observation of the universe is a really good combination and much stronger than anything else.”
When people bring up “QM mathematics does work!”, I ask – okay, but what would be the alternative?
If I try to imagine some system where “things” happen, but mathematics would have no power of explanation, e.g. there is simply no causality or apparent logic between events, no matter how closely you look at them. So “things do happen somehow”, but we don’t know why and will never know why.
One definition for this could be “magic”…
But isn’t this also exactly the definition of the kind of “randomness” that’s at the very core of QM?
So, I could equally say that QM also strongly suggests that mathematics does not always work to describe reality.
Comment #55 December 28th, 2017 at 3:58 pm
I guess one could say that QM randomness sort of vanishes if you consider multiverse theories – all the alternatives exist at once.
But, still, why are we subjectively experiencing one particular branch and not another?
It’s the same massive asymmetry that’s also (apparently) at the core of the consciousness of the self:
Why am I, at this moment, experiencing the life of a particular human, among the millions of trillions of other humans, animals, aliens, conscious AIs who have ever existed, exit, or will exist, anywhere in the known universe?
Comment #56 December 28th, 2017 at 11:09 pm
fred #55: I will not claim to have the answer, but I love thinking about such questions and I would like to suggest a possibility. Perhaps we have obtained some success with making predictions in spacetime coordinates precisely because they are not the primary coordinates of our experience. Perhaps, in our primary coordinates, each of us is “stuck” with experiencing (1) as a particular conscious entity (2) from a particular branch of a multiverse. Moreover, “each of us” may exist only because of such coordinates: some coordinates holding their own with spacetime, and at least as fundamental. In such a situation, with seemingly no direct navigation in these coordinates available (because consider, if you were to skip to an adjacent branch, your brain and the information physically stored by it would, I’d think, reflect the causal chain of events in that branch, and have no reason to carry a dissonant story of your “original” branch), perhaps we have not bothered to consider (much) such coordinates. Our bodies are spacetime-navigating machines, so why would we have?
Comment #57 December 29th, 2017 at 1:12 am
William Hird #53: Feynman was fond of making comments to the effect of “nobody understands such-and-such.” And yet, I think it’s fair to say that he understood magnetism a lot better than you do, and you in turn understand it better than a caveman.
In science, there’s almost never “the” explanation of something, what there is instead are layers of deeper and deeper understanding.
A child, who learns that opposite poles attract and likes repel, and that the effect is strongest when the poles are close, already understands something about magnets. Faraday understands more, and Maxwell more still. Crucially, at this point you’re no longer talking about instantaneous “action at a distance,” but only about effects propagating through an electromagnetic field at the speed of light. This field is as real as anything else, even though we directly perceive it only when there are the waves in it that we call visible light.
With Einstein, you get a deeper understanding still, because now you know something about why magnetism has to exist: it’s just an inevitable logical consequence of the electrical (Coulomb) force combined with the Lorentz invariance of spacetime.
OK, but why should there exist an electrical force? Well, one can dig deeper on that too, talking about QED and virtual photons and U(1) gauge symmetry, which are certainly things that Feynman understood.
Ah, but why should there have been a quantum field with U(1) gauge symmetry? Why should the world have been quantum-mechanical or Lorentz-invariant at all? There will always be some point at which the current understanding bottoms out. Indeed, if we knew why the world was quantum-mechanical or Lorentz-invariant, someone could next inquire about the cause of that, and so on forever.
But to my mind, the central insight that’s powered the scientific revolution, and by extension the modern world, since the time of Galileo is that you don’t have to understand everything in order to understand something.
Comment #58 December 29th, 2017 at 8:20 am
Scott #57
“But to my mind, the central insight that’s powered the scientific revolution, and by extension the modern world, since the time of Galileo is that you don’t have to understand everything in order to understand something.”
Why start with Galileo though?
Why not go further back and include way older astronomical knowledge, like eclipse prediction (dated back 2000 years at least, in many civilizations).
Also, shouldn’t engineering also be included as clear evidence of humans leveraging partial understanding of their environment using the scientific method? E.g. roman civil engineering, Antikythera mechanism, etc.
Comment #59 December 29th, 2017 at 9:22 am
Scott # 53:
I agree with your comment, but does it throw any more light on my point about the Vedic concept of the physical universe being some kind of illusion(Maya) to our mortal conciousness ? Sorry, but I think not. If you want to “wait it out” for a maybe deeper ,more mathematically precise understanding of physics that is going to take away all the weirdness of quantum mechanics, I will not be going on that train with you, although you are one cool cat and I would thoroughly enjoy the company of your keen intellect. I will stick with the Vedic description of reality and “wait it out” until that day when God shows me Herself how the trick was performed . OM 🙂
Comment #60 December 29th, 2017 at 11:20 am
fred #58: Indeed, I hesitated when I mentioned Galileo, because there were many people before him—the greatest of them Archimedes—who demonstrated through their actions and discoveries that they at least implicitly understood the scientific way of thinking as well as anyone today.
But I stuck with Galileo for two reasons. First, he represents the point at which the scientific way of thinking not only got discovered, but stayed discovered! Second, and more importantly, his dialogues are possibly the first place in history where the scientific attitude gets explicitly explained, modeled, and defended in modern terms. Not only that, but he even puts William Hird’s view—all physical appearances are mere illusions, only God truly understands anything, etc. etc.—into the mouth of Simplicio, only to have Salviati poke fun at the view and reject it. (Until Galileo makes Simplicio “triumph” over Salviati in the very last pages, because he overoptimistically thought that might appease the Inquisition…)
Comment #61 December 29th, 2017 at 3:17 pm
I’m a highschool student looking for internship opportunities of any sort in STEM. I’m very interested in quantum computing in particular, but again, anything would be cool.
I have a decent grasp of Python and have some projects on Github. I’ve taught myself the basics of calculus and linear algebra, as well as some basic mechanics from Hewitt’s Conceptual Physics. I have some limited experience soldering and with electronics, with Linux, and with the Arduino.
I’m currently working on a personal, unaffiliated-to-any-university research project on spontaneous parametric down conversion. I’m willing to learn anything necessary.
I am located in central Iowa. If you’re interested, my name links to my physics stack exchange profile; ping me in a chatroom or comment there.
Comment #62 December 29th, 2017 at 9:34 pm
Scott #32,
Well, as a knowledge representation project, over the course a year or two, I mapped all explanatory knowledge using wikipedia. I just know that a superintelligence is going to whip through all the knowledge domains in a few days (like Alpha Zero for chess) , and probably do the mapping to vastly better ‘resolution’ than me too. But already I found some very interesting patterns.
It does seem that you can ‘carve reality at the joints’ at certain points where new distinct levels of abstraction emerge, in the sense that there are new levels of explanation that seem to be heavily ‘insulated’ from the levels below. And there seems to be a clear pattern of a 3-level fractal splitting.
For instance, in the domain ‘Physics’, the 3-level splitting is quantum physics, classical physics (thermodynamics) and cosmology. It’s odd that there seems to be 2 clear boundaries where you can draw lines – the classical layer does indeed seem to be heavily insulated from the quantum layer. Look at my classifications:
Quantum layer:
https://en.wikipedia.org/wiki/User:Zarzuelazen/Books/Reality_Theory:_Quantum_Mechanics
Classical layer:
https://en.wikipedia.org/wiki/User:Zarzuelazen/Books/Reality_Theory:_Classical_Mechanics
Cosmological layer:
https://en.wikipedia.org/wiki/User:Zarzuelazen/Books/Reality_Theory:_Cosmology%26Astrophysics
I know that the quantum layer is supposed to be the fundamental one, but the split into 3 ‘clean’ levels of abstraction is odd. To my way of thinking it introduces a little bit of doubt about reductionism (the idea that the higher levels of abstraction are in principle entirely reducible to the lower levels).
Comment #63 December 30th, 2017 at 5:00 am
BQP is in AWPP and AWPP in P/poly implies BQP in P/poly but NP and PP are ok. What does this give?
Comment #64 December 30th, 2017 at 5:24 am
. #63: I don’t understand the question. Yes, if AWPP⊂P/poly then BQP⊂P/poly whereas it’s not known if NP or PP is in P/poly—although I believe PromiseAWPP⊂P/poly would give you PP⊂NP/poly and hence a collapse of PH.
Comment #65 December 30th, 2017 at 4:03 pm
Noob, LLC #45: I know little about Bob Doyle or why he started his project, but your question
begs to be answered by a link to his his surveys. It is also a good source for original material, which is often illuminating.
Comment #66 December 30th, 2017 at 6:38 pm
Scott, you seem to admire Steven Pinker, you had problems with SJW attacks for your now famous comment 171 and, if I remember well, you said you have some “heterodox” ideas that you think it’s dangerous to make public. Why aren’t you in the Heterodox Academy? Didn’t you know about it?
Heterodox Academy is an organisation of professors, adjunct professors, post-docs and graduate students who are for freedom of speech, founded by Steven Pinker, Jonathan Haidt and a few other academics, and now has over 1000 members.
https://heterodoxacademy.org
(I’m not a member, because I’m not an academic or graduate student, but I sympathize very much with their fight to protect freedom of thought.
Sorry if I made any mistakes, English isn’t my first language.)
Comment #67 December 31st, 2017 at 1:09 pm
William Hird #53,
“Sounds like you are forgetting that no one can give a simple explanation for the double slit experiment and that no one can give a simple explanation of why two magnets attract or repel each other (action at a distance, see the Richard Feynman YouTube video where he says he cannot give a simple explanation of why magnets work). If one of the greatest physicists of the 20th century cannot give a “laymans” explanation of action at a distance, then I “don’t have to” explain anything about physics to someone from the 1700’s”
Not my point. My point is that someone in 1700 could have made the same claim you are making about chaotic orbits. And they would have been wrong. So what is different about your argument and their argument?
Comment #68 December 31st, 2017 at 11:42 pm
Scott #57, #60
I wish everyone would stop heroworshipping Galileo for his antisocial personality. Admire his scientific accomplishments, but not his deliberate attempts to fight with and offend people.
Comment #69 January 1st, 2018 at 6:38 am
Oh NP is not in AWPP? BPP is in AWPP. If BPP=P then can AWPP still contain NP (for now it might since BPP in Sigma2)?
Also why does zoo not have BQPP(quantumPP)?
Comment #70 January 1st, 2018 at 6:39 am
Oh NP is not in AWPP? BPP is in AWPP. If BPP=P then can AWPP still contain NP (for now it might since BPP in Sigma2)?
Also why does zoo not have BQPP(quantumPP) and BQParityP(quantumParityP)?
Comment #71 January 1st, 2018 at 8:26 am
Thanks Piotr Migdal for the wonderfull quantum optics puzzle game!
…but could anyone provides some hint for pb #34? 😉
Comment #72 January 2nd, 2018 at 3:56 am
I’m new to the blog, so I apologize if this question has been addressed before or is otherwise dumb. I’m wondering if finding good designs for quantum computers might be one of the tasks that quantum computers have an edge in? Ostensibly they are going to be better at simulating the relevant processes, which might allow for a kind of bootstrapping of better and better designs as the computers improve. For example, we know light-harvesting complexes in plants exploit quantum effects, but likely there are undiscovered molecular structures that can outperform the ones currently used in nature. Maybe nature hasn’t found them yet because evolution is restricted to classical searching, but we could improve on that?
Comment #73 January 2nd, 2018 at 8:32 pm
Perhaps a silly query?
Comment #74 January 3rd, 2018 at 12:53 am
. #70: No, NP is not known to be in AWPP (and there’s an oracle relative to which it isn’t, based on the √n lower bound on approximate degree of the OR function), although I believe NP is in BPPPromiseAWPP. If so, then under derandomization hypotheses it’s in PPromiseAWPP, although I don’t know of a direct implication that P=BPP would have on this.
BQPP is just PP. I’m not sure what BQParityP would mean—did you have something in mind? In any case, I haven’t really been updating the zoo since 2004 or so—if you think classes are missing, please add them yourself!
Comment #75 January 3rd, 2018 at 1:05 am
zooid #72: Yes, I think there’s every reason to expect that building a scalable QC would help with some of the problems involved in building scalable QCs. 🙂 Mostly this is because you’d now have a quantum simulation capability, and wouldn’t have to resort to small-scale classical simulations to try to understand, e.g., the behavior of fault-tolerance schemes under realistic noise. But my favorite implication in this direction is that, with certain discrete quantum gate sets related to algebraic number theory, we know how to find the optimal gate sequences to generate 1-qubit rotations in polynomial time—if a fast factoring algorithm is available!
Comment #76 January 3rd, 2018 at 12:52 pm
Scott #75:
Could you give a link to this result? I don’t doubt that the optimal gate sequence generating algorithm runs in polynomial time iff the factoring algorithm it uses runs in polynomial time, but I do doubt that the distribution of numbers to be factored is such that a quantum factoring algorithm would be faster than a classical factoring algorithm for any practically feasible input size.
Comment #77 January 3rd, 2018 at 2:41 pm
Aula #76: Here’s the paper.
Comment #78 January 7th, 2018 at 6:37 pm
I’d like to place a want ad: I’m working on a book to explain QM to a lay audience. The basic approach is outlined in this paper:
http://www.flownet.com/ron/QM.pdf
and a draft first 1.5 chapters can be found here:
http://www.flownet.com/ron/edges.pdf
I’m looking for someone who really understands this stuff to look over my shoulder and make sure that I get the math and other technical details right. I’m willing to pay.
Comment #79 January 8th, 2018 at 5:44 pm
Happy New Year’s to the Shetl-Optimized community! I hope everyone had a wonderful holiday season!
I am embarrassed by my slowness to comment on this post– as I think that part of Scott’s graciousness here is due to my unusual outreach to him right before the holidays.
My name is Andrew Hartford. I’m currently running to represent New Jersey’s 12th Congressional District as the youngest member in the 2018 United States Congress (I’m 26). Rather than sharing excessive detail, I invite you to check out my website @ http://www.andrewdhartford.com.
The 1st person I reached out to about my campaign’s work plan was Scott. He has been a real intellectual hero of mine the past few years, as through and after graduating law school, I have become obsessed with the more technical aspects of this World. But more importantly, it was because I know how influential Scott is in the community of public intellectuals and I thought he could kickstart the effort (which is way more important than me)!
I have been frustrated with the rate of problem solving in DC, and also with how behind the 8-ball our country has been. I’m concerned that our current thinking (and prioritization of agenda items) is reactive, rather than strategic and focused. In a sentence full of bitter irony: today’s politics is backwards because we are not solving problems backwards– seeing the solution first (i.e. the chess board after the 20th move), and deriving the best path to achieve it (i.e. the correct order of moves 1-20).
Politicians have become very intellectually lazy and remarkably superficial. The vast majority simply engage in the process of “checking the boxes” of a party platform which they themselves do not contribute to building (or thoroughly understand the modern mechanics of). In a pragmatic sentence: America needs a public leader that can help produce an end-to-end detailed playbook, something which can provide the United States with a focused direction and a renewed purpose for the decades to come.
Towards achieving such, I have put together the open-source “Problems Of Our Time” competition (see https://www.andrewdhartford.com/uploads/2/0/5/0/20500914/problems_of_our_time__v1.2_.pdf ) as a way to focus my own work plan for the next few years, but also to help focus America’s thinking resources at-large. The inspiration for the endeavor is Hilbert’s 1900 AD problem set, which I think captures something worthy of continued emphasis: humans beings ask the right questions and try to solve them together. That is how we move forward with a focused and efficient direction.
I know that no matter how many good ideas I ever have (or any politician ever has), that the collective intelligentsia will forever be greater and grander. I believe that we need to find a more permanent fixture between the FORMAL public space (i.e. those in the arena) + our American intelligentsia if we are to tackle our existing problems fast enough (and in staying ahead of others on the horizon).
While my own team’s solutions have been in active development the past few years (I work with/am mentored by two friends who are CS profs @ UVA), I seek to attract as much talent as I can in tackling these 23 open problems (note: the last one is an obviously “non-political” question, but I included it to showcase my commitment of America re-entering a renaissance phase + because I want to attract the very smart people outside of “politics” proper to the effort; including, many of the readers of Scott’s blog).
This open-source initiative articulates a real game plan to accomplish our objective (i.e. building an American playbook), and the culminating debate + conference (January 2019) shall yield most productive work product for the public space (if we can get the right people involved). The debate would also be very fun and worthy of media coverage (which is the goal)!
Here is the current roadmap for the event: https://www.andrewdhartford.com/uploads/2/0/5/0/20500914/problems_of_our_time_roadmap__v1.2_.pdf
Here is the problem set: https://www.andrewdhartford.com/uploads/2/0/5/0/20500914/problems_of_our_time__v1.2_.pdf
If you want to be involved as an advisor or contributor, please let me know.
As I like to say: your contributions are helpful, your consideration is appreciated, and your respect will be earned.
Thank you. Best wishes to all of you with whatever you are working on in 2018. Please consider my arguments, the merits of my work plan (esp. relative to other formal public figures), and get involved if you are willing and able. America needs you all more than you might think.
I promise you that I’m trying very hard, and that you will not find anyone in the political theater more passionate and committed to the Enlightenment ideals with which I know many of you hold as foundational.
My Warmest Regards,
Andrew Downing Hartford
andrew.d.hartford@gmail.com
___________________________________________________
As some additional background to those interested:
The 12th district is a real jewel in the heart of Central NJ. It has a wonderful diversity of populations and living situations. It is home to the Institute of Advanced Study, Princeton University, TCNJ, Rider, and many big pharma/bio-tech companies. It also is home to NJ’s Capital (Trenton).
While there currently is a democratic incumbent, I challenge this individual in a heads up race. HOWEVER, it is a +15 D district so my run is not an indulgent act of utter selfishness, but a reasonable one (that we plan to win).
Not only is sub-30 under represented, but it is literally NOT represented. The party that acts first to get the first worthy and marketable young new leader will attract millions to that party in the next couple years.
To those who’s gut reaction is, “why are you challenging a Democrat?” (which is probably much less for the readers here), I offer the following argument: I’m confident that the answer is not simply to win substantial majorities of Democrats in Washington, but it is also necessary (and even more important) that we find 1) a new approach to the process of solving problems of the public space & 2) attract public leaders who are substantively capable of being creative, reasonable, and productive in the modern context of the 21st century.
I think I am such a leader, and therefore, that duty calls.
Comment #80 January 11th, 2018 at 7:56 pm
I have begun live streaming a series of videos teaching programming, aimed at beginners. I am teaching via making a series of small games and game related programs. Free, using free open source, cross platform tools, so anyone with a computer can follow along:
http://gameswithgo.org/
Streams are archived on youtube so you can catch up and then join us on twitch for the live streams. So if you know people who are curious about learning programming, send them over.
Comment #81 January 28th, 2018 at 3:38 pm
I am trying to build a marble computer like digicomp II and others. Like most of my ideas, it has no obvious practical applications (and likely no obscure ones). Check out my blog if you have an interest:
https://marblecomputing.blogspot.com/