Features:

QUANTUM COMPUTING REALITIES
by Christopher Lazou

LONDON: 01.15.2004: Tony Hey, Professor of Computation, University of Southampton, author of the book “A Quantum Universe” and currently director of the UK e-Science Core Programme gave a lecture to the British Computing Society London Branch titled: “Quantum Computing Realities”.

Below is a brief preamble of near future CMOS technologies and quantum computing in the spirit of Tony’s presentation.

As the ultimate physical limits of the silicon materials used in microelectronics appear on a horizon which could be just 10 years away, computer vendors are looking at alternatives such as quantum computing to continue the progress of the last half-century.

When one looks at the CMOS road map, VLSI technology at, say, 50 nanometres is possible in 3 to 5 years' time. However, when the technology goes below 100 nanometres it hits many problems, not least current leakage.

Recent work using organic material on copper demonstrated devices using 80 nanometre technologies. Copper is apparently a must for VLSI at these gate densities. The Industry Technology Road Map for Semiconductors, agreed by the International Semiconductor Association for logic devices on CMOS, predicts that scaling barriers kick in from about 2008 to 2014. For example, it is generally agreed that a one-nanometre thickness oxide is not possible.

In the past microelectronic advances were driven by conventional scaling, but now new approaches are needed to develop devices. New processes using new material, new architectures and new circuits are needed.

With the advent of larger 10x10mm chips, a new approach is to use a fast clocking strategy (at several GHz speed) and at the same time adopt dynamically reconfigured logic. This can be done at very high speed: in five nanoseconds eight tasks can be mapped on the same hardware device.

Another trend is to put multiple processors on a chip. To overcome high stand- by power dissipation, a software controlled power management circuit is needed. So the next generation of CMOS is likely to have equivalent scaling with adjustable wide range multiple parameters to allow many tasks to be performed on the same hardware device. Back-to-back processors can also eliminate inter-processor communication delays.

To illustrate where research is going an 8nm EJ-MOSFET-device, was built by NEC back in year 2001. This device requires less than one volt to power it.

The question is how do these device speeds translate when they are incorporated into computer systems? High end supercomputing is more than a chip: it also involves memory bandwidth, heat extraction and tight communication system integration. So although device developers see a life in CMOS for possibly the next 20 years, high performance computer system designers see extra barriers which bring this back to around 7 to 10 years in line with the Industry Technology Road Map for Semiconductors.

Beyond CMOS, after 2010 to 2014, there will be new material challenges. Some of these materials are in the experimental phase, with many, reliability, design, manufacturing process and operating environment issues to be solved. These include Josephson junction technology, single electron transistor (SET), and single flux quantum (SFQ).

With Josephson junction devices heat dissipation is about 1,000 times lower than that incurred with silicon. Many computer manufacturers, including IBM, Control Data, and NEC, demonstrated components with logic gates switching at 10 picoseconds (10 millionths of a millionth of a second) as early as 1981. As superconductivity occurs at low temperatures, the devices have to be submerged in cryogenic liquids. This causes difficulties in interconnection and chip packaging.

Single flux quantum can apply conventional Boolean algebra where the existence of single flux within a Josephson junction loop expresses zero or one. But quantum computing is completely different from conventional computing.

Professor Tony Hey gave an informative overview of the fundamental issues concerning quantum computing. He briefly described the work of early pioneers, Richard Feynman, John Bell, Gilles Brassard, Charles Bennett, IBM and then touched on the work of current date practitioners John Meyers, (Harvard and BBN Q-Net), Nicolas Gissin, (Geneva), Artur Eckert, (Cambridge, UK), and many others. It was Feynman in his quest for the Holly Grail in simulating the physical world with its quantum mechanical nature exactly who dreamed up the idea of building a quantum computer.

The main thrust of Tony’s lecture was encapsulated in: “The discovery that quantum physics allows fundamentally new modes of information processing has required the existing theories of computation, information and cryptography to be superseded. With significant progress being made in the practical use of quantum computing for securing communications with advanced cryptography, the future of this astonishing technology and the challenges to be overcome is discussed”.

Quantum computing, quantum encryption and teleportation are three lines of enquiry actively pursued at present. In brief, quantum computing, uses the properties of atom spin (sometimes ions) as its basic unit, a quantum bit, or Qubit. A conventional digital computer bit has values of either zero or one; in addition to these two states, quantum computers can also store zero and one, the superposition state simultaneously.

Those of you familiar with quantum mechanics will appreciate that a "0+1" corresponds to a Qubit made of a spin, whose state is superposition of 0 and 1 at equal probability. This corresponds to the state where the spin lies horizontally. This superposition states can be extended to more than one Qubit. For example, with 2 Qubits a superposition state of "11+00" is possible in quantum computers, but this cannot be realized classically, even if any classical superposition states are employed. (This state is called quantum entanglement). The use of Qubits with entanglement allows the development of a super-parallel quantum computer. By using N Qubits, one can do two to the power N calculations simultaneously. What one is calculating however, is the probability of the correct answer. This probability is further enhanced using a quantum Fourier transformation, one of the core building blocks of quantum computation, including the Shor’s algorithm.

Quantum computers can in theory do all calculations currently done on conventional computers, but this is not always advantageous as they require special algorithms and are unlikely to become general-purpose machines. It is certain that word processing for example, will remain on conventional computers. There are however, certain problems, which lend themselves to quantum computing. So far only two kinds of practical use have been discovered, in database searching using Grover’s algorithm and factorisation using Shor’s. This situation is expected to change as many more researchers pick up the challenge.

