# Points from my Honours Thesis

• There are lots of surprising correspondences between functional programming and quantum computing: uniqueness types (a concept designed to assist garbage collection) very neatly map onto the no-cloning theorem. In the Qgol evaluator, I declared the abstract *Quantum type to be unique, and could be assured of physical logic being preserved as a result.
• I created a formalism for describing quantum computation; as far as I could see, there is no meaning to the term "universal quantum computer", but apparently there were quite a few problems with what I wrote! The best I could come up with was the idea is of an acyclic dataflow network, in which the nodes are represented by unitary matrices. This is powerful, but not universal. I provided some so-so arguments showing why universality is probably impossible.
• I devised a formalism for describing all computational universes, including quantum and classical, as well as extending it with other extremeties.

A computational universe, U, is a four-tuple $\left( U$P, UQ, UF, UG ) where $U$P is a set of preparable and observable states; $U$P is a subset of the operable states $U$Q. The operations $U$F is a set of functions from $U$Q UQ forming a group under the operation of composition. $U$G is a function taking $\left(X x U$Q) to (X x UP) where X is an list (ordered set) of probabilities.

• Some examples:
• Classical computation
• $U$P = Z
• $U$Q = Z
• $U$F = computable functions
• $U$G = identity function
• Quantum computation
• $U$P = Z
• $U$Q = quantum superpositions on Z
• $U$F = functions composable from a quantum dataflow network
• $U$G = wavefunction collapse
• Or even some wackier ones -
A universe in which every function except the identity is incomputable
• $U$P = 1
• $U$Q = 1
• $U$F = { I }
• $U$G = { I }
• It actually extends to negative-time delay computation, and provides a nice way around the grandfather paradox: $U$Q might contain an element in which you are alive and your grandfather is dead before your mother was conceived, but $U$P won't. It works much the same way as a quantum system: you can't get hold of $1/2| 0 > + 1/2| 1 >$ (it just doesn't make sense); you can only get a 0 or a 1.
• If it is possible to parallelise a Qgol evaluator by having threads operate on separate datastructures (i.e. if it is possible for a system of the form $H$1 x H2 to be operated on by independant threads working on $H$1 and $H$2 separately), then quantum telegraph is impossible. This means that we can perform a "pseudo-experiment" just by doing some programming. Note that it is doing something deeper than running a numerical simulation; it is in fact making a statement of the implications of the mathematics we use to describe quantum theory.
Now... if you found the above interesting, and happen to have a spare PhD scholarship lying around....
Greg Baker
Last modified: Sat Dec 14 18:07:01 EST