The central reason why scaling is hard is actually extremely simple, and was understood from the very beginning. It’s that sufficiently reliable single-photon sources don’t yet exist. If your sources are unreliable, then the probability of an n-photon coincidence falls off exponentially with n. And that’s exactly what happens in the existing experiments, putting a hard cap on how large n can be if you want to finish taking data this century and within a reasonable budget.

In principle, this problem ought to be addressable through the development of optical multiplexing, or other technologies that could yield much better single-photon sources — in combination with scattershot, and theoretical results about how many losses you can tolerate and still be sampling from an asymptotically hard distribution. And it’s reasonable to hope for further progress in all these directions within the next decade, and to be disappointed if it doesn’t happen (in which case, of course, one will want to understand why). But these things don’t happen at blog speed, and I don’t think there’s any great mystery about why not.

]]>*fluid dynamics (which is in P for any reasonable formalization)*

I almost want to do a King of the Hill: “You’re not proving fluid dynamics easier, you’re proving P harder!”

]]>Maybe this is old hat to everyone else, but this sure seems really cool.

]]>So the question is, given that Q is dense in R, what is the generator of this process (logarithm of the transition function) and resolvent this process (Laplace transform of the transition function)?

]]>With all due respect to your list I think the single most important BS issue that intrigues me is why are people having so much trouble scaling beyond the 4 photon case. I do realize Jushua intended theoretical problems but still I find this part so relevant yet so under-blogged about.

I’m sure the experimentalists are very smart people and that makes the situation even more intriguing.

I wish there was a Scott analog for the experimental side of things who could have educated us on what’s actually going on out there on the experimental front.

Maybe I am just naive but then I’d love some insights into what’s hampering the attempts to even get to 10 photons. Because from what I remember even at 20 photons or so you are already at the limit where you’d be sampling faster than you could calculate and that’d be one fantastic result.

]]>I am more interested (personally) in programming language theory stuff, but this is a fun list. Thanks.

]]>I just realized there is an incredibly deep connection between the theory of Turing Machines and the theory of Stochastic Processes. Specifically a Turing Machine is process adapted to the filtration of the sequence of realized states in the computation. More exactly: let Z be the integers, representing the current position of the tape, S be the possible internal states, and W be the allowed symbols, then the observable measure space is E=Z*S*W. Our filtration on E is indexed by the time step of the computation t, so that F_t is the sigma algebra on all sequences of length t of elements of E. A Turing Machine is then a Markov Process adapted to F_T, giving the probability of the next state E_{n+1} given the current state E_n as P[E_n+1| E_n].

The incredible thing is that statements about P vs NP, and the halting problem then become statements about stopping time random variables, which gives us access to the powerful machinery of generators, resolvents, Hille-Yosida theorem, Feller-Dynkin theorem, and conservation theorems like Feynmann-Kac, Chapman-Kolomogorov. In a way it allows us to define the logarithm of the transition function of the Turing Machine.

Actually now that I think about it we could just let E=Z^3, and then let the probability measure P take care of restricting the symbols and the internal states.

…or I’m completely out to lunch and have been spending too much time reading probability theory.

]]>There’s something fundamentally flawed and circular with a form of democracy that can convict people based on laws that they then aren’t allowed to vote against.

]]>