2.7

# Multi-bit States

All of our important quantum algorithms will use more than one qubit. But before we get into using more than one qubit, let’s review how multi-bit states work in classical systems.

We call the set of our qubits our quantum register. In this Step and the next, we will explore how multi-qubit registers behave. First, we will review counting in binary, and the total size of the state space, and conclude with a brief digression into other types of number systems.

## How Many States are There?

Let’s look at how many states there are in a classical register.

If you have one bit, you have only two possibilities: zero and one (0 and 1). With two bits, you have four possibilities: 00, 01, 10, and 11. These correspond to the numbers 0, 1, 2, and 3, as we count in binary notation.

Each additional digit in our exponentially increases the number of states that are possible. With decimal notation, every additional digit multiplies the possibilities by ten: ones, tens, hundreds, thousands…With binary, instead each additional digit increases our space by a factor of two. With one digit, we have two possibilities, with two digits we have four, with three digits we have eight (not six!), with four digits we have 16, and so on. With $n$ bits, we can represent $2^n$ possible numbers. The first few binaries numbers are

Binary Decimal
0 0
1 1
10 2
11 3
100 4
101 5
110 6
111 7
1000 8
1001 9
1010 10
1011 11
1100 12
1101 13
1110 14
1111 15
10000 16
10001 17

and so on.

A common size of element in computers is the byte, which today always means eight bits. (This hasn’t always been so.) With eight bits, we can represent all of the numbers 00000000, 00000001, 00000010, … up to 11111111, giving us 0, 1, 2, … 255.

## Bigger Numbers and Computer Structure

A classical computer often has a set of small memories inside the CPU known as registers. These registers might be 8 or 16 bits, but today are most commonly either 32 or 64 bits. A 32-bit register has $2^{32} = 4,294,967,296$ possible states. A 64-bit register has $2^{64} = 18,446,744,073,709,551,616$ possible values.

As computer systems developed in the West, designers took advantage of a convenient coincidence. English groups powers of ten into three: thousands, then millions, then billions, and so on. Groups of ten bits correspond roughly to the same grouping: $2^{10} = 1,024$, and $2^{20} = 1,048,576$. This led to designers talking about “kilobits” meaning $2^{10}$, and “megabits” meaning $2^{20}$, and so on:

Prefix Exponent Decimal Nearby binary Decimal value
kilo $10^{3}$ 1,000 $2^{10}$ 1,024
mega $10^{6}$ 1,000,000 $2^{20}$ 1,048,576
giga $10^{9}$ 1,000,000,000 $2^{30}$ 1,073,741,824
tera $10^{12}$ 1,000,000,000,000 $2^{40}$ 1,099,511,627,776
peta $10^{15}$ 1,000,000,000,000,000 $2^{50}$ 1,125,899,906,842,624
exa $10^{18}$ 1,000,000,000,000,000,000 $2^{60}$ 1,152,921,504,606,846,976

Computer people often use these two loosely interchangeably, despite the difference of 10% or more at the tera level and above. Commonly, disk space, network bandwidth and CPU speeds are decimal, and memory capacities are the nearby binary values.

This coincidence is convenient in English, but East Asian countries (China, Korea and Japan) deal in multiples of $10^4$, so that $10^8$, $10^{12}$ and so on have special names. This results in confusion among our own students here in Japan, who sometimes struggle to do mental arithmetic with kilo, mega, giga and tera!

## Quantum Data

We will see in the next step that quantum data is stored in quantum registers, groups of qubits that similarly have the potential to count to exponentially large numbers with a small number of qubits.

## Other Notations

If you’re the curious type – and you certainly are, or you wouldn’t be taking this course – you might be interested in other ways of representing data besides binary. If you’re not interested, feel free to skip this part.

Obviously, you’re familiar with decimal notation, the way we count by tens, hundreds, thousands, and so on. Computer scientists often use hexadecimal, or base sixteen, notation, using the digits A to F to represent 10 to 15 (decimal). Thus, we count 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11… and so on. FF is 255 base ten, and 100 hex is 256 base ten.

The primary reason for using hexadecimal is that it is much less cumbersome than writing out large binary numbers, but it easily and conveniently converts to binary numbers when necessary, because one hexadecimal digit carries exactly four bits of information. If you want to become a computer engineer, you must become comfortable with hexadecimal notation.

Some early computers actually used ternary representations, with three states, instead of binary. Interestingly, there are two ways to value the three states: the obvious 0, 1 and 2, but also, 0, 1, and -1! Then counting proceeds 0, 1, (1,-1), (1,0), (1,1), (1,-1,-1), (1,-1,0), (1,-1,1), (1,0,-1) and so on!

Some quantum computer technologies naturally give rise to three states instead of two, and so a ternary system seems natural, but almost all of detailed algorithms that have been constructed have been designed for binary qubits, so we will continue to focus on binary systems here.

You can work in any basis; famously, the Babylonian system was sexagesimal, or base sixty, and the Mayan system was vigesimal, or base twenty. The Babylonian system’s legacy lives on today in the 60-minute hour and the 360-degree circle.

In fact, we can build computers – either classical or quantum – using continuous variables as well, a kind of analog computer. Analog classical computers were built up through the 1960s, and researchers such as Caltech’s Carver Mead continued working on them using VLSI in the 1980s. They work well on certain kinds of differential equations, performing integration and differentiation directly, making them useful for tasks such as predicting the tides. Some current-day researchers believe we will ultimately move back to such analog systems for many computational tasks that today are done digitally.