知っておきたいキーワード
Keywords you should know.

第 112 回

量子コンピューティング
出 崎 善 久††茨城大学 工学部
"Quantum Computing" by Yoshihisa Desaki (Faculty of Engineering, Ibaraki University, Ibaraki)
キーワード：量子コンピューティング，量子ビット，量子回路，重ね合わせ，Deutsch-Jozsa のアルゴリズム

1．まえがきムーアの法則が提唱されてからおよそ半世紀が経ち，集積回路の微細化とは異なる方向で計算機の能力向上を目

2．量子ビット
皆さんよくご存じのとおり，古典計算機では情報を 2 進数で扱います．普段パソコンやスマートフォンを使っている時には 2 進数を意識することはありませんが，ディスプレイに表示されている文字も，計算機の内部では 2 進数として扱われています．古典計算機では，2 進数の 1 桁をビット（bit）と呼んで計算の最小単位としています．これに対して，量子計算で計算の最小単位となるのは，量子ビット（quantum bit，または qubit）と呼ばれるものです．
1 ビットを 0, 1 で表すのと同様に，1 量子ビットを |0〉,|1〉 と表します（Dirac の記法と呼ばれています）．
量子計算機と古典計算機
古典計算機とは，量子計算機と対比して通常の計算機のことを指す用語で，量子コンピューティングの分野で広く使用されている用語です（言葉の頭に「古典」がつくと，量子力学的効果を考えないという意味になります）．
古典計算のビットは，物理的には電圧の値の高低等と結びつけて解釈されます．量子ビットの場合も同様に，物632 （116）指した研究が近年盛んに行われています．量子力学の考え方を計算に取り入れた量子計算機もその一つです．本稿では，代表的な計算モデルである量子回路に基づく量子コンピューティングについて説明します．

理系の量子力学的な状態を表したものであると解釈します．量子ビットは，以下のようにベクトルで表現することができます．
 1
 0
|0〉 =   , |1〉 =  
 0
 1次に，以下のような線形結合を考えてみましょう．
c ψ = c0 |0〉 + c1 |1〉 =  0  c 1
これもまた，1 量子ビットが取りうる値となります．上の式中の c0，c1 は確率振幅（probability amplitude）と呼ばれる複素数で，以下の式を満たすものとします．
|c0 |2 +|c1 |2 = 1
これは，|0〉, |1〉 に対応する状態を，係数 c0，c1 で重ね合わせた状態であると解釈できます．古典ビットは 0 と 1の 2 通りの状態しか表現できません．これに対して，係数c0，c1 が（2 乗和が 1 であれば）任意の複素数でよいことから，1 量子ビットが表現できる値は無限個あることがわかります．ただし，量子ビットを実現した物理系を

映像情報メディア学会誌 Vol. 70, No. 4, pp. 632 〜 636（2016）

知っておきたいキーワード

実際に測定すると，|0〉 または |1〉 のどちらか一つが得られ，各ビットが得られる確率は，|c0|2, |c1|2 となり量子コンピューティング|0〉⊗|0〉⊗|0〉, |0〉⊗|0〉⊗|1〉 ,, |1〉⊗|1〉⊗|1〉
ただし，この書き方だと見た目が煩雑になるので，通常ます．
1 量子ビットは，それに対応する物理系の量子力学的な状態を表すものでした．2 量子ビット（量子ビット 2 桁）
では二つの物理系の状態を表すことになるので， 以下の4 通りの状態を考える必要があります．
|0〉と|0〉 , |0〉と|1〉 , |1〉と|0〉 , |1〉と|1〉
これは数学的には直積なので，以下のように表すことがは以下の省略記法を使用します．
n個の|0 〉 の直積

|0000〉 =|0〉⊗|0〉 ⊗⊗|0〉n 桁の量子ビット|00···0〉 を |0〉|0〉 ···|0〉 と書くこともあります．1 量子ビットが変数や式で表現されている場合は，|x, x⊕y〉 のよ
うに書きます．
|00···0〉, |00···1〉, |11···1〉 は，n 量子ビットの計算基底できます．
|0〉⊗|0〉 , |0〉⊗|1〉 , |1〉⊗|0〉 , |1〉⊗|1〉
量子ビットの数を 3 以上に増やした場合も同様に，以下の（computational basis）と呼ばれるものです．1 量子ビットの場合と同様に，n 量子ビットもまた計算基底の線形結合で表すことができ，確率振幅の 2 乗和は 1 となります．

ように書くことができます．

ましょう．|0〉 に Hadamard ゲートを作用させると，以下3．量子回路のようになります．

