Untangling Complex Systems, page 95
When the opposite is true, we can infer the input from the output, and the information is pre-
served at every step, we are carrying out reversible logical operations. According to the Landauer’s
principle (Landauer 1961), any elementary irreversible logical operation determines a dissipation of
energy equal to kTln 2, and therefore an increase of entropy. Landauer’s principle has been confirmed
experimentally by measuring the amount of heat generated by erasure of a bit encoded by a single
colloidal particle optically trapped in a modulated double-well potential (Bérut et al. 2012). However,
recent theoretical studies (Maroney 2005; Gammaitoni et al. 2015), and experiments (López-Suárez
et al. 2016) have demonstrated that an irreversible logical operation can be performed in a thermo-
dynamically reversible manner (i.e., very slowly) and generate an amount of heat smaller than kTln 2.
Logically irreversible operations do not always imply a dissipation of energy into the environment.
Therefore, Landauer’s principle holds strictly only for “information entropy,” also called Shannon
entropy or uncertainty H (remind what we studied in Chapter 2): any irreversible logical operation that determines the erasure of one bit, increases the “information entropy” of one bit.4
A computation, whether it is performed on an abacus or by an electronic computer or in a soup of
chemicals, is a physicochemical process. How large is the computing machine? How much energy is
required to perform an operation? How fast does the computer run? How frequently does it give the
wrong result? The answers lie in the physical laws that govern the behavior of the computing machine.
13.3.2.2 Classical Physics
Initially, humans used fingers, small stones,5 notched sticks, knotted strings, and other similar devices to make computations. People gradually realized that these methods of calculation could not go far
4 Another example wherein “information entropy” pops up and that you might have encountered previously, is that associated with the process of mixing two ideal gases. The internal energy of the two gases does not change but the mixing
determines a loss of information. Try exercise 13.6.
5 The word calculation derives from the Latin “calculus” that means small stone.
How to Untangle Complex Systems?
485
enough to satisfy increasing computational needs. For counting with large numbers, they would have
had to gather too many pebbles or other tools. Once the principle of the numerical base had been
grasped, the usual pebbles were replaced with stones of various sizes to which different orders of units
were assigned. For example, if a decimal system was used, the number 1 could be represented by a
small stone, 10 by a larger one, 100 by a still larger one, and so on. It was a matter of time before some-
one developed first devices to facilitate calculation. Someone had the idea of placing pebbles or other
objects in columns, assigning a distinct order of units to objects belonging to different columns and
invented the counting board or abacus. Later, the arrangement of objects in columns was replaced with
a more elegant one, wherein pebbles could slide along parallel rods. The abacus was really useful to
make calculations with large numbers. A further significant contribution in this direction was contrib-
uted by the Scottish mathematician John Napier (1550–1617), who discovered that multiplication and
division of numbers could be performed by addition and subtraction, respectively, of the logarithms of
those numbers. Moreover, he designed his “Napier’s bones,” a manually-operated device that simpli-
fied calculations involving multiplication and division. In the 1620s, logarithmic scales were put to
work by the English mathematician and Anglican minister William Oughtred (1574–1660) who devel-
oped the slide rule, where each number to be multiplied is represented by a length on a sliding ruler.
Although abacus-like devices and sliding rulers were significant computational aids, they still
required direct physical and mental involvement of the operator with a consequent high risk of
mistakes, especially after many hours of labor. An improvement was achieved by devising the first
mechanical calculators. The history of mechanical computing machines is mostly the story of the
numeral-toothed wheels and the devices that rotate them to register digital and tens-carry values
(Chase 1980). The devices that rotate numeral wheels are grouped in (I) rotary or crank-type actua-
tors (see Figure 13.23a) and (II) reciprocating or cam actuators (see Figure 13.23b).
In the mid-seventeenth century, Blaise Pascal (1623–1662) built a mechanical adding and sub-
tracting machine called the Pascaline as an aid to his father Etienne, who was a high official in
Basse-Normandie, and following a revolt over taxes, he reorganized the tax system of that area
(Goldstine 1993). In the same century, Gottfried Wilhelm Leibniz (1646–1716) invented a device,
now known as the Leibniz wheel, suitable for doing not only additions and subtractions but also
multiplications and divisions. In the next two hundred years, mechanical calculating machines
were mainly remarkable gadgets exhibiting human ingenuity, rather than concrete aids to cal-
culation. Scientists, engineers, navigators, bankers, and actuaries who had to carry out complex
computations, demanding high accuracy, could trust in the pen, paper, and numerical tables (such
as trigonometric, multiplication, and logarithmic tables). Numerical tables were fruits of monoto-
nous and fatiguing mental labor, and often they were full of errors. For this reason, in the first
half of the nineteenth century, the English mathematician Charles Babbage (1791–1871) dreamt
of designing automatic mechanical computers to compile more accurate numerical tables and
10 8
6 4
2
6
4
2
0
−2
−4 −6
0
9
8
7
0
6
1
5
2
4
3
(a)
(b)
FIGURE 13.23 Two examples of digital value actuators: rotary or crank-type actuator (a), and reciprocating
or cam actuator (b).
486
Untangling Complex Systems
help people in routine calculations. He first designed a “Difference Machine” to compute polyno-
mial functions. At the heart of his machine’s operation was the use of gears to count. Babbage’s
Difference Machine was a single-purpose computer: it had only one program and one task. Later
on, Babbage contrived a general-purpose computing machine by designing an “Analytical Engine.”
The Analytical Engine had the essential features and elements of a modern electronic computer
but in a mechanical form. It was programmable using punched cards; it had a “Store,” a memory
where numbers and intermediate results could be held; and it had a separate “Mill,” a mechanical
processor where arithmetic logic unit and control flow were implemented in the form of condi-
tional branching and loops. The “Mill” allowed for performing all the four fundamental arithmetic
operations, plus comparison and optionally square roots. Finally, it had a variety of outputs includ-
ing hardcopy printout, punched cards, and graph plotting. Unfortunately, Babbage never finished
the construction of both his Difference Machine and his Analytical Engine. Probably, one reason
was that the technology of those days was not reliable enough. In retrospect, we can notice some
inherent problems with the use of mechanical devices for computing (Wolf 2017). One problem
is that mechanical components are relatively heavy. Therefore, a substantial amount of energy is
needed to make them work. Since the twentieth century, energy was generated by electric motors.
Another problem is that the mechanical components are subject to friction and hence to damage
in their connections.
The era of modern electronic computers began with a flurry of development before and during
the Second World War. At first, mechanical computers were overtaken by electromechanical com-
puters based on electric operated switches, called relays. These devices had a low operating speed
and were eventually superseded by much faster all-electric computers, originally using vacuum
tubes. At the same time, digital calculation replaced analog. The foundation of binary logic was laid
by the English mathematician George Boole (1815–1864), who published An Investigation of the
Laws of Thought in 1854. In his book, Boole investigated the fundamental laws of human reason-
ing and gave expression to them in the symbolical language of a Calculus, now known as Boolean
Algebra. In the 1930s, the American electrical engineer Claude Shannon (1916–2001) showed the
correspondence between the concepts of Boolean logic and the electronic circuits implementing the
logic gates. After the Second World War, the progress of computers continued, and the physicist
John von Neumann, inspired among others by the ideas of Alan Turing (1912–1954), proposed
his model that is still used in the current electronic computers that are based on transistors, as we
learned in paragraph 13.2.
13.3.2.3 Computing with Subatomic Particles, Atoms, and Molecules
A strategy to make electronic computers increasingly faster and energetically efficient is to minia-
turize the basic switching elements—the transistors. This strategy is called the top-down approach
and the pace of its accomplishment is epitomized by Moore’s law as we learned in paragraph 13.2.
The American physicist Richard Feynman (1918–1988) paved the way for an alternative strategy,
called the bottom-up approach in his seminal lecture titled “There is Plenty of Room at the Bottom,”
taken at the annual meeting of the American Physical Society at the end of 1959 (Feynman 1960).
The bottom-up approach is based on the idea of manufacturing computers by assembling atoms
and molecules. Matter at the atomic level does not behave classically but quantum-mechanically.
Indeed, the subatomic particles, atoms, and molecules can be used to process a new kind of logic
that is quantum logic. Quantum states of matter have different properties with respect to the classical
states of matter. Therefore, quantum information is different from classical information. The ele-
mentary unit of quantum information is the qubit or quantum bit (Schumacher 1995). A qubit is a
quantum system that has two accessible states, labelled as 0 and 1 (note that the “bracket” notation
means that whatever is contained in the bracket is a quantum-mechanical variable), and it can
exist as a superposition of them. In other words, a qubit, Ψ , is a linear combination of 0 and 1 :
Ψ = a 0 + b b [13.12]
How to Untangle Complex Systems?
487
wherein a and b are complex numbers, verifying the normalization condition
a 2 + b 2 = 1 [13.13]
The qubit can be described as a unit vector in a two-dimensional vector space, known as the Hilbert
space. The states 0 and 1 are the computational basis states and form an orthonormal basis for
the Hilbert space. The qubit can also be described by the following function (Chruściński 2006):
θ
ϕ
θ
Ψ =
cos 0 +
ei sin 1 [13.14]
2
2
wherein θ and ϕ define a point on the unit three-dimensional sphere, called the Bloch sphere (see
Figure 13.24). Represented on such a sphere, a classical bit could only lie on one of its poles, being the pure 0 and 1 states, respectively. A qubit can be implemented by any quantum two-level system.
An example is the vertical and horizontal polarization of a single photon; other examples are the
ground and excited states of an atom and the two spin states of a spin ½ particle within a magnetic
field.
Since quantum states can be protected, manipulated, and transported, quantum information
can be stored, processed, and conveyed. Therefore, it is possible to contrive quantum computers
(Deutsch 1989; Feynman 1982). The execution of a program can be described by the Schrödinger
equation. The latter applies only to isolated systems and is valid in the time interval separating a
preparation (when the system is initialized) and a measurement (when the output is extracted from
the system) (Wheeler and Zurek 1983). The Hamiltonian H generates a unitary evolution of Ψ ,
which can be visualized as rotation of the qubit on the Bloch sphere. The qubit maintains its norm
and the operation is reversible. When a calculation is ended, and a measurement is performed, the
superposition a 0 + b 1 behaves like 0 with probability a 2 and like 1 with probability b 2. The main difficulty in building a quantum computer comes from the fact that quantum states must continuously contend against insidious interactions with their environment (e.g., an atom colliding with
another atom or a stray photon) triggering loss of coherence.
A quantum computer promises to be immensely powerful because it can be in multiple states at
once. If it consists of N unmeasured qubits, it can be in an arbitrary superposition of up to 2N differ-
ent states simultaneously (the Hilbert space will be of 2N dimensions). A classical computer could be
|0⟩
|Ψ⟩
θ
ϕ
|1⟩
FIGURE 13.24 Representation of the qubit Ψ in the Bloch sphere.
488
Untangling Complex Systems
only in one of the 2N states at any one time (Bennet and DiVinceno 2000). For example, a quantum
superposition of 300 particles would create as many configurations as there are atoms in the known
Universe. The superposition can also involve the quantum states of physically separated particles
if they are entangled (Plenio and Virmani 2007). Working with superimposed states can speed up
not all, but some computations, such as the Shor’s algorithm for factoring an n-digit number (Shor
1997). This feature makes possible some tasks, such as the absolute secrecy of communication
between parties (i.e., quantum cryptography (Bennett et al. 1992)) that is impossible classically.
So far, different technologies have been proposed to implement quantum computations
(DiVincenzo 2000; Brumfiel 2012). For instance, trapped ions in atomic physics, nuclear and elec-
tron magnetic resonance spectroscopies, quantum optics, loops of currents in superconducting cir-
cuits, and mesoscopic solid-state systems like arrays of quantum dots. In these technologies, the
produced qubits have relaxation times sufficiently long to prevent quantum effects from decohering
away before ending a computation.
Whenever too fast decoherent effects are unavoidable, the lure of quantum information vanishes.
However, it is still possible to compute with molecules by processing “classical” logic. Since a
qubit, Ψ , can collapse into one of the two available states, 0 or 1 , it seems evident that only crisp
Boolean logic can be implemented at the atomic and molecular levels (see Figure 13.25). When the
computation trusts in a chemical transformation, involving just two distinct parallel routes, every
single molecule selects only one reaction path. Therefore, its behavior can be described in terms of
Boolean algebra (de Silva 2013; Szaciłowski 2008). In the case of three-level, or k-level, quantum
systems (with k > 3) that have three or k basis states, respectively, the decoherence gives the possibility of processing three-valued or multi-valued logics, also known as crisp logic wherein there
are more than two truth values (Andréasson and Pischel 2015). The ability to make computation by
molecules resides in their structures and reactivity (i.e., affinity). The order, the way the atoms of
a molecule are linked, and their spatial distribution rule the intra- and inter-molecular interaction
capabilities of the molecule itself, defining its potentiality of storing, processing and conveying
information.
In practical terms, computation with single molecules is feasible by exploiting microscopic tech-
niques that reach the atomic resolution, such as scanning tunneling microscopy (STM) or the atomic
force field microscopy (AFM) (Joachim et al. 2000).
Alternatively, it is possible to process logic by using large assemblies of molecules (for instance,
an Avogadro’s number of computing elements). These extensive collections of molecules become
macroscopic pieces of matter receiving inputs from the macroscopic world and giving back output
signals to the surrounding macro-environment. Therefore, inputs and outputs become macroscopic
variables whose values change in a continuous manner. They can be physical or chemical signals.
Physical signals can be optical or electrical or magnetic or mechanical or thermal. Optical signals
are particularly appealing because they can be easily focused and conveyed, and since they can be
Quantum
