[技術解説] 高速化の鍵は量子の「もつれ」や「重ね合わせ」ーー 量子コンピューターの原理を知る

記事をシェアする:

最先端の量子コンピュータ「IBM Q システム」が、従来のコンピューターの限界を超えた計算能力で新たな時代を切り拓く

* IBM Qはビジネスおよび科学アプリケーション向けの商用汎用量子コンピューティング・システムの構築に向けた業界初のイニシアチブです。詳しくは量子コンピューターに関するIBMの取り組み(US)をご覧ください。

量子コンピューターはなぜすごいのか

直近の量子コンピューターの有力な応用の一つは、物理学者のRichard Feynmanが示唆した物理系のシミュレーションです。特に量子系のシミュレーションの各ステップでは、考慮すべき系の状態数が爆発に増えるため、従来のコンピューターでは計算が困難です。一方、量子コンピューターの場合、シミュレーションする系の状態を量子ビットで表現できるため、複数の状態を量子ビットの重ね合わせで効率的に評価することができます。分子や化合物など新材料の発見や創薬においてこのようなシミュレーションが必要なケースが多くあります。

中長期的な応用としては最適化や機械学習があります。S.Jordan:Quantum Algorithm Zoo に300以上の量子アルゴリズムがリストアップされており、従来のコンピューターのアルゴリズムよりも、それらのほとんどの量子アルゴリズムの方が高速であることが証明されています。そのような高速化を可能にしたのは、量子コンピューター特有の「量子重ね合わせ」と「量子もつれ」の効果です。

超並列計算を可能にする「量子重ね合わせ」

量子コンピューターの原理を理解するためには、その最小の情報単位である1量子ビットと従来の1ビットの違いを理解する必要があります。1ビットは常に「0」か「1」のどちらかにしかなりませんが、1量子ビットは同時に「0」と「1」の両方にもなりえます。これがいわゆる量子重ね合わせです。ただし、「0」と「1」が重ね合わさった量子状態の量子ビットを観測することで、「0」か「1」のどちらかに収束します。つまり、私たちがその量子ビットを観測すると、そこから得られるのは従来の1ビットと同様、「0」か「1」のどちらかです。観測結果が100%の確率で「0」か「1」になる1量子ビットの量子状態を量子力学ではそれぞれ |0〉と |1〉とで表現します 。そして、「0」が確率 |a|² で、「1」が確率 |b|² で観測できる1量子ビットの量子状態は、a|0〉+b|1〉で表現します。 aとbは確率振幅と呼ばれる値で、一般的に複素数ですが説明を簡単にするために本稿ではaとbを−1と1の間の実数に限定します。その場合、|a|² と |b|² はそれぞれaとbの絶対値の自乗に相当し、その合計は100%の確率を表します。通常の確率は常に正であるため重ね合わせる 時に常に強め合うことしかできませんが、量子の確率振幅は正と負の値を取り得るため、量子状態を重ね合わせした時に強め合う効果以外にも、打ち消し合う効果も得られます。

ここで量子ビットの確率振幅と従来のビットの確率の違いを説明する例として、1量子ビットと1ビットを使ってマスを探索するロボットを考えてみます。探索ロボットは白黒のマスで作業すると仮定します。
まず従来のビットを用いる場合を紹介します。ロボットは自分がいるマスを記憶するために、白マスなら「0」、黒マスなら「1」というように1ビットを用いることにします。そして、時刻が1進むごとにロボットが今のマスにとどまって探索を続けるか、隣の黒マスに移動して探索するかをコイン投げの結果で決めるものとします。具体的には、コイン投げの結果が「表」なら今のマスにとどまり、「裏」なら異なる色のマスに移動することとします。コイン投げの確率が五分五分ならば、ロボットの初期時刻の位置によらず、次の時刻にロボットが白マスか黒マスにいる確率もやはり五分五分になります。この場合、ロボットの位置は50%の確率で「0」、50%の確率で「1」と書くことができます（図1）。

図1.コイン投げの結果に従って移動する探索ロボット
初期時刻は白マスにいたロボットは、次の時刻以降は白マスか黒マスかにいる確率はそれぞれ五分五分になるが、実際は各時刻にロボットは どちらかのマスにしか存在しない。

次に量子ビットを用いる場合を紹介します。ロボットは自分の位置が白マスか黒マスかを1量子ビットを用いて、白マスなら|0〉、黒マスなら|1〉、と表すことにします。次に、コイン投げを量子操作の一つであるアダマール変換に基づいて行うものとします。アダマール変換の詳細は割愛しますが、ロボットの現時刻の位置を表す状態が|0〉なら、次時刻の位置は確率振幅1/√2で|0〉にとどまり、または同じ確率振幅 1 /√2で |1〉に移動します 。 一方でロボットの現時刻の位置が|1〉なら、次の時刻の位置は確率振幅1/√2で|0〉に移り、確率振幅−1/√2で |1〉にとどまります。ロボットはどちらの位置にいても 次のマスの位置はそれぞれ確率50%（1/√2と−1/√2の確率振幅の絶対値の自乗がそれぞれ1/2）で従来のビットと同じですが、量子ビットの場合は現時刻の位置が|1〉の時、次時刻は負の確率振幅にとどまることに留意しながら、量子ビットを用いるロボットの位置の変化を図2で確認しましょう。

