万能量子Turing機械を用いたNP完全問題の多項式時間解法について
スポンサーリンク
概要
- 論文の詳細を見る
本論文では、重ね合わされた様相のなかの、特定の様相を観測することができると仮定すると、Deutschの万能量子Turing機械を用いて、NP-完全問題を多項式時間で解くことができることを示す。この仮定は、現在の物理学において広く支持されているものではないが、この仮定の是非は現時点では確定できない。実際、最近Aharonovらは、物理学における観測の全く新しい解釈を提案している。
- 1994-04-27
著者
-
西野 哲朗
北陸先端科学技術大学院大学情報科学研究科
-
西野 哲朗
電気通信大学電子情報学科
-
西野 哲朗
北陸先端科学技術大学院大学
-
三原 孝志
北陸先端科学技術大学院大学情報科学研究科
-
三原 孝志
九州東海大学工学部電子情報工学科
-
三原 孝志
北陸先端科学技術大学院大学
関連論文
- P=NP?問題の解決とNP完全問題の効率的解法に向けて
- 量子Turing機械によるNP完全問題の多項式時間解法について(計算量理論)
- 万能量子Turing機械を用いたNP完全問題の多項式時間解法について
- 量子コンピュータを用いたNP完全問題の多項式時間解法
- 量子コンピュータ
- 属性文法の複雑さ (<解説> 属性文法とその応用-IV)
- 連載「様々な角度から見たニューラルネットワークの将来像」の企画にあたって
- 属性文法の理論入門 ( 属性文法とその応用 I)
- 「属性文法とその応用」の連載開始にあたって
- EXACT学習 : 質問からの概念学習 (計算的学習理論とその応用)
- 廣瀬 健 著, "帰納的関数", 共立講座 現代の数学3, 共立出版, A5判, 214p., \3,600, 1989
- 井田哲雄 著, 計算機科学/ソフトウェア技術購座-2, "プログラミング言語の新潮流", 共立出版, A5判, \2,800, 1988
- 88-14 有向グラフに対するブラウザ
- 足立暁生 著, "計算基礎論", オーム社, A5判, 201P., \2,800, 1986
- 85-11 Prolog IIの論理的再構成
- ニューラルネットワークを用いたインド文字の特徴抽出について
- AuxPDAの同時計算量に対する一考察
- 第3回計算論的学習理論ワークショップ(ALT '92)報告
- 新企画「情報処理最前線」の連載開始にあたって
- 否定数限定回路の複雑さについて(計算量をめぐる基礎的研究)
- 否定数限定反転回路の複雑さの下界について(計算量理論)
- 否定数限定反転回路の複雑さについて
- On the complexity of negation-limited Boolean networks
- 量子コンピュータ
- Interpretations of the quantum theory and NP-complete problems
- Shor, P.W.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Proc.35th Annual Symp.on Foundations of Computer Science, pp.124-134 (1994).
- Walsh変換と効率的な量子アルゴリズム(量子情報理論とその応用)