量子コンピューティング

量子コンピュータは量子力学的現象を利用するコンピュータです。小規模では、物質は粒子と波の両方の特性を示し、量子コンピューティングは特殊なハードウェアを使用してこの動作を活用します。古典物理学ではこれらの量子デバイスの動作を説明できませんが、スケーラブルな量子コンピュータは、現代の「古典的な」コンピュータよりも指数関数的に高速に計算を実行できます^。理論上、大規模な量子コンピュータは、広く使用されている暗号化方式を破り、物理学者が物理シミュレーションを実行するのに役立ちます。ただし、現在の最先端技術は主に実験的で非実用的であり、有用なアプリケーションにはいくつかの障害があります。

量子コンピューティングにおける情報の基本単位である量子ビット(または「量子ビット」) は、従来のコンピューティングにおけるビットと同じ機能を果たします。ただし、2 つの状態 (バイナリ) のいずれかを取ることができる従来のビットとは異なり、量子ビットは2 つの「基本」状態の重ね合わせで存在することができ、これは大まかに言えば、同時に両方の状態にあることを意味します。量子ビットを測定すると、結果は従来のビットの確率的な出力になります。量子コンピューターが量子ビットを特定の方法で操作すると、波の干渉効果によって目的の測定結果が増幅される可能性があります。量子アルゴリズムの設計には、量子コンピューターが計算を効率的かつ迅速に実行できるようにする手順の作成が含まれます。

量子コンピュータはまだ実際の作業には実用的ではありません。高品質の量子ビットを物理的に設計することは困難であることが証明されています。物理的な量子ビットが環境から十分に分離されていない場合、量子デコヒーレンスが発生し、計算にノイズが導入されます。各国政府は、より長いコヒーレンス時間とより低いエラー率を備えたスケーラブルな量子ビットの開発を目指す実験研究に多額の投資を行っています。実装例には、超伝導体（電気抵抗を排除することで電流を分離する）やイオントラップ（電磁場を使用して単一の原子粒子を閉じ込める）などがあります。

原理的には、十分な時間があれば、古典コンピュータも量子コンピュータと同じ計算上の問題を解くことができます。量子の利点は計算可能性ではなく時間計算量の形で現れ、量子計算量理論は、一部の量子アルゴリズムが最もよく知られている古典アルゴリズムよりも指数関数的に効率的であることを示しています。大規模な量子コンピュータは、理論的には古典コンピュータでは妥当な時間では解けない計算上の問題を解くことができます。この超能力の概念は「量子超越性」と呼ばれています。このような主張は量子分野に大きな注目を集めていますが、近い将来の実用例は限られています。

長年にわたり、量子力学とコンピュータサイエンスの分野は、別個の学術コミュニティを形成してきました。^[1] 現代の量子理論は、原子スケールで観察される波動粒子二重性を説明するために 1920 年代に発展し、^[2]その後数十年間でデジタルコンピュータが登場し、面倒な計算を人間が行うコンピュータに取って代わりました。^{[3]両方の分野は}第二次世界大戦中に実用化され、コンピュータは戦時暗号で大きな役割を果たし、^{[4]量子物理学は}マンハッタン計画で使用された原子物理学に不可欠でした。^[5]

物理学者が量子力学モデルを計算問題に適用し、デジタルビットを量子ビットに置き換えると、量子力学とコンピュータサイエンスの分野が融合し始めました。1980年にポール・ベニオフは量子理論を使用して簡略化されたコンピュータを記述する量子チューリングマシンを発表しました。 ^[6] デジタルコンピュータが高速化すると、物理学者は量子力学をシミュレートする際のオーバーヘッドの指数関数的な増加に直面し、^[7]ユーリ・マニンとリチャード・ファインマンはそれぞれ独立して、量子現象に基づくハードウェアの方がコンピュータシミュレーションには効率的かもしれないと示唆しました。 ^{[8] [9] [10]} 1984年の論文で、チャールズ・ベネットとジル・ブラッサードは量子理論を暗号プロトコルに適用し、量子鍵配布によって情報セキュリティを強化できることを実証しました。^{[11] [12]}

その後、 1985年のドイチェのアルゴリズム^[13]、1993年のベルンシュタイン・ヴァジラニアルゴリズム[14]、1994年^のサイモンのアルゴリズム^[15]など、神託問題を解くための量子アルゴリズムが登場した。これらのアルゴリズムは実用的な問題を解決するものではなかったが、量子並列性と呼ばれることもある重ね合わせ状態の量子状態を持つブラックボックスに クエリを実行することで、より多くの情報を得ることができることを数学的に実証した。^[16]

ピーター・ショアはこれらの結果を基に、1994年に広く使われているRSAとディフィー・ヘルマン暗号プロトコルを破るアルゴリズムを開発し^[17]、量子コンピューティングの分野に大きな注目を集めました。1996年、グローバーのアルゴリズムは、広く適用可能な非構造化検索問題に対する量子的な高速化を確立しました。 ^{[18] [19]}同年、セス・ロイドは、量子コンピュータが古典的なシミュレーションに存在する指数関数的なオーバーヘッドなしで量子システムをシミュレートできることを証明し^[20] 、ファインマンの1982年の予想を検証しました。^[21]

長年にわたり、実験家たちはトラップイオンと超伝導体を使って小規模な量子コンピュータを構築してきました。 ^[22] 1998年には2量子ビットの量子コンピュータがこの技術の実現可能性を実証し、^{[23] [24]}その後の実験では量子ビットの数が増加し、エラー率が低下しました。^[22]

2019年、Google AIとNASAは54量子ビットのマシンで量子超越性を達成し、従来のコンピュータでは不可能な計算を実行したと発表しました。^{[25] [26] [27]}しかし、この主張の妥当性はまだ積極的に研究されています。^{[28] [29]}

2023年12月、物理学者は初めて個々の分子のエンタングルメントを報告しました。これは量子コンピューティングに大きな応用が期待されます。^[30]

