Until recently, the paradigm of computing was the Turing machine and its numerous equivalents. All operations are made with state machines. Each operation is irreversible and brings about an increase of entropy and, therefore, an expenditure of energy of at least kTln2 per bit. We show that optics allows the first practical quantum mechanical digital processors. These processors require digital input and produce digital output but need no intermediate state machines. We show that, in the sense of not requiring material devices which would otherwise be required, nothing is superior to something for computing.
Until recently, the paradigm of computing was the Turing machine and its numerous equivalents. All operations are made with state machines. Each operation is irreversible and brings about an increase of entropy and, therefore, an expenditure of energy of at least kTln2 per bit. We show that optics allows the first practical quantum mechanical digital processors. These processors require digital input and produce digital output but need no intermediate state machines. We show that, in the sense of not requiring material devices which would otherwise be required, nothing is superior to something for computing.
Digital computers can perform fast sequential operations. After bit operations, a definite sequence of zeros or ones is obtained, which is similar to the use of an electronic mechanism to quickly operate a huge abacus. The bit of a digital computer is in a definite state of zero or one, but actual physics is continuous. There exists a significant deficiency in using digital Turing machines to describe the physical world. On the other hand, quantum physics happens to be discontinuous, and, thus, quantum Turing machines are truly compatible with problems in the quantum world.
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.
The Church-Turing thesis says that a digital computer is a universal computational device; that is, it is able to simulate any physically realizable computational device. It has generally been believed that this simulation can be made efficient so that it entails at most a polynomial increase in computation time. This may not be true if quantum mechanics is taken into consideration. A quantum computer is a hypothetical machine based on quantum mechanics. We explain quantum computing, and give an algorithm for prime factorization on a quantum computer that runs asymptotically much faster than the best known algorithm on a digital computer. It is not clear whether it will ever be possible to build large-scale quantum computers. One of the main difficulties is in manipulating coherent quantum states without introducing errors or losing coherence. We discuss quantum error-correcting codes and fault-tolerant quantum computing, which can guarantee highly reliable quantum computation, given only moderately reliable quantum computing hardware.
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.
In 2001, all-optical quantum computing became feasible with the discovery that scalable quantum computing is possible using only single-photon sources, linear optical elements, and single-photon detectors. Although it was in principle scalable, the massive resource overhead made the scheme practically daunting. However, several simplifications were followed by proof-of-principle demonstrations, and recent approaches based on cluster states or error encoding have dramatically reduced this worrying resource overhead, making an all-optical architecture a serious contender for the ultimate goal of a large-scale quantum computer. Key challenges will be the realization of high-efficiency sources of indistinguishable single photons, low-loss, scalable optical circuits, high-efficiency single-photon detectors, and low-loss interfacing of these components.
Universal computing can be dated to 1903 when Alan Turing’s theoretical model of the Turing machine led a large-scale innovative revolution towards digital computing machines.¹ The next milestone is to process and control information at its fundamental level — quantum states of particles. Richard Feynman first pointed out that as certain types of computational problems get more complex, classical bits fail to give efficient answers.² For example, when simulating quantum mechanics, the amount of memory needed to describe a quantum system increases exponentially with the number of its components. A new device — a quantum computer — is therefore highly sought after by physicists.³