量子アルゴリズム

特 集

量子コンピュータ

コミュニケーション科学の新展開

量子通信

素因数分解だけではない量子計算の魅力──量子探索技術の可能性を探る
量子コンピュータは，量子力学独特の性質を積極的に利用して計算を行うコンピュータです．実用レベルに達するには，まだ長い年月がかかるといわれていますが，現在のコンピュータでは解けない問題を，超高速に解くことが期待されています．本稿では，現在知られている量子アルゴリズ
ムの中でも特に応用範囲が広いとされる量子探索を取り上げ，量子コンピュータの可能性について考えていきます．

たにせいいちろう

谷 誠一郎

NTTコミュニケーション科学基礎研究所

ウェアを動かす手順（アルゴリズム）

用されているRSA暗号は，素因数分が必要です．そして，アルゴリズムの解の困難性を安全性の根拠としていま英国の数学者Alan M. Turingによ善し悪しが計算速度を大きく左右するす．このため，Shorの発見は，量子り計算機モデルが考案されて以来，コことも，現在のコンピュータと同じでコンピュータが完成したら，現在使用ンピュータは著しい発展をとげましす．
このため，量子コンピュータのハーされている暗号が役に立たなくなるとた．現在のコンピュータも原理的にはドウェアが完成したとしても，それをいう意味でも非常に大きなインパクト

Turingのモデルと同じです．現在の用いて難しい問題を高速に解くためにがありました．

コンピュータばかりでなく，今後開発は，優れた量子アルゴリズムが欠かせされるものも含め，このモデルに基づません．

量子アルゴリズムの必要性

くコンピュータを「古典コンピュータ」と呼び，そのうえでの計算を「古典計算」と呼びます．

しかし，よく考えてみると，便利に使われている暗号が破られてしまうこ

ShorとGroverに よ る 高 速 量 子
アルゴリズムとは，うれしくないことです．専門的には，Shor の量子アルゴリズムの拡張もよく研究されており，素因数分解

一方，「量子コンピュータ」は量子量子アルゴリズムの代表例が，素因を含むもっと広範な問題群（隠れ部分力学的な性質を積極的に利用した，数分解を現在のコンピュータよりも指群問題＊）も高速に解けることが知ら

Turingのモデルとは原理的に異なる数倍高速に行う量子アルゴリズムでれています．これらの量子アルゴリズ（1）

コンピュータです（表）．このため，す．これは，1994年にPeter W. Shor

ムは，理論的には非常に重要ですが，古典コンピュータでは解くことが難しによって発見されました．素因数分解

現時点では，身近な問題との関連は薄い問題でも，高速に解くことが期待さは， 長 年 の 研 究 に も か か わ ら ず，く，そのメリットを理解するのは難し

れ，世界中で研究が進められています．

Turingのモデル上で高速に解く方法

いかもしれません．

量子コンピュータを動かすためには，がいまだ見つかっていない難しい問題

一方，Shorのアルゴリズムと並ん現在のコンピュータと同様に，ハードです．実際，インターネットなどで使で有名な量子探索アルゴリズム（量子探索）は，1996年にLov K. Grover（2）表

古典コンピュータと量子コンピュータの比較
古典コンピュータ

量子コンピュータ

情報の単位

ビット（bit）

量子ビット（qubit）

情報の数学表現

ブール値

複素ベクトル

基本演算

ブール演算（AND, OR, NOT）

一次変換
（ユニタリ変換）

計算モデルTuring 機械，論理回路

量子 Turing 機械，量子回路により発見されました．このアルゴリズムが解く探索問題とは，N 個のデータの中から所望のデータを探す問題です．古典コンピュータであれば，最悪＊ 隠れ部分群問題：数学の群論に関する問題．特別な場合として，素因数分解を解く際にキーとなる問題を含みます．

NTT技術ジャーナル 2014.937

コミュニケーション科学の新展開