コンピュータエンジニアは、通常、現代のコンピュータの動作を古典的な電気力学の観点から説明します。これらの「古典的な」コンピュータでは、一部のコンポーネント（半導体や乱数発生器など）が量子動作に依存している可能性がありますが、これらのコンポーネントは環境から分離されていないため、量子情報はすぐにデコヒーレンスします。プログラマーはランダム化アルゴリズムを設計する際に確率論に依存する場合がありますが、重ね合わせや干渉などの量子力学の概念は、プログラム分析にはほとんど関係ありません。

対照的に、量子プログラムはコヒーレントな量子システムの正確な制御に依存しています。物理学者は線形代数を使用してこれらのシステムを数学的に記述します。複素数は確率振幅をモデル化し、ベクトルは量子状態をモデル化し、行列はこれらの状態に対して実行できる操作をモデル化します。したがって、量子コンピューターのプログラミングは、結果として得られるプログラムが理論上は有用な結果を計算し、実際に実装可能であるような方法で操作を 構成することです。

物理学者チャーリー・ベネットは量子コンピュータと古典コンピュータの関係について次のように述べている。^[31]

古典的なコンピュータは量子コンピュータです...したがって、「量子的な高速化はどこから来るのか」と問うべきではありません。私たちは、「そうですね、すべてのコンピュータは量子です。...古典的な速度低下はどこから来るのか」と言うべきです。