初期時刻にロボットは白マスにいて、1量子ビットの状態は|0〉です。次の時刻に量子コイン投げによりロボットの量子ビットは1/√2 |0〉+1/√2 |1〉に変化し、「0」か「1」はそれぞれ五分五分の確率で観測できるので、先ほどの従来のビットの時と同じです。ただし、量子ビットを観測しなければ、量子重ね合わせの効果によりロボットは白マスと黒マスのどちらにも同時に存在することになります。その次の時刻に再び量子コイン投げを行うと今度は従来のビットの場合とは異なる結果になり、ロボットの位置は初期値の白マスに戻ってしまいます。これは、白マスにいる状態|0〉が量子コイン投げによって1/ √2 |0〉+ 1/ √2 |1〉に変化して、黒マスにいる状態|1〉が量子コイン投げによって1/√2 |0〉− 1/√2 |1〉に変化するため、1/√2 |0〉+1/√2 |1〉の量子重ね合わせの状態からロボットが量子コイン投げを行うと、|0〉の確率振幅は直前のマスからの確率振幅が同じ符号のため増幅する一方で、|1〉の確率振幅は直前のマスからの確率振幅が異なる符号のため干渉で打ち消し合います（図2）。

図2.量子コイン投げの結果に従って移動する探索ロボット
初期時刻は白マスにいたロボットは、次の時刻に白マスと黒マスの両方に同時に存在するが、次時刻に確率振幅の干渉で必ず白マスに戻る。 以降はその繰り返しとなる。

従来のビットの場合、ロボットがどのマスにいるかは常に五分五分の確率ですが、量子ビットの場合は量子重ね合わせと確率振幅の干渉の効果で、ロボットは偶数ステップでは初期の白マスに、奇数ステップでは白黒の両方のマスに五分五分の確率で存在します。このように量子重ね合わせと確率振幅をうまく活用し、ある段階で複数の状態（例えば、計算の中で考慮しなければならない全可能性に相当する状態）を同時に調べて、適切な操作で次の段階でとある限られた状態（例えば、計算の結果に相当する状態）に収束できるのが特徴です。

従来の統計学で説明できない相関を作り出す「量子もつれ」

量子コンピューターのもう一つ特有な効果である量子もつれ（または、量子エンタングルメント）は、量子重ね合わせから目的の計算結果を引き出すために欠かせません。量子もつれは、複数の量子ビットで表せる量子状態がそれらを構成する個々の量子ビットの量子状態の単純な積で表せない時に存在します。例えば、量子もつれによって2量子ビットの量子状態が、2つの独立した1量子ビットの量子状態で表せない場合です。先ほどの探索ロボットを使って説明しましょう。 仮に黒マスに宝物があると仮定します。先ほどの例ではロボットは自分がいるマスの位置を1量子ビットで記憶していましたが、ロボットが宝物を発見したかどうかを記憶するために、さらに1量子ビットを使うこととします。なお、ロボットは宝物があるマスを探索した場合必ず宝物を発見できるものと仮定します。ロボットの状態はマスの位置と宝物の有無の2量子ビットで表すことができます。初期時刻に白マスにいるロボットの状態を |0〉|0〉と表します。第一量子ビット(左)が位置を、第二量子ビット(右)が宝物の有無を表します。次の時刻に量子コイン投げでロボットは移動し、ロボットが黒マスに移動した場合は宝物を発見します。その時のロボットの状態は1/√2 |0〉|0〉+1/√2 |1〉|1〉で、第一と第二の量子ビットの両方とも「0」か「1」が五分五分で観測されますが、もし量子ビットのどちらか一方の値が観測により決まると、もう一方の量子ビットの値も決まってしまう関係にあります。この場合、第一量子ビットと第二量子ビットの間に量子的な絡み合いができ、それを量子もつれと呼びます。

例えば、第二量子ビットのみに着目して観測を行う場合、第一量子ビットの値がその観測結果によって瞬時に変化します。つまり、観測する前にロボットの位置は白マスと黒マスにそれぞれ確率50%ずつありますが、第二量子ビットを観測したらロボットの位置は、観測の結果が宝有りなら黒マス、宝なしなら白マス、と100%確定します（図3）。量子コンピューターではこの量子もつれの効果が以下のようによく利用されます。第一量子レジスター(複数の量子ビットのまとまり)に計算結果の候補値を、第二量子レジスターにその計算結果が適切かどうかのフラグを割り当てます。この第二量子レジスターのフラグが適切と高い確率で観測できたら、第一レジスターからは対応する計算結果が得られ、量子重ね合わせで得られた多くの解候補から欲しい解をうまく取り出すことができます。

