HOME  |   ENGINEERING  |   RESEARCH  |   CONTACT
Programming the Universe

SETH LLOYD
2011

All information that exists is registered by physical systems, and all physical systems register information.

Introduction
  • The significance of a bit depends not just on its value but on how that value affects other bits over time.
  • The bit is the smallest possible chunk of information. Every molecule, atom, and elementary particle registers bits of information.
  • The universe is a quantum computer.
  • The computational capability of the universe explains one of the great mysteries of nature: how complex systems such as living creatures can arise from fundamentally simple physical laws.
  • The quantum-computational nature of the universe dictates that the details of the future are intrinsically unpredictable.
  • Quantum computers are devices that harness the information-processing ability of individual atoms, photons, and other elementary particles.
  • Because a quantum bit, or "qubit," can register both 0 and 1 at the same time, a quantum computer can perform millions of computations simultaneously. A quantum computer is a democracy of information: every atom, electron, and photon participates equally in registering and processing information.
  • Asexual adaptation is problematic because the dictate of the world, "Change or die," runs directly counter to one of the primary dictates of life: "Maintain the integrity of the genome." By separating the function of adaptation from the function of maintaining the integrity of individual genes, sex allows much greater diversity while still keeping genes whole.
  • The compact nature of binary notation makes it easy to construct simple electronic circuits to do binary arithmetic. These circuits, in turn, are the basis for digital computers.
  • Range divided by precision tells you how many distinguishable values the device can register. The amount of available information is given by the number of bits required to count the available values.
  • In general, the best way to get more information is not to increase the precision of measurements on a continuous quantity, but rather to put together measurements on more and more quantities, each one of which may register only a few bits. The number of total alternatives described grows much faster than does the number of bits.
  • The meaning of a piece of information depends very much on how the information is to be interpreted.
  • The basic idea of information is that one physical system—a digit, a letter, a word, a sentence—can be put into correspondence with another physical system. The information stands for the thing. The word and the bit are means by which information is conveyed, though the interpreter must supply the meaning.
  • A computer is a machine that processes information. Quantum computers have both digital and analog aspects.
  • Computers process information by breaking it up into its component bits and operating on those bits a few at a time. Logic circuits allow a complicated logical expression to be built up out of simple operations that act on just a few bits at a time. Any desired logical expression can be built up out of NOT, COPY, AND, and OR logic gates.
  • In an electronic computer, bits are registered by electronic devices such as capacitors. A capacitor is like a bucket that holds electrons. Computer hard drive use bits that are registered by tiny magnets. Conventional digital electronic computer, logic gates are implemented using transistors, which can be thought of as a switch. In an n-type transistor, when the first input is kept at a low voltage the switch is open and current can't flow from the second input to the output; In a p-type transistor, when the first input is kept at low voltage the switch is closed, so current can flow. n- and p-type transistors can be wired together to create AND, OR, NOT, and COPY gates.
  • One counterintuitive result of a computer's fundamentally logical operation is that its future behavior is intrinsically unpredictable.
  • Kurt Gödel showed that any sufficiently powerful mathematical theory has statements that, if false, would render the theory inconsistent but that cannot be proved to be true.
  • The Halting Problem: no computer program can take as input another computer program and determine with 100 percent probability whether the first computer program halts or not.
  • The capacity for self-reference leads automatically to paradoxes in logic.
