量子コンピュータで加算回路を作る

今回からは前回までの論理回路の知識を使って、実際に計算をしてみます。
まずはQuantumChalleng2020でも出題された加算回路についてです。

QuantumChalleng公式

加算回路のベースは古典回路の半加算器と全加算器です。
加算回路ではXOR・AND・ORゲートを使って加算器を構成し、それらを最終的に量子ゲートに置き換えるということで実現が可能です。
そのため、今回の説明の大部分は古典回路の説明になります。

今回のエントリーではそのような回路を作るとどうして「1 + 1 = 2」などとコンピュータ上で計算ができるのかをご説明します。
主にこれまで論理演算や電子回路に触れてこなかった方向けの内容となります。

なお、実装はQiitaにいくつか記事が上がっています。
ここでは仕組みの理解を目指します。

対象とする読者

• 量子プログラミングに興味を持ち始めたばかりのエンジニア
• 量子計算に興味を持ち始めたばかりの高校生・大学生
• 数学・論理演算・電子回路に慣れていない方
  など

対象でない読者

• 計算機科学・電子工学関連ご出身の方
  など

※もちろん読んでいただける分には嬉しいですが、
特に前半部分は電子回路の授業で扱われていたり教科書にも載っている内容となりますので
いまさらと感じさせてしまうかもしれません。

前提とする知識

• 簡単な論理演算(AND, OR, NOT)が分かること
• 基本的な量子ゲート(X, CX, CCX)が分かること

バージョン情報

• Python 3.7.3
• Qiskit 0.23.1

目次

コンピュータ・計算機で足し算をするとは

量子でも古典でも、ビットは0か1の2つの値を取る物体・回路部品でしかありません。
それ自身に計算する機能も数値を表現する機能もありません。
数値の表現方法や計算方法を回路という形で人間が教えてあげることで、計算が可能になります。
(今ご覧なっているようにブログなどをグラフィックに表示したりアプリケーションを構築するというのはそれぞれのビットから見たらさらに高度なことです。)

実はこういった数字そのもの以外の「もの」を使った数値の表現や計算を人間は日常的にやっています。
それがこれから説明する「指・正の字・そろばん」などです。
まずはこれらで計算を行う仕組みを振り返って、コンピュータでの計算を理解しましょう。

指・正の字・そろばんなどで数を数える

「指・正の字・そろばん」のある状態と、その状態に対応する数値・数字の組み合わせは下図の通りです。

図1. 指・正の字・そろばんでの数の表現

それぞれ人間は次のようにものの状態から数値を解釈しています。

• 指は立っているその本数で数値を示します。
• 正の字は画数の合計で数値を示し、「正」の字が1つ出来上がれば「5」を示し、「正」の字が何文字出来上がったら「5 x 正の字の数」で5の倍数を示します。
• そろばんは上がっているコマの数(下の段が「1」上の段が「5」)が10進法のある桁の数値を示します。

計算機上での数の表現(2進数)

コンピュータではこれらと同様に、複数のビットを1列に並べて、何番目のビットが0か1かで人間が数値だと認識しています。 それが2進数と呼ばれる表記です。
これもコンピュータやビットという「もの」にとっては0と1が並んでいるだけです。

2進数(0/1表記、古典ビット(トランジスタの電圧)、量子ビット(Bloch球))と10進数は下記のように対応させ、人間が意味づけます。

図2. 2進数と古典状態・量子状態・10進数との対応関係

計算機上で足し算をするための手順

ここまでで、「もの」の状態と人間が認識する「数値・数字」との対応を確認しました。
ではそれぞれのものの「元の状態」に「1」を足すときの手順を振り返りましょう。

図3. 元の数に「1」増えるときの「もの」の状態変化

• 指は指をもう一本足すこと
• 正の字はもう一画足すこと
• そろばんはコマを1つ動かすこと

コンピュータの計算と一番近いのはそろばんです。
1つずつコマを上げていきますが、それができるのは4つまで。
5つめはなく、上段の「5」のコマを上げて、下段のコマはすべて下げます。 再び1増えるごとに下段のコマを増やしますが、「9」の次のコマがまたなくなります。
そうしたら左隣の桁のコマを1つ上げ、元々の桁のコマは全て下げ「10」を表現します。
これは「10 (左の桁の単位) x 1 + 1 (右の桁の単位) x 0」ということですね。

2進数ではそれが2ずつ起きます。
(表現するのに使える文字が0と1の2種類しかないため。)

計算を図にするとこちらです。

図5. 2進数の計算

この図でやっていることを手順として整理すると下記です。

• 足し算するための入力となる2つの数(0か1)をビットとして2つ用意する
• 計算結果の1桁目を次のルールで出力する
  • 入力が両方0なら0を出力：0 + 0 = 00を満たすため
  • 入力の片方が1なら1を出力：0 + 1 = 1 + 0 = 01を満たすため
  • 入力が両方1なら0を出力：1 + 1 = 10を満たすため
• 計算結果の2桁目を次のルールで出力する
  • 入力が両方0なら0を出力：0 + 0 = 00を満たすため
  • 入力の片方が1でも0を出力：0 + 1 = 1 + 0 = 01を満たすため
  • 入力が両方1なら1を出力：1 + 1 = 10を満たすため
