## Archive for January, 2007

Posted in Algebraic Topology, Concurrency theory, Philosophy, Physics, Quantum Computation, Quantum Field Theory, Quantum Gravity, Quantum Mechanics on January 16, 2007 by Christine

I’ve been working on the idea that quantum systems are inherently concurrent systems (see this previous post under construction). They can be examined under directed algebraic topology (or ditopology) tools (e.g., see here, or google about it).

The most interesting problem to model is quantum entanglement: underlying this phenomenon one abstracts out a quantum state as fundamentally corresponding to a set of concurrent processes. It would be interesting to examine how to restore local realism under this general hypothesis.

One can go further into this and ask whether quantization arises from the idea that, given that quantum systems are seen as concurrent systems, there are naturally forbidden regions in the multi-dimensional state space, where each dimension represents a concurrent process, defined by the fact that these processes locally share “resources” and no two processes can “act” on the shared resources at the same “time”. Forbidden regions correspond to the discretization of nature in the quantum limit.

So nature would fundamentally be a huge deadlock avoidance system.

Update: discussions can be found in the comment section of this blog entry over at n-Cateogry café.

Update: Below follows, for the record, a cut and paste from the discussion over at n-Category café. For the detailed links, please refer to that blog entry (see link above), where the comments appeared.

Christine, I assume the application of directed algebraic topology to concurrent systems is an outgrowth of the work of Herlihy and Shavit, which was done in the late 90s and won the 2004 Gödel Prize.

You might want to communicate with Prakash Panangaden at McGill about your work. He appears to have worked, as a theoretical computer scientist, on concurrent and distributed systems and also on quantum computing, and has a strong interest in the causal structure of general relativity and its connection to abstract notions arising in computer science.

Posted by:
Chris W. on January 17, 2007 1:58 AM |

In terms of applications of general geometrical methods to concurrency, the idea goes back to the 70’s. See Goubault, E. Geometry and Concurrency: A User’s Guide. But you are right to cite the work of Herlihy and Shavit as an evidence of how this subject is getting a lot of attention recently, and giving rise to important developments in the field. It looks a beautiful paper, but I have never studied it in detail.Panangaden also published in gr-qc, and this is one of his most interesting papers, I guess… I don’t know how far this is getting attention, but sounds an original and promissing line of research.

Best regards,

Christine

Posted by:
Christine Dantas on January 17, 2007 11:51 AM

Hi Christine, you probably already know that Carl Petri, one of the founders of Concurrent Systems as a field of study, used to propound the view that an adequate semantics for concurrency would need to be sufficiently broad to also encompass physics.

From what I’ve been reading recently on Anima ex Machina blog he’s updated this position somewhat to a more “out-there” Universe-is-a-Petri-net kind of stance. He might be right! (as might Smolin – I saw your Amazon review!) On the same page I linked you can also find thoughts of Seth Lloyd and some others on this topic from a conference in Berlin last year.

You’re probably also familiar with Vaughan Pratt who clearly thinks very deeply on this sort of topic (although his publications can be frighteningly dense).

When I was a CS student as Glasgow they used to ask us questions like the “big simulation” argument, just to freak us out. I was never able to see why this would confuse a hardy theoretical physicist though — surely they’d be interested (in theory) in the turtle at the bottom of the tower, ie the real simulation that presumably has to simulate itself?!

I’m looking forward to seeing where the quantum lambda-calculus course goes with this kind of thing. Quantum computation seems to rely on arbitrary-precision complex amplitudes — but having gone to all the trouble of defining True and False as morphisms in the course, surely we won’t now be allowed to pull high-precision complex numbers out of the hat? If you were designing a programming language they’d need to be defined and computed themselves somehow… who “computes” these amplitudes that they’re relying on?

Posted by:
Allan E on January 17, 2007 2:09 AM

Hi Allan,

And according to Nielsen and Chuang,

“Quantum computation and quantum information has taught us to think physically about computation (…) we can also learn to think computationally about physics.”

This view is attractive and I believe physics is heading towards this broad idea. I do not have a clue how far this will lead us.

Concerning Petri nets, these and other classical concurrency models have been generalized to the concept of po-spaces (“po” from “partial order”). See Sokolowski, S., Directed topology and concurrency a short overview.

Best,

Christine

Posted by:
Christine Dantas on January 17, 2007 12:21 PM

And concerning the question in your last paragraph, I don’t know how to answer to that… There is a huge gap between a broad idea and the technical details that one has to face in order to make the idea actually work or make sense! But thanks for pointing that out, I’ll have to think about it.

Posted by:
Christine Dantas on January 17, 2007 12:31 PM

Let me see if I understand what you’re getting at. If there are correlations among a set of concurrent processes, they must be constrained to avoid deadlocks. Perhaps the necessary constraints induce correlations and anti-correlations among states and state transitions in the system that resemble correlations among quantum states. These correlations also imply that the system avoid parts of its state space.

You seem to be assuming discretization at the outset, insofar as the number of concurrent processes is finite, and the associated state space is finite. Should I assume that you have in mind a continuous analog of a set of concurrent processes?