N 回程度のデータアクセスが必要で問題を切り出すことは難しく，切り出を表すことができ，さらに n 個の量子す．しかし，量子探索は，√N 回程度せたとしても探索アルゴリズム自体にビットでは， 0 … 0 から 1 … 1 までのデータアクセスで済ますことができさまざまな工夫をこらす必要が出てきの2 通りのビット列の重合せを表すこます．これは，素因数分解の場合のよます．このため，Groverのアルゴリとができます．数学の言葉を使うと，うに指数倍のスピードアップではありズムが発見されてから20年近く経た次のようになります．0︲軸と1︲軸をませんが，それでも N が巨大であれば，現在でも，量子探索のさまざまな改良持つ 2 次元複素ベクトル空間におい著しいスピードアップにつながりまや一般化が研究されています（図 ₁ ）．て，0︲軸上の単位ベクトル0が「 0 」―す．探索問題の最大の特徴は，問題設定の単純さと，それゆえの応用範囲のn→→を意味し，1︲軸上の単位ベクトル1が量子ビットと重合せ「 1 」を意味することとします．この広さにあります．実際，探索問題は，量子コンピュータが扱う情報の単位とき，「 0 と 1 の重合せ」とは，これさまざまな問題の部分問題として現れを量子ビットと呼びます（図 ₂ ）．1らのベクトルの合成α0＋β1のことでます．この部分問題を発見し，量子探つの量子ビットで，「 0 または 1 」ばす（係数α，βは複素数）．同様に，索を適用することにより，元の問題をかりでなく，それらの重合せを表現す

ｎ 個の量子ビットは，2 本の軸がある

極めて高速に，効率良く解くことが期ることができます．同様に， 2 つの量2 次元複素ベクトル空間上のベクトル待できます．ただし多くの場合，探索子ビットでは，00, 01, 10, 11の重合せを表します．量子ビットはベクトルで1990

Deutsch-Jozsa問題
Simon問題
位相計算問題

2000

20052010

固有値計算問題
Pell等式
Hidden Shift問題→nnBernstein-Vazirani問題

Shorの素因数分解・離散対数

1995

→

Jones多項式

可換群隠れ部分群問題

Groverの量子探索
Hybrid法

多項式法

量子カウンティング
連結性判定

Principal ideal

量子振幅増幅法
三角形発見

Adversary法

poly-near-Hamiltonian-group Aﬃne group部分集合発見
量子ウォーク探索
Semidirect product group隠れ部分群
２面体群隠れ部分群
AND-OR 木計算
Element Distinctness
Class group面体群隠れ部分群
Hidden nonlinear 負重みadversary法
オラクル同定平面性判定
Curvlet transformSpan Program法
nil-2 group隠れ部分群有界位数グラフ
線形計画
Minor-closed graph property

不定コスト量子振幅増幅法

Boolean hidden shift問題

理論的には重要だが，身近な問題との関連が薄い

現在

図1

重合せ

再帰量子ウォーク

Learning graph法

結合則テスト 部分グラフ発見 行列乗算

身近な応用例が豊富

量子アルゴリズム研究の流れ

数学表現

1 量子ビット ｛ ₀ , 1 ｝の重合せ

2 次元空間のベクトル

2 量子ビット ｛ ₀₀, ₀1, 1₀, 11 ｝の重合せ

₄ 次元空間のベクトル｛ ₀…₀₀, ₀…₀1, …, 1…11 ｝
n 量子ビット（2n個のビット列）の重合せ

2n次元空間のベクトル

1‑軸重合せ→β1→→→＝α0＋β10‑軸→α0

量子計算の基本操作（ユニタリ変換）例（→（θ）＝ cosθ−sinθ（ ））sinθ αcosθ β→→＝（αcosθ＋βsinθ）
0＋（−αsinθ＋βcosθ）1

図238

NTT技術ジャーナル 2014.9