図3.量子コイン投げの結果に従って移動し、探索結果を記憶するロボットの様子
初期時刻は白マスにいたロボットは、量子重ね合わせで次の時刻に白マスと黒マスの両方に同時に存在するが、それぞれの位置での 宝の有無を記憶すれば、位置と探索結果の記憶の間に量子もつれが生じ、片方が観測で確定したらもう一方もそれに応じて確定する。

以上の量子重ね合わせと量子もつれの効果を活用する量子アルゴリズムは、一般に次のように実行します（図4）。まず、入力xから計算したい解をf(x)と仮定します。このf(x)を計算するための方法は複数ありますが、量子アルゴリズムでは全計算方法の組合せに対応する量子重ね合わせを前述したアダマール変換などで生成した後に、全ての計算方法に対して超並列に解となるf(x)を計算します。計算方法が適切であればf(x)は正しく得られますが、そうではない場合もあります（図4の「失敗」）。計算方法と計算結果、つまり、f(x)または失敗、との間に前述の量子もつれで相関を作った後に、確率振幅の干渉を利用して最終的に計算したい解f(x)のみを残します。

実際に従来のアルゴリズムを凌ぐ代表的な量子アルゴリズムのほとんどは、図4のような計算フローに従います。例えば、Shorの素因数分解ではアルゴリズムのキーとなる周期性の抽出に量子重ね合わせと量子もつれが有効で指数関数的な高速化に成功しました。またGroverの量子探索アルゴリズムは、量子重ね合わせと確率振幅の性質をうまく利用し、構造のない探索問題でも従来の探索アルゴリズムに比べて多項式関数的な高速化を実現しました。Shorの素因数分解と比べて高速化の効果は高くありませんが、その適用範囲は広く、数々の量子探索アルゴリズムの基礎となっています。

図4.入力xから解f(x)を計算する量子コンピューターの計算フローの代表例
問題の入力xから計算を開始し、量子重ね合わせで全計算方法を超並列に調べ、解f(x)か失敗かの仕分けの結果を量子もつれで計算方法と相関 を持たせる。その後、確率振幅の干渉を経て計算の結果を取り出す。高い確率で観測から解f(x)を得るには、量子重ね合わせと確率振幅の干渉の設計が重要になる。

例えば、著者の一人が京都大学のチームと発見した量子アルゴリズムは、Groverの量子探索を使い、N枚のコインの中にk枚だけ重さが異なるコインを量子的な天秤を約k1/4 回用いて発見します^*2。この量子アルゴリズムも図4の通りに実行されます。その他、特殊なモデルの下で線形等式を解く量子アルゴリズム^*3 も知られており、大規模なレコメンデーション・システム^*4 や機械学習など、その原理を応用したさまざまな手法が報告されています。また、最適化においては特定の条件下で半正定値計画（SDP）を高速化できる量子アルゴリズム^*5 も見つかっており、今後の人工知能と最適化を革新させる技術として量子コンピューターへの期待が高まりつつあります。

*2: K.Iwama，H.Nishimura，R.Raymond，and J.Teruyama:“Quantum Counterfeit Coin Problems”，International Symposium on Algorithms and Computation (ISAAC)，p.73-84 (2010) .
*3: A.W.Harrow，A.Hassidim，and S.Lloyd:“Quantum Algorithm for Solving Linear Systems of Equations”，Physical Review Letters 15(103):150502 (2009).
*4: I.Kerenidis and A.Prakash:“Quantum Recommendation Systems”, Innovations in Theoretical Computer Science (ITCS’17), 2017. arXiv:1603.08675 (2016).
*5: F.G.S.L.Brandao and K.Svore:“Quantum Speed-ups for Semidefinite Programming”, The 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2017. arXiv:1609.05537 (2016) .

量子コンピュータ技術解説まとめ
IBM Qが目指す「量子コンピューターがある近未来」
量子コンピューター「IBM Q」誕生の背景

ルディー・レイモンド Rudy Raymond

日本アイ・ビー・エム株式会社 東京基礎研究所 量子アルゴリズム&ソフトウェア リサーチ・スタッフ・メンバー
京都大学大学院情報学研究科の博士後期課程修了。博士(情報学)。博士論文は「量子質問計算量および量子ネットワーク符号に関する研究」。量子学習理論、および、量子計算量と量子通信量に関する論文と講演が多数。IBMで最適化、データ解析・機械学習を活用す るプロジェクトに参画し 、人工知能技術の応用に貢献 。2015年 日本オペレーションズ・リサーチ学会待ち行列研究部会論文賞を共同受賞。最近は動的ボルツマンマシンの研究にも従事。

今道 貴司 Takashi Imamichi

日本アイ・ビー・エム株式会社 東京基礎研究所 量子アルゴリズム&ソフトウェア リサーチ・スタッフ・メンバー
京都大学大学院情報学研究科数理工学専攻の博士後期課程修了。博士(情報学)。 2010年に日本IBM東京基礎研究所に入所して 、現在は組合せ最適化および機械学習の研究に従事。