Graphic lambda calculus used for quantum programming (Towards qubits III)

I want to make a bit more clear one of the goals of the research on graphic lambda calculus, which are reported on this blog.  I stress that this is one of the goals and that this is live research,  in the making, explained here in order to attract, or invite others to join, or use this exploration for their purposes.

More precisely, further I present several justifications for two series of posts

which have as common goal the application of graphic lambda calculus to some form of quantum programming (probably some version of a quantum lambda calculus). I use the informative linked wiki page on quantum programming  for citing. Please click on the links to go where the real information is.

Efforts are underway to develop functional programming languages for quantum computing. Examples include Selinger’s QPL,[1] and the Haskell-like language QML by Altenkirch and Grattage.[2][3] Higher-order quantum programming languages, based on lambda calculus, have been proposed by van Tonder,[4] Selinger and Valiron [5] and by Arrighi and Dowek.[6]

Simon Gay’s Quantum Programming Languages Survey has more information on the current state of research and a comprehensive bibliography of resources.

I hope that in some finite time I can prove that there is a “quantum lambda calculus” sector in graphic lambda calculus. Let me explain why.

Basically, leaving much detail aside, quantum computation needs a  mix of at least two ingredients:

  • some algebraic structure, which contains objects like complex vector spaces, real projective spaces, unitary transformations, projections, etc,
  • some logical structure overarching the algebraic one (purists may say that in principle a lambda calculus would do).

The algebraic structure is not needed entirely, i.e. the needed part is the web of relations between the various algebraic operations. For example, the vector space operations are needed and not the points of the vector space. Likewise, we need “linearity”, “unitarity” and not particular linear or unitary transformations. Enough is to know how linearity and unitarity interact with the algebraic operations.

In the same way, as concerns the logic part, we need (say, if we are interested in a quantum lambda calculus) an abstraction an an application operations (like in lambda calculus) which interact well with the algebraic structure. Right?

There is one more ingredient needed: some form of evaluation procedure. There we can see a difference between a quantum and a classical lambda calculus. A quantum lambda calculus is more geometrical, less commutative than a classical one. One has to take care of phases, of the order of evaluations more than in the classical one.

Graphic lambda calculus seems to be a welcoming host for all these demands. Indeed, let’s see.

Graphic lambda calculus encodes algebraic structures in the barest way, by using only one gate: the emergent algebra gate \bar{\varepsilon}, with the parameter \varepsilon in a commutative group. This \varepsilon models “scale”, it is usually taken in (0, \infty) or in \mathbb{Z}. However, phase is a kind of scale, i.e. the formalism works well with the choice of the commutative group of scales to be \mathbb{C}^{*}.   Any algebraic operation and any algebraic computation in complex vector spaces, or in real projective spaces, may be expressed into graphic lambda calculus by the intermediary of the emergent algebra gate. Moreover, even some of the differential calculus (needed but not mentioned previously) can be embedded into graphic lambda calculus, in a kind of constructive way. This is the “emergent algebra” point of view, introduced in arXiv:0907.1520 .

So, shortly said, in graphic lambda calculus we have the algebraic structure needed. It “emerges” from the \bar{\varepsilon} gate, when we take the scale parameter to be in \mathbb{C}^{*}. With the barycentric move BAR from Towards qubits part I   we get the algebraic structures of vector spaces (see  how to get projective spaces in   part II, work in progress). More interesting, without the barycentric move we get Carnot groups, i.e. non-commutative vector spaces.

Question 1. What we obtain if in the formalism of quantum mechanics we renounce at complex vector spaces and we replace with their non-commutative version, the Carnot groups?

(This is the motivation for the series of posts Gromov-Hausdorff distances and the Heisenberg group part 0, part I, part II, part III  in this blog.)

For the logic part, we know that graphic lambda calculus has a sector which corresponds to untyped lambda calculus. In quantum programming it would be interesting to find a quantum version of the lambda calculus which interacts well with the algebraic structure. But in graphic lambda calculus are allowed interactions between the lambda calculus gates,  (or logical gates) of abstraction and application, and the algebraic gates. We don’t need more, that is what I shall try to convince you eventually. Indeed, probably obscured behind the lambda scale calculus  (which is a first, non-graphical version of the graphic lambda calculus), this was already explored in section 4 “Relative scaled calculus” of arXiv:1205.0139, where we see that to any scale parameter \varepsilon is associated a relative lambda calculus. This was done in whole generality, but for the needs of a quantum lambda calculus  “linearity moves” like in the  “Towards geometric Plunnecke graphs” series could be applied selectively, i.e. only with respect to  the (0, \infty) part of \mathbb{C}^{*}, thus obtaining a relative lambda calculus which is phase-dependent.

Question 2.  What would a relative scaled lambda calculus look like in graphic lambda calculus?

Finally, for the evaluation procedures which are adapted to quantum world, in this respect, for the moment, I have only results which indicate how to get usual evaluation procedures in graphic lambda calculus by destroying it’s geometrical nature (that’s what I call the “cartesian disease“, if you care), which are explained in some detail in   Packing and unpacking arrows in graphic lambda calculus    and Packing arrows (II) and the strand networks sector.

Question 3.  Design evaluation procedures in graphic lambda calculus which are geometrical, in the sense that, at least when applied to the yet vague quantum lambda sector of the graphic lambda calculus, they give evaluation procedures which are useful for quantum programming.

So, that’s it, I hope it helps a bit the understanding. You are welcome to join, to contradict me or to contribute constructively!

3 thoughts on “Graphic lambda calculus used for quantum programming (Towards qubits III)”

  1. I have not mentioned the big surprise encountered when working on lambda-scale calculus. I were after some form of a calculus with emergent algebra gates which could parallel the lambda calculus, but to my surprise I arrived to this scaled calculus where the family of relative calculi are structured into an emergent algebra.

    Otherwise said, I started with the goal of constructing a lambda calculus by using dilations and I ended by realizing that one can apply dilations to lambda calculus terms!

    Which terms may be “linear”, i.e. scale independent, or not, the second case being a good feature for a proposed quantum lambda calculus.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s