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:
- Examine a global variable
- Modify a global variable
- 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?
- Examining a global variable is non-local. How can an operation
here examine (interact) with data stored there?
- 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.
- 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?