量子ビットと重合せ特 集あったわけですから，量子ビット上のるためのステップ数も考慮に入れなけ確率で判定することです．探索問題を演算はベクトルに対する演算（ユニタればなりません．しかし，探索問題を部分問題として切り出すために，キー含め，本稿で扱う問題は，データアクとなるのは，18世紀にオイラーによっセスのためのステップ数のほうが支配て発見された基本的な定理です．

＊1リ変換）になります．

探索問題と量子アルゴリズム探索問題に限らず，N 個の入力デー的なので，以下ではデータアクセス回定理：n頂点からなるグラフが平面数に着目します．

性 を 持 つ な ら ば， 枝 の 数 は 高 々タX1,…, XN に依存する問題を解く際

この定理の応用例としてグラフのには，入力データにアクセスしなけれ平面性を判定する問題を考えてみまばなりません．その際，形式的にはイしょう．

ンデックス k でアクセスすると，入力データXk が得られると考えられます．

3n−6本である．
この定理を使って次のように問題を分割します（図 4 ）．

グラフの平面性判定①‌ n（n− 1 ）/ 2 個所の枝候補の中から，3n−5本の枝を特定する（グ量子コンピュータでは，このインデッ

グラフの平面性とは，枝を交差させラフの枝の数が3n−5本よりも少クスを量子ビットで記述するので，重ずに平面上にそのグラフを描画できる

ない場合は全枝を特定することね合わされたインデックスでアクセス性質です（図 3 ）．グラフが平面性をになる）

し，それに対応して，重ね合わされた持つならば，一般のグラフでは計算困②‌ 3n−5本の枝が見つかればオイ入力データを得ることができます．こ

難な多くの問題を高速に解けることがラーの定理により平面性はないのような重合せによるデータアクセス分かっており，グラフの平面性を判定（3n−5＞3n−6なので）を認めると，量子探索を次のように述する問題は重要な問題としてよく知ら③‌ 3n−5本未満の枝しか見つからべることができます（簡単のためデーれています．さて，Gを n 頂点からななければ，それが全枝であるの＊2

タの種類を 0 または 1 にしますが，る無向グラフ本質的ではありません）．

力として，Gの頂点の各組（i, j）間にで，さらなるデータアクセスなしとします．問題の入定理（量子探索）：N 個の入力デー枝があるかどうかのデータが次のよう

タX1,…, XN ∈｛ 0 , 1 ｝が与えられたに与えられたとしますに，高速に平面性を判定
ここで入力データへのアクセスに関係しているのは①だけです．少し考えときに，量子探索アルゴリズムは，・各‌ i ＝1,…,n ，各 j ＝1,…,n（ただると，①を行うためには， 1 本の枝を√N 回程度のデータアクセスによし， i ＜ j ）に対して，（i, j）間探す探索問題を3n−5 回解けば良いこり，Xi＝ 1 であるインデックス i をに枝があれば Xij＝ 1 ，なければとが分かります．したがって，①の部高確率で見つけ出すことができる．

Xij＝ 0 （すなわち，XijはGの隣接分を量子で高速化できます．結果とし―一般に，問題を解くために必要なステップ数は，このデータアクセス回数のほか，得られた入力データを処理す＊3行列の要素）．
1n（n− 1 ）個の入力問題は，この2
データXij が表すグラフGの平面性を高て，量子コンピュータでは n1.5 回程度のアクセスで十分であるのに対して，古典コンピュータでは n2 回程度のアクセスが必要であることを我々は数学的に証明しました（3）．この例でのポイ

枝を交差させずに平面上に描画可能な性質.
例：（a）は平面性がない．（b）は（a）から１本だけ枝を除いたグラフである．
この場合，矢印右の図のように描けるので，（b）は平面性がある．

ントは，グラフ理論の既存知識を用いることで初めて探索問題を切り出すことに成功した点です．量子で高速に判＊1（a） 平面性なし（b） 平面性あり

図3グラフの平面性＊2＊3

