Sorry for the high-latency reply. I’m aware of the species problem; in fact Ted Jacobson has a good paper on why it isn’t really a problem: http://arxiv.org/abs/gr-qc/9404039.

Basically you avoid the species problem if you believe that gravity is “induced” as in Sakharov’s approach, or by Jacobson’s approach of deriving gravity from thermodynamics of spacetime.

Another way to avoid the species problem is if gravity and matter are somehow unified, so that the number of species cannot vary. This would presumably be the case in something like string theory, or in a model like the one you developed with Sundance and Fotini where matter content is derived from spin networks.

It’s an old calculation (first due to Srednicki, maybe), that if you divide spacetime into two regions in ordinary QFT, the entanglement entropy is proportional to the area of the boundary. This is because you have to cut things off, and the entropy is dominated by the short distance contribution around the boundary. It’s not at all clear that this has anything to do with the usual notion of black hole entropy, however.

I think Srednicki was the first to do this, although there is an earlier paper by Bombelli et. al. where they derive a similar result for a half-plane instead of a sphere: http://prola.aps.org/abstract/PRD/v34/i2/p373_1.

There is also a paper by Rafael Sorkin, where he proves that the entanglement entropy satisfies a generalized second law. http://arxiv.org/abs/gr-qc/9705006. So the entanglement entropy
- Is a well-defined entropy coming from a coarse graining of the spacetime into two regions defined by the event horizon
- scales like the area (assuming a short distance cutoff)
- satisfies the generalized second law of thermodynamics
I would say that the evidence is pretty good that it has something to do with the macroscopic definition of black hole entropy.

Perhaps the comment is famous because many find it dumb. I think computer science is inextricably tied to computers the same way physics theory is inextricably tied to experiments.

Scott Aaronson is my kind of physicist. In all the debates about string theory, he finally decided,
From this day forward, my allegiances in the String Wars will be open for sale to t……

Wow, Fredkin is a “Shor Shorter” (do you have a standard name already?)—he believes factoring and discrete-log etc. are in P! I guess the conversation didn’t extend to whether physically realizing Grover’s O(\sqrt(N)) time is compatible with his “linear speed-up theorem” (has anyone seen a “proof” of that?), which is kind-of what I was asking.

I meant to clarify that “observing the lottery winner” included doling out the N tickets to begin with. I.e. is “preparing” a Grover-type problem symmetric with the effort of solving one? Call the winning ticket “black”, the rest “white”. Suppose first that you have N different spatial locations, in a square in 2D space or etc. If you have to deal a white or black ticket to each, I guess that means at least N units of effort, counted serially. But if the locations default to “white”—or if the representation of the problem is more implicit—then since the N possible problem setups max at logN bits of information each, it is not a violation for each to require O(sqrt(N)) or less effort to prepare. What good papers address this kind of information-representation / state-preparation issue, where “linear-vs.-quadratic” not “poly-vs.-superpoly” (like in state-preparation papers I know) is the issue?

I guess that’s enough “talking through my hat” for your blog, thanks! Comments on my quantum-basketball skills (as general science-writing) welcomed… And indeed, I’ve referenced Eppstein’s computer-chess notes myself—they seem to be the only ones that clearly say the nearly-50,000 bits used for Zobrist keys (== subset-XOR hashing) should be random. Many chess engines use PRGs of tiny initial entropy to generate the keys (I have one example on my site; there are more), and I speculate whether that plus their chaotic flogging of open-address hash tables might cause funny effects. They are concrete exponential-time algorithms. Note in my CRC Handbook chapter (27) notes with Eric Allender and Michael Loui on my site, right away we cite the concrete form of Stockmeyer’s “cosmological” lower bound (which we are revising from the recent journal version—it’s under 458 bytes of ASCII text), which is the right way of viewing statements like “chess is NP-hard”.

Or rather, computer science is no more about computers than human anatomy is about stethoscopes. Which is to say that Dijstra is only half right.

There are certainly people who think that Grover’s algorithm can’t be applied to “physical” databases.

I think that that is a strange question. It depends on the meaning of “can’t”. Yes, you could, in principle, but for what purpose? A classical search in an indexed database can be done in logarithmic (or polylogarithmic) time. If there is a fundamental reason that it cannot be indexed, then I am not sure why it should be called a database. I am sure that Grover’s algorithm should never have been described in terms of “databases”, because it is really an algorithm for combinatorial searches.

The Wolfram front has been pretty quiet.

That’s a relief. You know, the best review of Wolfram’s book is a single extra punctuation mark: A New Kind-Of Science.

I wasn’t sure how to continue the conversation after that.

If nothing else, you could have credited him with great candor.

(1) With reference to the advertised tenure-track position in quantum system engineering (see the second comment on this thread) our QSE Group’s newly-posted essay What is quantum system engineering? (click here) is posted in the hope of stimulating strong applicants, mainly by assuring folks that we still get to worry plenty about P vs NP when working as engineers.

(2) Ken Regan’s enjoyable chess-related post encourages me to confess that I too occasionally post P vs NP-related material on the computer chess blogs (click here). My own interest arises from geometric descriptions of interval arithmetic, which is a point of view not too dissimilar from yesterday’s Dowling and Nielsen preprint The geometry of quantum computing (click here).

Evidently, we’re all climbing the same mountain. So, Happy New Year to all, and may we all meet at the summit in fine weather!

A few responses to your first set of questions (I have nothing to say about the other two):

Are there any people who believe in Shor but not in Grover?

There are certainly people who think that Grover’s algorithm can’t be applied to “physical” databases.

Also, it’s possible to define a model of quantum computing — in which the “answer register” starts out in a maximally mixed state — that can implement Shor’s algorithm but not Grover’s algorithm. But I don’t know of anyone who actually believes that model.

How have arguments progressed since your thesis. both on the Wolfram/Fredkin front and interpreting your “quantum robot” D&C result?

The Wolfram front has been pretty quiet. Nothing really new about the quantum robot result either.

I talked to Fredkin a few months ago at Perimeter. He said he believes that P=BQP, and that the universe is a classical, nonrelativistic cellular automaton made of pixels many orders of magnitude larger than the Planck scale. I wasn’t sure how to continue the conversation after that.

Would that extend to say (in any sense) that observing the winner in a lottery with N tickets can be done with O(root-N) units of “effort”?

That’s exactly the content of Grover’s algorithm, and of Andris’s and my spatial search implementation of it.

You might be a philosopher, Drew, but you’re all right. To say I agree with you about computers being “Platonic telescopes” is an understatement. As you might know, Dijkstra reached for the same analogy in his famous remark about computer science, that it’s “no more about computers than astronomy is about telescopes.”

So many people want to uncritically accept anthromorphic reasoning, or reject anthropomorphic reasoning, that the attempt Scott makes to get at the justification of reasoning is a real breath of fresh air. Maybe like C.S. Peirce, they need him over at Popular Science magazine (which I believe was still predicting the flying cars, even in Peirce’s day).

Another note: I disagree with the poster that argues above that it is impossible to know the proof of a theorem from a popularization. If the popularization tells me what is presumed, and that only the rules of some accepted logical system are used, then I want to say I know that theorem — in fact, I might know the theorem better than someone who thought, by her direct examination of the actual steps in the reasoning, that it depended upon the Axiom of Choice, when a more restricted set of axioms would do.

We depend in the modern world on computing machines epistemologically, just as we depend on telescopic machines epistemologically. I have seen craters on the moon, and I have come to know the truth of theorems I could have never proved.