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 $(\; U$_P, U_Q, U_F, U_G ) 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 U_Q forming a group under the operation of composition. $U$_G is a function taking $(X\; x\; U$_Q) to (X x U_P) 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$₁ x H₂ to be operated on by independant threads working on $H$₁ and $H$₂ 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.