Random musings about functional languages and quantum computing

Almost all imperative languages (Fortran, C, Pascal, etc.) have ways of defining so-called "functions", which are not the same as what a mathematician would call a function. Functions in imperative languages can have side-effects, and be side-effected. It isn't always the case that
   f(x) + f(x) = 2 * f(x)    
For example, if f is a function which examines a global variable, increments it, and then returns a result which depends on that global variable, then the above equivalence is only occasionally true. It is quite startling to look over one's old code to see how very commonly this happens - remember that even printing to the screen is an example of of examining a global variable and then modifying it.

As an aside, this referential opacity, as it is called, is a major cause of bugs in complex systems. When function calls start getting to being several-hundred deep, it is nearly impossible to realise that the use of f here is modifying the output of g there. There is a lot of talk that the use of functional languages (in which referential transparency is assured) may make the development of big systems easier. From my experiences developing versions 2 and 3 of the q-gol evalutator, this is most definitely true.

There are three ways a function can interact with the rest of a program:

  1. Examine a global variable
  2. Modify a global variable
  3. Using a global constant
If no function anywhere in the program does 2, then all functions are referentially transparent - because there is no real difference between 1 and 3. But if anything at all does 2, then any function doing 1 is opaque. Any function that does 3, or none of the above is referentially transparent

Relation to quantum operations

It is perfectly reasonable to talk about functions returning quantum results, and similarly to talk about quantum computing programs. An interesting question - what is the physical meaning behind the three interactions above?
  1. Examining a global variable is non-local. How can an operation here examine (interact) with data stored there?
  2. Modifying a global variable is an even bigger no-no. Even if it were possible, it would be decidedly undesirable since it would produce unwanted correlations between qubits. Moreover it might individually distinguish some operations, making it impossible to use interference to merge results.
  3. Using a global variable is probably OK, since that would have to be done as part of the equipment which performs the unitary operation. There is no real problem with this.
Which gives the interesting conclusion : the only interesting quantum computing systems have functions which are all referentially transparent.

Garbage collection

To be continued - how do the functional and imperative models of garbage collection relate to junk bits and evaluation mechanisms in quantum computing?