量子ウォークによる高速探索

DOI Web Site

書誌事項

タイトル別名
  • Fast Search with Quantum Walks
  • リョウシ ウォーク ニ ヨル コウソク タンサク

この論文をさがす

抄録

<p>近年，量子アニーリング型量子コンピュータ・量子ゲート型量子コンピュータの商用化を始めとして量子コンピューティングへの関心が高まっている．それらの量子コンピュータ上で動作する高速探索アルゴリズムを実現するための方法の一つが量子ウォークである．量子ウォークは，量子ゲートを用いた計算モデルとの対応が明らかになっているモデルである．</p><p>量子コンピュータ上で動作する高速探索アルゴリズムとして，最もよく知られているものはグローヴァーのアルゴリズムである．このアルゴリズムは，N枚のカードのうちマークされた1枚のカードを見つける問題を対象とする．N枚のカードそれぞれに対応する量子状態の一様な重ね合せ状態を初期状態とし，次の二つの操作に対応するユニタリ行列を繰り返し作用させることで探索を行う．一つ目の操作は，マークされたカードに対応する確率振幅の符号を反転し，その他のカードの確率振幅を保つユニタリ行列変換，二つ目は確率振幅を一様に拡散させるユニタリ変換である．これら一連の操作により，通常の探索アルゴリズムではO（N）の計算時間を要するのに対し，O(√N) の試行回数で高確率にマークされたカードを探し出すことができる．</p><p>以上のアルゴリズムは，「N枚のカード」をグラフの「N個の頂点」に置き換えて考えることで，グラフ（ネットワーク）上の探索問題と見なすことができる．グローヴァーのアルゴリズムは，グラフ（ネットワーク）上の探索問題としては完全グラフ（全ての頂点対が辺で結ばれているグラフ）上の探索に対応している．そのため，探索アルゴリズムとしての汎用性を持たせるために，一般のグラフ上で高速探索可能なアルゴリズムが望まれる．このようなアルゴリズムを実現するための一つの方法として注目されているモデルが量子ウォークである．</p><p>離散時間量子ウォーク（DTQW）では，グラフ中のマークされた頂点に対応する確率振幅の符号を反転し，その他のカードの確率振幅はそのままにする役割を持つユニタリ行列と，確率振幅を一様に拡散させる役割を持つユニタリ行列の積で定義されるユニタリ行列を用いて，グローヴァーのアルゴリズムに対応する探索を行う．これにより，O(√N) の試行回数で高確率にマークされた頂点を探し出す．DTQWによる一連の時間発展がグラフの辺上のダイナミクスとして定義されるのに対して，連続時間量子ウォーク（CTQW）では，同様の役割を持つユニタリ行列を頂点上のダイナミクスとして実現可能である．</p><p>探索アルゴリズムの基礎となる量子ウォークは，ランダムウォークの量子版とみなせるモデルの一つであり，量子計算の基本的モデルとして近年注目を集めている．量子ウォークの理論的側面としてよく議論される性質は強い拡散性と局在化の共存であり，通常のランダムウォークと大きく異なる性質であるために種々のグラフ上での理論的検討が精力的に進められている．また，数理モデルとしての興味だけに留まらず，例えば，放射性廃棄物分離への応用可能性・トポロジカル絶縁体との対応が明らかになるなど，理論・実験を問わず，研究の裾野を広げている．さらに，物理的な実現についても捕捉イオン（trapped ion）や光子を用いる方法等により活発に行われている．</p>

収録刊行物

  • 日本物理学会誌

    日本物理学会誌 74 (10), 682-690, 2019-10-05

    一般社団法人 日本物理学会

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