Proposal for an Honours project : Q-gol

The proposal

Recently, it has been realised that quantum physics provides another paradigm for computation to replace the classical physics which has dominated computer science until now.

While research is growing at a staggering rate, it seems to be still held back by difficulties in describing algorithms. Peter Shor, for example, described an algorithm to run on a quantum computer which would factorise large integers. All things considered, it is probably conceptually no more difficult than, say, the Pollard rho algorithm, which can be written down in about half a page or so. But because we have no easy way to talk about such matters, it takes 18 pages to give a full, explicit description.

Imagine trying to explain euclid's algorithm if the only widely-understood descriptions for other algorithms were expressed as Turing machine programs. It would be like programming in raw binary with flow control given by a conditional "jump relative +/- 2" branch. There is no fundamental reason why it is impossible - but it would exceptionally hard to follow, and exceptionally hard to debug if ever it were to be used. Writing more complex algorithms would be an even more arcane art, understandable by only a few, and developed by far fewer.

Hence, I propose to develop a high level language in which to express algorithms for quantum computation, and to produce a simulator to run on a van Neumann computer which will approximate (with exponential slowdown!) the result of such programs. As an initial title, I have named this language Q-gol, for no really good reason as yet. As a guide to how succesful this has been, I propose to write Q-gol programs of :

With the objective being for these algorithms to become "human-friendly" programs in Q-gol which anyone trained in Q-gol will be able to understand "at a glance" in the same way that, say, that the GCD algorithm written in Pascal is "human-friendly".

It is a little early to judge what form the simulator will take, but it may be any subset of :

  1. A compiler - compiling to Toffolli or universal 2-bit gates. (There would also be some sort of simulator to run these)
  2. A compiler - compiling to unitary matrices!
  3. A compiler - generating C-language code so that a wide variety of researchers would be able to write Q-gol code.
  4. An interpreter - since the output of compiler 2 would be very unweildy and compilers 1 and 3 may may rapidly become outdated.

    Who benefits from the existence of Q-gol?

  5. Quantum computation researchers - who will have some concise way of expressing ideas to each other, and will have test beds to attempt to develop new ideas more accessibly.
  6. Physicists - as outlined by Deutsch in his seminal paper on the subject, most of the major questions of quantum physics can be resolved by running various quantum computer programs. While my simulator will not be able to answer these questions (!), it will make discussions about these matters much simpler. Similiarly, in the near future when small quantum computers can be built, it will save a lot of time and effort if such programs can be written and debugged in a "safe" environment
  7. Computer scientists - if a quantum computer algorithm language is not developed by a computer scientist, something will be developed by a physicist, or worse still, a mathematician! For our own sanity in 40-50 years time, I think this needs a computer scientist's perspective.
    More seriously, Q-gol will be (as far as I know) the first language designed in full knowledge that most of its operations must be reversible, and that expressions involving conditional branches must be kept to a minimum. This will certainly provide ideas for new software engineering paradigms.
  8. Mathematicians - mathematics develops furthest when there are many ways of describing "the same thing" - complex numbers in mod-arg form or as components, as vectors or as field elements. To add extra structure to the set of unitary matrices - by considering them as quantum computer algorithms - may well assist that area of study.
  9. Microsoft - since it could be more than half a century before desktop, reliable quantum computers are being built. With Q-gol, it will be possible for them to start development work now on "Windows 2050" and "Windows for Alternate Universes". With that large a time-frame, they might just make one deadline on time!

    Selected References

    P. Shor
    "Algorithms for Quantum Computation : Discrete Logarithms and Factoring"
    Proceedings, 35th Annual Symposium on Foundations of Computer Science (IEEE Press, November 1994)

    S. Lloyd
    "A potentially realizable quantum computer"
    Science, Vol 261, pp. 1569-1571 (1993)

    S. Lloyd
    "Envisioning a quantum computer"
    Science, Vol 263, pp. 695 (1994)

    D. Simon
    "On the power of quantum computation"
    Proceedings. 35th Annual. Symposium of the Foundations of Computer Science (IEEE Press, 1994)

    D. P. DiVincenzo
    "Two-bit gates are universal for quantum computation"
    manuscript; available via

    D. Deutsch
    "Quantum theory, the Church-Turing principle and the universal quantum computer"
    Proceedings Royal Society of London. Vol A400, pp.96-117 (1985)

    D. Deutsch
    "Quantum computational networks"
    Proceedings of the Royal Society of London. Vol 425, pp. 73-90 (1989)

    D. Deutsch and R. Jozsa
    "Rapid solution of problems by quantum computation" Proceedings of the Royal Society of London. Vol 439, pp. 553-558 (1992)

    R. Feynman
    "Quantum mechanical computers"
    Foundations of Physics, Vol 16, pp. 507-531 (1986)