| 講演名 | 1994/4/27 万能量子Turing機械を用いたNP完全問題の多項式時間解法について 三原 孝志, 西野 哲朗, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では、重ね合わされた様相のなかの、特定の様相を観測することができると仮定すると、Deutschの万能量子Turing機械を用いて、NP-完全問題を多項式時間で解くことができることを示す。この仮定は、現在の物理学において広く支持されているものではないが、この仮定の是非は現時点では確定できない。実際、最近Aharonovらは、物理学における観測の全く新しい解釈を提案している。 |
| 抄録(英) | In this paper,we show that the Deutsch′s universal quantum Turin g machine can solve any NP-complete problem in polynomial time under a physical assumption that we can observe the existence of a specific physical state in a given superposition of physical states.This assumption is not widely supported in current physics, however,no one knows whether this assumption is valid or not.In fact,very recently,Aharonov et al.have proposed a quite new interpretation of the observation. |
| キーワード(和) | 量子Turing機械 / 物理状態 / 論理式充足可能性判定間題 / 観測 |
| キーワード(英) | quantum Turing machine / physical state / satisfiability problem / observation |
| 資料番号 | COMP94-5 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1994/4/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 万能量子Turing機械を用いたNP完全問題の多項式時間解法について |
| サブタイトル（和） | |
| タイトル（英） | On a Method to Solve NP-Complete Problems in Polynomial Time Using the Universal Quantum Turing Machine |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子Turing機械 / quantum Turing machine |
| キーワード(2)（和/英） | 物理状態 / physical state |
| キーワード(3)（和/英） | 論理式充足可能性判定間題 / satisfiability problem |
| キーワード(4)（和/英） | 観測 / observation |
| 第 1 著者 氏名（和/英） | 三原 孝志 / Takashi Mihara |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information of Science,Japan Advanced Institute of Science and Technology,Hokuriku |
| 第 2 著者 氏名（和/英） | 西野 哲朗 / Tetsuro Nishino |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学情報科学研究科 School of Information of Science,Japan Advanced Institute of Science and Technology,Hokuriku |
| 発表年月日 | 1994/4/27 |
| 資料番号 | COMP94-5 |
| 巻番号（vol） | vol.94 |
| 号番号（no） | 26 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |