They’re Not Old, They’re Classics

No simplicity of mind, no obscurity of station, can escape the universal duty of questioning all that we believe.

William Kingdon Clifford

When introducing quantum computing, it’s easy to say, “It’s completely different from classical computing in every way!” Well, that’s fine, but to what exactly are you comparing it?

We start by looking at what a classical computer is and how it works to solve problems. This sets us up to later show how quantum computing replaces even the most fundamental classical operations with ones involving qubits, superposition, and entanglement.

Topics covered in this chapter

1. 2.1. What’s inside a computer?
   1. 2.1.1. Data, error correction, and storage
   2. 2.1.2. Memory
   3. 2.1.3. Central Processing Unit (CPU)
   4. 2.1.4. Graphics Processing Unit (GPU)
2. 2.2. The power of two
3. 2.3. True or false?
4. 2.4. Logic circuits
5. 2.5. Addition, logically
6. 2.6. Algorithmically speaking
7. 2.7. Growth, exponential and otherwise
8. 2.8. How hard can that be?
   1. 2.8.1. Sorting
   2. 2.8.2. Searching
9. 2.9. Summary

2.1 What’s inside a computer?

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

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

• 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, I would think about why I wanted the machine and what I wanted to do, and much less about the particular hardware. I don...

2.2 The power of two

For a system based on 0s and 1s, the number 2 frequently appears in classical computing. This is unsurprising because we use binary arithmetic, 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. decimal digit

A number such as 247 is 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. We write a binary number as a sum of bits (0 or 1) multiplied by powers of 2 in decreasing order, with no intermediate powers omitted. Here are...

2.3 True or false?

From arithmetic, let’s turn to basic logic. Here, there are only two values: True and False. We want to know what we can do with one or two of these values. True`gate-style False`gate-style

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: gate$not`gate-style not`gate-style

not True = False
not False = 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 “we will get ice cream.”

If neither you nor your sister cleans your rooms, or if only one of you cleans your room, 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...

2.4 Logic circuits

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. circuit$classical

We begin with examples of the core operations, also called gates. Rather than True and False, we use 1 and 0 as the values of the bits coming into and out of gates. gate$classical

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: gate$reversible

We frequently use the symbol “⊕” for the xor operation. ⊕ (xor) xor`gate...

2.5 Addition, logically

We can put these logic gates together to do addition using binary arithmetic, as we discussed in section 2.2: algorithm$addition

Focus on the values after the equal signs, and temporarily forget the carrying in the last case. The results are the same as what xor does with two inputs:

We lost the carry bit but limited ourselves 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! If we combine the xor and the and, and give ourselves two bits of output, we can do a simple addition of two bits.

Exercise 2.6

Try drawing a circuit that would do this before peeking at what follows. You are allowed to clone the value of a bit and send it to two different gates.

The circuit is

where A, B, S, and C are bits. The circuit takes two single input...

2.6 Algorithmically speaking

We often use the word “algorithm” generically to mean “something a computer does.” Quantitative analysts employ financial market algorithms to calculate the exact moment and price 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 create new spice mixtures for cooking.

Informally, an algorithm is a recipe. Like a food recipe, 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 it a name as above: “stir,” “bake,&...

2.7 Growth, exponential and otherwise

Many people who use the phrase “exponential growth” misuse it, somehow thinking it only means “very fast.” Exponential growth involves, well, exponents. Figure 2.4 is a plot showing four kinds of growth: exponential, quadratic, linear, and logarithmic. exponential$growth growth$exponential growth$quadratic growth$linear growth$logarithmic logarithm function$logarithm function$exponential function$quadratic

Figure 2.4: Four kinds of growth

I’ve drawn them so they all intersect at a point but afterward 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.

Look at the change in the vertical axis, the one I’ve labeled resources, versus the horizontal axis, labeled problem size...

2.8 How hard can that be?

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?

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

To end this chapter, we look at classical complexity. We consider sorting and searching and some algorithms for doing these procedures.

2.8.1 Sorting

Sorting involves taking multiple items and putting them in some kind of order. Consider your book collection. You can rearrange them so that the books are on the shelves in ascending alphabetic order by title. Or you can move them around so they are in descending order by the year of publication...

2.9 Summary

Classical computers have been around since the 1940s and are based on using bits, 1s and 0s, to store and manipulate information. This is naturally connected to logic, as we can think of 1 or 0 as True or False, respectively, and vice versa. From logic operators like and, we created logic circuits that perform higher-level operations such as 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 essential. By understanding the classical case, we’ll later be able to show where we can get a quantum improvement.