NMR量子計算によるNP完全問題と因数分解の解法

情報処理学会 Web Site 被引用文献1件 参考文献23件

書誌事項

タイトル別名
  • NMR リョウシ ケイサン ニ ヨル NP カンゼン モンダイ ト インスウ ブンカイ ノ カイホウ
  • Solving NP - Complete Problems and Factoring Problems by Using NMR Quantum Computation

この論文をさがす

抄録

1985年にDavid Deutschは，量子並列計算を実行できるuring機械として，量子uring機械（QTMと略す）を導入した．そして，1994年にPeter Shorが，QTMは任意に小さな誤り確率で，整数を多項式時間内に因数分解できることを示した．決定性uring機械は，整数を多項式時間内には因数分解できないと広く信じられているので，QTMは本質的に新しい計算モデルである可能性が高い．一方，多くの研究者が，QTMに基づく量子コンピュータを物理的に実現する方法について研究を進めている．なかでもNMR（核磁気共鳴）は，いくつかの理由から，量子コンピュータの実現方法として有望と考えられている．しかし，NMR上で実行される量子計算は，QTM上で実行される量子計算とは若干異なっている．たとえば，Shorの因数分解アルゴリズムは，そのままではNMR量子コンピュータ上では実行できない．本論では，最初にNMR 量子計算のモデルとして，Bulk量子uring機械（BQTMと略す）を定義する．そして，BQTMはNP完全問題のある種のインスタンスを効率良く解くことができ，また，整数を多項式時間内に因数分解できることを示す．

In 1985, David Deutsch introduced quantum uring machines (QTMs for short)as Turing machines which can perform so called quantum parallel computations. Then, in 1994, Peter Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. Since it is widely believed that any deterministic uring machines cannot factor integers in polynomial time, it is very likely that QTM is an essentially new model of computation. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor ’s factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we first define bulk quantum Turing machine (BQTM for short)as a model of the NMR quantum computation. Then, we show that BQTMs can solve certain instances of NP-complete problems efficiently, and can factor integers in polynomial time.

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (23)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