ここでは，量子ビットに対する計算のモデルとして広く知られている量子回路についてごく簡単に紹介します．
3.1

Hadamard ゲート

古典ビットに対する操作は，AND や OR 等の論理演算です．計算機として実装する際には，AND ゲートや ORゲートといった論理ゲートを電子回路として実現します．

1  1 1   11  1
   = 
1−10 2
2  1
1   1   0  |0〉+|1〉=   +    =22   0  1  H|0〉 =|1〉 に Hadamard ゲートを作用させた場合も同様に，量子回路モデルにおいて論理ゲートに相当するものは，量子ゲートと呼ばれています．まずは，1 量子ビットに対

H|1〉 =|0〉−|1〉
2する代表的な量子ゲートである Hadamard ゲートを取り上げてみましょう．
Hadamard ゲート（Hadamard gate）
1 量子ビットに対して Hadamard 変換 H を施すゲートです．ψ = c0|0〉 + c1|1〉 に H を作用させて ψ´ = c´0|0〉 +c´1|1〉 が得られます．
 c   c′ 1 1 1 H  0 =  0 , H = c   c′ 2  1 −1
11論理ゲートを論理関数で表現したのと同様に，量子ゲー以上の結果をまとめて，任意の1量子ビット|x〉にHadamardゲートを作用させて得られる式を与えておきます．
H|x 〉 =∑(−1) xz
2z∈{0,1}| z〉n 量子ビット |x〉 =|x1 x2 ··· xn〉 に対して Hadamard ゲートを並列に作用させると，以下のようになります 1）2）．
H ⊗ n |x 〉 = H ⊗ n |x1 x2  xn 〉= H|x1 〉 ⊗ H|x2 〉 ⊗  ⊗ H|xn 〉トは行列で表現できます．回路図では，図 1 のように四角xz(−1) 1 1

箱に接続されている線は量子ビットを表し，古典計算機∑z1 ∈{0,1}の論理ゲートと同様に，ゲートの左側の線を入力，右側∑(−1) n n

い箱の中にゲートの種類を表す情報を書いて表現します．

=の線を出力と解釈します．
ここで，Hadamard ゲートの性質について少し考えてみ22∑z∈{0,1}n

図 1 Hadamard ゲートxz(−1) 2 2z2 ∈{0,1}2|z2 〉 ⊗  ⊗|zn 〉∑ ∑∑z1 ∈{0,1} z2 ∈{0,1}=∑x zzn ∈{0,1}=|z1 〉 ⊗(−1) xz
2nzn ∈{0,1}x z + x2 z2 ++ xn zn(−1) 1 12n|z1 z2  zn 〉| z〉

上の式において，|z〉 =|z1 z2 ··· zn〉 であり，

（117） 633

知っておきたいキーワード

こうして得られた β00 は Bell 状態（Bell state）と呼ばれ，1 量子ビットの直積では表現することができません（β00 =(c00|0〉 + c01|1〉) ⊗ (c10|0〉 + c11|1〉) を満たす確率振幅の組
c00，c01，c10，c11 が存在しません）．また，1 ビット目が 0であれば 2 ビット目も 0，というようにビット間に相関が生じています．これを，量子もつれ（entanglement）と呼図 2 Hadamard ゲートの並列作用

び，古典計算では生じない量子計算固有の概念となっています．
量子ゲートを表す図では，古典計算の論理ゲートにならって入出力のビット数に応じて独立に線を書いていますが，このようにもつれた状態の入出力となる場合もあ

図 3 制御 NOT ゲートるため注意が必要です．
3.3xz = x1 z1 + x2 z2 +···+ xn zn としました．また，n 量子ビットに対する Hadamard ゲートの並列作用を H ⊗n で表すことにします（図 2）．
3.2

量子並列化回路

ここで，以下のような写像で定義された n + 1 量子ビットに対する量子ゲート Uƒ について考えてみましょう．
U ƒ :|x, y〉 →|x, y ⊕ ƒ( x)〉

制御 NOT ゲート(ƒ(x)はnビット入力 1ビット出力の関数)

2 量子ビットに対する代表的な量子ゲートとして，制御NOT ゲート（図 3）を紹介しておきます．
制御 NOT ゲート（Controlled NOT gate），あるいはCNOT ゲート

複数の量子ゲートを接続して得られる量子回路の例を図4に示します．この場合，回路図の左から右に向かって時間が流れると解釈し，一番左の量子ビット（回路の入力）にいくつかの量子ゲートを作用させて，計算結果となる

制御 NOT ゲートは，以下の写像で定義された 2 量子量子ビット（回路の出力）が得られます．この量子回路にビットに対して作用するゲートであり，古典計算機のψ0 =|00〉 を入力した場合，どのような出力 ψ2 が得られる