The Computational Universe
  • The computational universe is not an alternative to the physical universe.
  • Energy is the ability to do work. Energy makes physical systems do things.
  • The First Law of Thermodynamics: energy is conserved.
  • Quantum mechanics describes energy in terms of quantum fields, a kind of underlying fabric of the universe.
  • The energy in the quantum fields is almost always positive, and this positive energy is exactly balanced by the negative energy of gravitational attraction.
  • Energy makes physical systems do things. Information tells them what to do.
  • Entropy is the information required to specify the random motions of atoms and molecules. Entropy is the information contained in a physical system that is invisible to us. It is a measure of the degree of molecular disorder existing in a system.
  • The Second Law of Thermodynamics: the entropy of the universe as a whole does not decrease; in other words, the amount of unusable energy is increasing.
  • Free energy is energy in a highly ordered form associated with a relatively low amount of entropy. The energy in sugar is stored not in the random jiggling of atoms but in the ordered chemical bonds that hold sugar together.
  • Energy is conserved. Information never decreases. It takes energy for a physical system to evolve from one state to another. That is, it takes energy to process information.
  • The maximum rate at which a physical system can process information is proportional to its energy. The more energy, the faster the bits flip.
  • To do anything requires energy. To specify what is done requires information.
  • The universe sprang from nothing. As it expanded, it pulled more and more energy out of the underlying quantum fabric of space and time. The early universe could be described by just a few bits of information. The energy that was created was free energy. As the expansion continued, the free energy in the quantum fields was converted into heat, increasing entropy, and all sorts of elementary particles were created. After this first billionth of a second, the universe was very hot. Almost all of the energy that had been drawn into it was now in the form of heat. When all matter is at the same temperature, entropy is maximized. There was very little free energy.
  • Quantum mechanics produces detail and structure because it is inherently uncertain. Because of these quantum fluctuations, some regions of the early universe were ever so slightly more dense than other regions. The attractive force of gravity caused more matter to move toward these denser regions, further increasing their energy density. The ability of gravity to amplify small fluctuations in density is a reflection of a physical phenomenon known as "chaos." In a chaotic system, what begins as a tiny difference is amplified in time.
  • A universal computer need not be a complicated machine; all it must be able to do is take bits, one or two at a time, and perform simple operations upon them.
  • The failure of classical simulation of quantum systems suggests that the universe is intrinsically more computationally powerful than a classical digital computer.
Information and Physical Systems
  • The second law of thermodynamics states that each physical system contains a certain number of bits of information and that the physical dynamics that process and transform that information never decrease that total number of bits.
  • Entropy is a measure of the number of bits of unavailable information registered by the atoms and molecules that make up the world. The second law of thermodynamics comes about by combining this notion with the fact that the laws of physics preserve information. Nature does not destroy bits.
  • Whenever mechanical energy was turned into heat, an amount of entropy equal to the energy divided by the temperature was created. The kinetic energy of an atom is proportional to its temperature. The hotter something is, the faster its atoms are jiggling around. The faster the atoms jiggle, the more information is required to describe their jiggling, and thus, the more entropy they possess.
  • Temperature is a measure of the trade-off between information and energy: atoms at a high temperature require more energy to register a bit of information, and atoms at a low temperature require less energy to register a bit. Temperature is energy per bit.
  • If one could gain information about the microscopic behavior of the atoms in a gas, one could reduce its entropy: atom registers information: the amount of information required to describe where it is (position) and where and how fast it is going (velocity).
  • The second law of thermodynamics holds that the total amount of information never decreases. Information can be created but it can't be destroyed.
  • Erasure is a process that destroys information. During erasure, a bit that is initially 0 stays 0, and a bit that is initially 1 goes to 0. Erasure destroys the information in the bit. Any process that erases a bit in one place must transfer that same amount of information somewhere else. This is known as Landauer's principle.
  • Entropy is a quantity that measures how useful energy is. Energy with a small amount of entropy is useful (free) energy; energy with lots of entropy is useless. Entropy, which is just invisible information, is also a measure of ignorance.
  • Bits with values of which we are ignorant constitute the entropy of the system: a bit of entropy is a bit of ignorance. Note that the division between known and unknown information is to some degree subjective. Different observers can assign different values to the entropy of a system.
  • Suppose an unknown bit of information interacts with a known bit of information. After the interaction, the first bit is still unknown, but now the second bit is unknown, too. The unknown bit has infected the known bit, spreading the lack of knowledge, and increasing the entropy of the system.
  • The spread of ignorance increases the entropy of the individual bits in a system. But the entropy of the bits taken together remains constant.
  • Mutual Information: the spread of ignorance is reflected in the increase of this quantity. Each bit, on its own, has one bit's worth of entropy, but the two bits taken together also have only one bit's worth of entropy. The mutual information is equal to the sum of the entropies taken separately, minus the entropy of the two bits taken together.
  • When two atoms collide, any uncertainty about the position and velocity of the first atom tends to infect the second atom, rendering its position and velocity more uncertain and thus increasing its entropy.
  • The assumption of Molecular Chaos: even though the positions and velocities of two atoms might be correlated before their collision, repeated collisions between many atoms tend to dilute that correlation, so that two colliding atoms in a gas would in effect be uncorrelated at the moment of their collision. If the assumption of molecular chaos is true, then the entropies of the individual atoms almost always increase. The assumption of molecular chaos is a good one but is not true for all physical systems. Interactions between pieces of a system, such as atoms, tend to increase the entropies of those pieces, even if they have interacted before. This result justifies Boltzmann's assumption of molecular chaos.
  • In a chaotic system, the invisible information in the microscopic bits infects the macroscopic bits, causing the observable characteristics to wander in an uncertain fashion.
  • The second law says that increases in entropy cannot be reversed. In the case of the spin-echo effect, entropy has only apparently increased. Even though the entropy of the spins taken on their own increases and then decreases during the course of the echo, the underlying entropy of the spins taken together with the magnetic field remains the same.
  • Physical dynamics can be used to get information, and that information can be used to decrease the entropy of a particular element of a system, but the total amount of information/entropy does not decrease.
  • The second law of thermodynamics is a statement about information processing: the underlying physical dynamics of the universe preserve bits and prevent their number from decreasing.
  • The fact that atomic collisions in principle allow computation implies that the long-term future of a gas of atoms is intrinsically unpredictable.
