Bits
Links:: 2022 Introduction to Classical and Quantum Computing
In this chapter, we learn about the classical concepts shown in the table below:
# Bits
# Coins
 With $n$ coins, there are $2^n$ possible states.
# Dice
 With $n$ die, there are $6^n$ possible states.
# Encoding Information
 Systems with two states carry the smallest amount of information possible. ^2d378f
# Physical Bits
 Many physical systems have only two state, e.g. coins, light switch, CDs, etc., and others with more than two possible states can be treated as only having two if we ignore the rest of the states, e.g. electronic circuit (consider only two values ($0$ and $5$ Volts) out of many).
 Regardless of the physical system, we conventionally denote the two possible states as $0$ and $1$, the binary digits.
 Bit is an abbreviation for binary digits, which can be either $0$ or $1$. Bits are used to represent the states of any physical system with two states. It is the smallest unit of classical information ^2d378f. ^eb9c2d
# Binary
 Binary number, as the name suggest, only consist of $0$s and $1$s, e.g. $1101$ or $101_2$ where the subscript of $2$ can be included to denote that it is a base2 number. The leftmost bit is called the the most significant bit and the rightmost bit is called the least significant bit. ^acbfd3
# ASCII
 ASCII uses $7$ bits, i.e. $2^7 = 128$ possible states, to encode letters, numbers, symbols, and special commands (like carriage return or newline). $95$ out of $128$ states are used to encode printable characters, while the remaining $33$ states encode nonprintable characters. ^b529b1
 Nowadays, we need many more characters to encode (other languages, emojis, symbols).
 The most common modern standard to encode characters is UTF8 which uses up to $32$ bits ($2^{32} = 4,294,967,296$ states) to encode information. The first $128$ bit strings in UTF8 are the ASCII characters. ^5c5c82
# Logic Gates
 Logic gates are used to manipulate bits. They take one or more bits as input, and, depending on the input, output one or more bits. ^a0ed0d
# SingleBit Gates
 They take one bit as input and then output one bit.
 There are four possible singlebit gates:
 The Identity Gate
 The identity gate does nothing to the bit, i.e. $0$ remains $0$ and $1$ remains $1$. The identity gate is sometimes depicted by a triangle in a circuit diagram, but often, we omit the triangle and just draw a longer wire. ^b3cedc
 The NOT Gate:
 The NOT gate flips a bit from $0$ to $1$, or $1$ to $0$. Its circuit diagram is a triangle with a small circle. ^a9ff8d
 The always $0$ gate always outputs $0$ regardless of the input. It is not commonly used.
 The always $1$ gate always outputs $1$ regardless of the input. It’s not commonly used.
 The Identity Gate
# TwoBit Gates
 They take two bits as input, and output one or more bits.
 Five of the most important twobit gates are:
 The AND Gate:
 The AND gate outputs $1$ only when both of the input bits are $1$. Symbolically, it is represented as $AB$. ^dc8ae7
 The OR Gate:
 The OR gate outputs $1$ if either or both inputs are $1$. Symbolically, it is represented as $A+B$. ^6bb068
 The XOR Gate:
 The Exclusive OR (XOR) gate outputs $1$ when only one of the inputs is $1$, but not both. We write the $XOR$ of $A$ and $B$ as $A \bigoplus B$, where mathematically $\bigoplus$ is addition modulo $2$, meaning we take the reminder after dividing by $2$.
^4ed712
 The Exclusive OR (XOR) gate outputs $1$ when only one of the inputs is $1$, but not both. We write the $XOR$ of $A$ and $B$ as $A \bigoplus B$, where mathematically $\bigoplus$ is addition modulo $2$, meaning we take the reminder after dividing by $2$.
 The NAND Gate:
 The $NAND$ gate is simply NOT of AND. Symbolically, it is represented as $\overline{AB}$. It is a Universal Gate. ^259251
 The NOR Gate:
 The $NOR$ gate simply outputs the NOT of the OR Gate. Symbolically, it is represented as $\overline{A + B}$. It is a Universal Gate ^5ba44c
 The AND Gate:
# Logic Gates as Physical Circuits
 Electrical circuits can be used to create logic gates by connecting switches in various ways.
 Nowadays, computers use transistors as the switches, typically made of silicon, where a single computer processor can have tens of billions of transistors.