XOR に相当します．制御ビット |x〉 はそのまま出力さでしょうか．

れ，標的ビット |y〉 は |y´ 〉 =|x⊕y〉（⊕ は排他的論理和）となって出力されます．

最初に |00〉 の上位ビット（左側のビット）に Hadamardゲートを作用させて，以下の状態 ψ1 が得られます．

U CN :|x, y〉 →|x, x ⊕ y〉
複数の入出力線をもつ量子ゲートでは，上の入力を上位ビット，下の入力を下位ビットであると解釈します．2 量

ψ 1 = H|0〉⊗|0〉 =|0〉+|1〉2⊗|0〉 =|00〉+|10〉2

これに Uƒ を作用させると，子ビットの計算基底に制御 NOT ゲートを作用させると，以下のように制御ビット（上位ビット）の値により標的ビット（下位ビット）の値が変化します．
U CN |00〉 =|00〉, U CN |01〉 =|01〉,
U CN |10〉 =|11〉, U CN |11〉 =|10〉
ここで，重ね合わせた状態を含んだ 2 量子ビット ψ に制
御 NOT ゲートを作用させると何が起こるでしょうか．例
えば，以下のような ψ を考えてみます．

ψ=|0〉+|1〉2⊗|0〉 =

ψ 2 = U ƒψ 1 = U ƒ|00〉+|10〉2|10〉 |0, 0 ⊕ ƒ(0)〉 |1, 0 ⊕ ƒ(1)〉+= Uƒ+ Uƒ=2222|0, ƒ(0)〉 |1, ƒ(1)〉 |0, ƒ(0)〉+|1, ƒ(1)〉=+=222|00〉得られた ψ2 は |0,ƒ(0)〉 と |1,ƒ(1)〉 の重ね合わせになっており，関数 ƒ(x) の任意の入力に対する結果を並列に求め|00〉+|10〉ていることになります．古典計算機で関数の並列処理を2行う場合，入力の数だけプロセッサを並べる必要があるのに対し，量子計算機では量子ビットの性質を利用してこれに制御 NOT ゲートを作用させると，

β00 = U CN ψ = U CN
= U CN|00〉

2|10〉+ U CN
22|00〉 |11〉 |00〉+|11〉+==222634 （118）

並列処理を実現しているのです．

|00〉+|10〉

図 4 量子並列化回路

映像情報メディア学会誌 Vol. 70, No. 4（2016）

量子コンピューティング

4．Deutsch-Jozsa のアルゴリズム
量子計算機が古典計算機に対して明確に優位であることを示したアルゴリズムの例として，Deutsch-Jozsa のアルゴリズムについて説明します．まず，以下のような関数の推測問題について考えてみましょう．
関数の推測問題

図 5 Deutsch-Jozsa のアルゴリズムを実現する量子回路

力を ψ0 =|00 ··· 0〉 ⊗|1〉 としたとき，ψ1 は以下のようになります．

n ビット入力，1 ビット出力の関数 ƒ(x) は，定数型か分布型であるとする．ƒ(x) がどちらの型であるかを特ψ 1 = H ⊗ n |000〉 ⊗ H|1〉 =ψ1 に Uƒ を作用させると，以下のようになります．

分布型：ちょうど半分のxに対してƒ(x) = 0，残り半分のxに対してƒ(x) = 1（xの分布は任意）．

ψ 2 = U ƒψ 1 =∑(−1) ƒ( x ) |x 〉2x∈{0,1}n古典計算機で上の問題を解く場合のアルゴリズムの擬似コードを以下に示します．
x = f (0);for (i = 0; i < 2^ {n -1}; i ++) {y = f (i +1);
if (y ! = x) {break ;}
x = y;}
if (i == 2^ {n-1}) {println ("定数型") ;} else {println ("分布型") ;}|0〉−|1〉 ⊗

2 2n |x 〉x∈{0,1}n定するアルゴリズムを示せ．
定数型：すべてのxに対して，ƒ(x) = 0，またはƒ(x) = 1．

∑n|0〉−|1〉 ⊗2 

ψ2 の上位 n ビットに Hadamard ゲートを作用させると，

ψ3 =∑ ∑(−1) xz+ ƒ( x ) |z〉
2z∈{0,1}n x∈{0,1}nn|0〉−|1〉 ⊗
2 