As an illustration, the only way to do factorisation is to check, whether or not the number in question is factorised by each prime number in order. As the number of digits increase the time taken on conventional computers increases exponentially. For example, factorisation of the 129-digit number known as RSA-129 took eight months to perform using several thousands of PCs and factorisation of a number with 256 digits would take several million years to perform, even when using IBM’s Blue Gene petaflop/s computer promised for delivery in 2005. The safety of public key cryptography systems used on the Internet, rely on this difficulty of such calculations. Using Shor’s algorithm with a quantum computer with say 10,000 Qubits, this can be achieved in a few minutes. This has enormous implications on current cryptography and this is why for security reasons, people are now developing quantum mechanical cryptography keys.

It is claimed that this new technology (quantum cryptography) effectively removes the uncertainty about security, but does it? Systems being build are simplifications of the theoretical model and appear to have potentially an Achilles heal in the transmission of the key. According to Artur Eckert the BB84 quantum encryption protocol is potentially vulnerable to eavesdropping in practice. Even his protocol, using photon pairs is not 100% secure [See New Scientist 11.29.2003, pp24-27].

Quantum computers also have the potential for performing super-quick database searches, (using Grover’s algorithm), especially useful for searching the vast amount of information residing on the Internet, searching bio-informatic or engineering databases to extract optimal designs and so on.

Hardware developments are in their infancy and lagging behind requirements. It is estimated that around 10,000 Qubits are needed for practical factorisation.

The IBM experiment in 2001, using nuclear magnetic resonance (NMR), Isaac Chuang managed to use up to seven Qubits. The IBM experiment changed atoms into ions and used the two internal spin states of the ion as a Qubit. It then used the microwave pulses as addresses. Unfortunately, because of heat, the NMR method does not allow the generation of more than 15 Qubits. IBM is also developing the more promising solid-state device technology. I have tried to solicit the latest from IBM at Watson Labs, but unfortunately received no response.

NEC has demonstrated a solid-state Qubit, making a super-conductive single electron box with Josephson junctions, in 1999. Its work won NEC Japan's prestigious Nishina Memorial prize for physics, but there is a long way to go before Qubits can be used for realistic quantum computation, as this requires Qubits with much longer coherence time. In February 2003, NEC in collaboration with the Institute of Physical and Chemical Research, Japan, succeeded in building the first solid-state “integrated” circuit consisting of two, coupled, charge Qubits.

The recent announcement from the University of Queensland, Brisbane, Australia, that they have produced a quantum logic gate using linear optics illustrates that many avenues of research are still open in this field.

Using his own 4 by 4 Hadarmard control NOT gates mounted on a board, Tony gave a demonstration of Grover’s search algorithm, explaining how 16Qubits amount to16 electrons while an equivalent conventional device requires 65,536 wires, an enormous difference in size. Note that searching a random database using a classical algorithm requires O(N/2) steps. The Quantum algorithm requires O(square root N) steps.

There are many technological challenges and fundamental obstacles to overcome before building a quantum computer to solve large real physics problems. Because in quantum mechanics the very fact that an event is observed it is changed, a major problem to be overcome is whether the gate can be isolated long enough (coherence) to enable computation. To-date there is no solution in sight when using a large number of Qubits, thus unavoidable interactions with the environment lead to errors in the quantum computer. If or when the problems are solved, devices could be built with one billion transistors on a chip just one- nanometre square.

As David DiVincenzo from IBM, wrote in one of his papers: “the quantum computer at the present time is only a vision, but it is certainly not merely a fantasy. If the spin-resonance transistor that I have described proves to be unworkable, I am sure that ultimately some other quantum-computing device will do the job. Countless previous proposals for new computing devices have suffered “death by Moore’s law,” in which they are rendered irrelevant by the relentless advance of silicon technology (think of optical computing, or gallium arsenide). But quantum computing cannot suffer this fate; the theoretical work of Shor and others guarantees that even a quantum computer with just 10,000 bits, no matter how long it takes to build, will always have capabilities that no digital computer, at any time in the future, could have. So, come back in year 2030 to see how we’ve been doing”!

Re-enforcing this view, Tadashi Watanabe, senior vice president and executive general manager for R&D at NEC, wrote recently: “We are now facing various severe problems critical for our lives such as the energy and global environmental problems. In addition, with the progress in life science and nano-science, new methods of personalized tailor-made medical treatment and development of new medicine based on genome science, as well as new material development based on computer simulation are now within our range of realization, and these developments require an enormous amount of computing power. The quantum computer, if realized, will surely be a promising tool for such research and development. There are, however, many difficulties in realizing it. The current technology is only at the stage where we are just seeing the possibility of producing quantum devices. To produce a quantum computer for commercial use, we must resolve many problems such as design and manufacturing technologies, systems configuration, reliability and maintainability similar to the problems experienced with conventional computers....”.

He went on to say: “Even more important is the issue of software. The design methodology of software must be completely rebuilt in the quantum computer system because the principle of the computation mechanism is entirely different from that of the conventional computer based on the von Neumann model. The algorithms, languages, operating system software, and input/output system must be fundamentally reconsidered and newly developed, by which we mean abandoning all software assets accumulated in the past if we change to the quantum computer. Considering such things, the application field of the quantum computer may be very limited. Even so, however, its immeasurable power of computation will give full play to resolving the scientific and engineering problems we are now facing, and will face in the future”.

(Brands and names are the property of their respective owners) Copyright: Christopher Lazou, HiPerCom Consultants, Ltd., UK. Email: Chris@lazou.demon.co.uk January 2004.