# Universal Gates
 A set of gates that can perform all possible logic operations is called a Universal Gate Set. ^dbab19
 Following are some of the examples of universal gate sets:
# Adders and Verilog
# Adding Binary Numbers by Hand
 In general, to add two 4bit numbers $A_3A_2A_1A_0$ and $B_3B_2B_1B_0$, we need to carry four numbers $C_4,C_3,C_2,C_1$, and we get a fivebit sum $S_4S_3S_2S_1S_0$:
Since the leftmost carry is the leftmost digit of the sum, $S_4 = C_4$.
# Half Adder
 A circuit that adds two bits and outputs a carry and a bit of the sum is called Half Adder.
 Sum is the XOR of $A$ and $B$, and the carry is the AND of $A$ and $B$, i.e. $$S = A \oplus B, \quad C = AB.$$
 Code in Verilog:


# Full Adder
 A circuit that adds three bits (a carry into the sum and the two bits we want to add) and outputs a carry and a bit of sum is called a full adder.
 Carry out is $1$ when $A$ and $B$ are both $1$, or when $C_{in} = 1$ and $A \oplus B = 1.$: $$C_{out} = AB + C_{in}(A \oplus B)$$
 The sum $S$ is 1 whenever one of the inputs $A, B$, or $C_{in}$ are $1$, or when all three of them are $1$. This is equivalent to the XOR of all three bits: $$S = A \oplus B \oplus C.$$
 The logic circuit is:
 Code in Verilog:


# RippleCarry Adder
 It stings together a half adder and several full adders.
This is called a ripplecarry adder, since the carry from one addition ripples to the next addition.
# RippleCarry with Full Adders
 We can replace the first half adder with a full adder with a carryin of 0.
# Circuit Complexity
 If the ripplecarry adder consists entirely of full adders, then adding two nbit numbers requires $n$ full adders. Each full adder uses five logic gates, for a total of $5n$ logic gates.
 If the first adder is halfadder, then it reduces the number of gates to $4n + 2$.
# Circuit Simplification and Boolean Algebra
# Order of Operations'
# Association, Commutivity, and Distribution
 AND and OR are associative:
 $ABC = (AB)C = A(BC)$
 $A+B+C = (A+B)+C = A+(B+C)$
 AND and OR are commutative:
 $AB = BA$
 $A + B = B + A$
 AND and OR are distributive:
 $A(B+C) = AB + AC$
 $A+(BC) = (A+B)(A+C)$
# Identities Involving Zero and One
 $A0 = 0$
 $A1= A$
 $A + 0 = A$
 $A+1=1$
# SingleVariable Identities
 $A = \overline{\overline{A}}$
 $AA = A$
 $A\overline{A} = 0$
 $A + A = A$
 $A + \overline{A} = 1$
# TwoVariable Identities and De Morgan’s Laws
 $A + AB = A$
 $A + \overline{A}B = A + B$
 De Morgan’s Law states that the NOT of an AND is the OR of the NOTs, and the NOT of an OR is the AND of the NOTs.
 $\overline{AB} = \overline{A} + \overline{B}$
 $\overline{A+B} = \overline{A}\overline{B}$
^740272
# Circuit Simplification
 We can use the above defined identities to simply a circuit.
# Reversible Logic Gates
# Reversible Gates
 A Reversible Gate, is a logic gate where, given the output of the gate, we can always determine what the input was. For example, a NOT Gate.
 For a logic gate to be reversible, it must have the same number of input bits and output bits.
 No information is lost in reversible gates as we can always recover the inputs from the outputs.
# Irreversible Gates
 An Irreversible Gate is the opposite of a reversible gate. Given the output of the gate, we generally cannot determine what the input was. For example, the AND Gate.
 A gate will be irreversible if there are fewer possibilities for the outputs than the inputs, and also if there are fewer input bits than output bits.
 Information is lost in irreversible gates, as given an output, we generally do not know what the inputs were.