ビットが古典情報理論の基本概念であるのと同様に、量子ビットは量子情報の基本単位である。同じ用語「量子ビット」は、抽象的な数学モデルや、そのモデルによって表現されるあらゆる物理システムを指すのに用いられる。古典ビットは、定義により、0 と 1 で表すことができる 2 つの物理状態のいずれかに存在している。量子ビットも状態によって記述され、2 つの状態はしばしば と と書かれ、古典状態 0 と 1 の量子対応物として機能する。しかし、量子状態と はベクトル空間に属しており、つまりこれらに定数を掛けて足し合わせると、やはり有効な量子状態になる。このような組み合わせは、との重ね合わせとして知られている。^{[32] [33]}${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$

2 次元ベクトルは、数学的に量子ビットの状態を表します。物理学者は通常、量子力学の線型代数にディラック表記法を使用し、というラベルのベクトルを「ket psi」と書きます。量子ビットは 2 状態システムであるため、任意の量子ビット状態は という形式になります。ここで、と は標準の基底状態、^[b]であり、 とは確率振幅であり、一般には複素数です。^[33]または のいずれかがゼロの場合、量子ビットは事実上古典的なビットです。両方がゼロでない場合、量子ビットは重ね合わせ状態にあります。このような量子状態ベクトルは、 （古典的な）確率ベクトルと同様に機能しますが、重要な違いが 1 つあります。確率とは異なり、確率振幅は必ずしも正の数ではありません。^[35]負の振幅は、破壊的な波の干渉を可能にします。 ${\displaystyle |\psi \rangle }$ ${\displaystyle \psi}$${\displaystyle \alpha |0\rangle +\beta |1\rangle }$${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$${\displaystyle \alpha}$${\displaystyle \beta}$${\displaystyle \alpha}$${\displaystyle \beta}$

量子ビットを標準基底で測定すると、結果は古典的ビットになります。ボルンの規則は、振幅と確率の間のノルム二乗対応を表します。つまり、量子ビット を測定すると、状態は確率 でに、確率 でに崩壊します。有効な量子ビット状態はすべて、となる係数とを持ちます。たとえば、量子ビットを測定すると、 またはが等しい確率で 生成されます。${\displaystyle \alpha |0\rangle +\beta |1\rangle }$${\displaystyle |0\rangle }$${\displaystyle |\alpha |^{2}}$${\displaystyle |1\rangle }$${\displaystyle |\beta |^{2}}$${\displaystyle \alpha}$${\displaystyle \beta}$${\displaystyle |\alpha |^{2}+|\beta |^{2}=1}$${\displaystyle 1/{\sqrt {2}}|0\rangle +1/{\sqrt {2}}|1\rangle }$${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$

量子ビットを追加するごとに状態空間の次元が2倍になります。^[34] 例として、ベクトル⁠1/√2⁠ |00⟩ + ⁠1/√2⁠ |01⟩ は2量子ビット状態を表し、量子ビット|0⟩と量子ビット⁠ のテンソル積である。1/√2⁠ |0⟩ + ⁠1/√2⁠ |1⟩ 。このベクトルは、基底ベクトル|00⟩、 |01⟩、 |10⟩、および|11⟩によって張られる4次元ベクトル空間に存在します。ベル状態⁠ 1/√2⁠ |00⟩ + ⁠1/√2⁠ |11⟩ は、2 つの個別の量子ビットのテンソル積に分解することは不可能です。2 つの量子ビットは、その確率振幅が相関しているためにエンタングルされています。一般に、 n量子ビット システムのベクトル空間は2 ⁿ次元であり、これにより、古典コンピュータが量子コンピュータをシミュレートすることが困難になります。100 量子ビット システムを表すには、2 ^{100 個の}古典的な値を保存する必要があります。

この1量子ビットの量子メモリの状態は、古典的なメモリを古典的な論理ゲートで操作するのと同様に、量子論理ゲートを適用することで操作できます。古典的な計算と量子計算の両方で重要なゲートの1つは、行列で表すことができるNOTゲートです。数学的に は 、このような論理ゲートを量子状態ベクトルに適用することは、行列の乗算でモデル化されます。したがって、 $${\displaystyle X:={\begin{pmatrix}0&1\\1&0\end{pmatrix}}.}$$

${\displaystyle X|0\rangle =|1\rangle }$そして。${\displaystyle X|1\rangle =|0\rangle }$

単一量子ビット ゲートの数学は、2 つの重要な方法でマルチ量子ビット量子メモリに拡張できます。 1 つの方法は、単に量子ビットを選択し、そのゲートをターゲット量子ビットに適用し、メモリの残りの部分はそのままにすることです。 もう 1 つの方法は、メモリの別の部分が目的の状態にある場合にのみ、ゲートをそのターゲットに適用することです。 これら 2 つの選択は、別の例を使用して説明できます。 2 量子ビット量子メモリの可能な状態は次のとおりです 。制御 NOT (CNOT) ゲートは、次の行列を使用して表すことができます。 この定義の数学的帰結として、、、、および です。 言い換えると、CNOT は、最初の量子ビットが状態 にある場合にのみ、NOT ゲート (前述の) を 2 番目の量子ビットに適用します。最初の量子ビットが の場合、どちらの量子ビットにも何も行われません。 $${\displaystyle |00\rangle :={\begin{pmatrix}1\\0\\0\\0\end{pmatrix}};\quad |01\rangle :={\begin{pmatrix}0\\1\\0\\0\end{pmatrix}};\quad |10\rangle :={\begin{pmatrix}0\\0\\1\\0\end{pmatrix}};\quad |11\rangle :={\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}.}$$$${\displaystyle \operatorname {CNOT} :={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}.}$$${\textstyle \operatorname {CNOT} |00\rangle =|00\rangle }$${\textstyle \operatorname {CNOT} |01\rangle =|01\rangle }$${\textstyle \operatorname {CNOT} |10\rangle =|11\rangle }$${\textstyle \operatorname {CNOT} |11\rangle =|10\rangle }$${\textstyle X}$${\textstyle |1\rangle }$${\textstyle |0\rangle }$

要約すると、量子計算は量子論理ゲートと測定のネットワークとして説明できます。ただし、測定は量子計算の最後まで延期できますが、この延期には計算コストがかかる可能性があるため、ほとんどの量子回路は量子論理ゲートのみで構成され、測定は含まれないネットワークを表します。

量子並列処理は、量子コンピュータが複数の入力値に対して同時に関数を評価すると考えられるヒューリスティックです。これは、入力状態の重ね合わせで量子システムを準備し、評価する関数をエンコードするユニタリ変換を適用することで実現できます。結果の状態は、重ね合わせ内のすべての入力値に対する関数の出力値をエンコードし、複数の出力を同時に計算できるようにします。この特性は、多くの量子アルゴリズムの高速化の鍵となります。ただし、この意味での「並列処理」は、計算の最後の測定で得られる値が 1 つだけであるため、計算を高速化するには不十分です。量子アルゴリズムが有用であるためには、他の概念的な要素も組み込む必要があります。^{[36] [37]}

量子コンピューティングには、計算が分解される基本要素によって区別される さまざまな計算モデルがあります。

量子ゲートアレイは、計算を数量子ビットの量子ゲートのシーケンスに分解します。量子計算は、量子論理ゲートと測定のネットワークとして説明できます。ただし、測定は量子計算の最後まで延期できますが、この延期には計算コストがかかる可能性があるため、ほとんどの量子回路は、測定のない量子論理ゲートのみで構成されるネットワークを表します。

任意の量子計算（上記の形式では、量子ビット上のサイズの任意のユニタリ行列）は、かなり小さなゲートファミリからの量子論理ゲートのネットワークとして表現できます。この構築を可能にするゲートファミリの選択は、ユニバーサルゲートセットとして知られています。これは、そのような回路を実行できるコンピュータがユニバーサル量子コンピュータであるためです。一般的なゲートセットの1つには、すべてのシングルキュービットゲートと上記のCNOTゲートが含まれます。つまり、一連のシングルキュービットゲートとCNOTゲートを実行することで、任意の量子計算を実行できます。このゲートセットは無限ですが、ソロベイ-キタエフの定理を適用することで、有限ゲートセットに置き換えることができます。ここでは、少数量子ビットの量子ゲートを使用したブール関数の実装を示します。^[38]${\displaystyle 2^{n}\times 2^{n}}$${\displaystyle n}$

測定ベースの量子コンピュータは、量子ゲートテレポーテーションと呼ばれる技術を使用して、計算をベル状態の測定のシーケンスと、高度にエンタングルされた初期状態 (クラスター状態) に適用される単一量子ビットの量子ゲートに分解します。

量子アニーリングに基づく断熱量子コンピュータは、計算を初期ハミルトニアンから最終ハミルトニアンへのゆっくりとした連続変換に分解し、その基底状態に解が含まれる。^[39]

ニューロモルフィック量子コンピューティング（略称「n.quantum computing」）は、ニューロモルフィックコンピューティングを使用して量子演算を実行する、従来とは異なるコンピューティングタイプのコンピューティングです。量子アルゴリズム（量子コンピューティングの現実的なモデルで実行されるアルゴリズム）は、ニューロモルフィック量子コンピューティングでも同様に効率的に計算できることが示唆されています。従来の量子コンピューティングとニューロモルフィック量子コンピューティングはどちらも、物理学に基づいた従来とは異なるコンピューティング手法であり、フォン・ノイマン・アーキテクチャには従いません。どちらも、手元の物理的問題を表すシステム（回路）を構築し、システムのそれぞれの物理的特性を活用して「最小値」を求めます。ニューロモルフィック量子コンピューティングと量子コンピューティングは、計算中に同様の物理的特性を共有します。

トポロジカル量子コンピュータは、計算を2次元格子内のエニオンの編み込みに分解します。 ^[40]

量子チューリングマシンは、チューリングマシンの量子アナログです。^[6]これらの計算モデル、つまり量子回路、^[41] 一方向量子計算、^[42]断熱量子計算、^[43]トポロジカル量子計算^[44]はすべて、量子チューリングマシンと同等であることが示されています。このような量子コンピュータを完璧に実装すれば、他のすべてのコンピュータを多項式以下のオーバーヘッドでシミュレートできます。この等価性は実際の量子コンピュータでは必ずしも当てはまりません。シミュレーションのオーバーヘッドが大きすぎて実用的ではない場合があるためです。

閾値定理は、量子ビットの数を増やすことでエラーを軽減できることを示しているが^[45]、完全なフォールトトレラント量子コンピューティングは「かなり遠い夢」のままである。^[46]一部の研究者によると、ノイズの多い中規模量子( NISQ ) マシンは近い将来に特殊な用途に使用される可能性があるが、量子ゲートのノイズにより信頼性が制限される。 ^[46]ハーバード大学 の科学者は、他の方法よりも効率的にエラーを修正する「量子回路」の作成に成功し、実用的な量子コンピューターへの大きな障害を取り除く可能性がある。^{[47] [48]}ハーバード大学の研究チームは、 MIT、QuEra Computing、Caltech、プリンストン大学の支援を受け、 DARPAのノイズの多い中規模量子デバイスによる最適化 (ONISQ) プログラムによって資金提供を受けた。 ^{[49] [50]}

量子コンピューティングは、暗号化とサイバーセキュリティの分野で大きな潜在的応用が期待されています。量子力学の原理に基づく量子暗号化は、盗聴に耐性のある安全な通信チャネルの可能性を提供します。BB84 などの量子鍵配布 (QKD) プロトコルは、当事者間での暗号化鍵の安全な交換を可能にし、通信の機密性と整合性を保証します。さらに、量子乱数ジェネレーター (QRNG) は、安全な暗号化に不可欠な高品質の乱数を生成できます。

しかし、量子コンピューティングは従来の暗号システムにも課題を突きつけています。整数因数分解の量子アルゴリズムであるショアのアルゴリズムは、大きな数の因数分解の難しさを利用する RSA などの広く使用されている公開鍵暗号方式を破る可能性があります。従来のコンピューターと量子コンピューターの両方による攻撃に耐性のある暗号アルゴリズムの開発を伴うポスト量子暗号は、この懸念に対処することを目的とした活発な研究分野です。

量子暗号とポスト量子暗号の継続的な研究は、進化する量子コンピューティング能力に直面して通信とデータのセキュリティを確保するために不可欠です。新しいQKDプロトコルの開発、QRNGの改善、ポスト量子暗号アルゴリズムの標準化など、これらの分野における進歩は、量子時代における情報の完全性と機密性を維持する上で重要な役割を果たすでしょう。^[51]

量子暗号は、データを安全に伝送する新しい方法を可能にします。たとえば、量子鍵配送では、量子もつれ状態を使用して安全な暗号鍵を確立します。^[52]送信者と受信者が量子状態を交換すると、許可されていない盗聴者が繊細な量子システムを妨害し、検出可能な変更を導入するため、敵対者がメッセージを傍受しないことを保証できます。 ^[53]適切な暗号化プロトコルを使用すると、送信者と受信者は盗聴に耐性のある共有の秘密情報を確立できます。^{[11] [54]}

現代の光ファイバーケーブルは、比較的短い距離で量子情報を伝送することができます。現在行われている実験的研究では、より信頼性の高いハードウェア（量子中継器など）の開発を目指しており、この技術をエンドツーエンドのエンタングルメントを備えた長距離量子ネットワークに拡張したいと考えています。理論的には、これにより、分散型量子コンピューティングや強化された量子センシングなどの新しい技術アプリケーションが可能になります。^{[55] [56]}

量子アルゴリズムの発見の進歩は、典型的にはこの量子回路モデルに焦点を当てていますが、量子断熱アルゴリズムのような例外も存在します。量子アルゴリズムは、対応する古典的アルゴリズムに対して達成される高速化の種類によって大まかに分類できます。^[57]

最もよく知られている古典的アルゴリズムに比べて多項式以上の高速化を実現する量子アルゴリズムには、因数分解のためのショアのアルゴリズムや、離散対数の計算、ペル方程式の解法、より一般的にはアーベル有限群の隠れた部分群問題の解法など、関連する量子アルゴリズムがある。 ^{[57]これらのアルゴリズムは、}量子フーリエ変換の原始関数に依存する。同程度に高速な古典的アルゴリズムが発見できないことを示す数学的証明は見つかっていないが、証拠はこれがありそうにないことを示唆している。^[58]サイモンの問題やバーンスタイン・ヴァジラニ問題などの特定の神託問題では証明可能な高速化が実現するが、これは量子クエリモデルにおけるものであり、これは下限の証明がはるかに容易な制限付きモデルであり、必ずしも実際の問題での高速化にはつながらない。

化学や固体物理学における量子物理過程のシミュレーション、特定のジョーンズ多項式の近似、線形方程式系の量子アルゴリズムなどの他の問題では、量子アルゴリズムが超多項式的な高速化をもたらすように見え、BQP完全である。これらの問題はBQP完全であるため、それらに対する同等に高速な古典的アルゴリズムは、超多項式的な高速化をもたらす量子アルゴリズムがないことを意味するが、それはありそうにないと考えられている。^[59]

グローバーのアルゴリズムや振幅増幅のようないくつかの量子アルゴリズムは、対応する古典的アルゴリズムよりも多項式的な高速化をもたらします。 ^[57]これらのアルゴリズムは比較的控えめな二次的な高速化をもたらしますが、広く適用可能であり、したがって幅広い問題に対して高速化をもたらします。^[19]

化学とナノテクノロジーは量子システムの理解に依存しており、そのようなシステムを古典的な方法で効率的にシミュレートすることは不可能であるため、量子シミュレーションは量子コンピューティングの重要な応用となる可能性がある。^{[60]量子シミュレーションは、}衝突型加速器内の反応など、異常な条件下での原子や粒子の挙動をシミュレートするためにも使用できる。^[61] 2023年6月、IBMのコンピューター科学者は、量子コンピューターが物理学の問題に対して従来のスーパーコンピューターよりも優れた結果を生成したと報告した。^{[62] [63]}

世界の年間エネルギー生産量の約2％は、農業肥料産業におけるハーバー法で窒素固定してアンモニアを生産するために使用されています（自然界に存在する生物もアンモニアを生産しますが）。量子シミュレーションは、このプロセスを理解し、生産のエネルギー効率を高めるために使用される可能性があります。 ^[64]量子コンピューティングの初期の用途は、 2020年代半ばまでにハーバー・ボッシュ法の効率を改善するモデリングになることが期待されています^[65]が、さらに時間がかかると予測する人もいます。^[67]

量子計算の注目すべき応用は、現在使用されている暗号システムへの攻撃である。公開鍵暗号システムのセキュリティの基盤となる整数因数分解は、少数の素数の積（例えば、2つの300桁の素数の積）である大きな整数については、通常のコンピュータでは計算上実行不可能であると考えられている。 ^[68]これに比べて、量子コンピュータは、ショアのアルゴリズムを使用して因数を見つけることで、この問題を指数関数的に速く解くことができる。^{[69]この能力により、量子コンピュータは現在使用されている多くの}暗号システムを破ることができる。つまり、問題を解くための多項式時間（整数の桁数）アルゴリズムが存在するということである。特に、一般的な公開鍵暗号のほとんどは、整数の因数分解の難しさや離散対数問題に基づいており、どちらもショアのアルゴリズムで解くことができる。特に、RSA、Diffie-Hellman、楕円曲線Diffie-Hellmanアルゴリズムは破られる可能性があります。これらは、安全なWebページ、暗号化された電子メール、その他多くの種類のデータを保護するために使用されます。これらが破られると、電子プライバシーとセキュリティに重大な影響が及ぶ可能性があります。

量子アルゴリズムに対して安全な可能性のある暗号システムを特定することは、ポスト量子暗号の分野で活発に研究されているトピックである。^{[70] [71]}一部の公開鍵アルゴリズムは、ショアのアルゴリズムが適用される整数因数分解や離散対数問題以外の問題に基づいており、例えば符号理論の問題に基づくマケリース暗号システムなどである。^{[70] [72]}格子ベースの暗号システムは量子コンピュータによって破られることも知られておらず、多くの格子ベースの暗号システムを破る二面体隠れ部分群問題を解く多項式時間アルゴリズムを見つけることは、十分に研究された未解決の問題である。^[73]グローバーのアルゴリズムを適用して対称（秘密鍵）アルゴリズムをブルートフォースで破るには、基礎となる暗号アルゴリズムの呼び出しに約2n ^{/ 2回}相当の時間がかかることが証明されています。これは、古典的なケースでは約²ⁿであるのに対し、 ^[74]対称鍵の長さが実質的に半分になることを意味します。AES-256は、グローバーのアルゴリズムを使用した攻撃に対して、AES-128が古典的なブルートフォース検索に対して持っているのと同じセキュリティを備えています（キーサイズを参照）。

多項式量子高速化が可能な問題の最もよく知られた例は、データベース内の項目のリストからマークされた項目を見つける非構造化検索です。これは、データベースへのクエリを使用するグローバーのアルゴリズムによって解決できます。これは、従来のアルゴリズムに必要なクエリの2乗よりも少ないクエリです。この場合、利点は証明可能であるだけでなく、最適でもあります。グローバーのアルゴリズムは、任意の数のオラクル検索に対して目的の要素を見つける可能性が最大限に高いことが示されている。クエリ問題に対する証明可能な量子高速化の多くの例は、2対1関数の衝突を見つけるためのブラッサード、ホイヤー、タップのアルゴリズム^[75]や、NANDツリーを評価するためのファリ、ゴールドストーン、ガットマンのアルゴリズムなど、グローバーのアルゴリズムに基づいています。^[76]${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$${\displaystyle \Omega (n)}$

グローバーのアルゴリズムで効率的に解決できる問題には、次のような性質がある。^{[77] [78]}

1. 可能な回答のコレクションには検索可能な構造がありません。
2. チェックする可能性のある回答の数はアルゴリズムへの入力の数と同じであり、
3. 各入力を評価し、それが正しい答えであるかどうかを判断するブール関数が存在します。

これらすべての特性を持つ問題の場合、量子コンピュータでのグローバーのアルゴリズムの実行時間は、古典的なアルゴリズムの線形スケーリングとは対照的に、入力数（またはデータベース内の要素）の平方根に比例します。グローバーのアルゴリズムを適用できる一般的な問題クラス^[79]はブール充足問題であり、アルゴリズムが反復するデータベースはすべての可能な回答のデータベースです。この例と可能なアプリケーションは、パスワードを推測しようとするパスワードクラッカーです。このアルゴリズムを使用して対称暗号を破ることは、政府機関の関心事です。^[80]

量子アニーリングは、計算を実行するために断熱定理に依存しています。システムは、単純なハミルトニアンの基底状態に置かれ、それがゆっくりとより複雑なハミルトニアンに進化します。その基底状態は、問題に対する解を表します。断熱定理は、進化が十分に遅い場合、システムはプロセス全体を通じて常に基底状態に留まると述べています。断熱最適化は計算生物学の問題を解くのに役立つかもしれない。^[81]

量子コンピュータは古典コンピュータが効率的に生成できない出力を生成でき、量子計算は基本的に線形代数であるため、機械学習タスクを高速化できる量子アルゴリズムの開発に期待を表明する人もいます。^{[46] [82]}

例えば、HHLアルゴリズムは、発見者であるハロー、ハシディム、ロイドの名にちなんで名付けられ、従来のアルゴリズムよりも高速化できると考えられています。^{[46] [83]いくつかの研究グループは最近、}ボルツマンマシンとディープニューラルネットワークのトレーニングに量子アニーリングハードウェアの使用を検討しました。^{[84] [85] [86]}

深層生成化学モデルは、創薬を 促進する強力なツールとして登場しています。しかし、あらゆる薬物に似た分子の構造空間の巨大なサイズと複雑さは大きな障害となりますが、将来的には量子コンピュータによって克服される可能性があります。量子コンピュータは、複雑な量子多体問題^[20]を解くのに優れているため、量子化学を含むアプリケーションに役立つ可能性があります。したがって、量子GAN ^[88]を含む量子強化生成モデル^[87 ]が最終的に究極の生成化学アルゴリズムに開発されることが期待できます。

2023年現在、^[update]古典コンピュータはあらゆる実世界のアプリケーションにおいて量子コンピュータを上回る性能を発揮する。現在の量子コンピュータは特定の数学的問題の解決を高速化するかもしれないが、実用的なタスクに対しては計算上の優位性を与えない。科学者やエンジニアは量子コンピューティングハードウェアの複数の技術を研究しており、スケーラブルな量子アーキテクチャの開発を望んでいるが、深刻な障害が残っている。^{[89] [90]}

大規模量子コンピュータの構築には多くの技術的課題がある。^[91]物理学者のデイビッド・ディヴィンチェンツォは実用的な量子コンピュータに求められる要件として以下を挙げている。 ^[92]

• 量子ビットの数を増やすために物理的に拡張可能
• 任意の値に初期化できる量子ビット
• デコヒーレンス時間よりも高速な量子ゲート
• ユニバーサルゲートセット
• 簡単に読み取ることができる量子ビット。

量子コンピュータの部品調達も非常に困難である。グーグルやIBMが構築したような超伝導量子コンピュータには、原子力研究の副産物であるヘリウム3と、日本のCoax社のみが製造する特殊な超伝導ケーブルが必要である。 ^[93]

マルチ量子ビットシステムの制御には、厳密で決定論的なタイミング分解能を備えた多数の電気信号の生成と調整が必要です。これにより、量子ビットとのインターフェースを可能にする量子コントローラの開発が進みました。これらのシステムをスケーリングして、増加する量子ビット数をサポートすることは、さらなる課題です。^[94]

量子コンピュータの構築に伴う最大の課題の 1 つは、量子デコヒーレンスを制御または除去することです。これは通常、システムをその環境から分離することを意味します。外部世界との相互作用によりシステムがデコヒーレンスを引き起こすためです。ただし、デコヒーレンスの原因は他にも存在します。例としては、量子ゲート、および量子ビットを実装するために使用される物理システムの格子振動と背景熱核スピンがあります。デコヒーレンスは、実質的に非ユニタリーであるため不可逆であり、通常は回避できないとしても、高度に制御する必要があります。特に候補システムのデコヒーレンス時間、横緩和時間T ₂ ( NMRおよびMRI技術の場合、位相ずれ時間とも呼ばれます) は、低温で通常ナノ秒から秒の範囲です。^[95]現在、一部の量子コンピュータでは、重大なデコヒーレンスを防ぐために、量子ビットを 20 ミリケルビンに冷却する必要があります (通常は希釈冷凍機を使用^[96] )。^[97] 2020年の研究では、宇宙線などの電離放射線は、特定のシステムを数ミリ秒以内にデコヒーレンスさせる可能性があると主張しています。^[98]

その結果、時間のかかるタスクでは、量子ビットの状態を長時間維持しようとすると最終的に重ね合わせが壊れるため、一部の量子アルゴリズムが動作不能になる可能性があります。^[99]

これらの問題は、時間スケールが桁違いに短いため光学的アプローチではより困難であり、それらを克服するためによく引用されるアプローチは光パルス成形です。エ​​ラー率は通常、動作時間とデコヒーレンス時間の比率に比例するため、すべての操作はデコヒーレンス時間よりもはるかに速く完了する必要があります。

閾値定理で説明されているように、誤り率が十分に小さければ、量子誤り訂正を使用して誤りとデコヒーレンスを抑制することができると考えられます。これにより、誤り訂正方式がデコヒーレンスによって生じる誤りよりも速く誤りを訂正できる場合、合計計算時間はデコヒーレンス時間よりも長くなります。フォールトトレラント計算の各ゲートで必要な誤り率としてよく引用される数値は、ノイズが脱分極であると仮定すると 10 ⁻³です。

このスケーラビリティ条件を満たすことは、幅広いシステムで可能です。ただし、エラー訂正を使用すると、必要な量子ビットの数が大幅に増加するというコストがかかります。ショアのアルゴリズムを使用して整数を因数分解するために必要な数は依然として多項式であり、LとL ²の間であると考えられています。ここで、Lは因数分解される数の桁数です。エラー訂正アルゴリズムは、この数値をさらにL倍に増やします。1000ビットの数の場合、エラー訂正なしでは約10 ⁴ビットが必要になります。^[100]エラー訂正を使用すると、この数値は約10 ⁷ビットに増加します。計算時間は約L ²または約10 ⁷ステップで、1  MHzでは約10秒です。ただし、エンコードとエラー訂正のオーバーヘッドにより、実際のフォールトトレラント量子コンピュータのサイズは数桁増加します。慎重な推定^{[101] [102]}によれば、少なくとも300 万の物理量子ビットが、完全に誤り訂正されたトラップイオン量子コンピュータで5ヶ月で2,048ビットの整数を因数分解することを示しています。物理量子ビットの数に関して言えば、これまでのところ、これは1,024ビット以上のサイズを持つ実際に有用な整数因数分解問題に対する 最低の推定値です^{[103] 。}

安定性とデコヒーレンスの問題に対するもう一つのアプローチは、エニオン（準粒子）を糸として使い、編組理論を利用して安定した論理ゲートを形成するトポロジカル量子コンピュータを作成することである。 ^{[104] [105]}

物理学者ジョン・プレスキルは、プログラム可能な量子デバイスが最先端の古典的コンピュータの能力を超えた問題を解決できることを実証するという工学上の偉業を説明するために、量子超越性という用語を作り出した。 ^{[106] [107] [108]}その問題は必ずしも有用である必要はないため、量子超越性テストは将来のベンチマークとしてのみ考えられると考える人もいる。^[109]

2019年10月、Google AI QuantumはNASAの協力を得て、Sycamore量子コンピュータで計算を、一般的に世界最速のコンピュータと考えられているSummitよりも300万倍以上高速に実行することで、量子超越性を達成したと初めて主張した。 ^{[26] [110] [111]}この主張はその後異議を唱えられており、IBMはSummitが主張よりもはるかに高速にサンプルを処理できると述べており^{[112] [113]}、研究者は量子超越性を主張するために使用されたサンプリング問題に対するより優れたアルゴリズムを開発し、Sycamoreと従来のスーパーコンピュータの差を大幅に縮め^{[114] [115] [116]}、さらにはそれを上回っています。^{[117] [118] [119]}

2020年12月、 USTCのグループは、量子超越性を実証するために、光子量子コンピュータJiuzhangを使用して76個の光子に対する一種のボソンサンプリングを実装しました。[ 120 ] [ 121 ] ^{[ 122 ]}著者らは、現代の古典的なスーパーコンピュータでは、量子プロセッサが20秒で生成できるサンプル数を生成するのに6億年の計算時間が必要であると主張しています。^[123]

量子超越性の主張は量子コンピューティングに関する誇大宣伝を生み出したが^[124]、それらは実際の世界での有用な応用を直接意味するものではない、人為的なベンチマークタスクに基づいている。^{[89] [125]}

2024年1月、 Physical Review Lettersに掲載された研究では、新世代のサンウェイスーパーコンピューターを使用して実験的に生成されたビット列の正確な振幅を計算することで、量子超越性実験を直接検証し、多重振幅テンソルネットワーク収縮アルゴリズムに基づくシミュレーション機能の大幅な飛躍を実証しました。この開発は、量子コンピューティングの進化を強調し、量子超越性の主張を検証することに伴う進歩と複雑さの両方を浮き彫りにしています。^[126]

量子コンピューティングへの大きな期待、ハードウェアの大きな進歩、将来のアプリケーションに対する楽観的な見通しにもかかわらず、2023年のNatureのスポットライト記事は、現在の量子コンピューターを「今のところ、まったく役に立たない」と要約しました。^[89]この記事では、量子コンピューターはいずれにせよ従来のコンピューターよりも有用または効率的になることはまだないと詳しく説明しましたが、長期的にはそのようなコンピューターは有用である可能性が高いとも主張しています。2023年のCommunications of the ACMの記事^[90]では、現在の量子コンピューティングアルゴリズムは「ソフトウェア/ハードウェアスタック全体の大幅な改善がなければ、実用的な量子優位性には不十分」であることがわかりました。量子コンピューターで高速化を達成するための最も有望な候補は、たとえば化学や材料科学における「小規模データの問題」であると主張しています。しかし、記事では、機械学習など、検討した潜在的なアプリケーションの広範囲は「近い将来、現在の量子アルゴリズムでは量子優位性を達成できない」とも結論付けており、「ビッグデータの問題、非構造化線形システム、グローバーのアルゴリズムに基づくデータベース検索」の高速化を困難にする I/O 制約を特定しています。

この状況は、いくつかの現在および長期的な考慮事項に起因しています。

• 従来のコンピューター ハードウェアとアルゴリズムは、実用的なタスクに最適化されているだけでなく、特にGPUアクセラレーターを中心に急速に改善され続けています。
• 現在の量子コンピューティング ハードウェアは、ノイズに圧倒される前に、限られた量のエンタングルメントしか生成しません。
• 量子アルゴリズムは、一部のタスクにおいてのみ従来のアルゴリズムよりも高速化を実現しており、これらのタスクを実際のアプリケーションと一致させることは困難であることが判明した。有望なタスクやアプリケーションの中には、現在利用可能なリソースをはるかに超えるリソースを必要とするものがある。^{[127] [128]}特に、大量の非量子データの処理は量子コンピュータにとって課題である。^[90]
• いくつかの有望なアルゴリズムは「逆量子化」され、つまり、同様の複雑さを持つ非量子類似物が発見されました。
• 量子誤り訂正が量子コンピュータを実用的なアプリケーションに拡張するために使用された場合、そのオーバーヘッドにより、多くの量子アルゴリズムが提供する高速化が損なわれる可能性があります。^[90]
• アルゴリズムの複雑性分析では、アプリケーションでは当てはまらない抽象的な仮定が立てられることがあります。たとえば、入力データは量子状態でエンコードされてまだ利用できない可能性があり、Grover のアルゴリズムで使用される「オラクル関数」には、より高速なアルゴリズムに利用できる内部構造が備わっていることがよくあります。

特に、多数の量子ビットを持つコンピュータを構築しても、それらの量子ビットが十分に接続されておらず、十分に高いエンタングルメントの度合いを長期間維持できない場合は無駄になる可能性があります。従来のコンピュータよりも優れた性能を発揮しようとする場合、量子コンピューティングの研究者は量子コンピュータで解決できる新しいタスクを探すことがよくありますが、量子超越性の実証に見られるように、これに応じて効率的な非量子技術が開発される可能性があります。したがって、可能な限り最高の非量子アルゴリズム（未知である可能性があります）の複雑さの下限を証明し、一部の量子アルゴリズムがそれらの下限を無症状に改善することを示すことが望ましいです。

一部の研究者は、大規模なスケールで一貫性を維持する問題が主な理由だが、他の理由からも、スケーラブルな量子コンピュータが構築できるかどうかについて懐疑的な見方を示している。

ビル・アンルーは1994年に発表した論文で量子コンピュータの実用性に疑問を呈した。^[129] ポール・デイヴィスは400量子ビットのコンピュータはホログラフィック原理によって暗示される宇宙の情報量の限界とさえ矛盾すると主張した。^[130]ギル・カライのような懐疑論者は量子超越性が達成されるかどうか疑問視している。 ^{[131] [132] [133]}物理学者ミハイル・ディアコノフは量子コンピューティングに対する懐疑論を次のように表明している。

「したがって、このような有用な量子コンピュータの状態を任意の時点で記述する連続パラメータの数は...約10,300でなければなりません^{...このようなシステムの量子状態を定義する10,300}を超える連続可変パラメータを制御することを学ぶことはできるでしょうか？私の答えは簡単です。いいえ、絶対にできません。」^{[134] [135]}

実用的な量子コンピュータは、物理システムをプログラム可能な量子レジスタとして使用する必要があります。^[137]研究者は、信頼性の高い量子ビット実装の候補としていくつかの技術を研究しています。^[138] 超伝導体とトラップされたイオンは最も開発された提案の一部ですが、実験者は他のハードウェアの可能性も検討しています。^[139]

最初の量子論理ゲートはトラップイオンで実装され、最大20量子ビットのプロトタイプ汎用マシンが実現されました。しかし、これらのデバイスの背後にある技術は、複雑な真空装置、レーザー、マイクロ波、無線周波数装置を組み合わせたもので、フルスケールのプロセッサを標準的なコンピューティング機器に統合することは困難です。さらに、トラップイオンシステム自体にも克服すべき技術的課題があります。^[140]

最大の商用システムは超伝導デバイスをベースとしており、2000量子ビットまで拡張されています。しかし、より大きなマシンのエラー率は5％程度です。技術的には、これらのデバイスはすべて極低温であり、多数の量子ビットに拡張するには、ウェーハ規模の統合が必要であり、それ自体が深刻なエンジニアリング上の課題です。^[141]

量子コンピューティングのためのより安定した量子ビットを作成するための研究努力には、トポロジカル量子コンピュータアプローチが含まれます。たとえば、マイクロソフトは、エニオンと呼ばれる2次元準粒子の量子特性に基づいたコンピュータに取り組んでいます。^{[142] [143] [144]}

経営管理の観点から見ると、量子コンピューティングの潜在的な応用分野は、サイバーセキュリティ、データ分析と人工知能、最適化とシミュレーション、データ管理と検索の4つの主要カテゴリーに分類されます。^[145]

量子コンピューティング研究への投資は、公共部門と民間部門の両方で増加している。^{[146] [147]} あるコンサルティング会社は次のようにまとめている。^[148]

... 投資資金が流入し、量子コンピューティングの新興企業が急増しています。...量子コンピューティングは、従来の高性能コンピュータ の範囲と速度を超えた問題を企業が解決するのに役立つと期待されていますが、この初期段階では使用事例はほとんどが実験的かつ仮説的です。

古典コンピュータで解ける計算問題は量子コンピュータでも解ける。^[149]直感的に言えば、古典コンピュータの動作を含むすべての物理現象は量子コンピュータの動作の基礎となる量子力学を使って記述できると考えられているためである。

逆に言えば、量子コンピュータで解ける問題は古典コンピュータでも解ける。十分な時間があれば、紙とペンさえあれば量子コンピュータと古典コンピュータの両方を手動でシミュレートできる。より正式には、あらゆる量子コンピュータはチューリングマシンでシミュレートできる。言い換えれば、量子コンピュータは計算可能性の点で古典コンピュータを超えるパワーを提供しない。これは、量子コンピュータが停止問題のような決定不可能な問題を解くことができないことを意味し、量子コンピュータの存在はチャーチ＝チューリングのテーゼを反証するものではない。^[150]

量子コンピュータは、古典的コンピュータが解決できない問題を一切解決できませんが、特定の問題は古典的コンピュータよりも速く解決できるのではないかと考えられています。たとえば、量子コンピュータは整数を因数分解できることが知られていますが、古典的コンピュータではそうではないと考えられています。

量子コンピュータが誤差を制限して効率的に解くことができる問題のクラスは、 BQP（「誤差制限、量子、多項式時間」）と呼ばれます。より正式には、BQPは、誤差確率が最大1/3の多項式時間量子チューリングマシンで解くことができる問題のクラスです。確率的問題のクラスとして、BQPは、誤差制限のある多項式時間確率的チューリングマシンで解くことができる問題のクラスであるBPP（「誤差制限、確率的、多項式時間」）の量子版です。^[151]であることが知られており、 であると広く疑われており、これは直感的に、量子コンピュータは時間計算量の点で古典的コンピュータよりも強力であることを意味します。^[152]${\displaystyle {\mathsf {BPP\subseteq BQP}}}$${\displaystyle {\mathsf {BQP\subsetneq BPP}}}$

BQP とP、NP、およびPSPACEとの正確な関係はわかっていません。ただし、次のことがわかっています。つまり、決定論的古典コンピュータで効率的に解ける問題はすべて量子コンピュータでも効率的に解くことができ、量子コンピュータで効率的に解ける問題はすべて多項式空間リソースを持つ決定論的古典コンピュータでも解くことができます。さらに、BQP は P の厳密なスーパーセットであると考えられています。つまり、決定論的古典コンピュータでは効率的に解けない問題でも、量子コンピュータでは効率的に解ける問題が存在するということです。たとえば、整数因数分解と離散対数問題はBQP に含まれることがわかっており、P の範囲外であると考えられています。BQP と NP の関係については、P に含まれないと考えられている NP の問題の一部が BQP にも含まれるという事実 (たとえば、整数因数分解と離散対数問題はどちらも NP に含まれる) 以外にはほとんどわかっていません。次のことが推測されています。つまり、量子コンピュータでは効率的に解決できないが、効率的にチェック可能な問題が存在すると考えられている。この信念の直接的な結果として、BQPはNP完全問題のクラスとは独立しているのではないかとも疑われている（NP完全問題がBQPに含まれる場合、 NP困難性からNPのすべての問題はBQPに含まれることになる）。^[153]${\displaystyle {\mathsf {P\subseteq BQP\subseteq PSPACE}}}$${\displaystyle {\mathsf {NP\nsubseteq BQP}}}$

• アーロンソン、スコット(2013)。『デモクリトス以降の量子コンピューティング』ケンブリッジ大学出版局。doi : 10.1017 / CBO9780511979309。ISBN 978-0-521-19956-8. OCLC  829706638.
• グランブリング、エミリー、ホロウィッツ、編（2019）。量子コンピューティング：進歩と展望。ワシントンDC：全米アカデミー出版。doi ：10.17226/ 25196。ISBN 978-0-309-47970-7. OCLC  1091904777. S2CID  125635007.
• マーミン、N. デイビッド(2007)。量子コンピュータサイエンス：入門。doi : 10.1017 / CBO9780511813870。ISBN 978-0-511-34258-5. OCLC  422727925.
• ニールセン、マイケル、チュアン、アイザック(2010)。量子コンピューティングと量子情報(10 周年記念版)。doi : 10.1017/ CBO9780511976667。ISBN 978-0-511-99277-3. OCLC  700706156. S2CID  59717455.
• Shor, Peter W. (1994).量子計算アルゴリズム: 離散対数と因数分解.コンピュータサイエンスの基礎に関するシンポジウム.サンタフェ、ニューメキシコ: IEEE . pp. 124–134. doi :10.1109/SFCS.1994.365700. ISBN 978-0-8186-6580-6。

• ウィキメディア・コモンズの量子コンピュータ関連メディア
• Wikiversity の量子コンピューティングに関する学習教材
• スタンフォード哲学百科事典：「量子コンピューティング」、Amit Hagar と Michael E. Cuffaro 著。
• 「量子計算の理論」、数学百科事典、EMS Press、2001 [1994]
• アンディ・マトゥシャックとマイケル・ニールセンによる、好奇心旺盛な人のための量子コンピューティング

講義

• 決意ある人のための量子コンピューティング -マイケル・ニールセンによる 22 本のビデオ講義
• デイビッド・ドイチュによるビデオ講義
• アンリ・ポアンカレ研究所での講義（スライドとビデオ）
• 量子コンピューティング入門オンライン講義、エドワード・ジェルジュオイ (2008)
• ロモナコ、サム。2006 年 7 月にオックスフォード大学で行われた量子コンピューティングに関する 4 つの講義