# 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.

© Keio University