Here is a simple and fairly concrete model you might want to examine. Consider the state space to include a set of n Boolean variables, and the concurrent processes to be n Boolean transition functions of two variables that yield a “subsequent” state for each of the variables. The processes (transition functions) share resources in the significant sense that each of the functions operates on two variables, at least one of which might be used as an input by another function. What would constitute a deadlock in such a system, and what is required to avoid it? Is there necessarily a stochastic component to the system’s behavior? That is, does the transition structure have to rearrange itself every so often, in a way that can’t be described deterministically? I realize this is a very sketchy problem formulation.

By the way, with respect to the relevance of algebraic topology, the set of transition functions in this simple model can be considered as defining an abstract simplicial complex; the Boolean variables are the vertices and the functions define the edges. (Remember however that these functions have some internal structure, since we have 16 distinct, albeit interrelated, Boolean functions to choose from.) My previous questions can then be posed as questions about the “moves” that can and must occur within this complex, in order to avoid certain “pathologies” in the evolution of the system. (By the way, in this light, the collection of transition functions can be loosely regarded as a “gas” of edges [1-D!] which is evolving in parallel with and necessarily coupled to a “gas” of Boolean state variables.)

One more point: The Boolean variables are of course undergoing transitions with successive “time steps”. One might ask if one can define a causal order on these transitions or “events”. That is, given one such event, can one say that it was preceded in a well-defined way by another set of events, and followed accordingly by yet another set of events? It is not immediately evident how such a description is to be derived from the transition functions, although one might plausibly expect that it should be possible.

(I have in mind here a complementary description in terms of causal sets. By the way, regarding the compatibility of discreteness based on causal sets with Lorentz invariance, see Discreteness without symmetry breaking: a theorem [1 May 2006].)

Posted by:
Chris W. on January 17, 2007 4:26 AM

Dear Chris W.,

Thanks for this elaborate comment. Your first paragraph summarizes well the broad idea.

And yes, one could assume a continuous “scheduling” of the processes, and also the space could be assumed to be infinite dimensional. What I think is important here is to assume a local partial order – a “po-space”… (I’m interested in ergodic moves…) Examples of such spaces are found here:

* Sokolowski, S., Classifying holes of arbitrary dimensions in partially ordered cubes. Tech. Rep. 2000-1, Kansas State University, Computing and Information Sciences, Aug. 2000. linke here.

* Raussen, M., Geometric investigations of fundamental categories of dipaths. Unpublished, 2001. (sorry, can’t find the link now).

* Gaucher, P., About the globular homology of higher dimensional automata. Cahiers de Topologie et Geometrie Differentielle Categoriques XLIII-2 (2002), 107156. link here.

And thanks for proposing a problem. I guess we all have sketchy ideas for the moment! No problem about that, in fact it is great to know that this is quite an open field for research.

Your comment has given me months to think over! Don’t have much valuable to add for the moment, but thanks a lot.

Christine

## Russian elementary physics books

Posted in Physics on January 13, 2007 by Christine

Brazilian students willing to undertake the ITA/IME exams (for admission to their undergraduate courses) will like know that Editora Vestseller is making available several books from the russian MIR publishers that are out of print or available at a high price elsewhere. I have purchased myself recently a copy of Saraeva‘s book (Portuguese translation) from Vestseller and it arrived in excellent condition, in time, and at a good price. I do not know whether they sell outside Brazil. The ITA/IME exams are demanding for the students and most questions are at the level of or inspired by questions found in russian physics books.

A typical problem in Saraeva (problem 200): will the system below stay in equilibrium?

One should of course work out all the forces acting in the system and not rely on a careless first impression.

## QFT review

Posted in Book Reviews, Physics, Quantum Field Theory on January 12, 2007 by Christine

An American Physics Student in England has written a nice review of books and lecture notes on Quantum Field Theory for beginners.

I’ve been patiently(*) studying Zee’s book for some time now (it’s been a while since I last opened a page of it, though). Sigh. It seems I am an eternal beginner… But that is all right: the important thing is keep moving (forward). I have so many interests that distract me. But I hope this year I can find more discipline in me — and hence, more time for so many interesting books out there.

(*) That means: making all exercises and thinking about them… Yet, I don’t believe I’ll get Peskin and Schroeder this year yet, although I’d like to.

Ref.: [Zee]

Edited: BTW, it seems I cannot get some factors of $2\pi$right. For instance, I get it in the denominator instead of the nominator in the derivations of page 11; I get a $(2\pi)^n$in equation (20) on page 15, and etc etc. Not important, but I get annoyed not to know where my mistakes are…

## How does she know it?

Posted in Biology on January 12, 2007 by Christine

Look at this picture:

It is a common spider in my garden. But her web is quite unusual: look how she enforced it exactly where her legs usually stay (she likes to stay immobile in that position).

Now, how does she know it?

## The logic of solids

Posted in Mathematics, Philosophy on January 2, 2007 by Christine

Henri Bergson wrote, in his Creative Evolution:

”(…) the human intellect feels at home among inanimate objects, more especially among solids, where our action finds its fulcrum and our industry its tools; that our concepts have been formed on the model of solids; that our logic is, pre-eminently, the logic of solids; that, consequently, our intellect triumphs in geometry, wherein is revealed the kinship of logical thought with unorganized matter, and where the intellect has only to follow its natural movement, after the lightest possible contact with experience, in order to go from discovery to discovery, sure that experience is following behind it and will justify it invariably.”

I look forward to a study relating Bergson’s view and Category theory; some discussions about this over at n-Category café last year can be seen following my comment there. This is a subject I intend to start studying in 2007.