ここで，ψ3 の上位 n ビットが |00 ··· 0〉（z = 00 ··· 0 の場合）となっている項の係数について考えてみましょう．係数を表す式に z = 00 ··· 0 を代入すると，∑x∈{0,1}n(−1) xz+ ƒ( x )2n=z= 000∑(−1) ƒ( x )x∈{0,1}n2nとなり，具体的に係数の値を求めることができる式になりました．すなわち，容易にわかるように，2n–1 個目の入力 x まで ƒ(x) の値が・ ƒ(x) が定数型の場合，係数の値は± 1すべて同じ場合，2n–1 + 1 個目の入力 x に対する結果を求・ ƒ(x) が分布型の場合，係数の値は 0めるまでは，ƒ(x) がどちらの型かを特定できません．このとなります．確率振幅に対する制約から，係数が± 1 の項場合，ƒ(x) の計算を 2n–1 + 1 回行う必要が生じます．したがあるということは，それ以外の項の係数が 0 になることがって，関数の推測問題を古典計算機で解く場合の計算を意味します．したがって，ƒ(x) が定数型の場合は，上量は O (2n)となります．一般に，計算量が指数関数で表さ位 n ビットを測定すると必ず |00 ··· 0〉 が得られます．一

れた問題は，計算量が多いという意味で古典計算機では方，ƒ(x) が分布型の場合の |00 ··· 0〉 の係数は 0 なので，解くのが困難な問題であるとみなされます．

|00 ··· 0〉 を測定して得る確率は 0 となります．

ランダウの記号

以上をまとめると以下のようになります．

計算機科学の分野では，n ビットで表現されたアルゴ

Deutsch-Jozsa のアルゴリズム

リズムの入力に対して，計算量を n の関数 ƒ(n) で表し（1）図 5 の量子回路に |00 ··· 0〉|1〉 を入力する．

ます．計算量は n → ∞ とした場合の漸近的な挙動で評（2）出力された結果の上位 n ビットを測定する．

価するため，ƒ(n) の係数等は通常は無視されます．例（3）測定結果が |00 ··· 0〉 であれば定数型，そうでなけえば，ƒ(n) = an2 + bn + c の場合は O(n2)と表記し，n2の係数 a や 2 次の項よりも小さい項 bn + c については考慮しません．

れば分布型であると判断する．
古典計算機では関数 ƒ(x) を 2n–1 + 1 回呼び出す必要がありましたが，量子計算機では量子ゲート Uƒ を 1 回作用さ古典計算機で解くのが困難な問題を，量子計算機ではどせることで問題を解くことができます．関数の推測問題のようにして少ない計算量で解くのでしょうか．関数の自体は実用的なものではありませんが，Deutsch-Jozsa

推測問題に対するアルゴリズムを実現する量子回路を図 5のアルゴリズムは量子計算の優位性を初めて示したものに示します．

であるという点で重要です（実用的なアルゴリズムとしてアルゴリズムの処理の経過を量子回路の途中の状態を調べることで追ってみましょう（詳細は文献 1）2）参照）．入は，Shor のアルゴリズムや Grover のアルゴリズム等が知られています）．
（119） 635

知っておきたいキーワード

量子コンピューティング

参

5．むすび
本稿では，量子回路に基づく量子コンピューティン
グの基礎について説明しました．量子コンピューティ
ングを実現する計算モデルは，これまでに多数提案されています．その一つである量子アニーリングや量子考

文献1）木村達也訳： 量子コンピュータと量子通信 I −量子力学とコンピュータ科学− ，オーム社（2004）
2）宮野健次郎，古澤明： 量子コンピュータ入門第 2 版 ，日本評論社（2016）
3）小林 聡ほか編： ナチュラルコンピューティング・シリーズ第 0巻−自然計算へのいざない− ，近代科学社（2015）

断熱計算では，時間に伴う変化を表す方程式に従って物理系を変化させ，最適化問題の解を得る計算モデルです．広く知られている焼きなまし法の解を得る過程に，量子力学の考え方を持ち込んだのが特徴です 3）．
（2016 年 4 月 15 日受付）

で さ き

よしひさ

出崎 善久 1996 年，大阪大学大学院基礎工学研究科物理系専攻博士後期課程退学．同年，東京都立大学工学部助手．2000 年より，茨城大学に勤務．
画像処理を対象としたハードウェアアルゴリズム，専用プロセッサの研究等に従事．

キーワード募集中
この企画で解説して欲しいキーワードを会員の皆様から募集します．ホームページ（http://www.ite.or.jp）の会員の声より入力可能です．また電子メール（ite@ite.or.jp），FAX（03-3432-4675）等でも受け付けますので，是非，編集部までお寄せください．
636 （120）（編集委員会）
映像情報メディア学会誌 Vol. 70, No. 4（2016）