Quantum Mechanics
  • Planck's constant relates energy to frequency.
  • Just as every wave is made up of particles, every particle—an electron, an atom, a pebble—has a wave associated with it. The wave is associated with the position of the particle. The distance between the peaks of the wave is related to the particle's speed. The wave's frequency is proportional to the energy of the particle.
  • The double-slit experiment illustrates the fact that a particle doesn't have to be either "here" or "there." Because of its underlying wavelike nature, a particle can be both "here" and "there" at the same time. The bigger something is, however, the harder it is to coax it into existing in two places at once. The more interactions it tends to have with its surroundings.
  • In order to go through both slits at once and produce an interference pattern, a particle must pass through the slits undetected. Observation (or measurement, as it is conventionally called) destroys interference.
  • Decoherence: the process by which the environment destroys the wavelike nature of things by getting information about a quantum system.
  • Entropy increase: almost any interaction between one thing and another causes the first thing to get information about the second, and vice versa. The same mechanism operates to make quantum objects behave in a more classical way.
  • The Uncertainty Principle states that if the value of some physical quantity is certain, then the value of a complementary quantity is uncertain.
  • It's not hard to flip a quantum bit, or qubit, by applying a magnetic field. By varying the amount of time for which you apply the magnetic field, you can also put the spin in a variety of superpositions.
  • There are many more transformations that can be applied to a quantum bit than to a classical bit. Classical and qubit transformations have in common a one-to-one transformation. The action can be reversed.
  • Rotations of individual quantum bits, together with controlled-NOT operations, constitute a universal set of quantum logic operations.
  • Regard the second law of thermodynamics and irreversibility of quantum measurements as probabilistic laws: entropy tends to increase and information is highly likely to spread. But sometimes they don't.
  • Quantum mechanics, unlike classical mechanics, can create information out of nothing.
  • In the classical system, if we know the state of the whole, then we also know the state of the pieces. But when a quantum system is in a definite state, the pieces of the system need not be in a definite state.
  • In entangled states, we can know the state of a quantum system as a whole but not know the state of the individual pieces.
  • The universe is a quantum system, and almost all of its pieces are entangled.
  • Entanglement is responsible for the generation of information in the universe.
  • With entanglement, measuring the spin of the first particle about some axis also puts the second particle in a definite state of spin about that axis, but does not change the outcome of measurements made on the second spin.
  • It is not possible to send information from the first spin to the second just by making measurements on the first spin. Entanglement does not involve action at a distance.
  • Two entangled spins share one and only one quantum bit, and yet they are capable of giving opposite answers to an infinite variety of questions.
  • The measurement problem stems from the presence of those parts of the wave function corresponding to alternatives that do not actually happen. We can ignore the other parts of the wave function at exactly the moment when they have no further effect on us. The future history of the wave function decoheres.
  • In the case of the double-slit experiment, there are two possible histories. These histories are coherent and interfere with each other to create the pattern of bands on the wall. If making a sequence of measurements on a quantum system changes its future behavior, then the histories corresponding to the possible sequences of outcomes of the measurements are coherent.