ユニタリ変換：任意の 2 つのベクトルの内積を変えない線形変換．直感的には， 2 つのベクトルの角度とそれぞれの長さを変えない変換．
無向グラフ：向きを持たない枝からなるグラフ．
隣接行列： n 頂点グラフ G の隣接行列 Aとは， n 行 n 列の行列で, 要素 A［ i, j ］で頂点 i , j 間の枝の有無を表したもの．

NTT技術ジャーナル 2014.939

コミュニケーション科学の新展開

定できるグラフの重要な性質は，ほか率が p の古典アルゴリズムがあれ題です（図 5 ）．この問題は，分散計にも多数知られており，例えば，連結ば，アクセス回数がc/√p 程度で，算のさまざまな問題を解く際に，部分かつ，成功確率が 1 に近い量子ア問題として出現します．
しかしながら，ルゴリズムをつくることができる．

各ノードが識別子をあらかじめ持ってさらに， p の値が正確に分かっていることを仮定しない一般的な条件下いれば，成功確率を 1 にすることにおいて，古典通信（通常のビットのができる．

送受信）と古典計算では，有限時間内出することを考えます．すなわち，入探索問題に対するランダム抽出の場に確率 1 では解けないことが数学的力データX1,…, XN の中からランダムに合， c ＝ 1 ， p ＝1/N であるので，対に証明されています．ところが，量子1 つ選択してアセクスします．N 個の応する量子アルゴリズムのアクセス回

計算と量子通信を使えば，有限時間内データの中に所望のデータがちょうど数は，c/√p＝√N となります．つまり，に確率 1 で解けることを我々は証明

1 つだけある場合，この方法の成功確特別な場合が，Groverの量子アルゴしました（4）．これは，量子計算と古典率は，わずかにN 分の 1 です．量子探リズムになっています．直感的に，上計算が質的に異なることを示していま索を大雑把に表現すると，このランダ記の定理は，元となる古典アルゴリズす．なお，この結果の最初の証明は，ム抽出を「重合せ」で√N 回程度繰りムを重合せで1/√p 回程度繰り返すこ量子振幅増幅を用いていませんでした

返していることと同じなのです．古典とで成功確率を 1 近くまで増幅できが，後に量子振幅増幅を用いた別証明

コンピュータでは，成功確率N 分の 1るといっています．同じアイデアを用を与えました．以下にそのアイデアをのランダム抽出をN 回程度繰り返さないると， 1 台の量子コンピュータ上で述べます．

いと，成功確率を 1 近くまで増幅できのアルゴリズムだけでなく，複数の量ないわけですから，量子探索は，ラン子コンピュータからなる量子ネット＊4性＊5の判定やハミルトンパス―の存在判定などがあります．

量子探索の一般化
古典コンピュータ上で，ランダム抽――――＊6

ダム抽出の成功確率を，ずっと少ないワーク

繰り返し回数で， 1 近くにまで増幅しムなどにも適用することができます．ているとみることができます．この考＊4連結性：任意の 2 頂点に対して， 1 本または複数の枝をたどることによって，一方の頂点から他方に到達できるようなグラフの性質．
＊5 ハミルトンパス：グラフの枝をたどることによって，すべての頂点をちょうど 1 回だけ訪れることができるとき，その経路のことをハミルトンパスといいます．
＊6 ：量子ネットワーク上では，量子ビットを送受信する量子通信が行われます．量子通信は，光子に量子ビットを載せて光ファイバで通信することにより，すでに量子鍵配送で実用化されています．

上での分散計算アルゴリズリーダ選挙問題

え方を以下のように一般化できることが知られています．

リーダ選挙問題とは，ネットワーク定理（量子振幅増幅）: 入力へのア上のノードどうしで自律的にリーダをクセス回数が c で，かつ，成功確決定するという分散計算の本質的な問

入力データ
頂点 i ，j 間に枝はある？

量子アルゴリズム

YesかNo①③ たかだか3n‑6本しか見つからない

3n‑5本の枝を探す

たかだか3n‑6本の枝に対し，既存アルゴリズム

Yes
No

② 成功

ここに探索問題！

「枝の探索」を3n‑5回繰り返し

