If I were to buy a laptop today, I would need to think about the following kinds of hardware options:

• size and weight of the machine
• quality of the display
• processor and its speed
• memory and storage capacity

Three years ago I built a desktop gaming PC. I had to purchase and assemble and connect:

• the case
• power supply
• motherboard
• processor
• internal memory
• video card with a graphics processing unit (GPU) and memory
• internal hard drive and solid state storage
• internal Blu-ray drive
• wireless network USB device
• display
• speakers
• mouse and keyboard

As you can see, I had to make many choices. In the case of the laptop, you think about why you want the machine and what you want to do, and much less about the particular hardware. You don’t have to make a choice about the manufacturers of the parts nor the...

For a system based on 0s and 1s, the number 2 shows up a lot in classical computing. This is not surprising because we use binary arithmetic, which is a set of operations on base 2 numbers.

Most people use base 10 for their numbers. These are also called decimal numbers. We construct such numbers from the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, which we often call digits. Note that the largest digit, 9, is one less than 10, the base.

A number such as 247 is really shorthand for the longer 2 × 10² + 4 × 10¹ + 7 ×10⁰. For 1,003 we expand to 1 × 10³ + 0 × 10² + 0 × 10¹ + 3×10⁰. In these expansions we write a sum of digits between 0 and 9 multiplied by powers of 10 in decreasing order with no intermediate powers omitted.

We do something similar for binary. A binary number is written as a sum of bits (0 or 1) multiplied by powers of 2 in decreasing order with no intermediate powers omitted. Here are some examples...

From arithmetic let’s turn to basic logic. Here there are only two values: true and false. We want to know what kinds of things we can do with one or two of these values.

The most interesting thing you can do to a single logical value is to replace it with the other. Thus, the not operation turns true into false, and false into true:

For two inputs, which I call p and q, there are three primary operations and, or, and xor. Consider the statement ‘‘We will get ice cream only if you and your sister clean your rooms.’’ The result is the truth or falsity of the statement ‘‘we will get ice cream.’’

If neither you nor your sister clean your rooms, or if only one of you clean your room, then the result is false. If both of you are tidy, the result is true, and you can start thinking about ice cream flavors and whether you want a cup...

Now that we have a sense of how the logic works, we can look at logic circuits. The most basic logic circuits look like binary relationships but more advanced ones implement operations for addition, multiplication, and many other mathematical operations. They also manipulate basic data. Logic circuits implement algorithms and ultimately the apps on your computer or device.

We begin with examples of the core operations, also called gates.

To me, the standard gate shapes used in the United States look like variations on spaceship designs.

Rather than use true and false, we use 1 and 0 as the values of the bits coming into and out of gates.

This gate has two inputs and one output. It is not reversible because it produces the same output with different inputs. Given the 0 output, we cannot know which example produced it. Here are the other gates we use, with example inputs:

The symbol...

Using binary arithmetic as we discussed in section 2.2

Focusing on the value after the equal signs and temporarily forgetting the carrying in the last case, this is the same as what xor does with two inputs.

We did lose the carry bit but we limited ourself to having only one output bit. What gate operation would give us that 1 carry bit only if both inputs were also 1, and otherwise return 0? Correct, it’s and! So if we can combine the xor and the and and give ourselves two bits of output, we can do simple addition of two bits.

The word ‘‘algorithm’’ is often used generically to mean ‘‘something a computer does.’’ Algorithms are employed in the financial markets to try to calculate the exact right moment and price at which to sell a stock or bond. They are used in artificial intelligence to find patterns in data to understand natural language, construct responses in human conversation, find manufacturing anomalies, detect financial fraud, and even to create new spice mixtures for cooking.

Informally, an algorithm is a recipe. Like a recipe for food, an algorithm states what inputs you need (water, flour, butter, eggs, etc.), the expected outcome (for example, bread), the sequence of steps you take, the subprocesses you should use (stir, knead, bake, cool), and what to do when a choice presents itself (‘‘if the dough is too wet, add more flour’’).

We call each step an operation and give...

Many people who use the phrase ‘‘exponential growth’’ use it incorrectly, somehow thinking it only means ‘‘very fast.’’ Exponential growth involves, well, exponents. Here’s a plot showing four kinds of growth: exponential, quadratic, linear, and logarithmic.

I’ve drawn them so they all intersect at a point but afterwards diverge. After the convergence, the logarithmic plot (dot dashed) grows slowly, the linear plot (dashed) continues as it did, the quadratic plot (dotted) continues upward as a parabola, and the exponential one shoots up rapidly.

Take a look at the change in the vertical axis, the one I’ve labeled resources with respect to the horizontal axis, labeled problem size. As the size of the problem increases, how fast does the amount of resources needed increase? Here a resource might be the time required for the algorithm...

Once you decide to do something, how long does it take you? How much money or other resources does it involve? How do you compare the worst way of doing it with the best?

When you try to accomplish tasks on a computer, all these questions come to bear. The point about money may not be obvious, but when you are running an application you need to pay for the processing, storage, and memory you use. This is true whether you paid to get a more powerful laptop or have ongoing cloud costs.

To end this chapter we look at classical complexity. To start, we consider sorting and searching and some algorithms for doing them.

Whenever I hear ‘‘sorting and searching’’ I get a musical ear worm for Bobby Lewis’ 1960 classic rock song ‘‘Tossin’ and Turnin’.’’ Let me know if it is contagious.

2.8.1 Sorting

Sorting involves taking multiple items and putting them in some kind...

Classical computers have been around since the 1940s and are based on using bits, 0s and 1s, to store and manipulate information. This is naturally connected to logic as we can think of a 1 or 0 as true or false, respectively, and vice versa. From logical operators like and we created real circuits that can perform higher-level operations like addition. Circuits implement portions of algorithms.

Since all algorithms to accomplish a goal are not equal, we saw that having some idea of measuring the time and memory complexity of what we are doing is important. By understanding the classical case we’ll later be able to show where we can get a quantum improvement.

References

[1]

Thomas H. Cormen et al. Introduction to Algorithms. 3rd ed. The MIT Press, 2009.

[2]

R.W. Hamming. ‘‘Error Detecting and Error Correcting Codes’’. In: Bell System Technical Journal...