Atoms at Work
  • Electrons are negatively charged, so they are attracted to the positively charged nucleus. The electric force binds electrons to the nucleus. Each electron has a wave associated with its position and velocity. The places where an electron’s wave is big are where the electron is likely to be found. The shorter the length of the wave, the faster the electron is moving. Finally, the rate at which the wave wiggles up and down is proportional to the electron’s energy. An atom’s electrons consist of a set of discrete waves, so there are only so many orbits they can take.
  • When an electron jumps from a higher energy state to a lower one, it emits a chunk, or quantum, of light—a photon—whose energy is equal to the difference between the energies of the two states. Atoms can absorb energy only in specific chunks (quanta). The fact that atoms respond to light only at frequencies corresponding to their spectrum is useful.
  • A quantum computer can perform two distinct tasks simultaneously. This arises from the wave nature of quantum mechanics, because waves can be superposed. But you must not look at the computation while it is occurring. To get the full symphonic effect of a quantum computation, you must let the all the waves in the computation interfere with one another.
  • Decoherence of computation occurs when any passing electron or atom interacts with the quantum computer in such a way as to get information about what the quantum computer.
  • In a superconductor, electrons encounter almost no resistance as they move from place to place. Electrons can move through the material in a way that preserves quantum coherence: they stay entangled. Researchers have built and exhibited the coherent control of superconducting qubits.
The Universal Computer
  • Classical digital computer deals with discrete quantities. In a quantum computer, there is no distinction between analog and digital computation. Qubits are also continuous, because of their wave nature; their states can be continuous superpositions.
  • Because the behavior of elementary particles can be mapped directly onto the behavior of qubits interacting via logic operations, a simulation of the universe on a quantum computer is indistinguishable from the universe itself.
  • A quantum computation "doesn't care" how it is embedded in space and time as long as the qubits interact with one another in the right sequence.
  • Einstein's equations relate the geometry of spacetime to the behavior of the matter in it. That geometry tells matter where to go, and the matter tells the geometry how to curve.
    • Complexity Simplified
      • Although the basic laws of physics are comparatively simple in form, they give rise, because they are computationally universal, to systems of enormous complexity.
      • Algorithmic Information is a measure of how hard it is to represent a text or a bit string using a computer.
      • Computer languages provide a method for assigning meaning to strings of bits. The numbers that can be produced by short programs are those that have mathematical regularities. As the number to be produced gets longer and longer, the length of the translating program becomes, relatively, smaller and smaller, adding comparatively little length to the algorithmic information content. The shortest program to produce a bit string can be thought of as a compressed representation of the bit string. The algorithmic probability is greatest for the shortest programs.
      • Simple programs together with lots of information processing give rise to complex outputs.
      • Negentropy is the opposite of entropy. Negentropy consists of known, structured bits.
      • The Thermodynamic Depth of a physical system is equal to the number of useful bits that went into assembling the system. Thermodynamic depth is the spatial computational complexity of the shortest program.
      • Effective complexity is a measure of the amount of regularity in a system.
      • The idea of axiomatic design is to minimize the information content of the engineered system while maintaining its ability to carry out its functional requirements.
      • Chemical reactions can readily produce AND, NOT, and COPY operations. Chemical reactions are computationally universal.
      • While the total amount of free energy within the horizon continues to grow, the density of free energy—the amount of free energy per cubic meter—is decreasing.
      • After the Big Bang, as different pieces of the universe tried out all possible ways of processing information, sooner or later, seeded by a quantum accident, some piece of the universe managed to find an algorithm to reproduce itself. Life evolved by processing genetic information to try out new strategies for survival and reproduction. Some living systems eventually discovered sex, a technique that vastly increases the rate at which new evolutionary strategies and algorithms can be explored, because it speeds up the rate of genetic information processing. Somewhere human beings hit upon language, which allowed people to process information in a highly distributed fashion.
      • The vast majority of the information processing in the universe lies in the collision of atoms, in the slight motions of matter and light.

      These notes were taken from Seth Lloyd's book.
      Find out more about Seth Lloyd at Wikipedia


© 2020 Cedric Joyce