物理的実現可能性に優れたNMR量子探索アルゴリズム

情報処理学会 Web Site 参考文献14件

書誌事項

タイトル別名
  • ブツリテキ ジツゲン カノウセイ ニ スグレタ NMR リョウシ タンサク アルゴリズム
  • A New Physically Realizable Quantum Search Algorithm
  • 計算理論

この論文をさがす

抄録

本論では，測定誤差がε< 1 であるNMR（Nuclear Magnetic Resonance）量子計算機（NMRQCと略記）上で動作する，新しい量子探索アルゴリズムを提案する．具体的には，解が複数個存在する探索問題に対する，新しいNMR量子探索アルゴリズムを提案する．探索問題の解空間のサイズをNとするとき，このアルゴリズムは，εN +min{n log 1ε} 回のオラクル呼び出しを行うことにより，成功確率1で解を発見する．通常の量子計算機上で成功確率1で解探索を行うためには，N回のオラクル呼び出しが必要であることが知られているので，提案アルゴリズムの方がより高速に動作する．そして，量子オラクルを作り替えることができるような問題に対しては，提案アルゴリズムの実行において必要となる量子ビット数を節約できることを示す．さらに，提案アルゴリズムは，量子重ね合わせ状態を維持しなければならない時間が短いので，物理的実現可能性が非常に高い．

In this paper, we propose a new quantum search algorithm on NMR (Nuclear Magnetic Resonance) quantum computers (NMRQCs for short) with the measurement accuracy ε < 1. That is, we propose a new NMR quantum search algorithm to solve search problems which have multiple solutions. Our algorithm can search one solution with certainty using εN + min{n, log 1ε } oracle calls, where N is the cardinality of the search space. Since, it is known that the ordinary quantum computer requires N oracle calls to solve the search problem with certainty, our NMR quantum search algorithm solves the problem more efficiently. Then, we show that our algorithm can be executed with small number of qubits for the problems where the quantum oracle can be reconstructed. Since, our algorithm requires short entanglement time, we can conclude that our algorithm is highly physically realizable.

収録刊行物

参考文献 (14)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

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

問題の指摘

ページトップへ