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.

32 Responses to “Quantum Computing Since Democritus Lecture 20: Cosmology and Complexity”

  1. joXn Says:

    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″.)

  2. joXn Says:

    Ack, HTML ate my comment. “infinitely often if N < 3, and never if N >= 3″.

  3. Moshe Says:

    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.

  4. Joe Shipman Says:

    I still don’t buy that positive uniform curvature implies finiteness. Consider a helix.

  5. Daniel Says:

    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.

  6. harrison Says:

    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!

  7. Scott Says:

    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!

  8. Scott Says:

    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…

  9. Daniel Says:

    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.

  10. David Speyer Says:

    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.

  11. Scott Says:

    Thanks, David!

  12. Bob Solovay Says:

    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.

  13. Scott Says:

    Thanks, Bob!

  14. ScentOfViolets Says:

    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?

  15. asdf Says:

    (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?

  16. Scott Says:

    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.

  17. ScentOfViolets Says:

    That said, I don’t know a reference or a quick argument for the fact that uniform positive curvature forces compactness.

    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.

  18. Scott Says:

    ScentOfViolets: I think it was implicit that we just care about our own connected component.

  19. ScentOfViolets Says:

    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.

  20. Douglas Knight Says:

    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.

  21. ScentOfViolets Says:

    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’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’.

    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.

    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.)

  22. John Sidles Says:

    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.

  23. Douglas Knight Says:

    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.

  24. Douglas Knight Says:

    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.

  25. Greg Egan Says:

    ScentOfViolets wrote:

    In what sense are we talking of curvature in this instance?

    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.

  26. Douglas Knight Says:

    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.

  27. Greg Egan Says:

    “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.

  28. John Sidles Says:

    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.

  29. Douglas Knight Says:

    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.

  30. Jonathan Vos Post Says:

    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?

  31. John Sidles Says:

    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}

  32. Douglas Knight Says:

    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.