図440

NTT技術ジャーナル 2014.9

グラフの平面性を判定する量子アルゴリズム

平面性あり平面性なし

特 集

リーダ選挙問題（さまざまな分散計算の問題を解くうえで部分問題として出現）
ネットワーク上のコンピュータどうしで，自律的にリーダを選出できるか？
成功確率
1

コンピュータどうしでリーダ役を自律的に選出
リーダ量子アルゴリズム

古典アルゴリズム0

計算時間

古典計算＋古典通信

有限時間内に確率１では解けない

量子計算＋量子通信

有限時間内に確率１では解ける

図5（注）各ノードの識別子を仮定しない場合

リーダ選挙問題を解く量子アルゴリズム

まず最初に，次のような単純な古典ある種の半正定値計画法＊ 8 を基にしアルゴリズムを考えます．①各ノードた量子アルゴリズムなども盛んに研究がコインを投げ，コインの表を出した

され，数学や計算機科学のさまざまなノードがただ 1 つのときに，そのノー分野との関連が知られるようになってドをリーダと決定する．②ノード数をいます．また，アルゴリズムを量子回n とすると，このアルゴリズムの成功路に落とし込む部分の効率化に関するn確率は， p ＝n/2 であることは簡単に研究も着実に進歩しています（5）．しか分かる．③成功確率の値が正確に分し，未解明な問題は今なお数多くあり，かっているので，量子振幅増幅を使っまだまだ発展途上といえます．これら――て，コイン投げを1/√p＝ √2n/n 回程の問題を解決するためには，数学 ・ 物

度繰り返すことで成功確率を 1 にす

理 ・ 計算機科学の最新の知識を結集しることができる．て，新たな技術を開発していく必要がさらに，この①～③のアイデアを洗練させると，コイン投げは n 回程度に減らすことができます．

今後の展望
これまでの20年間の膨大な研究を通して，量子計算理論は高度に発展してきました．
最近では，ランダムウォー
ク＊ ₇ の量子版（量子ウォーク）や，＊7＊8

ランダムウォーク：グラフの隣接頂点間を確率的に移動することにより，グラフの頂点をたどる確率モデル．
半正定値計画法：半正定値行列を用いて記述できる，最適化手法の一種．線形計画法
を特殊な場合として含みます．

Hierarchy of Constant-Depth Exact Quantum
Circuits,” Proc. CCC2013, pp.168‒1₇8,
Stanford, U.S.A., June 2013.

あるのです．
■参考文献（1） P. W. Shor: “Algorithms for quantum
computation: Discrete logarithms andfactoring,” Proc. FOCS1994, pp.124‒134,
Santa Fe, U.S.A., Nov. 1994.
（2） L. K. Grover: “A fast quantum mechanicalalgorithm for database search,” Proc.
STOC1996, pp.212‒219, Philadelphia, U.S.A.,
May 1996.
（3） A. Ambainis, K. Iwama, M. Nakanishi, H.
Nishimura, R. Raymond, S. Tani, and S.
Yamashita: “Quantum Query Complexity ofBoolean Functions with Small On-Sets,”
Lecture Notes in Computer Science,Vol. 5369, pp.90₇‒918, 2008.
（4） S. Tani, H. Kobayashi, and K. Matsumoto:“Exact quantum algorithms for the leader
election problem,” ACM Transactions on
Computation Theory, Vol.4, No.1, pp.1-24,
March 2012.
（5） Y. Takahashi and S. Tani: “Collapse of the谷誠一郎

私たちは，量子情報科学の研究をさらに推進し，量子コンピュータの能力を最大限に活かすことを目指します．

◆問い合わせ先

NTTコミュニケーション科学基礎研究所
メディア情報研究部
情報基礎理論研究グループ
TEL ₀₄₆-2₄₀-₃₆₅₈
FAX ₀₄₆-2₄₀-₄₇₀₉
E-mail tani.seiichiro lab.ntt.co.jp

NTT技術ジャーナル 2014.941