- 著者
-
鈴野 聡志
増田 夏樹
大矢 雅則
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. IT, 情報理論 (ISSN:09135685)
- 巻号頁・発行日
- vol.99, no.187, pp.49-54, 1999-07-16
量子コンピュータとは, 量子力学を動作原理とするコンピュータのことである. 現在のコンピュータに比べ, 量子状態の干渉性を用いて計算を高速にでき, 発熱を少なくできるなどの特徴を持ち, 次世代のコンピュータとして期待されている. ナップサック問題とはNP完全に属する問題で, 現在のコンピュータでは効率よく解くアルゴリズムは見つかっていない. 本論文では, 量子コンピュータが高速に計算できる証明とし, ナップサック問題の量子アルゴリズムを述べ, quピットを表現する重ね合わせ状態ができれば, ナップサック問題が多項式時間で解けることを示す.