Quantum Computing Since Democritus Lecture 20: Cosmology and Complexity
Come watch me attempt to explain the implications of a positive cosmological constant for computational complexity theory. If this blog is about anything, it’s about me talking about subjects I don’t understand sufficiently well and thereby making a fool of myself. But it’s also about experts taking the time to correct me. The latter is the primary saving grace.
Follow
Comment #1 August 21st, 2008 at 1:32 pm
Interesting. I wonder if the findability of an object in N dimensions of space given a cosmological constant L is related to the question of whether or not a random walk will return to its starting point. (The answer to this question is famously “infinitely often if N = 3”.)
Comment #2 August 21st, 2008 at 1:33 pm
Ack, HTML ate my comment. “infinitely often if N < 3, and never if N >= 3”.
Comment #3 August 21st, 2008 at 2:38 pm
Just to be contrary (again), I think it is fair to say that the role of holographic bounds in quantum gravity is unclear at the moment. Some of them seems pretty unlikely, in fact, and all of them use concepts that are undefined in regimes where the metric strongly fluctuates (which entropy is bounded by which area if there is no background metric?). In any event, they are far from an established bit of future (or present) theories of QG.
Comment #4 August 21st, 2008 at 3:32 pm
I still don’t buy that positive uniform curvature implies finiteness. Consider a helix.
Comment #5 August 21st, 2008 at 6:26 pm
Scott, classic sequential computation sounds like an extremely unrealistic computational model when you try to build 20 billion light years size computers. The Very Important Spaceship carries the Turing machine’s head everywhere, while the rest of the universe is standing still?
Does it affect the complexity class if you change the computational model to something parallel? I’m thinking of cellular automata, but maybe you have more convenient and/or physically more realistic formalizations for a fully parallel universe-sized computational device.
Comment #6 August 22nd, 2008 at 12:24 am
Oh man, “Brooklyn is not expanding” has got to be one of my favorite lines from any movie ever.
Anyway, I personally consider stuff like this to fall in the domain of physics as opposed to computer science — after all, there’s nothing inherently true about models of computation that means that we can only achieve DSPACE(O(1)) complexity. It’s a physical limitation. That said, good lecture!
Comment #7 August 22nd, 2008 at 8:52 am
Joe: Yeah, I was looking for a proof of that claim, but just found an assertion in the paper by Cornish and Weeks. Is it true for 2- and higher-dimensional manifolds for false for 1-dimensional ones? Mathematicians: please help!
Comment #8 August 22nd, 2008 at 8:56 am
Daniel: Great question! Yes, it does change the complexity class if you allow parallel computing elements. But you then have to ask, how many such elements? And how can they be distributed within the region? We can’t have them distributed in a way that violates the Schwarzschild or holographic bounds…
Comment #9 August 22nd, 2008 at 10:09 am
Scott: I don’t know anything about cosmology, but I’ll try to suggest a simple parallel model, based on the simplifying requirement of “let’s not move stars”.
The distribution of stars and galaxies (hopefully) does not violate the Schwarzschild and holographic bounds. I don’t know what this distribution is, but it is surely well-studied by cosmologists. Whatever it is, we can formally define a parallel computational model by assuming only local, finite interactions on it. The time requirement for any such local interaction is simply the time needed to travel to a neighbouring star, so it slowly grows with each time step.
There may be problems regarding the energy-consumption of such a device, but these problems were not factored into the fully sequential model either, as far as I can see.
Comment #10 August 22nd, 2008 at 3:13 pm
A helix, despite appearances, is not curved. Neither, in the sense we are discussing, is a circle or a cylinder. If you lived on a helix and took measurements along it, you would never be able to tell that you were not living on a flat piece of string. Similarly with a circle or cylinder as long as you never went far enough to wrap around.
By contrast, even local measurements can detect that you live on a sphere. Let R be the radius of the earth. If you stand in a field and measure out a circle of radius r from a fixed point, measuring along the ground, its perimeter will be 2*pi*R*sin(r/R) which is about 2*pi*r – (1/3)*pi*r^3/R^2. So you could compute the curvature of the earth by local measurements. (Of course, this computation assumes a perfectly smooth spherical earth. In practice, you could only measure this if r^3/R^2 was bigger than the local bumps in the country side.)
That said, I don’t know a reference or a quick argument for the fact that uniform positive curvature forces compactness.
Comment #11 August 22nd, 2008 at 4:36 pm
Thanks, David!
Comment #12 August 22nd, 2008 at 5:49 pm
Theorem 19.4 of Milnor’s Morse Theory seems highly relevant.
This implies that a complete Riemannian manifold with Ricci curvature bounded below by a positive constant is compact.
Indeed Milnor explicitly states this as Corollory 19.5
Milnor cites a paper of S. B. Myers “Riemannian manifolds with positive mean curvature” Duke Math Journal vol. 8 (1941) pp. 401-404. But the proof is contained in Milnor’s book.
Comment #13 August 22nd, 2008 at 6:01 pm
Thanks, Bob!
Comment #14 August 22nd, 2008 at 11:10 pm
David, I don’t think that is right. It’s been a while, but don’t you have kappa, the curvature, and tau, the torsion? If you parameterize the helix as (rcost,rsint,ht)/sqrt(h^2+r^2) – I think that this is the unit parameterization with Frenet frames but I’m too lazy to look it up – you get kappa=r/(r^2+h^2) and tau=h/(r^2+h^2). If you’re talking about measuring curvature from the ‘inside’ as it were, I would assume that you are talking about a ‘fat’ helix. It also has nonzero local curvature (except at the ‘top’ and ‘bottom’.)
Is there another sense that I’m missing out on?
Comment #15 August 23rd, 2008 at 2:56 am
(Off-topic) Hey Scott, tell me something. I’ve been re-reading some of your articles about how difficult (and maybe even undecidable) the P!=NP problem is: relativization, natural proofs, etc. But we don’t even know that P!=PSPACE. Shouldn’t that be a lot easier? Do the same obstacles apply? Why are people working so hard on P!=NP instead of tackling the easier version first?
Comment #16 August 23rd, 2008 at 9:28 am
asdf: It’s like asking, “why are people working so hard on colonizing other galaxies, instead of tackling the easier problem of colonizing other solar systems?”
Very few people do work directly on P vs. NP, nor do they work directly on P vs. PSPACE. There are so many questions vastly easier than either of them (and which are prerequisites to them) that we already can’t answer. But sure, anyone would be thrilled to prove P≠PSPACE, and conceivably it really is easier. Though note that the relativization, natural proofs, and algebrization barriers all apply to P vs. PSPACE as surely as to P vs. NP.
Comment #17 August 23rd, 2008 at 11:37 am
Looking at this again, I don’t think that it does. Otoh, curvature that is always everywhere greater than zero does force convexity. That and the assumption of connectedness will get you compactness. That’s from Do Carmo, iirc.
Comment #18 August 23rd, 2008 at 11:53 am
ScentOfViolets: I think it was implicit that we just care about our own connected component.
Comment #19 August 23rd, 2008 at 12:13 pm
Well, yes, but it’s always better to err on the side of explicitness if one is not 100% sure. I was only 99% sure. Anyway, that’s the mode of attack – you get at it through convexity. Also, iirc, if one insists on absolutely uniform positive curvature, the only manifold that satisfies this is the n-sphere.
Comment #20 August 23rd, 2008 at 4:03 pm
ScentOfViolets,
there are two notions of curvature, intrinsic and extrinsic. Extrinsic curvature is about an embedded manifold and how its geometry differs from the ambient space, in particular, how its geodesics diverge from the geodesics in the ambient space (which would be straight lines in Rn). 1-manifolds have no curvature; they’re all locally the same, once you parameterize them by arc lenght. Frenet frames are extrinsic, but have more than just curvature. Convexity is also extrinsic–it’s about lines outside the surface.
The surface of revolution of a parabola is non-uniformly positively curved, convex, connected, and not compact.
I prefer “uniformly positive curvature” to “uniform positive curvature,” which I think is ambiguous. If you want “uniform” to modify “curvature” rather than “positive,” say “constant” or “homogeneous.”
It’s true that a manifold with positive curvature that is not only homogeneous, but also isotropic (ie, curvature is the same in all directions), has universal cover the sphere, but complex projective space is positively curved, homogeneous, but not isotropic.
Comment #21 August 23rd, 2008 at 4:49 pm
I’m not sure what you mean here, it looks as if you’re comparing apples and oranges if you’re going with convexity as a measure of some extrinsic property. That is, it seems nonsensical in your usage to say the R^2 is ‘convex’.
Certainly, I’m just going with the local terminology here(I’m more of an algebraic geometer.) I’m just pointing out that there is an ambiguity in the first instance with the helix; but in either case, the statement is not true. It is not clear what it means to be ‘inside’ in the 1-d case(that is not, ‘there is no curvature’, but ‘the notion of curvature does not exist’), and in the ‘fat’ case the intrinsic curvature is most definitely nonzero locally, and this is trivially easy to see. Think of negative curvature on the inside of a torus vs the positive curvature on the outside. Otoh, the total curvature, positive and negative sums to zero, ie, the global curvature is zero. Getting back to my original question, this is why I am asking: in what sense are we talking of curvature in this instance? I don’t understand all of lecture 20, needless to say.
(Also, I’m rather weak on the subject, I’ve not had much differential geometry, and that was a while ago.)
Comment #22 August 23rd, 2008 at 8:39 pm
It’s nice to see people talking about the geometry of quantum state-space. Just to remark, from a quantum simulation point of view, the the most widely used state-space manifolds have a multi-linear algebraic structure that guarantees negative Ricci curvature.
These negative-curvature quantum manifolds include (for example) the matrix product states that useful in condensed matter physics. And if we ask “on what quantum manifolds are the discrete states generated by Clifford algebras most compactly embedded?”, then the answer again is negatively-curved manifolds.
Comment #23 August 23rd, 2008 at 8:57 pm
Yeah, I should have said: “you’re talking about extrinsic things, while Myers’s theorem and relativity are about intrinsic curvature.” In relativity, there’s no outside to compare with.
I didn’t say R2 was convex, I said the surface of revolution of a parabola. A parabola isn’t any old line, but one with an embedding in R2; similarly, its surface of revolution comes with an embedding in R3. The metric of that surface is interesting enough that you might say intrinsic things about it (like that it has positive curvature, without being compact), but convexity is about its embedding.
I’ll take that as a flimsy excuse to mention the intrinsic property of the distance function being convex. This turns out to be the same as negative curvature. Also, I’ll take your mention of algebraic geometry as a flimsy excuse to use the phrase “Atiyah class.”
I don’t know what you mean about the curvature of a solid helix or torus. As an open set of R3, a solid torus looks to me to be locally the same as R3, ie, flat. I suppose you could consider a solid torus to have the translation invariant metric, so that it’s flat, but the inclusion in R3 is distorted. But that’s at a different level than the kind of distortion of curvature.
I would tend to say that the curvature of a 1-manifold is the zero 2-form (which I’d say exists). You might say that the sectional curvature is a function on the space of infinitesimal 2-planes, but the set of functions on the empty set is not itself not empty, but a point.
Comment #24 August 23rd, 2008 at 9:08 pm
ScentOfViolets,
by “fat helix/torus” do you mean the 2-dimensional boundary of a thickening? then everything you say is correct (zero on top…); in particular, it isn’t uniformly positive, so Myers’s theorem doesn’t apply. There’s probably some relationship between the intrinsic curvature of the 2-manifold and the extrinsic curvature of the 1-manifold.
Comment #25 August 23rd, 2008 at 9:23 pm
ScentOfViolets wrote:
In the cosmology of a homogeneous, isotropic universe, when people talk about the universe being “positively curved, negatively curved, or flat”, what they are talking about is the Ricci scalar curvature of the homogeneous 3-manifolds, i.e. the 3-dimensional slices through spacetime on which everything looks the same, which can sensibly be thought of as slices of constant “cosmological time”.
For 2-dimensional manifolds, the Ricci scalar is just twice the Gaussian curvature. For 1-dimensional manifolds, the Ricci scalar is 0 everywhere.
The Ricci scalar is an intrinsic measure of curvature, i.e. it can be derived solely from measurements within the manifold, and it doesn’t require, or refer to, any embedding of the manifold in a larger space.
Though the usual way to get to the Ricci scalar is to start with the Riemann curvature tensor and contract it on two indices to get the Ricci curvature tensor, and then take the trace of that … the “Direct geometric interpretation” given in the Wikipedia article on the Ricci scalar is a nice shortcut to the essential point: if you construct a Taylor series for the ratio between the volume of a small n-sphere of radius r in your manifold (i.e. the set of points you get by travelling at most a distance r along geodesics in every possible direction) and the volume of an n-sphere of radius r in Euclidean space, the second order term contains the Ricci scalar. Specifically, S is -3(n+2) times the second derivative of the volume ratio wrt r, evaluated at r=0.
But sometimes it’s easier to use a similar formula for the surface area of these n-spheres; S is -3n times the second derivative of the surface area ratio wrt r, at r=0.
For example, in any 1-dimensional manifold, the volume is just the length of an interval, 2r, which is the same as the Euclidean case, so the ratio is exactly 1, so the Ricci scalar is 0.
For a sphere of radius a, you need to consider a circle of geodesic radius r, i.e. a circle that subtends an angle of r/a from centre to perimeter. The 1-dimensional “surface area” in this case is just the circumference of this circle, and the ratio of “surface areas” is simply (a/r) sin (r/a). The second derivative of that ratio evaluated at r=0 is just -1/(3 a^2 ), and the Ricci scalar is -6 times that, or 2/a^2. Which, as I mentioned earlier, is just twice the Gaussian curvature.
Comment #26 August 24th, 2008 at 1:49 am
Sorry, Ricci, but “Ricci scalar curvature” is an awful term, because the Ricci curvature is something else. Scalar curvature doesn’t impose much of a topological restriction. Every manifold in dimension above 2 has a metric with constant scalar curvature -1. Every simply connected non-spin manifold has a metric with constant scalar curvature +1, as do half of the simply connected spin ones, although probably not in dimension 4.
In contrast, the full Ricci curvature has Myers’s theorem. Relativity is also about the full Ricci curvature. The cosmological constant is basically the negative of the scalar curvature.
Sectional curvature is the easiest to understand: it’s a function on 2-planes, given by the induced Gauss curvature on a surface tangent to that 2-plane. This misses all the structure of curvature, such as the possibility of separating scalar, Ricci, and Weyl curvature. It does have the advantage over the tensor point of view that it’s clear what it means to compare it to a number.
Comment #27 August 24th, 2008 at 2:16 am
“Scalar curvature”,”Ricci scalar”, “Ricci scalar curvature”, “Ricci curvature scalar” … as long as there’s a “scalar” in there, nobody will actually confuse it with the full Ricci tensor — which is something else, yes, but since the scalar curvature is its trace, it’s hardly harmful or misleading to say “Ricci scalar curvature” to remind people of that, and also to make it clear that you’re not talking about any other curvature scalar (such as mean curvature or Gaussian curvature). No doubt an audience of relativists or differential geometers will instantly know what’s meant by “scalar curvature” in any particular context, but that’s not the audience reading this blog.
Comment #28 August 24th, 2008 at 9:55 am
What is curvature? The way Gauss conceived it on two-dimensional surfaces, and Riemann extended it to arbitrary dimensions, was in turns of sectional curvature.
To calculate the sectional curvature, we start at any point, and we choose two independent vectors. We define a section as the two-dimensional surface swept by geodesics whose tangent vectors at the chosen point are linear combinations of the two vectors.
We define the sectional curvature to be positive or negative, according to whether the 2D intrinsic geometry of the sectional surface is spherical or hyperbolic.
It turns out that the sectional curvature and the (four-index) Riemann curvature tensor are geometrically equivalent … if we know the curvature of every section, then we know the full Riemann curvature tensor, and vice versa.
The precise relation is simple. Given a Riemann manifold with inner product ⟨,⟩, the sectional curvature function S(,) and the Riemann curvature tensor R(,,,) are related by
S(u,v)=R(u,v,u,v)/(⟨u,u⟩⟨v,v⟩-⟨u,v⟩⟨v,u⟩)
where the vectors u and v span the desired section.
This illustrates that from a strictly geometric point of view, the sectional curvature function is the “natural” way to define curvature.
This relation can be regarded as the definition of the Riemann curvature tensor. Particularly on complex manifolds, the resulting explicit expression for R(,,,) in terms of the Hermitian metric is very simple and natural … with no Christoffel symbols required … this is one of Kähler’s famous “long list of miracles” that occur on complex manifolds.
Comment #29 August 24th, 2008 at 7:00 pm
joXn,
I think the answer is that in the presence of negative curvature, a random walk will not return to its starting point, even in 2 dimensions. On a large enough scale, it will look like a geodesic.
Comment #30 August 28th, 2008 at 4:11 pm
I submitted perhaps too many hotlinks and citations on “negative curvature, a random walk” which is a robust field, with interesting results. If I could quickly find a dozen, then anyone else with google scholar can, too. Douglas Knight somewhat oversimplifies. It’s all about calculation and simulation, for those of us with intuition less developed than with Greg Egan and John Sidles.
I, for one, appreciate Scott Aaronson’s brilliant speculations, made without being held back by immersion in tangential topics. Starting 1968 when I hung out with Feynman at Caltech, I stated to many people my opinion that our universe is indistinguishable from a simulation running in a larger universe, but as if our was a least-action fixed point in an infinite tree of such embeddings.
The question was: how much computation, with what complexity, does the universe take to calculate (locally, modulo spooky action at a distance) its own next state, and what artifacts of discretization of space-time (planck) can be distinguished from the limit to the GR continuum?
Comment #31 August 28th, 2008 at 5:16 pm
Dear Douglas
Thank you for that fine remark about “random walks look like geodesics on large-dimension negatively curved manifolds” … I wonder if you can provide a reference for it?
It dovetails nicely with a theorem which states that any complex manifold that has an immersion in a large-dimension Euclidean manifold—meaning, pretty much any state-space manifold that physicists ever do practical computations upon—has negative holomorphic bisectional curvature.
It is becoming clear (IMHO) that one reason for the exponentiating increase in quantum simulation capability seen in recent decades is derives purely from Riemann/Kahler geometry — the negative biholomorphic sectional curvature theorem helps ensure that quantum simulation codes “seldom get lost.”
@article{, Author = {S. I. Goldberg and S. Kobayashi}, Journal = {Journal of Differential Geometry}, Pages = {225–233}, Title = {Holomorphic Bisectional Curvature},Volume = 1, Year = 1967}
Comment #32 August 29th, 2008 at 1:08 pm
I was thinking of Furstenberg & Kesten. There’s a later version that deals with more general groups, and thus hyperbolic space, but I don’t know the cite, nor do I know a result for inhomogeneous spaces, but I’m pretty sure it’s true for pinched negative curvature. Weird things happen with the heat kernel under negative curvature, from which non-recurrence can probably be easily read off, but I don’t know how it relates to the geodesic behavior.
If you’re in a compact setting, the geodesic result is probably not a good way of looking at things.