量子加速
ナビゲーションに移動
検索に移動
量子加速（りょうしかそく、英語：Quantum Speedup）とは、実用的な問題を解くに当たって量子コンピュータが古典的コンピュータの計算速度を上回ること。
概要[編集]
量子コンピュータが古典的コンピュータを上回る効率で解いたアルゴリズムが、現実的な問題解決において有用であった場合に量子加速が認められる。 量子加速を実証できる可能性のある代表的なアルゴリズムには、
- ショアのアルゴリズム
- 素因数分解を行うためのアルゴリズム。1994年に数学者のピーター・ショア（Peter Williston Shor）が提唱[1]。
- グローバーのアルゴリズム
- 整頓されていないデータベースから目的の値を検索するアルゴリズム。1996年にロブ・グローバー（Lov Grover）が発見。
などがある。これらの他、ペル方程式も量子計算で効率化できるという噂もある。
なお、量子ビットのエラーを修正する「誤り訂正」を十分に行えない量子計算機では、解けるアルゴリズムの規模は小さくなり量子加速の実証が困難となる。そのため、エラーをカバーするために大量の量子ビットを用意したり、誤り耐性量子コンピュータを開発する必要がある。また、量子計算に特化した有用なアルゴリズムの発見も引き続き重要な課題である。
出典[編集]
- ↑ “Microsoft Quantumの研究者は、非構造化問題の最大の量子スピードアップを特定しました”. Microsoft (2020年5月4日). 2021年2月13日確認。