量子計算モデル

量子計算は、古典的なビットを重ね合わせやエンタングルメントが可能な量子状態に置き換えることで、量子回路や複雑性クラスBQPといったモデルを定義します。これらのモデルは、一部の問題を古典的な方法よりも高速に解決できると考えられています。

Definition

量子計算のモデルは、量子ビットに保存された情報を処理します。量子ビットの状態は複素空間における単位ベクトルであり、計算は可逆な量子ゲートを適用して重ね合わせとエンタングルメントを生成し、最終的な測定によって量子状態によって確率が設定された古典的な結果が得られます。

Scope

このトピックでは、量子ビットと量子ゲート、量子回路モデルとその量子チューリングマシンとの等価性、効率的な量子計算の複雑性クラスBQPとその古典的クラスとの関係、ショアの因数分解アルゴリズムやグローバーの探索アルゴリズムといった基礎的なアルゴリズム、そしてモデルを定義する上での測定とデコヒーレンスの役割について扱います。

Core questions

• 重ね合わせとエンタングルメントは計算能力をどのように変えるのか？
• 効率的な量子クラスBQPと古典的クラスの関係は何か？
• どのような問題に対して量子アルゴリズムは証明可能または明らかな高速化をもたらすのか？
• 測定とクローン禁止の原理は量子計算をどのように制約するのか？

Key theories

量子回路モデルとBQP

効率的な量子計算は、普遍的なゲートセット上の多項式サイズの量子回路によって捉えられ、クラスBQPを定義します。BQPはPを含み、それを拡張すると考えられていますが、依然としてPSPACE内に位置するとされています。

量子高速化

ショアのアルゴリズムは整数を多項式時間で因数分解し、グローバーのアルゴリズムは非構造化空間を二次的な高速化で探索します。これらは特定のタスクにおける量子モデルの具体的な利点を示しています。

Clinical relevance

量子モデルは、量子ハードウェアとアルゴリズムの設計を導きます。ショアの因数分解アルゴリズムは、因数分解の困難性に基づいた公開鍵暗号システムを脅かし、ポスト量子暗号の開発を促しています。一方、量子シミュレーションは化学や材料科学における進歩を約束します。

History

ファインマンは1982年に量子システムを用いて物理学をシミュレートすることを提案し、ドイチュは1985年に量子チューリングマシンを形式化しました。ショアの1994年の因数分解アルゴリズムとグローバーの1996年の探索アルゴリズムは具体的な高速化を示し、量子計算を計算複雑性理論の主要な分野へと変え、実験的努力の原動力となりました。

Debates

量子優位性はどの程度大きく、大規模に物理的に実現可能か？

量子コンピュータは古典的なコンピュータと同じ関数を計算するため、問題は効率性です。BQPと古典的クラスの正確な関係は未解決であり、デコヒーレンスにもかかわらず大規模な耐障害性量子コンピュータを構築できるかどうかは、科学的および工学的な未解決の問題として残っています。

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

量子コンピュータは古典的なコンピュータができないことを計算できるのか？

いいえ。量子コンピュータは古典的なコンピュータと全く同じ種類の問題を解決します。違いは速度です。大きな数の因数分解のような特定の問題では、量子モデルは劇的に高速であるように見えますが、原理的に計算可能なものの境界を拡張するものではありません。

量子計算はなぜ暗号学にとって重要なのか？

ショアのアルゴリズムは、大規模な量子コンピュータが大きな整数を因数分解し、離散対数を効率的に計算することを可能にし、今日の通信の多くを保護している公開鍵システムを破る可能性があります。この見込みは、量子マシンにとっても困難であると考えられる問題に基づいたポスト量子スキームの探求を推進しています。