| 講演名 | 1997/11/8 組合せ的最適化問題を多項式時間で解く量子コンピュータについて 須鎗 弘樹, 上坂 吉則, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 1994年, Bell研のShorは公開鍵暗号の基礎である素因数分解を量子コンピュー夕上で多項式時間で解くことのできるアルゴリズムを発見した. この発見を機に, '80年代からFeynmanらが始めた量子コンピュータの概念が一躍脚光をあびることとなった. そして, 今日まで多くの研究者が「古典的な計算機では膨大な計算量を要する問題を量子コンピュータで解くと, どれほどその計算量が減少するか」という問題に挑んでいる. 本論文では, 組合せ的最適化問題をある条件の下で多項式時間で解くことのできる量子コンピュータ上のアルゴリズムを, 巡回セールスマン問題を例として提示する. |
| 抄録(英) | In 1994 Shor discovered an efficient algorithm for factoring huge integers, which can find the key to solve a cipher of public-key cryptosystem within polynomial time on a quantum computer. His discovery surprised many scientists, so that they have been trying to answer the following question :" What kind of problems call a quantum computer solve more efficiently than a classical one ? " In this paper an efficient algorithm is presented for solving a combinatorial optimization problem such as TSP within polynomial time on a quantum computer under a certain assumption. |
| キーワード(和) | 量子コンピュータ / 組合せ的最適化問題 / TSP / 多項式時間 |
| キーワード(英) | Quantum Computer / Combinatorial Optimization Problem / TSP / Polynomial Time |
| 資料番号 | NLP97-116 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 1997/11/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 組合せ的最適化問題を多項式時間で解く量子コンピュータについて |
| サブタイトル（和） | |
| タイトル（英） | On a Quantum Computation for Solving a Combinatorial Optimization Problem within Polynomial Time |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子コンピュータ / Quantum Computer |
| キーワード(2)（和/英） | 組合せ的最適化問題 / Combinatorial Optimization Problem |
| キーワード(3)（和/英） | TSP / TSP |
| キーワード(4)（和/英） | 多項式時間 / Polynomial Time |
| 第 1 著者 氏名（和/英） | 須鎗 弘樹 / Hiroki Suyari |
| 第 1 著者 所属（和/英） | 千葉大学 工学部 共通講座 Inter Department, Faculty of Engineering, Chiba University |
| 第 2 著者 氏名（和/英） | 上坂 吉則 / Yoshinori Uesaka |
| 第 2 著者 所属（和/英） | 東京理科大学 理工学部 情報科学科 Department of Information Sciences, Faculty of Science and Technology, Science University of Tokyo |
| 発表年月日 | 1997/11/8 |
| 資料番号 | NLP97-116 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 372 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |