NMR量子計算によるNP完全問題と因数分解の解法(<特集>量子計算)

概要

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