Michael Mainelli, The Z/Yen Group
Charles Ross, Quantum Computing in Europe Pathfinder Project
[A version of this article originally appeared as "The Potential Impact of Quantum Computing", Croner Business Networks Briefing, Issue 20, (26 November 1998) pages 6-8.]
From the Finite to the Infinite: The Potential Impact of Quantum Computing
A quantum may be the smallest measurable finite unit, but quantum computing may unlock the doors to infinity. Quantum computing is widely touted as "the next big thing" in computing, despite the fact that most experts concede that the first quantum computer may be some years off. Do business users of technology today need to care about a possible technology of the future? If so, what should they watch out for?
The End of Moore's Law?
One of the few recognised `laws' of computing is Moore's law, an observation in 1965 by Intel co-founder Gordon Moore that integrated circuit capacity appeared to double with each new chip and that each new chip was released within eighteen to twenty-four months of the old. Much of this was achieved by continually reducing the size of the processing unit. Forecasters believed that this exponential growth had to reach a limit, and that the limit would be near the level where the processing unit reached the size of one atom, which is where quantum effects take over. On current trends, this limit to growth was expected in the first decade of the next century. Quantum effects were either a barrier or an opportunity - what about a quantum computer?
In 1985, David Deutsch, a researcher at Oxford, published a paper suggesting that sub-atomic effects, quantum physics, could be applied to computational problems. He defined a "quantum parallel computer" and quantum computation as "computation that requires quantum-mechanical processes, especially interference". The working group of the Quantum Computing in Europe Pathfinder Project, set up by the Long Term Research Unit of DGIII of the European Commission and others, suggests that "by employing the extraordinary properties of quantum mechanical operations, such as superposition, entanglement, complementarity and uncertainty, data can be encoded in the quantum states of matter or light and manipulated with unprecedented speed and efficiency".
Now You See It, Now You Don't Even Understand It
Quantum physics began around the turn of the century with the observational paradox that matter at the sub-atomic level appeared to exist at times as particles and at other times as waves. Further, matter at the sub-atomic level did not appear to be in a fixed state, i.e. "on" or "off", but appeared to decide its state based on interaction with an observer. The story of quantum physics is one of the great intellectual success stories of the past century, with many famous names playing significant roles, Einstein, Bohr, Schrödinger, Planck, Heisenberg, Pauli, Dirac and De Broglie. A complete understanding of the mechanics of quantum computing eludes most people who have not kept up with quantum physics and the associated mathematics, but this could be said of much base-level computing technology.
Although still developing, quantum theory accords surprisingly well with the universe, in fact better than almost all other physical theories. However, physicists continue to discuss interpretations of the underlying mechanisms. For instance, Deutsch believes that quantum computation "is performed in collaboration between parallel universes". The entire "multi-verse" will be processing for us. Other quantum physics researchers have more prosaic interpretations of super-position and uncertainty. In spite of the disagreement about the deeper metaphysical interpretation, the evidence supporting quantum theory is such that researchers have already begun with confidence to develop programming approaches for virtual quantum computing machines which have not been built. Hard-headed observers would prefer to have a real machine. For the moment real machines are a bit trickier.
Gambling on Quantum Probabilities
Government organisations such as USA's DARPA, the UK's Defence Evaluation and Research Agency, the Deutsche Forschungsgemeinschaft, and the European Union are already spending significant research monies, as well as leading players in the information technology and networking industries, in order to get closer to a real machine. In 1994 Peter Shor at Bell Labs designed a quantum circuit. In December 1997 H Jeff Kimble at Caltech produced a stable quantum logic gate based on a single caesium atom. His stable quantum logic gate has been christened a `qubit' or `quantum bit'. In theory, a qubit can be in many simultaneous `states' which depend on the status of adjacent, or `entangled', qubits. To date, less than a handful of qubits have been made to work together for the briefest of periods. Many other related technologies also exploit quantum effects - ion traps; numerical information stored in carbon molecules, `buckey balls', at room temperature; light emitting silicon; or GigaHertz DNA computer circuits based on Nuclear Magnetic Resonance - and all may well be part of the final physical solution. All is not easy however. Without digressing, decoherence, which can be thought of as somewhat similar to noise in conventional electronic circuits, is still a significant practical obstacle.
Whether the future qubit is based on electrons or light, complex molecules or more basic particles, researchers are already working on problems to submit to the unbuilt quantum computer. Two intriguing algorithms are already in the public domain and under discussion. Shor gives a formula which will decode public key cryptography, rendering current leading-edge security technologies ineffective. Other researchers are showing how quantum computing will enable a completely new form of private key cryptography, which will be completely secure from decryption and also show when any attempt has been made to tamper with a message. Grover has demonstrated how a quantum computer could analyze a large database in seconds for problems which conventional computers would take many years to process.
For many years, supercomputers, or massively parallel computers, have often functioned as time machines for Moore's law, showing what computing might look like when day-to-day computers caught up, typically four or five years later. Quantum computing has obvious similarities to supercomputing, although the vast theoretical processing advantage of quantum computing makes comparisons with the supercomputer of today fairly pointless. To a degree, quantum computers will have reached the point of instantaneous problem-solving for almost all computational problems (although researchers are hard at work imagining the problems which quantum computers will be unable to solve). Quantum computing may also revolutionise storage devices, permitting the storage of virtually infinite amounts of data in a handful of molecules. For some time, the networking community has postulated a scenario of infinite bandwidth on demand. Quantum computing adds two other scenarios of infinite processing power and infinite storage. Quantum computing may also bring infinite networking closer. Professor Gisin in Geneva has processed information between `entangled photons' instantly over ten kilometres. Because of entanglement, all the world's computing could in theory be instantaneously networked in a giant, super, quantum computer - a true world wide web.
Pounds, Shillings and Superposition
Before the superlatives and science beg incredulity, pragmatic businessmen have to ask why should they care, who is going to be affected, when will they be affected, where will it matter most, what can they do and how can they benefit. Before answering those questions it may be helpful to have a mental image of how quantum computers work in theory without resorting to photons and electrons. One of the easiest, practical metaphors for a quantum computer is a spreadsheet which has the ability to place in each cell a probability distribution function which can be manipulated using probability distribution functions in other cells. Today's spreadsheets have add-ons, such as Crystal Ball or @risk, which already provide such capabilities. However, when using spreadsheets with probability distribution functions today, one must sample time and time again to build up an accurate picture of the result, typically using techniques such as Monte Carlo analysis. Even on today's supercomputers, such models are too slow for many real world problems, such as instantaneous portfolio analysis in the financial markets, context-dependent speech recognition at low error rates, complex logistical solutions or instant data-mining of large consumer databases. To take the spreadsheet metaphor into the quantum computing world, now imagine that there is the capacity for billions of spreadsheet cells, each with a complex distribution function interacting simultaneously with all the other cells to arrive at a solution virtually instantaneously.
If your industry would be transformed by an infinite, instantaneous, complex spreadsheet combined with infinite storage and instantaneous communication, then you need to keep an eye on quantum computing. Quantum computing will directly affect the design of secure networks and data transmission. Some of the first applications are likely to be in the financial markets, which already make direct use of supercomputers, but find them too slow. Some of the next applications will also transfer from supercomputers, such as complex engineering design projects, but the wave of change will continue. Among the possible areas for complete transformation are:
logistics and distribution - all logistical calculations become virtually instantaneous;
service jobs - many roles could be eliminated with true speech recognition - the best fit of voice and meaning can be immediately found and customers would never know it was a computer;
consumer industries - advanced statistics can be used to pinpoint individual preferences changing minute by minute;
telecommunications - imagine eliminating telephone tag by being able to simultaneously schedule the millions of desired connections among people trying to contact each other, or even more radically, eliminating the need for fixed lines at all;
publishing - if quantum computing can break through the speech recognition barrier, then keyboards become unnecessary, opening the path to the wrist-watch computer instantaneously in touch with the whole of human knowledge, art, culture and commerce.
The limits to quantum computing today are imagination. As small qubit machines are built, we will see the boundaries of the technology more clearly, just as Turing's theoretical machine performed a bit less perfectly when it had to assume the flesh and blood of silicon and electricity. One interesting point is that even a small number of linked qubits in a stable, reliable device could begin tackling significant problems, probably highly computationally-dependent, valuable ones at first, which seems to point at quick hits in finance. A potentially useful model for assessing the possible impact is the following matrix which attempts to set out some of the potential hotspots:
I Thought Qubits Built the Pyramids
Most articles on future technology must violate Sam Goldwyn's warning - "never make forecasts, especially about the future". This article will abide with Sam on the time of arrival. It is difficult to say when quantum computing will have an impact. The very possibility already concerns people in the military and finance who deal with cryptography, but that does not make quantum computing real. Researchers give time frames of anything from five to twenty years for some basic aspects. A few researchers admit that they feel a quantum computer may never be built.
If your business relies on secure transmission or cryptography you should be looking at quantum computing today. If your business is networks, data storage or computation you should be watching current research. If you feel that you might be in a potential future hotspot, because removing limits to networks, data storage or computation could transform your industry, it may be worth introducing the impact of quantum computing into some of your strategic scenarios. What is certain is that the uncertainty of the quantum world will affect the `real' world sometime soon, probably.