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

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:

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.

複数ビットの状態

実用的な量子アルゴリズムの多くは複数の量子ビットを必要とします。 ですが、複数の量子ビットについて学習を始める前に、まずは従来型のコンピューターがどのように複数のビット情報を操作しているのかを見ていきましょう。

量子コンピュータの中に組み込まれる一連の量子ビットは、一般的に量子レジスタと呼ばれます。 このステップ、及び次ステップで量子レジスタがどのように動くかを学習しますが、 まずは二進法(binary)の数え方と、表現可能な状態空間のサイズについておさらいした後、他の記数法に関して簡単に触れてみたいと思います。

状態の組み合わせ

まず、古典レジスタ(従来型コンピュータに内蔵される一連のビット)内にいくつの状態があるかを見てみましょう。

一つのビット(bit)では、0か1かの二通りの状態を表現できますので、2ビットでは、各ビットの組み合わせにより00, 01, 10, 11の四通りの状態を表すことが可能です。この４つの状態は、 十進数の 0,1,2,3 に対応しています。数字の桁を一つ増やすたびに、表せる状態の数は指数関数的に増加します。 十進法では、1桁、10桁、100桁、1000桁のように桁が一つ増える毎に表せる状態の数が10倍ずつ増加します。 二進法においては、桁ごとに2倍ずつ増加し、1桁では2つ、2桁では4つ、3桁では8つ（6つではないので注意）、4桁では16つの状態を表すことができます。 よって、(n)ビットでは(2^n) 種類の状態を表せることが分かります。 二進法と十進法の対応表は、以下のようになっています。

情報量を表す単位として、バイト(byte)という言葉をよく見かけます。現在は、1バイトは8ビットとして定義付けられていますが、実は昔はこの単位の定義が定まっていませんでした。 1バイト(8ビット)では00000000, 00000001, 00000010….11111111までの状態を表現でき、十進法でいう0から255までの数字に対応しています。

より大きな数とコンピューターの構造

従来型コンピューターの多くは、CPU内にレジスタと呼ばれる小型の記憶装置が内蔵されています。 レジスタの大きさは8bitや16bitの場合もありますが、今日では32bitか64bitのどちらかが一般的です。 32bitのコンピューターは(2^{32} = 4,294,967,296)通りの数の表現が可能であり、64bitのコンピューターは(2^{64} = 18,446,744,073,709,551,616)通りの数の表現が可能となっています。

英語圏では、サウザンド(thousand =1,000), ミリオン(million =1,000,000), ビリオン(billion = 1,000,000,000)等のように、大きな数字を3桁区切りで呼びます。 10ビット毎にグループ分けした場合、(2^{10} = 1,024)や(2^{20} = 1,048,576)等と、3桁ずつ大きくなる数字と近似していたので、対応した呼び名をつけ、(2^{10})ビットをキロビット(kilobit), (2^{20})ビットをメガビット(megabit)というように呼ぶようになりました。

ミリオン(1,000,000)やメガビット(1,048,576)は、桁数的には同じですが、見ての通り全く等価な数字という訳ではありません。実際に、テラビットレベルを超えたあたりから、その差は10%を上回ります。 それでもなお、専門家の多くはこの差を気に留めず、便宜性のため互換性のある単位として扱うことが少なからずあります。通常、ディスクの容量、ネットワークの帯域幅やCPU速度は十進法をベース(キロビット =(10^{3} = 1,000)等)に記述されており、メモリの容量は二進法をベース(キロビット =(2^{10} = 1,024)等)に記述されます。

一方で、東アジア諸国（中国、韓国、日本）では、万=(10,000)や億=(100,000,000)のように4桁区切りが一般的です。 こういったルールの違いが、kilo、mega、giga、tera等の単位を使った暗算をする時に、特に日本の学生にとって、混乱を招いてしまう要因になっているのも事実です。

量子データ

次のステップでは、量子ビットのかたまりである「量子レジスタ」について学習します。量子データは、この量子レジスタに保存されます。量子レジスタもまた、古典レジスタ同様、ほんの少しの量子ビットで指数関数的に多くの数値を表現することが可能です。

その他の表記法

もしあなたが好奇心旺盛な人であるならば(このコースを受けている時点で好奇心旺盛な人なのでしょうが）、二進法以外の表記法にも興味があるかと思います。もし、興味を惹かれない場合、構わずこの項を飛ばしてください。

当然、一、十、百、千のように数を数える十進法については慣れ親しんでいるかと思います。 コンピュータ科学の専門家は、AからFのアルファベットで十進法でいう10から15を表す、十六進法(hexadecimal)を用いることが多々あります。 つまり、十六進法を使って数を数える時は0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11, …のようになり、FFは十進法の255にあたり、100は十進法の256にあたります。

この表記法を用いる主な理由は、二進法をつかって巨大な数字を書くよりもずっとコンパクトに収まり、十六進法の1桁が正確に4ビットの情報を持っているため、必要に応じて簡単かつ便利に2進法に変換することが出来るためです。コンピュータエンジニアになりたい場合は、16進表記に慣れておく必要があります。

初期のコンピュータの中には、二進法の代わりに三進法を採用していたものがあります。 興味深いことに、3つの異なる状態を評価する方法は２つあります。明白な0,1および2を使った表記だけでなく、0,1および-1を使った表記法も存在します。-1 を使う場合では、数を数える時、0, 1, (1,-1), (1,0), (1,1), (1,-1,-1), (1,-1,0), (1,-1,1), (1,0,-1)のように続きます。

いくつかの量子コンピュータにおける技術は2つではなく3つの状態を生み出すため、三進数体系はうまく当てはまるように思えますが、考案されている主なアルゴリズムの殆どが二進法ベースの量子ビットを想定して設計されています。よって、ここでは二進法に基づいたシステムのみに焦点を当ててコースを続けます。

実際には、どんな数を底に使っても計算はできます。有名なのは、バビロニア数学の60を底に使った六十進法(sexagesimal)や、マヤ文明で使われていた20を底とした二十進法(vigesimal)が挙げられます。バビロニア数学の六十進法は、今日でも、60分という時間単位や、円の角度である360度などで活用され続けています。

事実、アナログコンピュータのように連続値を使用して、従来型あるいは量子コンピュータを構築することもできます。 従来型のアナログコンピュータは1960年代に構築され、1980年代頃にはカリフォリニア工科大学のCarver Mead氏等によって超大規模集積回路(VLSI)を活用したアナログコンピュータの研究が進められていました。 こういったコンピューターは特定の微分方程式の解を求めたり、積分微分や潮位の予測などに対しては優位に動作します。今日、計算の殆どがデジタルに処理をされている中、一部の研究者達はその処理が部分的にアナログな手法によって解決されていくことになると予想をしています。