Introduction Computation is an operation on symbols. We tend to perceive symbols as abstract entities, such as numbers or letters from a given alphabet. However, symbols are always represented by selected properties of physical objects. The binary string 10011011010011010110101101 may represent an abstract concept, such as the number 40 711 597, but the binary symbols 0 and 1 have also a physical existence of their own. It could be ink on paper (this is most likely to be how you see them when you are reading these words), glowing pixels on a computer screen (this is how I see them now when I am writing these words), or different charges or voltages (this is how my word processor sees them). If symbols are physical objects and if computation is an operation on symbols then computation is a physical process. Thus any computation can be viewed in terms of physical experiments, which produce outputs that depend on initial preparations called inputs. This sentence may sound very innocuous but its consequences are anything but trivial! On the atomic scale matter obeys the rules of quantum mechanics, which are quite different from the classical rules that determine the properties of conventional computers. Today’s advanced lithographic techniques can etch logic gates and wires less than a micrometer across onto the surfaces of silicon chips. Soon they will yield even smaller parts and inevitably reach a point at which logic gates are so small that they are made out of only a handful of atoms. So, if computers are to become smaller in the future, new, quantum technology must replace or supplement what we have now. The point is, however, that quantum technology can offer much more than cramming more and more bits onto silicon and multiplying the clock-speed of microprocessors. It can support an entirely new kind of computation, known as quantum computation, with qualitatively new algorithms based on quantum principles.
Introduction Computation is an operation on symbols. We tend to perceive symbols as abstract entities, such as numbers or letters from a given alphabet. However, symbols are always represented by selected properties of physical objects. The binary string 10011011010011010110101101 may represent an abstract concept, such as the number 40 711 597, but the binary symbols 0 and 1 have also a physical existence of their own. It could be ink on paper (this is most likely to be how you see them when you are reading these words), glowing pixels on a computer screen (this is how I see them now when I am writing these words), or different charges or voltages (this is how my word processor sees them). If symbols are physical objects and if computation is an operation on symbols then computation is a physical process. Thus any computation can be viewed in terms of physical experiments, which produce outputs that depend on initial preparations called inputs. This sentence may sound very innocuous but its consequences are anything but trivial! On the atomic scale matter obeys the rules of quantum mechanics, which are quite different from the classical rules that determine the properties of conventional computers. Today’s advanced lithographic techniques can etch logic gates and wires less than a micrometer across onto the surfaces of silicon chips. Soon they will yield even smaller parts and inevitably reach a point at which logic gates are so small that they are made out of only a handful of atoms. So, if computers are to become smaller in the future, new, quantum technology must replace or supplement what we have now. The point is, however, that quantum technology can offer much more than cramming more and more bits onto silicon and multiplying the clock-speed of microprocessors. It can support an entirely new kind of computation, known as quantum computation, with qualitatively new algorithms based on quantum principles.
On the atomic scale, matter obeys the rules of quantum mechanics which are quite different from the classical rules that determine the properties of conventional computers. Today's advanced lithographic techniques can etch logic gates and wires less than a micron across onto the surfaces of silicon chips. Soon they will yield even smaller parts and inevitably reach a point where logic gates are so small that they are made out of only a handful of atoms. So, if computers are to become smaller in the future, new, quantum technology must replace or supplement what we have now. This article provides a grand overview of quantum information theory from the concept of quantum bits (qubits) to entanglement to quantum computation to quantum cryptography.
Behold your computer. Your computer represents the culmination of years of technological advancements beginning with the early ideas of Charles Babbage (1791-1871) and eventual creation of the first computer by German engineer Konrad Zuse in 1941. Surprisingly however, the high speed modern computer sitting in front of you is fundamentally no different from its gargantuan 30 ton ancestors, which were equipped with some 18000 vacuum tubes and 500 miles of wiring! Although computers have become more compact and considerably faster in performing their task, the task remains the same: to manipulate and interpret an encoding of binary bits into a useful computational result. A bit is a fundamental unit of information, classically represented as a 0 or 1 in your digital computer. Each classical bit is physically realized through a macroscopic physical system, such as the magnetization on a hard disk or the charge on a capacitor. A document, for example, comprised of n-characters stored on the hard drive of a typical computer is accordingly described by a string of 8n zeros and ones. Herein lies a key difference between your classical computer and a quantum computer. Where a classical computer obeys the well understood laws of classical physics, a quantum computer is a device that harnesses physical phenomenon unique to quantum mechanics (especially quantum interference) to realize a fundamentally new mode of information processing. In a quantum computer, the fundamental unit of information (called a quantum bit or qubit), is not binary but rather more quaternary in nature. This qubit property arises as a direct consequence of its adherence to the laws of quantum mechanics which differ radically from the laws of classical physics. A qubit can exist not only in a state corresponding to the logical state 0 or 1 as in a classical bit, but also in states corresponding to a blend or superposition of these classical states. In other words, a qubit can exist as a zero, a one, or simultaneously as both 0 and 1, with a numerical coefficient representing the probability for each state. This may seem counterintuitive because everyday phenomenon are governed by classical physics, not quantum mechanics – which takes over at the atomic level. This rather difficult concept is perhaps best explained through an experiment. Consider Figure 1 below:
We have seen how information can be encoded onto a quantum system by selecting the state in which it is prepared. Retrieving the information is achieved by performing a measurement, and the optimal measurement in any given situation is usually a generalized measurement. In between preparation and measurement, the information resides in the quantum state of the system, which evolves in a manner determined by the Hamiltonian. The associated unitary transformation may usefully be viewed as quantum information processing; if we can engineer an appropriate Hamiltonian then we can use the quantum evolution to assist in performing computational tasks. Our objective in quantum information processing is to implement a desired unitary transformation. Typically this will mean coupling together a number, perhaps a large number, of qubits and thereby generating highly entangled states. It is fortunate, although by no means obvious, that we can realize any desired multiqubit unitary transformation as a product of a small selection of simple transformations and, moreover, that each of these need only act on a single qubit or on a pair of qubits. The situation is reminiscent of digital electronics, in which logic operations are decomposed into actions on a small number of bits. If we can realize and control a very large number of such operations in a single device then we have a computer. Similar control of a large number of qubits will constitute a quantum computer. It is the revolutionary potential of quantum computers, more than any other single factor, that has fuelled the recent explosion of interest in our subject. We shall examine the remarkable properties of quantum computers in the next chapter. In digital electronics, we represent bit values by voltages: the logical value 1 is a high voltage (typically +5 V) and 0 is the ground voltage (0 V). The voltage bits are coupled and manipulated by transistor-based devices, or gates. The simplest gates act on only one bit or combine two bits to generate a single new bit, the value of which is determined by the two input bits. For a single bit, with value 0 or 1, the only possible operations are the identity (which does not require a gate) and the bit flip.
In the Name of the Pasta, and of the Sauce, and of the Holy Meatballs … – Bobby Henderson, The Gospel of the Flying Spaghetti Monster, 2006 After the conceptual comes the practical. While the study of quantum foundations is as old as quantum theory itself, the field of quantum computing is relatively new. So new in fact that large-scale, practical quantum computing is still not a reality. A typical ‘quantum computer’ takes many months to set up before performing such astounding tasks as factoring 6 into 3 × 2. Nonetheless, if those machines would exist, we know that we would gain amazing speed-ups in solving some hard (classical) computational problems, such as those involved in breaking a huge portion of cryptographic systems in use today. Before we get into ‘quantum computing’, we should say a couple of things about ‘computing’. What is computing? Our answer by now probably won't come as such a shock: it's a process theory! Computation is indeed all about wiring the inputs and outputs of small processes together to make bigger processes. More specifically, a computation consists of a (finite) set of basic processes, which are wired together according to some (also finite) instructions, which we refer to as an algorithm or simply a program . The only essential difference between classical and quantum computation is the contents of the basic processes. For classical computation, these operations consist of things like logical operations (e.g. XOR) or reading/writing locations in memory. For quantum computation, we can extend this with quantum processes and classical-quantum interactions such as measurements. So quantum computing is all about figuring out how to write new kinds of programs that exploit these new building blocks to build faster algorithms or accomplish new kinds of tasks that aren't possible classically. The first quantum algorithms were ‘proofs of concept’, in the sense that they solved some problem much faster than a classical computer, but the kinds of problems they solved were not particularly interesting in their own right. However, this changed drastically with the advent of Grover's quantum search and Shor's factoring algorithms.
In the preceding chapter we established that a suitable set of quantum gates, complemented by quantum error correction, allows us to produce a desired multiqubit unitary transformation. This transformation is one of the three steps in a quantum computation; the others, of course, are the preparation of the qubits in their initial state and the measurement of them after the transformation has been implemented. A quantum computation is designed to solve a problem or class of problems. The power of quantum computers is that they can do this, at least for some problems, very much more efficiently and quickly than any conventional computer based on classical logic operations. If we can build a quantum computer then a number of important problems which are currently intractable will become solvable. The potential for greatly enhanced computational power is, in itself, reason enough to study quantum computers, but there is another. Moore’s law is the observation that the number of transistors on a chip doubles roughly every eighteen months. A simple corollary is that computer performance also doubles on the same timescale. Associated with this exponential improvement is a dramatic reduction in the size of individual components. If the pace is to be kept up then it is inevitable that quantum effects will become increasingly important and ultimately will limit the operation of the computer. In these circumstances it is sensible to consider the possibility of harnessing quantum effects to realize quantum information processors and computers. We start with a brief introduction to the theory of computer science, the principles of which underlie the operation of what we shall refer to as classical computers. These include all existing machines and any based on the manipulation of classical bits. The development of computer science owes much to Turing, who devised a simple but powerful model of a computing device: the Turing machine. It its most elementary form, this consists of four elements. (i) A tape for data storage, which acts as a memory. This tape has a sequence of spaces, each of which has on it one of a finite set of symbols. (ii) A processor, which controls the operations of the machine.
Digital computers are based on devices that can take on only two states, one of which is denoted by 0 and the other by 1. By concatenating several 0s and is together, 0-1 combinations can be formed to represent as many different entities as desired. A combination containing a single 0 or 1 is called a bit. In general, n bits can be used to distinguish among 2 n distinct entities and each addition of a bit doubles the number of possible combinations. Computers use strings of bits to represent numbers, letters, punctuation marks, and any other useful pieces of information. In a classical computer, the processing of information is done by logic gate. A logic gate maps the state of its input bits into another state according to a truth table. Quantum computers require quantum logic, something fundamentally different to classical Boolean logic. This difference leads to a greater efficiency of quantum computation over its classical counterpart. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.