# Toffoli Gate: A Reversible AND Gate
 The Toffoli Gate has three inputs $A, B,$ and $C$. To be reversible, it needs to have three outputs, and they are $A, B,$ and $AB \oplus C$.
 The Toffoli gate can be constructed using an AND Gate and an XOR Gate. We take the $AND$ of $A$ and $B$, and we take the $XOR$ of $AB$ with $C$ to get $AB \oplus C$.
 Toffoli gate is a Universal Gate.
 The Toffoli gate is also called the ControlledControlledNOT gate or CCNOT gate. Whether the third bit is flipped is controlled by whether the first two bits are 1. That is, if A = B = 1, then the Toffoli gate flips C, and otherwise it does nothing.
# Making Irreversible Gates Reversible
 We can use an (some) additional XOR Gate and apply it to one or more additional inputs to make an irreversible gate reversible.
# Error Correction
# Errors in Physical Devices
 A single event upset is when high energy particles (like cosmic rays, radiation etc.) strike computers, causing bits to flip from $0$ to $1$ to $0$.
 Transmitting data through the internet may also corrupt some bits.
# Error Detection
 The simplest way to detect errors is to repeat each bit multiple times so that multiple physical bits encode a single logical bit. This is called the repetition code.
 So if we want to send the letter “Q” in ASCII, which is represented by the sevenbit string $1010001$, we would actually send $$11 00 11 00 00 00 11.$$ If one of the physical bits is flipped, say due to a single event upset or transmission error, then instead of receiving $00$ or $11$, the recipient would receive $01$ or $10$, indicating that an error is occurred.
 The binary strings $00, 01, 10,$ and $11$ are called codewords.
 The parity of a bit string is whether the bit string has an even or odd number of 1’s. ^482618
 The codewords $00$ and $11$ have an even parity, while the codewords $01$ an $10$ have an odd parity. This can be computed using the XOR Gate, since $0 \oplus 0 = 1 \oplus 1 = 0$ (even parity) and $1 \oplus 0 = 0 \oplus 1 = 1$ (odd parity).
 If we use the repetition code with two physical bits per logical bit, only onebit errors can be detected.
# Error Correction
 If we use three bits for the repetition code, we can correct the error by taking the majority vote: $$\displaylines{001, 010, 100 \rightarrow 000, \newline 110, 101, 011 \rightarrow 111.}$$
 This is an example of an errorcorrecting code.
 We can use parity checks to correct the error, without every needing to know the actual codeword. This will be helpful in Quantum Computing because it won’t collapse the qubit’s state.
 In case of a logical bit represented with three bits, it can detect and correct the error if a single bit flips. But if two or three bits flip, then it can’t. This is called an uncorrectable error.
 Let $p$ denote the probability of a single bit flipping. The probability of two specific bits getting flipped is $p^2$, and since there are three combinations for two of the three bits to be flipped (the two bits could be the first two bits, the last two bits, or the first and last bits), the probability of any two bits getting flipped is $3p^2$. An uncorrectable error also occurs when all three bits gets flipped, and the probability of that occurring is $p^3$. The coefficient of this is simply $1$ because there is only $1$ way to choose $3$ bits out of $3$. So, the probability of an uncorrectable error occurring is $$3p^2 + p^3.$$ As long as this is less than $p$, which is the probability that an error occurs without error correction, then it is favorable to do error correction $$3p^2 + p^3 < p.$$ Solving this inequality, we see that the 3bit repetition code is better than no error correction when $$0 < p < 0.303.$$
# Computational Complexity
# Asymptotic Notation
 BigO is the most commonly used asymptotic notation, and it is useful for specifying the worstcase behavior of an algorithm. Mathematically, $f (n) = O(g(n))$ means there exists constants $c$ and $n_0$ such that $f (n) ≤ cg(n)$ for all values of $n$ greater than $n_0$.
 Littleo notation is used when we want the inequality to be strictly “less than”. So we can write $5n − 3 \neq o(n^2)$. Mathematically, $f (n) = o(g(n))$ means there exists constants $c$ and $n_0$ such that $f (n) < cg(n)$ for all values of $n_0$.
 A lower bound on the asymptotic behavior of a function is denoted using bigOmega notation. Mathematically, $f (n) = Ω (g(n))$ means there exists constants $c$ and $n_0$ such that $f (n) ≤ cg(n)$ for all values of $n$ greater than $n_0$. We could also write $5n − 3 = Ω (1)$ to mean that $5n − 3$ is lower bounded by a constant.
 If we want the inequality to be strictly “greater than,” we use a lowercase symbol, or littleomega notation. Mathematically, $f (n) = o(g(n))$ means there exists constants $c$ and $n_0$ such that $f (n) < cg(n)$ for all values of $n$ greater than $n_0$.
 To specify that $5n − 3$ scales linearly with n, we use bigTheta notation. We write this as $5n − 3 = Θ (n)$, and it means that $5n − 3$ is both upper bounded and lower bounded by $n$, asymptotically. That is, $5n − 3 = O(n)$ and $5n − 3 = Ω (n)$. Combining the mathematical definitions of each, $f (n) = Θ (g(n))$ means there exists constants $c_1, c_2,$ and $n_0$ such that $c_1g(n) ≤ f (n) ≤ c_2g(n)$ for all values of $n$ greater than $n_0$.
