1．は じ め に
なぜ量子力学を使った情報処理を考える必要があるの でしょうか？ 我々が使うコンピュータは，ムーアの“法 則”に従って計算速度は指数関数的に向上してきました． しかし，速度の向上には物理的な限界は必ず存在します． つきつめていけば，CPU などの構成装置の微細化にお いて，原子の大きさが与える影響などの細かくすること で生じてくる現象が，限界を与える壁になってしまい ます．そこで，「細かいからこそ起きる現象を積極的に 使って情報処理を行ったらどうなるだろうか？」という 逆の発想をすることは自然な流れです．ここでいう，細 かいからこそ起きる現象とは，まさに量子力学が記述す る世界です．それゆえ，量子力学を使って情報処理を行 うことを考えるのです．このような情報処理は量子計算 と呼ばれています．実は，専門家の間では，量子計算は 従来の計算（古典計算）よりも高い能力をもっていると 認識されています．そこで，量子計算とはどのようなも のなのかを俯瞰的に説明するとともに，「どのような意 味で高い能力をもっていると理解されているのか？」や 「どのような情報処理は量子計算でやると速くできるの か？」という素朴な疑問に答えられることをこの文章の 目標とします． なお，前号において，宇都宮氏による量子計算の実現 に向けた実験的な観点からの解説がありました [宇都宮 14]．今号では，情報理論から見た量子計算の位置付け という観点で解説を行います．2．「量子計算」の分類
量子計算を説明するためには，対応する計算モデルを 導入して抽象的に扱うことで，実装方法に依存しない普 遍的な議論をする必要があります．その一方で，量子計 算と一言で言っても，量子力学を使った情報処理と定義 すると，さまざまな計算モデルをつくることができます． これらの計算モデルは，回路ベースの量子計算 [Nielsen 04]・断熱量子計算 [Seki 98]・量子チューリング機械 [Deutsch 85]・測定ベースの量子計算 [Raussendorf 03] の四つの計算モデルに大別することができます．これら のうち，量子計算を感覚的に理解するためには，最初の 二つの計算モデルが適しています． 回路ベースの量子計算は，量子計算が優れているとい うことを説明するうえで重要な計算モデルです．一方， 断熱量子計算は，実装が比較的容易な計算モデルであり， 量子力学を利用した情報処理を実装したと主張している 現状で唯一の機械である D-Wave 社 [D-Wave] の機械は， この計算モデルの実装を目指したものです．そこで，こ の二つの計算モデルを中心に説明をしていきたいと思い ます．3．古典計算の回路モデル
量子計算の計算モデルを詳しく説明する前に，比較対 象として，直感で理解できる古典計算の計算モデルであ る回路モデルを説明しましょう．回路モデルでは，図 1 のような回路（特にここでは古典回路と呼びます）によっ て，情報処理の過程を表現します．古典回路は，ビット 列の入力を情報処理の最小単位であるゲートによって逐 次的に操作し，出力を得る一連の操作を表現します． 図 1 において，時間は横軸によって表現され，左から 右にいくに従って時間が経過することを表し，それぞれ量子力学を使った情報処理
Information Processing by Using Quantum Dynamics
加藤 豪
NTTコミュニケーション科学基礎研究所Go Kato NTT Communication Science Laboratories. [email protected]
Keywords:
quantum computer, circuit-based quantum computer, measurement-based quantum computer, adiabatic quantum computer, quantum annealing, D-Wave.図 1 古典回路の例． 時間は左から右に流れ，黒い線によってビット を表現します．情報処理は，釣鐘型の記号で表 される NAND（論理積の否定）の操作と，塗り つぶした丸で表される分岐（コピー）の操作に よって行われます．
の黒線が一つのビットを表しています．利用可能なゲー トの集合をゲートセットと呼びますが，ここで定義する 回路モデルのゲートセットの要素は二つのゲート（釣鐘 型の記号と塗りつぶした丸．それぞれ NAND とコピー） です．与えられた古典回路の実行に必要な計算時間は， その古典回路の中で使っているゲートの個数であるとみ なします．古典回路は，ビット列からビット列への変換 であり，一つの古典回路は一つの関数を表現していると みなすことができ，古典回路の計算時間こそがそれに対 応する関数の計算時間であると考えます． ゲートセットの要素として特定の二つのゲートを取り 上げているため，いま定義した回路モデルは特殊なもの であると感じるかもしれません．しかし，計算モデルの 「能力」を議論するうえにおいては，この定義は決して 特殊なものではありません．というのも，例えば，入出 力それぞれが c ビット以下（ここでは，c は 2 以上の数） の任意の操作をするゲートの集合をゲートセットとする 計算モデルを考えたとしても，上述のゲートセットが 2 個の計算モデルとこの計算モデルとが，同等の「能力」 をもっていることがわかるためです．ほかにも，ゲート セットとして，c ビット以下（ここでは，c は 3 以上の数） の可逆な任意の操作をするゲートの集合とすることで可 逆回路モデルと呼べるような計算モデルも定義できます が，このようなモデルでも，もとの回路モデルと同じ能 力をもっていることが示せます． ただし，「能力」という言葉は少し丁寧に定義する必 要があります．ここで述べる能力とは，非常に粗い視点 からの定義です．そもそも，古典計算を実現する最新の 計算機はここで示した回路モデルよりももっと複雑な構 造をもっています．さらに，古い計算機と最新の計算機 とでさえ速さは全く異なります．しかしそれらすべてを， 同等の能力をもっていると表現できるような粗い視点を もち込むことで，普遍的な議論をすることを可能にして います（厳密には，計算機をスケーラブルに無限に拡張 したものが回路モデルの能力と同等になります）．具体 的には，二つの計算モデル 1 と 2 が与えられたときに， ［計算モデル 1 の能力］≦［計算モデル 2 の能力］という 優劣関係にあるための必要十分条件が次のようなもので あると定義します：二つの計算モデルに依存した多項式 f （T）があって，任意の関数 g が計算モデル 1 を使って 計算時間 Tgで計算できるとき，計算モデル 2 を使えば 計算時間 f（Tg）以下で計算できること．よって，能力と は特定の関数に対する絶対的な計算時間の多寡を表現す るものではありません．例えば，ある関数を二つの異な る計算モデルによって計算させたとしても，必ずしも優 れた能力をもっている計算モデルの計算時間のほうが少 ないわけではありません． このような能力という粗い定義をもち込むことで，新 旧の計算機や回路モデルがすべて同等の能力であると認 識することができ，量子計算との比較を普遍的に行うこ とができるようになります．そこで，以後，回路モデル や新旧の計算機をまとめて古典計算と述べることにしま す．先回りして答を少し述べると，このような粗い見方 をしてさえ，古典計算よりも量子計算のほうが高い能力 をもっていると予想されています．
4．回路ベースの量子計算
ここで，先に示した回路モデルと対比する形で，回路 ベースの量子計算の説明をします．ただし，以下で行う 「量子ビット」，「測定」などの定義に関して，「なぜそん な定義にするのか？」という疑問には一切答えてはいな いことをご承知願います．というのも，ここに示す描像 は量子力学の世界を自然に書き下したモデルであり，普 段の世界から想像することは困難なため，あえて説明し ていません．そのため，「なぜそのような世界を考える のか？」という疑問は横に置いておいて，「そのような 世界だったら何が起きるのか？」に焦点を当てているこ とを頭の片隅に置いておいてください． 回路ベースの量子計算は，図 2 のような回路（特にこ こでは量子回路と呼びます）によって，情報処理の過程 を表現します．量子回路は，「量子ビット」と呼ばれる ものの列を入力とし，情報処理の最小単位であるゲート によって逐次的に操作し，すべてのゲートを通ったら後 に「測定」を行います．「測定」という操作は量子ビッ ト列からビット列への確率的な変換であり，測定によっ て得られたビット列を出力とします．つまり，回路ベー スの量子計算においても，出力はビット列なのです． 古典回路と同様に，図 2 において時間は左から右に流 れます．一つの黒線が，扱う情報の単位である量子ビッ トを表します．ここで定義する計算モデルのゲートセッ ト（許容されるゲートの集合）の要素は 2 種類（塗りつ ぶされた丸と十字の入った丸をつなげた記号と四角）で あり，それぞれ C-NOT と呼ばれる 2 個の量子ビット（2 量子ビット）への特定の操作と，Umで表される 2 × 2 のユニタリ行列で特徴付けられる 1 個の量子ビット（1 量子ビット）への操作です．与えられた量子回路の実行 に必要な計算時間は，量子回路の中で使用しているゲー トの個数であるとみなします． 図 2 量子回路の例． 塗りつぶされた丸と十字の入った丸をつなげた記号 で表現される C-NOT と呼ばれる 2 個の量子ビット に対する操作と，四角で表される 1 個の量子ビット に対する操作からなります．半楕円の列で表現され る測定によって出力のビット列を得ます．ここで，この計算モデルで扱っている量子ビット列の 状態を数学的に表現してみましょう．n 個の量子ビット の列は，2n次元の線形空間（H）中の長さが 1 のベクト ル |φ〉によって表されます．この線形空間 H は構造を もっていて，n 個の二次元複素線形空間の直積空間とし て書かれます．ここで，それぞれの二次元複素線形空間 をそれぞれの量子ビットと認識します．そこで，ベクト ル |φ〉が，それぞれの二次元空間中のベクトル |ψj〉の 直積で書けるときには，そのそれぞれのベクトル |ψj〉 がそれぞれの量子ビットの状態を記述しているとみなせ ます．しかし，状態を表すベクトル |φ〉がそのような 構造をもっていない場合は，どれか一つの量子ビットを 取り上げてその状態だけを記述する表現というものは存 在しないことに注意してください（他の部分との相関が 存在するため単独での忠実な表現方法が存在しないので す）． ゲートが引き起こす作用の数学的構造も同様に見てい きましょう．量子回路におけるゲートを空間 H 中の変 換ととらえる場合，ユニタリ行列で表現される変換（二 つのベクトルの内積が変換前と後で変わらない線形変 換）であることを要求します．例えば，図 2 における U4という 2 × 2 のユニタリ行列により特徴付けられる ゲートは，二つ目の量子ビットにのみ影響を与えるゲー トであり，具体的には Id⨂U4⨂Id⨂Id⨂…と書くことが できます．ただし，Id はそれぞれの二次元空間での恒等 演算とします．また，⨂ は直積記号です．C-NOT も 2 量子ビットからなる四次元空間へのユニタリ行列を空間 H へのユニタリ行列へと同様に拡張することで定義しま す． 測定は，空間 H の直交基底を固定することで定義さ れます．まず，量子ビットは二次元空間なので，直交す る二つのベクトルからなる基底を定義することができま す．そこで，この固定された直交基底をそれぞれ 0/1 ベ クトルと呼び | 0〉/| 1〉と書きます．すると，この 0/1 ベクトルの直積ベクトルの集合によって全体空間 H の 基底が定義されます．これを計算基底と呼びます．定義 からわかるように，一つのビット列によって一つの基底 ベクトルが特定されます．この直交基底によって以下の ように測定を定義します．測定の入力を状態 |φ〉とす ると，出力として確率的にビット列が得られます．この とき，ビット列 x が出力される確率は，ビット列 x によっ て特定される基底ベクトルへの射影演算子 Pxを状態 |φ〉 に作用させて得られるベクトルの長さの二乗 Px|φ〉2 となります． 量子回路の入力は量子ビット列であると書きました が，空間 H の任意の状態を入力としては許しておらず， 計算基底のいずれかの基底ベクトルを入力状態であると します．よって入力はビット列によって特定される状態 であり，そのビット列そのものを入力であると考えるこ ともできます．よって，量子回路は，ビット列からビッ ト列への確率的な関数を表現しているとみなすことがで きます． このように「量子ビット」や「計算時間」を定義して いる理由は，この計算モデルを実装した場合，その実装 装置（量子計算機）が大きくなることに比例して，扱え る量子ビット数が増える一方，一つのゲートを実施する のに必要な時間は一定であると考えているためです． ここで示した回路ベースの量子計算においてゲート セットは非常に特殊なものでしたが，回路モデルと同様 に，計算モデルがもつ能力という視点に立つと，決して 特殊な定義ではありません．というのも，量子ビット列 の入力・ゲートの逐次的実行・測定による出力ビットの 生成という構成は全く同じで，ゲートセットのみを，影 響を与える量子ビット数が c 以下（ここでは c は 2 以上 の数）となるようなすべてのユニタリ操作からなる集合 へと変更することで拡張した回路ベースの量子回路を定 義することもできます．しかし，回路ベースの量子回路 は拡張してもしなくても同じ能力をもっていることが証 明できます．そのため，ここで定義した回路ベースの量 子計算の能力は，決して特殊なものではありません．
5．量子計算は速いのか？
ここまで来たところで，少し初心に戻ってみましょう． 「量子計算を考えるのは自然の流れだ」ということを最 初の章で主張しました．でも，量子計算を実装できたと して本当に価値があるのでしょうか？ 量子計算を研究する専門家の間では価値があるだろう と信じられています．というのも，量子計算の能力は古 典計算の能力よりも真に高いと信じているからです．そ の理由は次のような事実からくるものです． まず，回路モデルと同じ能力をもつ可逆回路モデルに よって定義される任意の古典回路に対して，その古典回 路に含まれるすべての可逆なゲートをユニタリ行列に対 応させることで，拡張した回路ベースの量子計算によっ て定義される量子回路をつくることができます．このよ うにつくられた二つの回路は，定義から同じ関数を同じ 計算時間で実行することがわかります．つまり，［回路 モデルの能力］≦［回路ベースの量子回路の能力］がい えるわけです． さらに，いくつかの関数の集合によって，この二つの 計算モデルの能力に真の優劣があることが暗示されてい ます．具体的な関数の集合の例としては，因数分解（入 力が二つの素数の積であった場合，その二つの素数を直 列につなげたものが出力となるような関数）があげられ ます．因数分解は，入力のビット数に対して 3 乗のオー ダの計算時間となるような量子回路で構成できることが 知られています（Shor のアルゴリズム）[Shor 94] ．他 方で，入力のビット数に対して多項式の計算時間になる ような因数分解を実現する古典回路はないと多くの人が信じています．このことが正しければ，古典計算の能力 より回路ベースの量子計算の能力のほうが真に高いと言 えています． ここで，「暗示」だとか「信じている」などと書かざ るを得ないのは，与えられた関数を実現する古典回路 の計算時間に非自明な下限を与えることが困難なためで す．実際，古典計算よりも回路ベースの量子計算の能力 のほうが真に高いという証明は現在においても存在しま せん（計算機が独立に情報処理するものではないオラク ル問題などの場合は除きます）．そもそも，Shor のアル ゴリズムなど，効率的な量子回路のすべてが，関数に応 じて職人技的につくられたものであり，与えられた古典 回路から，なにがしかの意味で効率化された量子回路を つくる方法論などというものは今もって存在しません． ただ，計算量の専門家が一般的にどの程度，量子計算 の能力が高いと想像しているかを指摘しておくことは意 味があるでしょう． 入力のビット数に対して，多項式の計算時間で解ける 関数の集合は「簡単な問題」とし，それ以外の関数の集 合を「難しい問題」と大雑把に分けることができます（あ くまで言葉の定義であり，「簡単な問題」に含まれる関 数が必ずしも短時間で計算できることを意味しているわ けではありません）．ここで，古典計算において簡単な 問題の集合を P と表します．また，回路ベースの量子計 算において簡単な問題の集合を BQP と表します．上で 述べた専門家が信じている状況を P や BQP を使ってベ ン図で書くと，図 3 のようになります NPは正解の候補を与えられたときに古典計算によっ て正否をチェックすることが簡単な問題です．回路ベー スの量子計算の能力は古典計算の回路モデルに劣らない ことは，P が BQP に包含されていることに反映されて おり，Shor のアルゴリズムの存在は，因数分解が BQP に入っていることに反映されています．また，古典計算 では入力ビット数に対して多項式の計算時間で因数分解 ができないという予想が，P の外に因数分解があること に反映されています．割り算が入力ビット数の多項式時 間でできることは，因数分解したい数に対する因数の候 補の正否を多項式時間でチェックできることを意味し ており，因数分解が NP に含まれることに反映されてい ます．一方で，NP の中で最も難しい問題（NP- 完全問 題）は量子計算で，難しい問題だろうと信じられており [Aaronson 05]，3-SAT が BQP の外に書かれていること に反映されています． 以上の例以外にも，いくつかのよく調べられている問 題があるので，このベン図における位置付けを説明して おきましょう． グラフとは，頂点に対応するラベルの集合と，辺に対 応するラベルの対の集合によって表現されます．二つの グラフの表現において，片方の表現におけるラベルを他 のラベルに読み替えるだけで，もう片方の表現になる場 合に，その二つのグラフは同型であると言います．グラ フ同型問題とは，二つのグラフの表現が与えられたとき に同型かどうかを判定する問題です．グラフ同型問題は， NP-完全問題よりも簡単であるけれども，P には入って いない問題と考えられており，BQP に含まれるかどう かが精力的に研究されている問題です．しかし，現状に おいては，まだ量子計算にとって「簡単な問題」である という確かな証拠は得られていません [Nielsen 04]． 離散対数問題とは，a と b と N という三つの整数が入 力として与えられて，an≡ b（mod N）となる整数 n の 存在が保証されるときに，これを求める問題です．この 問題は，因数分解で使う手法と似た手法によって，量子 回路を使って多項式時間で解くアルゴリズムが見付けら れています [Nielsen 04]． これらの状況証拠をもとに，多くの専門家は BQP・P・ NPなどの集合には差分があるだろうと予想しています． しかし，BQP ⊇ P は自明である一方，BQP ≠ P は証明 されてはいません．つまり，因数分解など，BQP には含 まれていて P に含まれないという問題の候補はあるもの の，その証明自体はまだできていないのです．それゆえ に，現状では「量子計算は古典計算よりも能力が真に高 いと信じられている」という言い方をせざるを得ません． ここまで，能力という粗い尺度で量子計算を評価して きました．実際，ここまでの文章において，量子計算は 古典計算よりも「速い」または「速いと考えられている」 とは決して書いていないことに注意してください．つま り，計算したい関数を決めたところで，量子計算を使っ たときに何時間で計算できるかという疑問に対しては， 何も答えることができないのが現状であり，この疑問に 対する答はどの計算モデルをどのように実装したかに強 く依存するのです．実物ができていない段階で普遍的な 議論をしようとすると，この程度の粗い議論が限界であ るというのが現実です． その一方で，現状の技術から想定される実装方法を土 台として，量子計算はどれくらい速いのかを正面から想 定する取組みもあります．例えば，Shor のアルゴリズ ムを，想定される量子計算の実装方法で実行した場合に， 1 000ビットくらいの数であれば 1 日程度で因数分解が 3-SATなど （NP-完全問題） 図 3 専門家が想像している問題の難しさを表すベン図． Pは古典計算において簡単な問題の集合．NP は正解 の候補を与えられたときに古典計算で正否をチェッ クするのが簡単な問題の集合．BQP は回路ベースの 量子計算において簡単な問題の集合．
できるという概算があります [Devitt 13]．他方，インター ネットなどでよく使われている RSA 暗号の安全性の拠 り所となっているのは，1 000 ビット程度の長さの数字 を現在の計算機で因数分解するのは現実的な時間では困 難であるという事実です．つまり，ここでの想定どおり の量子計算の実装ができれば，RSA 暗号の安全性は消 失します．この事実から，量子計算の潜在能力の高さを 感覚的に実感してもらえるのではないでしょうか． ここまで示したように，回路ベースの量子計算は，量 子計算の能力の優位性を示すために重要な計算モデルで す．そのため，多くの理論的な研究が存在する一方で， 想定される実装方法があるとはいえ，このモデルを実 際の物理系で実現しようとすると，量子ビット列を表現 している物理系の状態を環境由来のノイズから守ること や，複数の量子ビットにまたがるゲートの正確かつ確実 な実行が困難であり，現実の技術の延長線上にはまだ実 現が見えていないというのが現状です．そのために，こ れらの困難を避けることができる，断熱量子計算という 計算モデルが考えられました．
6．断熱量子計算
断熱量子計算が情報処理において扱う対象は回路ベー スの量子計算と同様の量子ビット列です．さらに，最後 に状態を測定することで，出力のビット列を得るという 点や，ユニタリ行列によって状態を操作するという点も 同じです．ただ，そのゲートセットが異なります．断熱 量子計算は，回路ベースの量子計算における離散的なユ ニタリ行列を細分化した微小変化を連続的に作用させた 計算モデルとみなすことができます．この状況をあえて 図案化をすると，図 4 のようになります． 図 4 は図 2 と同様に左から右にかけて時間が進んでお り，横軸を t というパラメータで書くと，左端は t ＝ 0 に， 右端を t ＝ T に相当します．時間依存する状態を表現す るベクトル |φ（t）〉は，ベクトルの微分方程式＊1 （1） によって時間発展が決まります．ここで，右辺にエルミー ト行列 H（x）（固有ベクトルが直交し固有値が実数にな る行列）が出てくる理由は，滑らかに変化をするユニタ リ行列に対して，その微分が必ずエルミート行列に虚数 単位を掛けた行列となるためです． このように，数学的な構造は量子回路におけるゲート を単に連続化しただけです．しかし，計算の思想は大き く変化しています．まず，量子回路の場合は個々のゲー トは少数の量子ビットにだけ作用したものしか許容して いませんでしたが，エルミート行列 H（x）はそれぞれの xで必ずしも一部の量子ビットにのみに影響を与える行 列ではありません．ただ，任意のエルミート行列が「局 所的」であるとします．局所的なエルミート行列とは， c個（ここでは c は 6 以上の数＊2）以下の量子ビットに しか作用しないエルミート行列の和で書けることを意味 します．つまり，H（x）は c 個の量子ビットからなる 2c 次元空間中のエルミート行列を全体空間 H に拡張した エルミート行列 h（x）を使って H（x）＝Σj jh（x）と書けj るとします．ここでの定義においては，操作を連続化し たため，量子回路のような，何かを「数える」ことで計 算時間を定義することができなくなりました．そこで， 上の方程式（1）におけるパラメータ T を計算時間と定 義します．しかし，このような定義であると，どんな計 算であろうと，H（x）による計算時間を無限に小さい時 間に短縮することができます．というのも，H（x） ：＝ aH（x）を代わりのエルミート行列として使って T/a の 時間をかけて得られる出力の確率分布は元の出力の確率 分布と同じであることが式（1）からわかります．そこで， 上記以外の条件として，H（x）の固有値の上限と下限に 制限を設けます．この制限によって，この計算モデルで 計算したときに必要な時間が定義可能になり，他の計算 モデルとの比較が可能になります． 以上が，断熱量子計算で扱われる状態と操作の数学的 なモデルです．しかし，この設定では，回路ベースの量 子計算との違いは操作が連続化したうえ，操作を表現す るエルミート行列が局所的というより緩い条件になった とみなせてしまいます．しかし，断熱量子計算のモデル では，この数学的な構造の利用方法に対しても制限をし ています．その制限を説明するためには，量子力学にお ける断熱定理を説明する必要があります． 量子力学における断熱定理（量子力学的断熱定理） [Messiah 72] エルミート行列 H（x）の任意の固有値 u（x）と固有ベj クトル |ψ（x）〉が x に対して十分滑らかで，入力の量子j ビット列を |φ（0）〉：＝ |ψ（0）〉とし，H（x）を使って式 j 図 4 断熱量子計算における回路の例． 黒線は量子ビットを表現します．入力は個々の量子 ビットの空間中のベクトル |＋〉：＝（|0〉＋|1〉）2－1/2の 直積ベクトルであり，最後の測定で出力のビット列 を得ます．途中のグラデーションがかかった箱は， 微小変化を生じさせるユニタリ行列を連続的に作用 させることを表現します． ) ( ) / ( ) (t H t T t dt d i φ ＝ φ − ( )2 1 pjT T x x H dx d j j x,' ( )2 2 ) ( max ＊1 ℏ＝1 の単位系で書いています． ＊2 c が 6 以上の定数であれば，何であってもこの計算モデルは同 じ能力をもちます [van Dam 04] ．c を含め，この計算モデルをど こまで制限しても同じ能力をもち続けるかは未解決な問題です．（1）に従って時間発展させた場合， （2） が成り立ちます．ただし，p（T）は二つのベクトル |j φ（T）〉 と |ψ（1）〉の内積であり， Mj 2は行列 M の固有値の 絶対値の二乗の最大値であり， です． ここで，入力の状態を，量子ビットの空間中のベクト ル |＋〉：＝（|0〉＋|1〉）2－1/2の直積ベクトルであると制限 します．また，H（0）は，その最低固有値 u1（0）に対 応する固有ベクトルが入力状態と同じになるようなエル ミート行列であると制限します．H（x）は固有値・固有 ベクトルが x に対して滑らかに変化するものとします． そして，計算時間 T は |φ（T）〉が H（1）の最低固有値 に対応する固有ベクトルに十分に近くなる時間（ 内積 p（T）がある定数より大きくなるような T ）と定義しま 1 す．このように陰に計算時間を定義したとしても，量子 力学的断熱定理が条件を満たす T が存在することを保証 してくれます． このように定義した計算モデルは回路を使った二つの 計算モデルと違って，直感的には何らかの関数を表現し てはいるわけではありません．そこで，この計算モデル のイメージをもってもらうために，具体例として，与え られた 3-SAT 論理式において真になる節の最大数をこ の計算モデルで求める問題を考えます．ただし，3-SAT 論理式とはたかだか三つのリテラルからなる節の論理積 であり，節とはリテラルの論理和であり，リテラルとは， 論理変数またはその否定です．まず，二つのエルミート 行列 S0/1を定義します．そのために，ビット値 1/0 を論 理変数の真・偽と同一視することによって，ビット列の 各ビットを論理変数と同一視します．S1は計算基底に対 して対角な行列であり，対角要素は，与えられた 3-SAT 論理式において，計算基底に対応するビット列を論理値 とみなしたときの偽となる節の数とします．さらに，j 番目の量子ビットにのみ と作用するエルミート行列を sjとして，S0：＝Σj sjとし ます．この二つのエルミート行列を使って H（x）：＝（1－ x）S0＋xS1と定義すると計算モデルとしての条件をすべ て満たしています（S1は 3-SAT 論理式の定義から局所 的であることがチェックできます）．ここで，十分に大 きな T を使って計算をすれば，結果として得られる出力 のビット列は，与えられた 3-SAT 論理式の真になる節 の数が最大となるような論理変数の値に対応するものに なっています．よって，十分に時間をかければ，与えら れた 3-SAT 論理式の真になる節の最大数を求める問題 は断熱量子計算によって解けることがわかりました． ここで示した例は NP- 困難な問題（NP- 問題の中で 最も難しい問題である NP- 完全問題を含む問題）です． しかし，十分に時間をかければ解けるとしか計算時間に 関して言及していないことに注目してください．という のも，このとき計算時間の指標となるのは，式（2）の 右辺ですが，分子の大きさは 3-SAT 論理式の節の数に 比例する程度である一方，分母の∆（x）は 3-SAT 論理1 式の具体的な形に大きく依存します．実際，最悪値を量 子ビット数の関数として数値的に調べると∆（x）は指数1 関数的に減少していることが確かめられています．その ため，3-SAT 論理式に関する問題を上述のように断熱量 子計算を単純に使って解こうとしても，計算時間は論理 変数の数に対して指数関数的にかかることが予想されま す．
7．計算モデルのもつ能力の関係
上述のように，回路ベースの量子計算と断熱量子計算 の二つの計算モデルは，数学的な構造は同じですが，計 算手法は大きく異なります．そこで，量子計算における 異なる計算モデルの能力の比較をしてみましょう．ただ， 能力の大小関係を定義するとき，計算モデルによって定 義される回路を関数とみなす必要がありました．断熱量 子計算の回路では，解こうとする問題の特徴は H（1）で 表現されており，入力としての量子ビット列は問題の特 徴（例えば 3-SAT 論理式の具体的な形）を表現してい ません．そこで，断熱量子計算での回路では，H（1）の 形を特定するために必要なビット列を古典的な入力と解 釈することで，回路全体を確率的な関数の表現であると 認識します．これにより，他の二つの計算モデルと能力 を比較できるようになります． 実は，量子計算において，これまでに説明した二つの 計算モデルを含む4種類の量子計算の計算モデルは（ゲー トセットや H（x）の自由度など極端に制限しないなどの 適切な定義において），能力は同じであることが知られ ています [Messiah 72, Nishimura 02]．つまり，回路ベー スの量子計算にとって簡単な問題の集合として BQP を 定義しましたが，他の三つのどの量子計算の計算モデル における簡単な問題の集合も同じであるといえます．そ こで，BQP は「量子計算で簡単な問題」と表現します． さらには，簡単な問題の集合が BQP になるような計算 モデルを普遍的量子計算ということにします．8．量子計算への一里塚としての D-Wave
以上を総括すると，普遍的量子計算が（いかなる計算 モデルであれ）実装できれば，因数分解も分解したい整 数の桁に対して多項式時間で解けるため，すばらしい！！ 因数分解が多項式時間で解けるのだから，普遍的量子計 算を実装した装置は（スーパーコンピュータを含めた） − ( ) 2 1 pj T T x x H dx d j j x 2 2 ' , ( ) ) ( max ＝min ( )− ( ) : ) ( ' u x u' x x j j j j j 1 −11 −1古典計算機よりも速く計算できる問題があるに違いな い！！ というのが専門家の素直な直感です． では，そもそも普遍的量子計算を実装した量子計算機 というものは現実にあるのでしょうか？ 先に指摘した とおり，回路ベースの量子回路を実現するのは困難であ り，断熱量子計算に近いものを実装した D-Wave 社の機 械（以後 D-Wave と呼ぶ）のみが，量子力学を使った情 報処理装置といえます．それでも，量子力学的な性質は ノイズでかき消されているのではないかという疑いが今 でも存在し，論争が続いていることは前号に記載のあっ たとおりです． そこで，ここでは D-Wave が彼らの主張どおりに動い ているかどうかの検証は脇に置いて，「どのように動く と主張しているのか？」と「主張するとおりに動いてい た場合にどのような意義があるのか？」という 2 点に対 して，今まで述べてきた文脈を使って答えてみましょう． まず，D-Wave は断熱量子計算を実装することで，普 遍的量子計算を実装しようとしています．しかし，断 熱量子計算の定義で要求されている H（x）の自由度は 備えていません．つまり，D-Wave が普遍的量子計算と 同等の能力をもっているかどうかは現在でも不明です （D-Wave の能力が普遍的量子計算を凌駕しないことは 容易に示せます）．事実，D-Wave 社の主張においても， D-Waveは普遍的量子計算を実装するための一里塚であ ると述べており，普遍的量子計算を実装した装置である とは主張していません．つまり，D-Wave のスケールを 大きくしていき，扱える量子ビットの数を増やしていっ ても，必ずしも，因数分解を簡単に解ける保証はありま せん（そのような方法は，現状では知られていません）． 実は，D-Wave 1 と呼ばれる装置は D-Wave の中で最 新の 1 世代前の装置ですが，多くの情報が D-Wave 社 から提供されています [D-Wave]．そこで，D-Wave 1 を 具体例として，D-Wave の量子力学を利用した情報処理 装置としての意義のより詳しい説明を試みたいと思いま す．
9．D-Wave 1 は何をしてくれるのか？
D-Wave 1は断熱量子計算の実装を目標としたもので あり，H（x）に対して余分な制約がある点のみが理想的 な断熱量子計算と異なる装置であるということができま す．そこで，D-Wave 1 で許される H（x）の構造を陽に 示します．そのために，図 5 で示されたグラフ（V, E） を使います．頂点 V の要素を j や k という変数で表し， 辺 E をその辺が結んでいる頂点のセット〈j, k〉で表す ものとします． D-Wave 1が扱う個々の量子ビットは図 5 の個々の頂 点に対応しており，128 個存在します．扱える H（x）は H（x）：＝（1－f（x））H0 0＋f（x）H1 1という形をしており，f（x）b （b ∈ {0, 1}）は x＝0 のときに 0 で x＝1 のときに 1 と なる単調増加関数です．H1はエルミートで計算基底に 対して対角な行列であり，128 個のビット値（1＋bj）/2 を要素とするビット列によって同定される基底ベクトル で決まる H1の対角成分は， （3） という関数で記述されます．ただし，hjはおのおのの頂 点に対応する量子ビットごとに，K〈 j, k〉は図に示された 352個の辺ごとに，それぞれ割り当てられる変数であり， それぞれの値は {－1, －6/7, －5/7, …, 6/7, 1 } の 15 個の 値のうちのどれか一つに設定することができます．H0 は 3-SAT 論理式の例のときに定義した S0と同じもので す． まとめると，D-Wave 1 を情報処理装置としてみると， 変数 hjと K〈 j, k〉と T の値を入力として受け取り，式（1） に従って変化した状態 |φ（T）〉を生成し，その状態を測 定することで得られるビット列を出力する装置であると いえます．式（3）の最低値を与える bjの列に対応するビッ ト列を「正解」とすると，計算時間 T が十分に長ければ， 量子力学的断熱定理によって正解が出力されることが保 証されます． しかし，計算時間 T は D-Wave 1 への入力であり，正 解を高い確率で出力させるためには，指定した変数から 決まる H（x）から∆（x）の 0 ≦ x ≦ 1 における最小値1 を別途計算し，その値と関係式（2）を使って T を決定 する必要があります．10．D-Wave の存在意義
D-Wave 1が実現する H（x）は，断熱量子計算の計算 モデルの定義で要求されている，「6 個以下の量子ビッ トにしか作用しないエルミート行列の和の形で書ける行 図 5 グラフ（V, E）． Vは頂点の集合であり，図中の丸によって表現され ています．個々の頂点は，一つの量子ビットに対応 します．E は頂点をつなぐ辺の集合です．灰色の色 分けは構造を見やすくするため行ったものであり， 機能的な違いはありません． E k j k j k j V j j jb K bb h , , ＋ −列」の一部しか実現できていません．実は，H（x）とし て実現できるべきエルミート行列の範囲を定義以上に制 限しても，計算モデルの能力が低下しない場合があるこ とが示されています．しかしそれでも，D-Wave 1 の程 度まで H（x）を制限してしまうと，能力の低下を否定す ることはできていません． その一方で，D-Wave 1 が表現して扱うことができる 問題の範囲は比較的広いといえます．というのも，図 6 のグラフに対応する関数（3）であれば，hj＝0 かつ K〈 j, k〉∈ {－1, 0, 1} であっても，この関数の最低値を与 える bjを求めることは NP- 困難な問題 [Barahona 82] です．他方，図 5 を適切に拡張すれば，図 6 のグラフが サブグラフとして含まれます．つまり，D-Wave 1 をス ケーラブルにした装置は，NP- 困難の問題を扱うことが できることを示しています．しかし，この扱う問題の広 さは，必ずしも計算モデルの能力の高さを表すわけでは ありません．そもそも，量子計算量の研究をやっている 人達の多くは，BQP の中に NP- 完全の問題は含まれて いないだろうという感触をもっており，3-SAT のような NP-完全問題を D-Wave 1 をスケーラブルにした装置で 解こうとしても，その装置が理想的に動作している範囲 においては，高い確率で正解を得るために必要な計算時 間 T は，入力のビット数に対して多項式時間より大きく なるだろうと専門家は認識しているということになりま す．つまり，NP- 完全な問題などは，理想的に動作する D-Wave 1にとっても難しい問題であると考えられてい るわけです． では，D-Wave は断熱量子計算を実装するための一里 塚としての技術的意義しかないのでしょうか？ 今まで の計算量の立場からの議論の範囲においては，あまり肯 定的な結論は出てきませんでした．しかし，物理的な視 点からの次の指摘を最後にします． D-Wave 1に hjと K〈 j, k〉と T を入力として与えると， （3）の最小値を与えることが期待されるビット列 bjが 出力として与えられます．このとき，量子力学的断熱定 理により，正解が得られる可能性が十分に大きくなる T を計算することは原理的には hjと K〈 j, k〉と（2）を使えば 可能であると述べましたが，式（2）から得られるのは あくまで理想的な場合の十分条件でしかありません．し かし，D-Wave は物理的な機械であり，ノイズの影響も 厳然と存在します．実は，このノイズは，必ずしも否定 的な影響を与えるとは言い切れません．というのも，熱 力学によれば，理想的には式（1）のような時間変化を する場合に，絶対零度の環境系との弱いつながりによっ て発生するノイズの影響を受けると，そのときどきのエ ルミート行列 H（x）の最低固有値に対応する固有ベクト ルに確率的に近づく性質があることが知られています． つまり，D-Wave が十分に冷えた環境にさらされている と，その影響により正解が得られる確率が上がるのです． このような理想的な状況からずれる効果によって，断熱 定理から予想される効果以上に現実の D-Wave がもって いる能力が高くなる可能性も否定できません．さらに， D-Waveを動かせば T が十分に大きくなくても何らかの 出力が得られます．断熱定理や熱力学の知見から，出力 が正解でなかったとしても，式（3）の値が小さくなるビッ ト列のほうが出力される確率が高い傾向をもっているこ とがわかります．これらの事実によって，D-Wave が理 想的な動きをしなかったとしても，ヒューリスティック に最適化問題を解く情報処理装置であると捉えることが できます．
11．ま と め
量子力学を使った情報処理と一言で言っても，複数の 計算モデルが存在します．しかし，普遍的量子計算であ れば計算モデルが異なっても，同等の能力をもっていま す．普遍的量子計算では因数分解を入力長に対して多項 式の時間で解くことができるため，いかなる計算モデル であれ，普遍的量子計算の実装ができれば理論的には大 きなインパクトを与えるでしょう．さらに，その装置は これまでの計算機を質的に上回る情報処理リソースであ るともいえるでしょう．ただ，「入力長に対して何乗の 計算時間なのか」や，「実際にどれくらいの速さで因数 分解ができるのか」という，より細かな議論をするため には，計算モデルを細かく指定したり，実装方法を検証 したりする必要があるでしょう． 現状では，量子力学を使った情報処理装置であると主 張しているのは D-Wave のみです．しかし残念ながら， この装置が理想的に動いたとしても，普遍的量子計算の 実装ではないでしょう．一方で，この機械が扱う問題 は，NP- 困難な問題であり，短い時間で適当な情報処理 をしても，何らかの正しそうな答を出力してくれるため， ヒューリスティックな情報処理をする機械として機能し ます．さらに，外部からの熱力学的なノイズの影響など の理想的状況からのずれは，まだ完全には理解されてお らず，理論的に予想される理想的な挙動のときよりも高 い能力をもっている可能性さえあります．そのため，こ の D-Wave 1 が解く（式（3）の値の最小値またはそれ 図 6 二次元格子に近いグラフに近い値を与える bjの列を求める）という問題に置き換 えることが容易な問題などを扱うときは，この機械が有 効に使える可能性が高いといえるでしょう． 普遍的量子計算の実装ができれば，インパクトがある ということから，今後もさまざまな計算モデルでの実装 装置の構築が試みられるでしょう．しかし，ここで言う インパクトとは，計算量的な議論からくる粗い議論であ り，実際に役に立つかどうかを知るには，実装された計 算モデルと実際に解きたい問題との親和性を判断するな ど，もう少し具体的な評価が必要となるでしょう． 謝 辞 塚田恭章氏，河野康泰人氏，谷誠一郎氏に適切な助言 をいただきましたことを，ここに感謝を申し上げます． また，高橋康博氏からは有用なご指摘をいただきました ことを，特に感謝申し上げます．
◇ 参 考 文 献 ◇
[Aaronson 05] Aaronson, S.: NP-complete problems and physical reality, ACM SIGACT News（March 2005）
[Barahona 82] Barahona, F.: On the computational complexity of Ising spin glass models, J. Phys. A: Math. Gen., Vol. 15, pp. 3241-3253（1982）
[Deutsch 85] Deutsch, D.: Quantum theory, the church-turing principle and the universal quantum computer, Proc. R. Soc.
Lond, A, Vol. 400, pp. 97-117（1985）
[Devitt 13] Devitt, S. J. Stephens, A. M. Munro, W. J. and Nemoto, K.: Requirements for fault-tolerant factoring on an atom optics quantum computer, Nat. Commun., Vol. 4, p. 2524（2013） [D-Wave] http://www.dwavesys.com/
[Messiah 72] Messiah, A. 著，小出昭一郎，田村二郎 訳：量子力学 3， 東京図書（1972）
[Nishimura 02] Nishimura, H. and Ozawa, M.: Computational complexity of uniform quantum circuit families and quantum Turing machines, Theor. Comput. Sci., Vol. 276, pp. 147-181 （2002）
[Nielsen 04] Nielsen, M. A. and I. L. Chuang 共著，木村達也 訳： 量子コンピュータと量子通信，Ⅰ・Ⅱ・Ⅲ，オーム社（2004） [Raussendorf 03] Raussendorf, R., Browne, D. E. and Briegel,
H. J.: Measurement-based quantum computation on cluster states, Phys. Rev., A, Vol. 022312（2003）；Raussendorf, R. Harrington, J. and Goyal, K.: A fault-tolerant one-way quantum computer, Ann. Phys., Vol. 321, pp. 2242-2270（2006） [Seki 98] Seki, Y. and Nishimori, H.: Quantum annealing in the transverse Ising model, Phys. Rev. E, Vol. 58, p. 5355（1998）； Farhi, E. Goldstone, J. Gutmann, S. J. Lapan, Lundgren, A. and Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem,
Science, Vol. 292, p. 472（2001）
[Shor 94] Shor, P. W.: Algorithms for quantum computation: Discrete logarithms and factoring, Proc. 35th FOCS, pp. 124-134（1994）
[van Dam 04] van Dam, W., Mosca, M. and Vazirani, U.: How powerful is adiabatic quantum computation?, Proc. 42nd
FOCS, p. 279-287（2001）；Aha ronov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S. and Regev, O.: Adiabatic quantum computation is equivalent to standard quantum computation,
Proc. 45th FOCS, pp. 42-51（2004）
[宇都宮 14] 宇都宮聖子：量子コンピュータの新潮流：量子アニー リングと D-Wave, 人工知能，Vol. 29, No. 2, pp. 190-194（2014） 2014年 3 月 25 日 受理 加藤 豪 NTTコミュニケーション科学基礎研究所，研究主任． 2004年東京大学大学院理学系研究科物理学専攻博士 課程修了．量子計算・量子暗号・量子通信などの量 子情報理論研究に従事．
