VSJ – April 2004 – Work in Progress

Steve Cumbers, FIAP is a director of TopQuark and Vice President of the IAP Council to which he is standing for re-election this spring. Here, he treats us to an invigorating trot (well, gallop) through the history of modern physics pausing for breath at the gates of quantum computing about which, he tells me, he will have more to say later.

Francis Bacon’s empiricism, Galileo Galilei’s insight and Isaac Newton’s mathematization gave us classical physics: a clockwork universe where the only impediment to determinism is complexity. In the nineteenth century, Michael Faraday and James Clerk Maxwell added electromagnetism to the classical repertoire. Albert Einstein appended special relativity in 1905, to harmonise mechanics with electromagnetism; and general relativity in 1915, whereby gravity is seen as a manifestation of space-time curvature. However, there were tantalising phenomena that physicists could not account for using either classical (pre-relativistic) or neo-classical (relativistic) physics.

Max Planck succeeded in explaining one of these anomalies, the blackbody radiation curve, when in 1900 he proposed that energy is transferred in tiny discrete packets. Each packet is an irreducible quantum (photon) of action, equal in energy to a constant times the frequency of the electromagnetic radiation. Einstein explained another anomaly, the photoelectric effect, using Plank’s idea, and proposed that all radiation is intrinsically particulate. In 1913, Neils Bohr explained the hydrogen spectrum: electrons move in restricted orbits (quantized states) about the atomic nucleus. In 1924, Louis de Broglie introduced wave-particle duality by devising a wave theory of electrons. Then, during the late 1920s, Erwin Schrödinger (and his cat), Werner Heisenberg and Paul Dirac completed this grand paradigm shift. Henceforth, quantum physics, the dreams that stuff is made of, would occupy centre stage in science and underpin much new technology.

Meanwhile in automatic computing, nothing revolutionary had happened since Charles Babbage proposed his Analytical Engine a century earlier. Then, in the 1930s, Kurt Gödel’s recursive functions, Alonzo Church’s lambda calculus, and Alan Turing’s eponymous machine gave us classical computer science. The equivalence of these individual formulations led to the Church-Turing thesis: any realisable computer is equivalent to an abstraction known as a universal Turing machine and every algorithm (well-defined procedure) can be carried out by such a machine. However, this Newtonian science of computers was really a branch of pure mathematics. Indeed, it was generally assumed that the essential characteristics of a computer were independent of its physical implementation. As Edsger Dijkstra put it, ‘computer science is no more about computers than astronomy is about telescopes’. Until, that is, the packing density of transistors becomes so great that quantum effects start to break through. But rather than suffer from this CMOS endpoint and see Moore’s Law repealed, can we exploit quantum physics to our computational advantage?

During the 1980s, Paul Benioff’s quantum description of a classical Turing machine, Richard Feynman’s speculations on the relative efficiencies of classical versus quantum computers and, especially, David Deutsch’s models of quantum Turing machines, laid the foundations of quantum computer science. Yet little interest was shown until the mid-1990s. Then Peter Shor discovered a quantum algorithm for factorizing integers that is exponentially faster than any known classical algorithm and Lov Grover discovered a quantum algorithm for finding an item in an unsorted database in the square root of the time taken by the best classical algorithm. There are serious implications to these discoveries. For example, Shor’s algorithm could be used to break most of the ciphers in use today.

So, two quantum programs of practical significance have been written. All that is needed is a quantum computer to run them. Research continues apace but the technological challenges are formidable. However, even the conceptual possibility of a quantum computer requires a true science of computing based on physics as well as mathematics. It may even be that nature itself is a computation — perhaps we are an exquisite virtual reality created by an advanced civilisation for teaching their history to their children.

[Interesting project or development? Let us know at eo@iap.org.uk!]

Comments are closed.