• 出力は左から順に「2桁目を表現する回路の出力」「1桁目を表現する回路の出力」と並べ、人間はこの2進数表記と10進数表記を対応させて認識する。
  • 2進数の00 = 10進数の0
  • 2進数の01 = 10進数の1
  • 2進数の10 = 10進数の2
  • 2進数の11 = 10進数の3

これらを満たす回路を次節で組んでいきましょう。

古典での加算回路(半加算器・全加算器)の作り方

前節の内容で「1 + 1 = 2」を計算するための手順が分かりました。
これを「半加算器」と言います。
さらに下の桁からの桁上がりを考慮して足し算する回路を半加算器を組み褪せて作ります。
これを「全加算器」と言います。

半加算器

前節の内容を真理値表で表すと下記です。
1桁目はXORゲートで表せ、2桁目はANDゲートで表せます。 実際にそうなっているはずなので、確かめてみてください。

1桁目

入力1	入力2	出力
0	0	0
0	1	1
1	0	1
1	1	0

2桁目

入力1	入力2	出力
0	0	0
0	1	0
1	0	0
1	1	1

2つの入力ビットからそれぞれのゲートにつなぎ、それぞれのゲートからの出力を計算結果とします。 (下図) 一般に1桁目の計算結果であるXORの計算結果をSum(S)、2桁目の桁上がりをCarry(C)と呼びます。

図6. 半加算器。A, Bが入力。上の太い三日月型の部品がXORゲート。下の半楕円型の部品がANDゲート。SがSum(加算結果の一桁目)でCがCarry(加算結果の2桁目)。(図は http://www.cs.shinshu-u.ac.jp/Lecture/LogicCirc/chap9/chap9.htmlから引用。)

入力と出力の対応が下記です。
たしかに「0 + 0」から「1 + 1」までの計算が人間が行う結果と一緒になっていると思います。

半加算回路の計算結果

A	B	C	S	計算(10進数)
0	0	0	0	0 + 0 = 0
0	1	0	1	0 + 1 = 1
1	0	0	1	1 + 0 = 1
1	1	1	0	1 + 1 = 2

全加算器

続いて全加算器です。
これは、下の桁からの桁上がりを考慮するための回路です。

例えばひっ算をするときに次の状況がよくあると思います。(2進数)

図7. 2進数のひっ算

この緑色の計算をコンピュータ上でもできるようにしたのが全加算器です。

要点としては、その桁の計算結果に下の桁からの桁上がり(Carryの値)を足して最終結果とするということです。

結論から先に、回路図と計算結果の表は下記になります。

図8. 全加算器。HA：Half Adder(半加算器)、FA：Full Adder(全加算器)の略称。Ci：下の桁からの桁上がり。Co：その桁で発生した桁上がり

A	B	Ci	Co	S	10進数での計算
0	0	0	0	0	0 + 0 + 0 = 0
0	0	1	0	1	0 + 0 + 0 = 1
0	1	0	0	1	0 + 1 + 0 = 1
0	1	1	1	0	0 + 1 + 1 = 2
1	0	0	0	1	1 + 0 + 0 = 1
1	0	1	1	0	1 + 0 + 1 = 2
1	1	0	1	0	1 + 1 + 0 = 2
1	1	1	1	1	1 + 1 + 1 = 3

ある桁の入力A, Bと下の桁からの桁上がり(Carry)Ciの3つの入力があります。 A, Bの計算を半加算器で行い、そのSumとCiも半加算器で計算します。
最終的な桁上がりは、最初のA + B の時点か、そのあとのA +B + Ciの結果のどちらかなのでそれを右下のORゲートで判断します。

実際にはこの全加算器が何個も連なることで大きな数の計算ができるようになっているのですね。
最後に出力となるビットの値(上の図だとSとCo)を読んで2進数表記でならべることで下記のように人間はそのビット列を数値と認識します。

古典から量子への加算回路の置き換え

古典ゲートを量子ゲートに置き換え

前回までで古典論理ゲートと量子ゲートとの対応を確認しました。
そのままこの全加算器にも下記の要領で当てはめます。

図9. 古典ゲートを量子ゲートに置き換え

そしてこれは量子コンピュータの特徴ですが、ゲートの出力の線の本数は入力と同じになります。
よって、最終的に不要なビットが生じますが、無視して量子全加算器の回路は下図になります。

図10. 古典全加算器と量子全加算器の対応。量子加算器で文字がないビットは途中の演算で使うのみで最終的に測定しない。

計算例

例えばQuantumChallengeに提出した下記の回路を計算してみます。

図11. ひっ算の緑枠部の計算を全加算器で実現(A = 0, B = 1, Ci = 1)

この測定結果は下記です。 ひっ算で計算すると同じようにA + B + Ci = 0 + 1 + 1 = 10が成り立っていて確かに計算できてそうです

図12. 図11の測定結果

以上が量子ビットを使って足し算するための回路の組み方と計算が行われる仕組みです。
これは単純な足し算を量子回路上でどう実現するか、という話でしたが、他の様々な問題も工夫して量子回路に置き換えて何らかの答えを出せるようにします。

まとめ

• コンピュータで計算をするにはXORとANDゲートを組み合わせればよい
• 量子コンピュータでも同様にXORとANDゲートを組み合わせればよい
• 一般に行いたい計算が実現できるように量子ゲートを組み合わせればよい