1 Bits1.1 The Boolean Bit1.2 The Circuit Bit1.3 The Control Bit1.4 The Physical Bit1.5 The Quantum Bit1.5.1 An Advantage of Qubits1.6 The Classical Bit1.7 SummaryChapter 1BitsInformation is measured in bits, just as length is measured in m eters and time is measured in seconds. Ofcourse knowing the amount of information, in bits, is not the same as knowing the information itself, whatit means, or what it implies. In these notes we will not consider the content or meaning of information, justthe quantity.Different scales of length are needed in different circumstances. Sometimes we want to measure lengthin kilometers, sometimes in inches, and sometimes in˚Angstr¨oms. Similarly, other scales for informationbesides bits are sometimes used; in the context of physical systems information is often measured in Joulesper Kelvin.How is information quantified? Consider a situation or experiment that could have any of several possibleoutcomes. Examples might be flipping a coin (2 outcomes, heads or tails) or se lec ting a card from a deck ofplaying cards (52 possible outcomes). How compactly could one person (by convention often named Alice)tell another person (Bob) the outcome of such an experiment or observation?First consider the case of the two outcomes of flipping a coin, and let us suppose they are equally likely.If Alice wants to tell Bob the result of the coin toss, she could use several pos sible techniques, but theyare all equivalent, in terms of the amount of information conveyed, to saying either “heads” or “tails” or tosaying 0 or 1. We say that the information s o conveyed is one bit.If Alice flipped two coins, she could say which of the four possible outcomes actually happened, by saying0 or 1 twice. Similarly, the result of an experiment with eight equally likely outcomes could be conveyed withthree bits, and more generally 2noutcomes with n bits. Thus the amount of information is the logarithm(to the base 2) of the number of equally likely outcomes.Note that conveying information requires two phases. First is the “setup” phase, in which Alice and Bobagree on what they will communicate about, and exactly what each sequence of bits means. This commonunderstanding is called the code. For example, to convey the suit of a card chosen from a deck, their codemight be that 00 means clubs, 01 diamonds, 10 hearts, and 11 spades. Agreeing on the code may be donebefore any observations have bee n made, so there is not yet any information to be sent. The setup phase caninclude informing the recipient that there is new information. Then, there is the “outcome” phase, whereactual sequences of 0 and 1 representing the outcomes are sent. These sequences are the data. Using theagreed-upon code, Alice draws the card, and tells Bob the suit by sending two bits of data. She could do sorepeatedly for multiple experiments, using the same code.After Bob knows that a card is drawn but before receiving Alice’s message, he is uncertain about the suit.His uncertainty, or lack of information, can be expressed in bits. Upon hearing the result, his uncertainty isreduced by the information he receives. Bob’s uncertainty rises during the setup phase and then is reducedduring the outcome phase.Author: Paul Penfield, Jr.This document: http://www.mtl.mit.edu/Courses/6.050/2007/not es/c hapt er1. pdfVersion 1.4, January 2, 2007. Copyrightc 2007 Massachusetts Institute of TechnologyStart of notes · back · next | 6.050J/2.110J home page | Site map | Search | About this document | Comments and inqui ries11.1 The Boolean Bit 2Note some important things about information, some of which are illustrated in this example:• Information can be learned through observation, experiment, or measurement• Information is subjective, or “observer-dependent.” What Alice knows is different from what Bobknows (if information were not subjective, there would be no need to communicate it)• A person’s uncertainty can be increased upon learning that there is an observation about which infor-mation may be available, and then can be reduced by receiving that information• Information can be lost, either through loss of the data itself, or through loss of the code• The physical form of information is localized in space and time. As a consequence,– Information can be sent from one place to another– Information can be stored and then retrieved later1.1 The Boolean BitAs we have seen, information can be communicated by sequences of 0 and 1 values. By using only 0 and1, we can deal with data from many different types of sources, and not be concerned with what the datameans. We are thereby using abstract, not specific, values. This very powerful approach lets us ignore manymessy details associated with specific information processing and transmission systems.Bits are simple, having only two possible values, and the mathematics used to denote and manipulatesingle bits is not difficult. It is known as Boolean algebra, after the mathematician George Boole (1815 -1864). In some ways Boolean algebra is similar to the algebra of integers or real numbers which is taught inhigh school, but in other ways it is different.Algebras deal with variables that have certain possible values, and with functions which, when presentedwith one or more variables, return a result which again has certain possible values. In the case of Booleanalgebra, the possible values are 0 and 1.There are exactly four Boolean functions of a single variable. One of them, called the identity, simplyreturns its argument. Another, called not, or negation, or inversion, or complement, changes 0 into 1 andvice versa. The other two simply return either 0 or 1 regardless of the argument. Here is a table showingthese four functions:x f(x)Argument IDENT IT Y NOT ZERO ON E0 0 1 0 11 1 0 0 1Table 1.1: Boolean functions of a single variableNote that Boolean algebra is simpler than algebra dealing with integers or real numbe rs, each of whichhas infinitely many functions of a single variable.How many Boolean functions are there of two variables A and B? Each of the two arguments can take oneither of two values, so there are four pos sible input combinations. There are 16 different ways of assigningthe two Boolean values to four inputs. Of these 16, two simply ignore the input, four assign the output tobe either A or B or their complement, and the other ten depend on both arguments. The most often usedare AND , OR, XOR (exclusive or), NAND (not