著者

鈴野 聡志 増田 夏樹 大矢 雅則

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. IT, 情報理論 (ISSN:09135685)

巻号頁・発行日

vol.99, no.187, pp.49-54, 1999-07-16

---

量子コンピュータとは, 量子力学を動作原理とするコンピュータのことである. 現在のコンピュータに比べ, 量子状態の干渉性を用いて計算を高速にでき, 発熱を少なくできるなどの特徴を持ち, 次世代のコンピュータとして期待されている. ナップサック問題とはNP完全に属する問題で, 現在のコンピュータでは効率よく解くアルゴリズムは見つかっていない. 本論文では, 量子コンピュータが高速に計算できる証明とし, ナップサック問題の量子アルゴリズムを述べ, quピットを表現する重ね合わせ状態ができれば, ナップサック問題が多項式時間で解けることを示す.