Brief Historical Survey and Perspectives

Various names are commonly associated to the invention and development of modern computing science. Among them, are George Boole (1815–1864), author of a work published in 1854 with the title: An investigation into the laws of thought, on which are founded the mathematical theories of logic and probabilities, which founded the nowadays called Boolean Algebra, and Claude Shannon (1916–2001) who, in 1938 on his MIT MSc Thesis, A symbolic analysis of relay and switching circuits, proposed a way for representing Boolean logic operators through relays and switches.

However, the Theory of Computation became an area of abstract mathematics only after the work of Alan Turing (1912–1954) and Alonzo Church (1903–1995). On his attempt to answer one of the challenges proposed by the great mathematician David Hilbert in 1928, the entscheidungsproblem or decision problem, Turing arrived to an abstract model of computation known as the Turing Machine. His idea was published in 1936 as a ground breaker paper entitled On computable numbers, with an application to the entscheidungsproblem [1]. A Turing Machine operates with a minimum number of symbols and instructions to perform logic operations: it is the embryo of all modern programmable computers.

Another breakthrough paper appeared twelve years afterwards, in 1948, again by Claude Shannon: A mathematical theory of communication [2]. On this paper, Shannon defined the unit of information, the binary digit, or bit,1 and established the theory which tells us the amount of information (i.e., the number of bits) which can be sent per unit time through a communication channel, and how this information can be fully recovered, even in the presence of noise in the channel. This work founded the Theory of Information.

The computation and information technologies have developed very close to each other, in an astonishingly rapidly pace, for the last 50 years. Nowadays, a few square centimeters computer chip possesses hundreds of millions of electronic constituents, and a hairy thin optical fibre can transmit and maintain millions of conversations simultaneously!

On the side of pure Physics, the 20th Century also produced some “miracles”, one of them – and possibly the most important of all – was Quantum Mechanics. The early development of this theory has attached to it a whole team of brilliant scientists: Max Planck, Niels Bohr, Albert Einstein, Louis de Broglie, Erwin Schrödinger, Wolfgang Pauli, Werner Heisenberg, only to name some of the best known. Quantum mechanics contains the rules of how to approach and solve problems involving particles such as electrons, protons, nuclei, atoms, molecules, and the interactions between these particles and radiation. Along the years, computers entered physics as a powerful ally for the analysis and development of physical models in particle and nuclear physics, condensed matter, gravitation, astrophysics, biological and ecological systems, and so on. In particular, the development of condensed matter magnetism and semiconductor physics resulted in important feedback to computer technology itself. This symbiotic relationship between physics and computers, deepened for decades until the point where computers themselves started to be seen by the physicists, no longer as an auxiliary tool for the solution of complicated mathematical problems, but as physical systems, subject to the laws of physics, just like everything else! This insight led to a novel and exciting area of research in Physics: Quantum Computation and Quantum Information.

Quantum Information is the area of research in physics in which quantum resources are identified for the application in information processing, as well as the means to produce, store, send and recover information traveling through communication channels. One example of quantum resource for communication is entanglement, and one example of quantum information processing is superdense coding. To the more specific application of quantum resources to the development of quantum computer algorithms and quantum hardware, we call Quantum Computation. One example of quantum algorithm is the Shor factorization algorithm, and one example of quantum computing hardware are nuclear spins.

The “formal” beginning of the research field called Quantum Computation and Quantum Information can be attributed to a paper published in 1980 by Paul Benioff [3]: The computer as a physical system: a microscopical quantum mechanical Hamiltonian model of computers as represented by Turing machines. In this paper it is pointed out for the first time that unitary transformations undergone by quantum systems can be used to implement computing logical operations. However, the work of Benioff was inspired by an earlier paper, published in 1973 by the IBM physicist Charles Bennett [4]. In his paper, Logical reversibility of computation, Bennett showed that computation could be built entirely on the basis of reversible logic, although actual computers operate with irreversible processes. Indeed, computation is carried out in computers through the action of the so-called logic gates. One complete set of such gates are the NOT, AND and OR gates. Whereas NOT is a reversible gate (in the sense that the information at the input of the gate can be recovered applying the gate to the output), AND and OR are irreversible, in the sense that information is lost in their action, implying an increase of entropy equal to at least kB ln 2 for each bit which is lost.2 On the other hand, quantum unitary transformations are reversible: from the knowledge of the state of a quantum system in time t0, one can obtain the state in later time t: |ψ(t) = U(t, t0)|ψ(t0), where U(t,t0) is a unitary propagator which satisfies the Schrödinger equation. However, since UU† = 1, where 1 is the identity matrix, one can recover |ψ(t0) from |ψ(t) through the operation: |ψ(t0) = U† (t, t0)|ψ(t). Of course, this is only valid for isolated systems. One of the major triumphs of Quantum Information Theory has been the development of tools which allow the treatment of non-isolated systems for quantum computation.

After Benioff, in the year of 1985, David Deutsch gave a decisively important step towards quantum computers presenting the first example of a quantum algorithm [6]. The Deutsch algorithm shows how quantum superposition can be used to speed up computational processes. Another influent name is Richard Feynman, who was involved about the same time in the discussions of the viability of quantum computers and their use for quantum systems simulations [7].

However, it was in 1994 that a main breakthrough happened, calling the attention of the scientific community for the potential practical importance of quantum computation and its possible consequences for modern society. Peter Shor discovered a quantum algorithm capable of factorizing large numbers in polynomial time [8]. Classical factorization is a kind of problem considered by computation scientists to be of exponential complexity. This basically means that the amount of time required to factorize a number N bits long, increases exponentially with N. In contrast, a quantum computer running Shor algorithm would require an amount of time which would be a polynomial function of N. This is a huge difference! To give an example, if N = 1024 bits, a classical algorithm would take about 100 thousand years to factorize the number, whereas Shor algorithm would accomplish the task in a few minutes!

Shor algorithm has not yet been tested in numbers that long, but its quantum working principles have already been demonstrated in laboratory, through the technique of nuclear magnetic resonance (NMR) [9]. The algorithm clearly raises important concerns about the security of cryptosystems based on the factorization of large numbers, such as the RSA protocol. Arthur Eckert captures the essence of the problem in the quote [10] “… modern security systems are in a sense already insecure… ”.

A few years after the discovery of Shor algorithm, in 1997, another important algorithm was discovered by Lov Grover [11]. The so-called Grover algorithm is a quantum search algorithm, which makes use of quantum superposition and quantum phase interference to find an item in a disordered list of N items with a squared speedup with respect to an equivalent classical algorithm. After the discoveries of Shor and Grover algorithms the interest in quantum computation and quantum information has grown dramatically along the years, as exemplified in Figure 1, which shows the number of refereed papers published in the subject from 1990 till nowadays.3