EITC/QI/QIF Quantum Information Fundamentalsは、古典物理学ではなく量子物理学の法則に基づいており、古典物理学に比べて質的な利点を提供する、量子情報と量子計算の理論的および実用的側面に関するヨーロッパのIT認定プログラムです。
EITC/QI/QIF量子情報の基礎のカリキュラムは、量子力学の紹介(ダブルスリット実験と物質波干渉の考察を含む)、量子情報(キュービットとその幾何学的表現)の紹介、光分極、不確実性の原理、量子をカバーしていますエンタングルメント、EPRパラドックス、ベル不等式違反、ローカルリアリズムの放棄、量子情報処理(ユニタリー変換、シングルキュービットおよびXNUMXキュービットゲートを含む)、ノークローニング定理、量子テレポーテーション、量子測定、量子計算(マルチの紹介を含む) -量子ビットシステム、ゲートのユニバーサルファミリー、計算の可逆性)、量子アルゴリズム(量子フーリエ変換、Simonのアルゴリズム、拡張Churh-Turing論文、Shor'q量子因数分解アルゴリズム、Groverの量子検索アルゴリズムを含む)、量子観測可能物、Shrodingerの方程式、量子ビットの実装、量子複雑性理論、断熱量子計算イオン、BQP、スピンの概要、次の構造内で、このEITC認定の参照として包括的なビデオ教訓的なコンテンツを含みます。
量子情報は、量子システムの状態に関する情報です。 これは、量子情報理論の研究の基本的な実体であり、量子情報処理技術を使用して操作することができます。 量子情報とは、フォンノイマンエントロピーに関する技術的定義と一般的な計算用語の両方を指します。
量子情報と計算は、量子力学、コンピューターサイエンス、情報理論、哲学、暗号学などの分野を含む学際的な分野です。 その研究は、認知科学、心理学、神経科学などの分野にも関連しています。 その主な焦点は、微視的スケールで物質から情報を抽出することです。 科学における観察は、現実の基本的な特徴的な基準であり、情報を取得するための最も重要な方法のXNUMXつです。 したがって、観測を定量化するために測定が必要であり、科学的方法にとって非常に重要です。 量子力学では、不確定性原理により、一方の基底の固有状態が他方の基底の固有状態ではないため、非可換オブザーバブルを同時に正確に測定することはできません。 両方の変数が同時に明確に定義されていないため、量子状態に両方の変数に関する決定的な情報を含めることはできません。 量子力学における測定のこの基本的な特性のために、この理論は、完全に決定論的である古典力学とは対照的に、一般に非決定論的であると特徴付けることができます。 量子状態の非決定論は、量子システムの状態として定義される情報を特徴づけます。 数学的には、これらの状態は古典的なシステムの状態の重ね合わせ(線形結合)になります。
情報は常に物理システムの状態でエンコードされるため、それ自体が物理的です。 量子力学は微視的レベルで物質の特性を調べることを扱いますが、量子情報科学はそれらの特性から情報を抽出することに焦点を当て、量子計算は量子情報処理技術を使用して量子情報を操作および処理し、論理演算を実行します。
量子情報は、古典的な情報と同様に、コンピューターを使用して処理し、ある場所から別の場所に送信し、アルゴリズムで操作し、コンピューターサイエンスと数学で分析することができます。 古典的な情報の基本単位がビットであるのと同じように、量子情報はキュービットを扱います。キュービットは、0と1の重ね合わせで存在する可能性があります(同時にいくらか真と偽です)。 量子情報は、いわゆるエンタングル状態でも存在する可能性があります。これは、測定で純粋に非古典的な非局所相関を示し、量子テレポーテーションなどのアプリケーションを可能にします。 エンタングルメントのレベルは、量子情報の尺度でもあるフォンノイマンエントロピーを使用して測定できます。 最近、量子コンピューティングの分野は、現代の計算、通信、および暗号化を混乱させる可能性があるため、非常に活発な研究分野になっています。
量子情報の歴史は、古典物理学が量子物理学に革命を起こした20世紀の変わり目に始まりました。 古典物理学の理論は、紫外破綻や電子が原子核に渦巻くなどの不条理を予測していました。 最初、これらの問題は、古典物理学にアドホックな仮説を追加することによって取り除かれました。 やがて、これらの不条理を理解するために新しい理論を作らなければならないことが明らかになり、量子力学の理論が生まれました。
量子力学は、波動力学を使用してシュレーディンガーによって、行列力学を使用してハイゼンベルグによって定式化されました。 これらの方法の同等性は後で証明されました。 彼らの定式化は、微視的システムのダイナミクスを説明しましたが、測定プロセスを説明する上でいくつかの不十分な側面がありました。 フォンノイマンは、作用素環論を使用して、測定とダイナミクスを説明する方法で量子論を定式化しました。 これらの研究は、測定を介して情報を抽出するための定量的アプローチではなく、測定の哲学的側面を強調していました。
1960年代に、ストラトノビッチ、ヘルストローム、ゴードンは、量子力学を使用した光通信の定式化を提案しました。 これは、量子情報理論の最初の歴史的出現でした。 彼らは主に通信のエラー確率とチャネル容量を研究しました。 その後、Holevoは、量子チャネルを介した古典的なメッセージの送信における通信速度の上限を取得しました。
1970年代には、原子トラップや走査型トンネル顕微鏡など、単一原子の量子状態を操作する技術が開発され始め、単一原子を分離して配列することが可能になりました。 これらの開発以前は、単一の量子システムを正確に制御することは不可能であり、実験では、多数の量子システムをより粗く同時に制御することが利用されていました。 実行可能な単一状態操作技術の開発は、量子情報と計算の分野への関心の高まりにつながりました。
1980年代に、アインシュタインの相対性理論を反証するために量子効果を使用することが可能かどうかという関心が高まりました。 未知の量子状態を複製することが可能であれば、絡み合った量子状態を使用して光速よりも速く情報を送信することが可能であり、アインシュタインの理論を反証します。 しかし、複製不可能定理は、そのような複製が不可能であることを示しました。 この定理は、量子情報理論の最も初期の結果のXNUMXつでした。
暗号化からの開発
孤立した量子システムを研究し、相対性理論を回避する方法を見つけようとすることにすべての興奮と関心があるにもかかわらず、量子情報理論の研究は1980年代に停滞しました。 しかし、ほぼ同時に、別の手段が量子情報と計算に手を出し始めました。暗号化です。 一般的な意味で、暗号化は、相互に信頼できない可能性のあるXNUMXつ以上の関係者が関与する通信または計算を行う問題です。
ベネットとブラザードは、BB84量子暗号プロトコルを使用して長距離で密かに通信する方法である、検出されずに盗聴することは不可能な通信チャネルを開発しました。 重要なアイデアは、観測が観測を妨害する量子力学の基本原理の使用であり、安全な通信回線に盗聴者を導入すると、通信しようとするXNUMXつの当事者が盗聴者の存在をすぐに知ることができます。
コンピュータサイエンスと数学からの発展
アラン・チューリングのプログラム可能なコンピューターまたはチューリングマシンの革新的なアイデアの出現により、彼は、実際の計算をチューリングマシンを含む同等の計算に変換できることを示しました。 これはチャーチチューリングテーゼとして知られています。
すぐに、最初のコンピューターが製造され、コンピューターのハードウェアが非常に速いペースで成長したため、生産の経験を通じて、その成長はムーアの法則と呼ばれる経験的関係に体系化されました。 この「法則」は、集積回路内のトランジスタの数がXNUMX年ごとにXNUMX倍になるという予測的な傾向です。 表面積あたりの電力をより多くパックするためにトランジスタがますます小さくなり始めると、量子効果が電子機器に現れ始め、不注意な干渉を引き起こしました。 これは、アルゴリズムを設計するために量子力学を使用する量子コンピューティングの出現につながりました。
この時点で、量子コンピューターは、特定の問題について、従来のコンピューターよりもはるかに高速であるという見込みを示しました。 そのような問題の例の1994つは、Deutsch–Jozsaアルゴリズムとして知られるDavidDeutschとRichardJozsaによって開発されました。 ただし、この問題は、実用的なアプリケーションをほとんどまたはまったく保持していませんでした。 Peter Shorは、XNUMX年に、整数の素因数を見つけるという非常に重要で実用的な問題を思いつきました。 離散対数問題は、それが呼ばれたように、量子コンピューターでは効率的に解決できましたが、古典的なコンピューターでは解決できなかったため、量子コンピューターはチューリングマシンよりも強力であることを示しています。
情報理論からの発展
コンピュータサイエンスが革命を起こしていた頃、クロードシャノンを通じた情報理論とコミュニケーションも革命を起こしていました。 シャノンは、情報理論のXNUMXつの基本的な定理を開発しました。ノイズのないチャネルコーディング定理とノイズの多いチャネルコーディング定理です。 彼はまた、送信される情報を保護するためにエラー訂正コードを使用できることを示しました。
量子情報理論も同様の軌跡をたどり、1995年にベンシューマッハはキュービットを使用してシャノンのノイズのないコーディング定理に類似したものを作成しました。 エラー訂正の理論も開発されました。これにより、量子コンピューターはノイズに関係なく効率的な計算を行い、ノイズの多い量子チャネルを介して信頼性の高い通信を行うことができます。
量子ビットと情報理論
量子情報は、多くの印象的でなじみのない方法で、ビットに代表される古典的な情報とは大きく異なります。 古典的な情報の基本的な単位はビットですが、量子情報の最も基本的な単位はキュービットです。 古典的な情報はシャノンエントロピーを使用して測定されますが、量子力学的アナログはフォンノイマンエントロピーです。 量子力学システムの統計集団は、密度行列によって特徴付けられます。 古典的な情報理論における多くのエントロピー測定値は、Holevoエントロピーや条件付き量子エントロピーなどの量子の場合にも一般化できます。
古典的なデジタル状態(離散的)とは異なり、キュービットは連続値であり、ブロッホ球上の方向によって記述できます。 このように連続的に評価されているにもかかわらず、量子ビットは量子情報の可能な限り最小の単位であり、量子ビットの状態が連続的に評価されているにもかかわらず、値を正確に測定することは不可能です。 XNUMXつの有名な定理は、量子情報の操作の限界を説明しています。
- テレポーテーション禁止定理。これは、キュービットを(完全に)古典的なビットに変換できないことを示しています。 つまり、完全に「読み取る」ことはできません。
- 任意の量子ビットがコピーされるのを防ぐ量子複製不可能定理、
- 任意のキュービットが削除されるのを防ぐ、削除しない定理、
- ブロードキャストなしの定理。これは、任意のキュービットが複数の受信者に配信されるのを防ぎますが、場所から場所へ(たとえば、量子テレポーテーションを介して)転送することはできます。
- 量子情報の保存を実証する非表示の定理。これらの定理は、宇宙内の量子情報が保存されていることを証明し、量子情報処理に独自の可能性を開きます。
量子情報処理
キュービットの状態には、そのすべての情報が含まれています。 この状態は、ブロッホ球上のベクトルとして表現されることがよくあります。 この状態は、線形変換または量子ゲートを適用することで変更できます。 これらのユニタリ変換は、ブロッホ球上の回転として記述されます。 古典的なゲートはブール論理のよく知られた操作に対応しますが、量子ゲートは物理的なユニタリ作用素です。
量子システムの揮発性と状態のコピーが不可能なため、量子情報の保存は、古典的な情報の保存よりもはるかに困難です。 それでもなお、量子誤り訂正を使用することで、量子情報を原則として確実に保存することができます。 量子エラー訂正コードの存在は、フォールトトレラントな量子計算の可能性にもつながりました。
古典的なビットは、量子ゲートを使用して、キュービットの構成にエンコードし、その後取得することができます。 それ自体では、単一のキュービットは、その準備に関するアクセス可能な古典的な情報をXNUMXビットしか伝えることができません。 これがHolevoの定理です。 ただし、超高密度符号化では、送信者は、XNUMXつの絡み合った量子ビットのXNUMXつに作用することにより、それらの結合状態に関するXNUMXビットのアクセス可能な情報を受信者に伝達できます。
量子情報は、古典的な通信チャネルの概念と同様に、量子チャネル内で移動できます。 量子メッセージのサイズは有限で、キュービットで測定されます。 量子チャネルは、XNUMX秒あたりの量子ビットで測定される有限のチャネル容量を持っています。
量子情報、および量子情報の変化は、フォンノイマンエントロピーと呼ばれるシャノンエントロピーの類似物を使用して定量的に測定できます。
場合によっては、量子アルゴリズムを使用して、既知の従来のアルゴリズムよりも高速に計算を実行できます。 この最も有名な例は、指数以下の時間をとる最高の古典的なアルゴリズムと比較して、多項式時間で数値を因数分解できるショアのアルゴリズムです。 因数分解はRSA暗号化の安全性の重要な部分であるため、Shorのアルゴリズムは、量子コンピューターが使用されている場合でも安全な暗号化スキームを見つけようとするポスト量子暗号の新しい分野に火をつけました。 量子超越性を実証するアルゴリズムの他の例には、グローバーの検索アルゴリズムが含まれます。このアルゴリズムでは、量子アルゴリズムにより、可能な限り最高の古典的アルゴリズムよりもXNUMX次の速度が向上します。 量子コンピューターによって効率的に解決できる問題の複雑さのクラスは、BQPとして知られています。
量子鍵配送(QKD)を使用すると、従来の暗号化とは異なり、従来の情報を無条件に安全に送信できます。従来の暗号化は、実際には行われていなくても、原則として常に破られる可能性があります。 QKDの安全性に関する特定の微妙な点はまだ熱く議論されていることに注意してください。
上記のすべてのトピックと違いの研究は、量子情報理論を構成します。
量子力学との関係
量子力学は、微視的物理システムが自然界でどのように動的に変化するかを研究するものです。 量子情報理論の分野では、研究された量子システムは、現実世界の対応物から抽象化されています。 量子ビットは、たとえば、物理的には線形光量子コンピューターの光子、トラップ型イオン量子コンピューターのイオン、または超伝導量子コンピューターのように大量の原子の集まりである可能性があります。 物理的な実装に関係なく、量子情報理論によって暗示されるキュービットの限界と特徴は、これらすべてのシステムが複素数上の密度行列の同じ装置によって数学的に記述されるために成り立ちます。 量子力学とのもうXNUMXつの重要な違いは、量子力学は調和振動子などの無限次元システムを研究することが多いのに対し、量子情報理論は連続変数システムと有限次元システムの両方に関係していることです。
量子計算
量子コンピューティングは、重ね合わせ、干渉、エンタングルメントなどの量子状態の集合的な特性を利用して計算を実行する一種の計算です。 量子計算を実行するデバイスは、量子コンピューターとして知られています。:I-5現在の量子コンピューターは小さすぎて、実際のアプリケーションでは通常の(従来の)コンピューターよりも優れていますが、整数因数分解などの特定の計算問題を解決できると考えられています。 (RSA暗号化の基礎となる)、従来のコンピューターよりも大幅に高速です。 量子コンピューティングの研究は、量子情報科学のサブフィールドです。
量子コンピューティングは、物理学者のポールベニオフがチューリングマシンの量子力学モデルを提案した1980年に始まりました。 リチャード・ファインマンとユーリ・マニンは後に、量子コンピューターには、古典的なコンピューターでは実現不可能なことをシミュレートする可能性があることを示唆しました。 1994年、Peter Shorは、RSA暗号化通信を復号化する可能性のある整数を因数分解するための量子アルゴリズムを開発しました。 1998年、Isaac Chuang、Neil Gershenfeld、Mark Kubinecは、計算を実行できる最初の1990キュービット量子コンピューターを作成しました。 23年代後半から実験が進んでいるにもかかわらず、ほとんどの研究者は「フォールトトレラントな量子コンピューティングはまだかなり遠い夢である」と信じています。 近年、量子コンピューティング研究への投資は、公共部門と民間部門で増加しています。 2019年XNUMX月XNUMX日、Google AIは、米国航空宇宙局(NASA)と協力して、従来のコンピューターでは実行不可能な量子計算を実行したと主張しましたが、この主張が有効であったかどうかは、活発な研究。
量子コンピューター(量子コンピューティングシステムとも呼ばれます)には、量子回路モデル、量子チューリングマシン、断熱量子コンピューター、一方向量子コンピューター、さまざまな量子セルオートマトンなど、いくつかの種類があります。 最も広く使用されているモデルは、量子ビットまたは「キュービット」に基づく量子回路です。これは、古典的な計算のビットにいくぶん類似しています。 キュービットは、1または0の量子状態、または1と0の状態の重ね合わせになります。 ただし、測定される場合は常に0または1です。 どちらかの結果の確率は、測定直前のキュービットの量子状態に依存します。
物理量子コンピューターの構築に向けた取り組みは、高品質の量子ビットを作成することを目的とした、トランスモン、イオントラップ、トポロジカル量子コンピューターなどの技術に焦点を当てています。量子論理ゲート、量子アニーリング、または断熱量子計算のいずれか。 現在、有用な量子コンピューターを構築することには多くの重大な障害があります。 量子デコヒーレンスと状態の忠実度に悩まされているため、量子ビットの量子状態を維持することは特に困難です。 したがって、量子コンピュータにはエラー訂正が必要です。
古典的なコンピューターで解決できる計算問題は、量子コンピューターでも解決できます。 逆に、量子コンピューターで解決できる問題は、少なくとも原則として十分な時間があれば、古典的なコンピューターでも解決できます。 言い換えれば、量子コンピューターはチャーチチューリングの理論に従います。 これは、量子コンピューターが計算可能性の点で古典的なコンピューターに勝る追加の利点を提供しない一方で、特定の問題に対する量子アルゴリズムは、対応する既知の古典的なアルゴリズムよりも大幅に低い時間計算量を持っていることを意味します。 特に、量子コンピューターは、従来のコンピューターでは実行可能な時間内に解決できない特定の問題を迅速に解決できると考えられています。これは、「量子超越性」として知られる偉業です。 量子コンピューターに関する問題の計算の複雑さの研究は、量子複雑性理論として知られています。
量子計算の一般的なモデルは、量子論理ゲートのネットワークの観点から計算を説明します。 このモデルは、古典的な回路の抽象的な線形代数の一般化と考えることができます。 この回路モデルは量子力学に従うので、これらの回路を効率的に実行できる量子コンピューターは物理的に実現可能であると信じられています。
nビットの情報で構成されるメモリには2 ^ nの可能な状態があります。 したがって、すべてのメモリ状態を表すベクトルには、2 ^ n個のエントリがあります(状態ごとにXNUMXつ)。 このベクトルは確率ベクトルと見なされ、メモリが特定の状態で検出されるという事実を表します。
従来のビューでは、1つのエントリの値は100(つまり、この状態になる確率はXNUMX%)であり、他のすべてのエントリはゼロになります。
量子力学では、確率ベクトルを密度演算子に一般化することができます。 量子状態ベクトル形式は、概念的に単純であり、量子システム全体が知られている純粋な状態の密度行列形式の代わりに使用できるため、通常最初に導入されます。
量子計算は、量子論理ゲートと測定のネットワークとして説明できます。 ただし、測定は量子計算の最後まで延期できますが、この延期には計算コストがかかる可能性があるため、ほとんどの量子回路は、量子論理ゲートのみで構成され、測定を行わないネットワークを表します。
任意の量子計算(つまり、上記の形式では、nキュービット上の任意のユニタリ行列)は、かなり小さなゲートファミリーからの量子論理ゲートのネットワークとして表すことができます。 このような回路を実行できるコンピューターはユニバーサル量子コンピューターであるため、この構造を可能にするゲートファミリーの選択はユニバーサルゲートセットとして知られています。 そのような一般的なセットのXNUMXつには、すべての単一量子ビットゲートと上からのCNOTゲートが含まれます。 これは、CNOTゲートと一緒に単一キュービットゲートのシーケンスを実行することにより、任意の量子計算を実行できることを意味します。 このゲートセットは無限ですが、Solovay-Kitaevの定理に訴えることで、有限のゲートセットに置き換えることができます。
量子アルゴリズム
量子断熱アルゴリズムのような例外は存在しますが、量子アルゴリズムの発見の進歩は通常、この量子回路モデルに焦点を合わせています。 量子アルゴリズムは、対応する従来のアルゴリズムよりも高速化のタイプによって大まかに分類できます。
最もよく知られている古典的なアルゴリズムよりも多項式のスピードアップ以上のものを提供する量子アルゴリズムには、因数分解のためのショアのアルゴリズムと、離散対数の計算、ペル方程式の解法、より一般的にはアベリア有限群の隠れたサブグループ問題の解法のための関連する量子アルゴリズムが含まれます。 これらのアルゴリズムは、量子フーリエ変換のプリミティブに依存します。 可能性は低いと考えられますが、同等に高速な古典的アルゴリズムを発見できないことを示す数学的証明は見つかりませんでした。は量子クエリモデルにあります。これは制限付きモデルであり、下限を証明するのがはるかに簡単であり、必ずしも実際の問題のスピードアップにつながるとは限りません。
化学および固体物理学からの量子物理プロセスのシミュレーション、特定のジョーンズ多項式の近似、線形方程式系の量子アルゴリズムなどの他の問題には、超多項式の高速化をもたらすように見える量子アルゴリズムがあり、BQPが完全です。 これらの問題はBQPで完全であるため、同様に高速な古典的アルゴリズムは、量子アルゴリズムが超多項式の高速化をもたらさないことを意味しますが、これはありそうもないと考えられています。
グローバーのアルゴリズムや振幅増幅などの一部の量子アルゴリズムは、対応する従来のアルゴリズムよりも多項式の高速化を実現します。 これらのアルゴリズムは、比較的控えめなXNUMX次高速化を提供しますが、広く適用できるため、さまざまな問題の高速化を実現します。 クエリ問題の証明可能な量子高速化の多くの例は、グローバーのアルゴリズムに関連しています。これには、グローバーのアルゴリズムを使用する、XNUMX対XNUMXの関数で衝突を見つけるためのBrassard、Høyer、Tappのアルゴリズム、NANDを評価するためのFarhi、Goldstone、Gutmannのアルゴリズムが含まれます。木、これは探索問題の変形です。
暗号化アプリケーション
量子計算の注目すべきアプリケーションは、現在使用されている暗号システムへの攻撃です。 公開鍵暗号システムのセキュリティを支える素因数分解は、それらが少数の素数の積(たとえば、300つのXNUMX桁の素数の積)である場合、大きな整数の通常のコンピューターでは計算上実行不可能であると考えられています。 比較すると、量子コンピューターは、ショアのアルゴリズムを使用してこの問題を効率的に解決し、その要因を見つけることができます。 この機能により、問題を解決するための多項式時間(整数の桁数)アルゴリズムがあるという意味で、量子コンピューターは現在使用されている暗号化システムの多くを破ることができます。 特に、一般的な公開鍵暗号のほとんどは、整数の因数分解の難しさや離散対数の問題に基づいており、どちらもショアのアルゴリズムで解決できます。 特に、RSA、Diffie–Hellman、および楕円曲線Diffie–Hellmanアルゴリズムが壊れている可能性があります。 これらは、安全なWebページ、暗号化された電子メール、およびその他の多くの種類のデータを保護するために使用されます。 これらを破ると、電子のプライバシーとセキュリティに重大な影響があります。
量子アルゴリズムに対して安全である可能性のある暗号システムを特定することは、ポスト量子暗号の分野で活発に研究されているトピックです。 一部の公開鍵アルゴリズムは、コーディング理論の問題に基づくマックエリス暗号システムのように、Shorのアルゴリズムが適用される整数因数分解と離散対数の問題以外の問題に基づいています。 格子ベースの暗号システムが量子コンピューターによって破壊されることも知られておらず、多くの格子ベースの暗号システムを破壊する二面体の隠れたサブグループ問題を解くための多項式時間アルゴリズムを見つけることは、よく研究された未解決の問題です。 強引に対称(秘密鍵)アルゴリズムを破るためにGroverのアルゴリズムを適用するには、従来の場合の約2nと比較して、基礎となる暗号化アルゴリズムの約2n/2の呼び出しに等しい時間が必要であることが証明されています。つまり、対称鍵の長さは効果的に半分:AES-256は、Groverのアルゴリズムを使用した攻撃に対して、AES-128が従来のブルートフォース検索に対して持っているのと同じセキュリティを備えています(キーサイズを参照)。
量子暗号は、公開鍵暗号の機能の一部を実行できる可能性があります。 したがって、量子ベースの暗号化システムは、量子ハッキングに対して従来のシステムよりも安全である可能性があります。
検索の問題
多項式量子高速化を認める問題の最もよく知られている例は、データベース内のn個のアイテムのリストからマークされたアイテムを見つける非構造化検索です。 これは、データベースへのO(sqrt(n))クエリを使用するグローバーのアルゴリズムによって解決できます。これは、従来のアルゴリズムに必要なOmega(n)クエリよりもXNUMX次関数的に少なくなります。 この場合、利点は証明可能であるだけでなく、最適でもあります。グローバーのアルゴリズムは、任意の数のOracleルックアップで目的の要素を見つける可能性が最大になることが示されています。
グローバーのアルゴリズムで対処できる問題には、次の特性があります。
- 可能な回答のコレクションには検索可能な構造はありません。
- チェックする可能性のある回答の数は、アルゴリズムへの入力の数と同じであり、
- 各入力を評価し、それが正解であるかどうかを判断するブール関数が存在します
これらすべての特性に関する問題の場合、量子コンピューターでのグローバーのアルゴリズムの実行時間は、従来のアルゴリズムの線形スケーリングとは対照的に、入力(またはデータベース内の要素)の数の平方根としてスケーリングされます。 グローバーのアルゴリズムを適用できる問題の一般的なクラスは、ブール充足可能性問題であり、アルゴリズムが反復するデータベースは、考えられるすべての回答のデータベースです。 これの例と(可能な)アプリケーションは、パスワードを推測しようとするパスワードクラッカーです。 Triple DESやAESなどの対称暗号は、この種の攻撃に対して特に脆弱です。[要出典]この量子コンピューティングのアプリケーションは、政府機関の大きな関心事です。
量子システムのシミュレーション
化学とナノテクノロジーは量子システムの理解に依存しており、そのようなシステムを古典的に効率的な方法でシミュレートすることは不可能であるため、多くの人が量子シミュレーションが量子コンピューティングの最も重要なアプリケーションの2つになると信じています。 量子シミュレーションは、衝突型加速器内の反応などの異常な条件での原子や粒子の挙動をシミュレートするためにも使用できます。 量子シミュレーションは、二重スリット実験で重ね合わせた粒子とプロトンの将来の経路を予測するために使用される可能性があります。[引用が必要]年間世界エネルギー出力の約XNUMX%は、農業におけるハーバープロセス用のアンモニアを生成するための窒素固定に使用されます肥料産業では、天然に存在する生物もアンモニアを生成します。 量子シミュレーションは、このプロセスが生産を増加させることを理解するために使用される可能性があります。
量子アニーリングと断熱最適化
量子アニーリングまたは断熱量子計算は、断熱定理に基づいて計算を行います。 システムは、単純なハミルトニアンの基底状態に置かれます。これは、基底状態が問題の問題の解決策を表す、より複雑なハミルトニアンにゆっくりと進化します。 断熱定理は、進化が十分に遅い場合、システムはプロセス全体を通して常に基底状態にとどまると述べています。
機械学習
量子コンピューターは、従来のコンピューターでは効率的に生成できない出力を生成でき、量子計算は基本的に線形代数的であるため、機械学習タスクを高速化できる量子アルゴリズムの開発に希望を表明する人もいます。 たとえば、線形方程式システムの量子アルゴリズム、またはその発見者であるハシディズム、ハシディズム、ロイドにちなんで名付けられた「HHLアルゴリズム」は、古典的な対応物よりも高速化すると考えられています。 最近、いくつかの研究グループが、ボルツマンマシンとディープニューラルネットワークをトレーニングするための量子アニーリングハードウェアの使用を検討しました。
計算生物学
計算生物学の分野では、量子コンピューティングは多くの生物学的問題を解決する上で大きな役割を果たしてきました。 よく知られている例のXNUMXつは、コンピューティングゲノミクスと、コンピューティングによってヒトゲノムのシーケンスにかかる時間が大幅に短縮されたことです。 計算生物学が一般的なデータモデリングとストレージをどのように使用しているかを考えると、計算生物学へのその応用も同様に生じると予想されます。
コンピューター支援ドラッグデザインとジェネレーティブケミストリー
深層生成化学モデルは、創薬を促進するための強力なツールとして登場します。 しかし、すべての可能な薬物のような分子の構造空間の巨大なサイズと複雑さは重大な障害を引き起こし、それは将来量子コンピューターによって克服される可能性があります。 量子コンピューターは、複雑な量子多体問題を解決するのに自然に適しているため、量子化学を含むアプリケーションに役立つ可能性があります。 したがって、量子GANを含む量子強化生成モデルは、最終的には究極の生成化学アルゴリズムに発展する可能性があると期待できます。 量子コンピューターと量子変分オートエンコーダーなどの深い古典的ネットワークを組み合わせたハイブリッドアーキテクチャーは、すでに市販のアニーラーでトレーニングでき、新しい薬物のような分子構造を生成するために使用できます。
物理量子コンピューターの開発
課題
大規模な量子コンピューターの構築には、多くの技術的な課題があります。 物理学者のDavidDiVincenzoは、実用的な量子コンピューターの次の要件をリストしています。
- 量子ビットの数を増やすために物理的にスケーラブルであり、
- 任意の値に初期化できる量子ビット、
- デコヒーレンス時間よりも速い量子ゲート、
- ユニバーサルゲートセット、
- 読みやすい量子ビット。
量子コンピューターの部品の調達も非常に困難です。 グーグルやIBMによって構築されたもののような多くの量子コンピューターは、核研究の副産物であるヘリウム3と、日本企業であるCoaxCoによってのみ製造された特別な超電導ケーブルを必要とします。
マルチキュービットシステムの制御には、厳密で決定論的なタイミング分解能を備えた多数の電気信号の生成と調整が必要です。 これは、量子ビットとのインターフェースを可能にする量子コントローラーの開発につながりました。 増え続けるキュービットをサポートするためにこれらのシステムをスケーリングすることは、追加の課題です。
量子デコヒーレンス
量子コンピューターの構築に伴う最大の課題の2つは、量子デコヒーレンスの制御または除去です。 これは通常、外部世界との相互作用によってシステムがデコヒーレンスを引き起こすため、システムをその環境から分離することを意味します。 ただし、他のデコヒーレンスの原因も存在します。 例としては、量子ゲート、量子ビットの実装に使用される物理システムの格子振動とバックグラウンド熱核スピンがあります。 デコヒーレンスは事実上単一ではないため不可逆的であり、回避しない場合でも通常は高度に制御する必要があります。 特に候補システムのデコヒーレンス時間、横緩和時間T20(NMRおよびMRI技術の場合、ディフェージング時間とも呼ばれます)は、通常、低温でナノ秒から秒の範囲です。 現在、一部の量子コンピューターでは、大幅なデコヒーレンスを防ぐために、キュービットを2020ミリケルビンに冷却する必要があります(通常は希釈冷凍機を使用)。 XNUMX年の研究では、宇宙線などの電離放射線は、それにもかかわらず、特定のシステムを数ミリ秒以内にデコヒーレンスさせる可能性があると主張しています。
その結果、キュービットの状態を十分に長く維持すると、最終的に重ね合わせが破損するため、時間のかかるタスクによって一部の量子アルゴリズムが動作しなくなる可能性があります。
これらの問題は、タイムスケールが桁違いに短く、それらを克服するためによく引用されるアプローチが光パルス整形であるため、光学的アプローチではより困難です。 エラー率は通常、デコヒーレンス時間に対する動作時間の比率に比例するため、どの動作もデコヒーレンス時間よりもはるかに速く完了する必要があります。
量子しきい値定理で説明されているように、エラー率が十分に小さければ、量子エラー訂正を使用してエラーとデコヒーレンスを抑制することが可能であると考えられます。 これにより、エラー訂正スキームがデコヒーレンスによってエラーが発生するよりも速くエラーを訂正できる場合、合計計算時間はデコヒーレンス時間より長くなります。 フォールトトレラント計算に必要な各ゲートのエラー率についてよく引用される数値は、ノイズが脱分極していると仮定すると10-3です。
このスケーラビリティ条件を満たすことは、さまざまなシステムで可能です。 ただし、エラー訂正を使用すると、必要なキュービットの数が大幅に増加するというコストが発生します。 ショアのアルゴリズムを使用して整数を因数分解するために必要な数は、依然として多項式であり、LとL2の間にあると考えられます。ここで、Lは因数分解される数の桁数です。 エラー訂正アルゴリズムは、この数値をLの追加係数で膨らませます。1000ビットの数値の場合、これは、エラー訂正なしで約104ビットが必要であることを意味します。 エラー訂正を使用すると、数値は約107ビットに上昇します。 計算時間は約L2または約107ステップで、1MHzでは約10秒です。
安定性-デコヒーレンス問題への非常に異なるアプローチは、エニオン、スレッドとして使用される準粒子、および安定した論理ゲートを形成するためのブレード理論に依存するトポロジカル量子コンピューターを作成することです。
量子至上主義
量子超越性は、ジョン・プレスキルによって造られた用語であり、プログラム可能な量子デバイスが最先端の古典的なコンピューターの能力を超えた問題を解決できることを実証する工学的偉業を指します。 この問題は有用である必要はないので、量子超越性テストを潜在的な将来のベンチマークとしてのみ見ている人もいます。
2019年3,000,000月、Google AI Quantumは、NASAの支援を受けて、Sycamore量子コンピューターで計算を実行することで量子超越性を達成したと主張する最初の人物となりました。コンピューター。 その後、この主張に異議が唱えられました。IBMは、Summitは主張よりもはるかに高速にサンプルを実行できると述べており、研究者は量子超越性を主張するために使用されるサンプリング問題に対してより優れたアルゴリズムを開発し、Sycamoreと古典的なスーパーコンピューター。
2020年76月、USTCのグループは、量子超越性を実証するために、フォトニック量子コンピューターJiuzhangを使用して600個の光子に一種のボソンサンプリングを実装しました。 著者らは、古典的な現代のスーパーコンピューターは、量子プロセッサーが20秒で生成できるサンプル数を生成するために16億年の計算時間を必要とするだろうと主張しています。 2021年127月XNUMX日、量子コンピューティングサミットで、IBMはIBMEagleという名前のXNUMXキュービットマイクロプロセッサを発表しました。
物理的な実装
量子コンピューターを物理的に実装するために、その中で多くの異なる候補が追求されています(キュービットを実現するために使用される物理システムによって区別されます):
- 超伝導量子コンピューティング(小さな超伝導回路、ジョセフソン接合の状態によって実装されたキュービット)
- トラップ型イオン量子コンピューター(トラップ型イオンの内部状態によって実装されるキュービット)
- 光格子の中性原子(光格子に閉じ込められた中性原子の内部状態によって実装されるキュービット)
- 量子ドットコンピューター、スピンベース(例:Loss-DiVincenzo量子コンピューター)(トラップされた電子のスピン状態によって与えられるキュービット)
- 量子ドットコンピュータ、空間ベース(二重量子ドットの電子位置によって与えられるキュービット)
- 設計された量子井戸を使用した量子コンピューティング。これにより、原則として、室温で動作する量子コンピューターの構築が可能になります。
- 結合量子細線(量子ポイントコンタクトによって結合された量子細線のペアによって実装されたキュービット)
- 溶液中の分子の核磁気共鳴で実装された核磁気共鳴量子コンピューター(NMRQC)。ここで、キュービットは、溶解した分子内の核スピンによって提供され、電波でプローブされます。
- 固体NMRケイン量子コンピューター(シリコン中のリン供与体の核スピン状態によって実現されるキュービット)
- 電子オンヘリウム量子コンピューター(キュービットは電子スピン)
- 空洞量子電気力学(CQED)(高フィネス空洞に結合されたトラップされた原子の内部状態によって提供されるキュービット)
- 分子磁石(スピン状態によって与えられるキュービット)
- フラーレンベースのESR量子コンピューター(フラーレンに包まれた原子または分子の電子スピンに基づくキュービット)
- 非線形光学量子コンピューター(線形要素と非線形要素の両方を介して光のさまざまなモードの状態を処理することによって実現されるキュービット)
- 線形光量子コンピューター(ミラー、ビームスプリッター、位相シフターなどの線形要素を介してさまざまなモードの光の状態を処理することによって実現されるキュービット)
- ダイヤモンドベースの量子コンピューター(ダイヤモンドの窒素空孔中心の電子または核スピンによって実現されるキュービット)
- ボーズ・アインシュタイン凝縮ベースの量子コンピューター
- トランジスタベースの量子コンピューター–静電トラップを使用したポジティブホールのエントレインメントを備えたストリング量子コンピューター
- 希土類金属イオンをドープした無機結晶ベースの量子コンピューター(光ファイバー内のドーパントの内部電子状態によって実現されるキュービット)
- 金属のようなカーボンナノスフェアベースの量子コンピューター
- 多数の候補者は、急速な進歩にもかかわらず、量子コンピューティングはまだ揺籃期にあることを示しています。
計算が分解される基本的な要素によって区別される多くの量子計算モデルがあります。 実際の実装では、関連するXNUMXつの計算モデルは次のとおりです。
- 量子ゲートアレイ(計算は数キュービットの量子ゲートのシーケンスに分解されます)
- 一方向量子コンピューター(高度に絡み合った初期状態またはクラスター状態に適用される一連のXNUMXキュービット測定に分解された計算)
- 量子アニーリングに基づく断熱量子コンピューター(計算は、最初のハミルトニアンから最後のハミルトニアンへのゆっくりとした連続変換に分解され、その基底状態には解が含まれます)
- トポロジカル量子コンピューター(2D格子内のエニオンの編組に分解された計算)
量子チューリングマシンは理論的には重要ですが、このモデルの物理的な実装は実現可能ではありません。 XNUMXつの計算モデルはすべて同等であることが示されています。 それぞれが、多項式のオーバーヘッドを超えずに他方をシミュレートできます。
認定カリキュラムについて詳しく知るために、以下の表を展開して分析することができます。
EITC/QI/QIF Quantum Information Fundamentals Certification Curriculum は、ビデオ形式のオープンアクセス教材を参照しています。 学習プロセスは、関連するカリキュラム部分をカバーする段階的な構造 (プログラム -> レッスン -> トピック) に分かれています。 ドメインの専門家による無制限のコンサルティングも提供されます。
認定手続きの確認について詳しくは 仕組み.
主な講義ノート
U.ヴァジラーニ講義ノート:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
補足講義ノート
L. Jacaketal。 講義ノート(補足資料付き):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
主な教科書
量子計算と量子情報の教科書(ニールセン、チュアン):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
追加の講義ノート
J.プレスキル講義ノート:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
A.チャイルズレクチャーノート:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
S.アーロンソンの講義ノート:
https://scottaaronson.blog/?p=3943
R. de Wolf講義ノート:
https://arxiv.org/abs/1907.09415
その他のおすすめ教科書
古典的および量子計算(キタエフ、シェン、ヴィアリー)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
デモクリトス以来の量子コンピューティング(アーロンソン)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
量子情報の理論(Watrous)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
量子情報理論(ウィルド)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
EITC/QI/QIF 量子情報基礎プログラムの完全なオフライン自己学習準備資料を PDF ファイルでダウンロード