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 :
- Peter Shor's algorithms for discrete logarithms and factoring
- David Deutsch's algorithms for testing Bell's inequality and
the EPR paradox
- Any other important algorithms I find in the literature.
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 :
- A compiler - compiling to Toffolli or universal 2-bit gates.
(There would also be some sort of simulator to run these)
- A compiler - compiling to unitary matrices!
- A compiler - generating C-language code so that a wide variety
of researchers would be able to write Q-gol code.
- 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?
- 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.
- 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
- 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.
- 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.
- 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 http://vesta.physics.ucla.edu:7777/
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)