# Complexity Classes
 In computer science, an algorithm is called efficient if it takes polynomial time, e.g. $n^{1000}$. On the other hand, an algorithm is inefficient if it takes exponential time, e.g. $2^n$.
 Complexity Classes are used to classify different problems, depending on how easy or how hard a certain problem is. ^de57a3
 Class P, which stands for PolynomialTime, contains those problems that can be solved efficiently (in polynomial time) by classical computer. ^115dd2
 Some problems in Class P are:
 Matchmaking in the " Stable Marriage problem".
 Determining if a number is prime.
 Linear programming.
^be6bfa
 Class NP (the N stands for a nondeterministic Turing machine, and the P stands for polynomial) problems are those problems whose solution can be quickly verified by a computer in polynomial time. ^51019f
 It includes problems such as:
 Factoring
 Graph Isomorphism
^f828ff
 Certain problems within NP Class have a special property called completeness, and we call these problems NPCOMPLETE. If we can find an efficient solution to any NPCOMPLETE, then we can use it to find an efficient solution to any NP problem. ^3112c4
 Some NPCOMPLETE problems include:
 Solving n × n Sudoku puzzles.
 Traveling salesman problem.
 Hamiltonian path problem.
 Bin packing problem.
^550585
 Some NPCOMPLETE problems include:
 A literal million dollar question is Whether P and NP are equal.
 Class PSPACE contains all the problems that can be solved by a computer using a polynomial amount of memory, without any limits on time. Generalizations of many games are in PSPACE. ^fe3a39
 It is generally believed that $P \neq NP$ and $NP \neq PSPACE$ (and hence $PSPACE \neq P$), but none of these relations have been proved yet.
# Turing Machines
# Components
 A Turing machine consists of four parts:
 A tape divided into cells, each with a symbol from some finite alphabet.
 A head that can read or write to the tape.
 A register that stores the state of the Turing machine.
 A list of instructions or program.
 Turing machines can compute everything that a circuitbased computer can compute.
# Incrementing Binary Numbers
 Example of a Turing machine being used to add 1 (increment) to a binary number can be seen in the textbook.
# ChurchTuring Thesis
 The ChurchTuring Thesis states that everything that is computable can be computed with a Turing machine, although it could take a long time (e.g., exponential time). ^ec4b63
 The Strong ChurchTuring Thesis says that any model of computation, be it the circuit model or something else, can be simulated by a probabilistic Turing machine with at most polynomial overhead. ^f1351a
 Quantum computers would not violate the regular ChurchTuring Thesis. That is, what is impossible to compute remains impossible. The hope, however, is that quantum computers can violate the Strong ChurchTuring Thesis, that they will efficiently solve problems that are inefficient on classical computers.
 While there is no proof of this hope, there is strong Evidence for Quantum Computers to violate Strong ChurchTurning Thesis.
 The complexity class of problems efficiently solved by a quantum computer is called Class BQP.
# Summary
 The smallest unit of classical information is the Bit, which can be used to encode information.
 Bits are operated on by Logic gates. Together, these gates can be used to perform any computation, and sets of these gates are also universal.
 The mathematics that describes logic gates is called boolean algebra.
 Logic gates can be made reversible.
 In physical systems, errors sometimes occur, but as long as the error rates are sufficiently low, they can be corrected.
 Classical computers can efficiently solve some problems, while other problems take an exponential amount of time.
 It is believed that quantum computers can efficiently solve some of the problems that are hard for classical computers.