量子アルゴリズム

量子コンピューティング において、量子アルゴリズムは量子コンピューティングの現実的なモデルで実行されるアルゴリズムであり、最も一般的に使用されるモデルは量子回路計算モデルです。^{[1] [2]}古典的（または非量子）アルゴリズムは、有限の命令シーケンス、または問題を解決するためのステップバイステップの手順であり、各ステップまたは命令は古典的コンピュータで実行できます。同様に、量子アルゴリズムはステップバイステップの手順であり、各ステップは量子コンピュータで実行できます。すべての古典的アルゴリズムは量子コンピュータでも実行できますが、^{[3] ：126}量子アルゴリズムという用語は一般に、本質的に量子的であると思われるアルゴリズム、または量子重ね合わせや量子もつれ などの量子コンピューティングの重要な機能を使用するアルゴリズムに対して使用されます。

古典的コンピュータでは決定できない問題は、量子コンピュータでも決定できないままです。 ^{[4] : 127}量子アルゴリズムが興味深いのは、量子アルゴリズムが利用する量子重ね合わせと量子もつれは一般に古典的コンピュータでは効率的にシミュレートできないため、一部の問題を古典的アルゴリズムよりも速く解決できる可能性があるということです（量子優位性を参照）。

最もよく知られているアルゴリズムは、因数分解のためのショアのアルゴリズムと、非構造化データベースまたは順序なしリストを検索するためのグローバーのアルゴリズムです。ショアのアルゴリズムは、因数分解のための最もよく知られている古典的なアルゴリズムである一般数体ふるいよりもはるかに（ほぼ指数関数的に）高速に実行されます。^[5]グローバーのアルゴリズムは、同じタスクに対する最良の古典的なアルゴリズムである線形検索^[6]よりも2乗的に高速に実行されます。

量子アルゴリズムは、一般的に使用される量子計算の回路モデルでは、いくつかの入力量子ビットに作用し、測定で終了する量子回路によって記述されるのが一般的です。量子回路は単純な量子ゲートで構成され、各量子ゲートは有限数の量子ビットに作用します。量子アルゴリズムは、ハミルトンオラクルモデルなど、他の量子計算モデルで記述されることもあります。^[7]

量子アルゴリズムは、アルゴリズムに含まれる主な技術によって分類できます。量子アルゴリズムでよく使用される技術/アイデアには、位相キックバック、位相推定、量子フーリエ変換、量子ウォーク、振幅増幅、位相量子場理論などがあります。量子アルゴリズムは、解決する問題の種類によってグループ化することもできます。たとえば、代数問題に対する量子アルゴリズムの調査を参照してください。^[8]

量子フーリエ変換は離散フーリエ変換の量子版であり、いくつかの量子アルゴリズムで使用されている。アダマール変換も、体F ₂上の n 次元ベクトル空間上の量子フーリエ変換の例である。量子フーリエ変換は、多項式数の量子ゲートのみを使用して量子コンピュータで効率的に実装できる。^[要出典]

Deutsch-Jozsa アルゴリズムは、ブラック ボックスの問題を解決します。このブラック ボックスの問題は、任意の決定論的古典コンピュータでは指数関数的に多くのクエリが必要ですが、量子コンピュータでは 1 回のクエリで解決できます。ただし、制限誤差の古典アルゴリズムと量子アルゴリズムを比較すると、古典的な確率アルゴリズムは、小さなエラー確率で定数回のクエリで問題を解決できるため、高速化はありません。このアルゴリズムは、関数fが定数 (すべての入力で 0 またはすべての入力で 1) か、バランスが取れている (入力ドメインの半分で 1 を返し、残りの半分で 0 を返す) かを判断します。

Bernstein-Vazirani アルゴリズムは、最もよく知られている古典的なアルゴリズムよりも効率的に問題を解決する最初の量子アルゴリズムです。このアルゴリズムは、BQPとBPPの間にオラクル分離を作成するために設計されました。

Simon のアルゴリズムは、制限誤差確率アルゴリズムを含む従来のアルゴリズムよりも指数関数的に高速にブラック ボックス問題を解決します。効率的であると考えられる従来のアルゴリズムすべてよりも指数関数的に高速化するこのアルゴリズムは、Shor の因数分解アルゴリズムの動機となりました。

量子位相推定アルゴリズムは、固有ベクトルに比例する量子状態とゲートへのアクセスが与えられた場合に、ユニタリ ゲートの固有ベクトルの固有位相を決定するために使用されます。このアルゴリズムは、他のアルゴリズムのサブルーチンとして頻繁に使用されます。

ショアのアルゴリズムは離散対数問題と整数因数分解問題を多項式時間で解きます。^[9]一方、最もよく知られている古典的なアルゴリズムは超多項式時間かかります。これらの問題はP完全またはNP完全ではないことが知られています。また、ショアのアルゴリズムは非ブラックボックス問題を多項式時間で解く数少ない量子アルゴリズムの1つです。最もよく知られている古典的なアルゴリズムは超多項式時間で実行されます。

アーベル隠れ部分群問題は、サイモンの問題、ペル方程式の解、環 R の主イデアルのテスト、因数分解など、量子コンピュータで解ける多くの問題を一般化したものです。アーベル隠れ部分群問題には、効率的な量子アルゴリズムが知られています。[ 10 ^]より一般的な隠れ部分群問題 (群は必ずしもアーベルではありませんが) は、前述の問題のほか、グラフ同型性や特定の格子問題の一般化です。効率的な量子アルゴリズムは、特定の非アーベル群に対して知られています。しかし、グラフ同型性^[11]の効率的なアルゴリズムを与える対称群や、特定の格子問題 を解く二面体群に対する効率的なアルゴリズムは知られていません。 ^[12]

ガウス和は指数和の一種である。これらの和を推定する最もよく知られている古典的なアルゴリズムは指数時間を要する。離散対数問題はガウス和の推定に帰着するため、ガウス和を推定する効率的な古典的なアルゴリズムは離散対数を計算する効率的な古典的なアルゴリズムを意味するが、これはありそうにない。しかし、量子コンピュータはガウス和を多項式精度で多項式時間で推定することができる。^[13]

nビットの文字列をブール値にマッピングするn個のランダムなブール関数からなるオラクルを考えてみましょう。その目的は、アダマール・フーリエ変換において、少なくとも3/4の文字列が次の式を満たすようなn nビットの文字列z 1 , _... , z _{n を}見つけることです 。

${\displaystyle |{\チルダ {f}}(z_{i})|\geqslant 1}$

少なくとも1/4は満足している

${\displaystyle |{\チルダ {f}}(z_{i})|\geqslant 2.}$

これは、限界誤差量子多項式時間（BQP）で実行できます。 ^[14]

振幅増幅は、量子状態の選択された部分空間の増幅を可能にする技術です。振幅増幅の応用は、通常、対応する古典的なアルゴリズムよりも2倍の速度向上をもたらします。これは、グローバーのアルゴリズムの一般化と考えることができます。^{[引用が必要]}

グローバーのアルゴリズムは、従来必要とされるクエリの代わりにクエリのみを使用して、N個のエントリを持つ非構造化データベース（または順序なしリスト）からマークされたエントリを検索します。 ^[15]従来、制限誤差の確率アルゴリズムを許可する場合でもクエリが必要です。 ${\displaystyle O({\sqrt {N}})}$${\displaystyle O({N})}$${\displaystyle O({N})}$

理論家たちは、ボーム力学における隠れた変数の履歴にアクセスできる標準的な量子コンピュータの仮説的な一般化を検討した。（そのようなコンピュータは完全に仮説的なものであり、標準的な量子コンピュータではないし、量子力学の標準理論の下では不可能でさえある。）そのような仮説的なコンピュータは、最大でステップ数でN項目のデータベースの検索を実装することができる。これは、グローバーのアルゴリズムが実行するステップ数よりもわずかに速い。しかし、どちらの検索方法でも、どちらのモデルの量子コンピュータでもNP完全問題を多項式時間で解くことはできない。 ^[16]${\displaystyle O({\sqrt[{3}]{N}})}$${\displaystyle O({\sqrt {N}})}$

量子カウンティングは、検索問題の一般化を解決します。これは、順序なしリスト内のマークされたエントリが存在するかどうかを単に検出するのではなく、その数を数える問題を解決します。具体的には、クエリのみを実行して、最大 の誤差で要素リスト内のマークされたエントリの数をカウントします。ここで、 はリスト内のマークされた要素の数です。^{[17] [18]}より正確には、アルゴリズムはマークされたエントリの数 の推定値を の精度で出力します。 ${\displaystyle N}$${\displaystyle \epsilon }$${\displaystyle \Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)}$${\displaystyle k}$${\displaystyle k'}$${\displaystyle k}$${\displaystyle |kk'|\leq \varepsilon k}$

量子ウォークは、古典的なランダムウォークの量子的な類似物です。古典的なランダムウォークは、いくつかの状態にわたる確率分布で記述できますが、量子ウォークは、状態にわたる量子重ね合わせで記述できます。量子ウォークは、いくつかのブラックボックス問題に対して指数関数的な高速化をもたらすことが知られています。^{[19] [20]}また、多くの問題に対して多項式的な高速化を提供します。量子ウォークアルゴリズムを作成するためのフレームワークが存在し、多目的なツールです。^[21]

実験構成におけるボソンサンプリング問題では^{、[22]中程度の数の}ボソン（光子など）の入力が、定義されたユニタリー性によって制約された多数の出力モードにランダムに散乱されることを前提としています。個々の光子が使用される場合、問題は多光子量子ウォークと同型です。^[23]この場合の問題は、ボソンの入力配置とユニタリー性に依存する出力の確率分布の公平なサンプルを生成することです。 ^[24]この問題を古典的なコンピューターアルゴリズムで解くには、ユニタリー変換行列のパーマネントを計算する必要がありますが、これには非常に長い時間がかかるか、まったく不可能な場合があります。2014年には、^{[25]既存の技術と単一光子状態を生成する標準的な確率的方法を適切な量子計算可能な}線形光ネットワークへの入力として使用でき、出力確率分布のサンプリングは量子アルゴリズムを使用した方が明らかに優れていることが提案されました。 2015年の調査では^{[26] 、サンプリング問題は}フォック状態の光子以外の入力に対しても同様の複雑さを持つことが予測され、コヒーレント振幅入力の大きさに応じて、計算複雑さが古典的にシミュレーション可能なものからボソンサンプリング問題と同じくらい困難なものへと移行することが確認されました。

要素の個別性問題は、リストのすべての要素が個別であるかどうかを判断する問題です。 従来、サイズのリストにはクエリが必要ですが、量子コンピュータのクエリで解決できます。 最適なアルゴリズムはAndris Ambainisによって提案され、^[27] Yaoyun Shiは、範囲のサイズが十分に大きい場合に厳しい下限を初めて証明しました。^[28] Ambainis ^[29]とKutin ^[30]は独立して（異なる証明を介して）その作業を拡張し、すべての関数の下限を取得しました。 ${\displaystyle \Omega (N)}$${\displaystyle N}$${\displaystyle \Theta (N^{2/3})}$

三角形発見問題は、与えられたグラフに三角形（サイズ3のクリーク）が含まれているかどうかを判断する問題です。量子アルゴリズムの最もよく知られている下限はですが、知られている最良のアルゴリズムはO( N ^1.297 )回のクエリを必要とし、^{[31]これまでの最良のO(} N ^1.3 )回のクエリよりも改善されています。 ^{[21] [32]}${\displaystyle \Omega (N)}$

式は、各内部ノードにゲートがあり、各リーフ ノードに入力ビットがあるツリーです。問題は、入力へのオラクル アクセスを与えられた状態で、ルート ノードの出力である式を評価することです。

よく研究されている公式は、NANDゲートのみを持つバランスのとれた二分木です。^[33]このタイプの公式は、ランダム性を使用したクエリを必要とします。 ^[34]ただし、量子アルゴリズムを使用すると、クエリで解決できます。この場合のより優れた量子アルゴリズムは、非従来型のハミルトンオラクルモデル用のアルゴリズムが見つかるまで知られていませんでした。^[7]すぐに標準設定でも同じ結果が得られました。^[35]${\displaystyle \Theta (N^{c})}$${\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754}$${\displaystyle \Theta (N^{1/2})}$

より複雑な数式に対する高速量子アルゴリズムも知られている。^[36]

問題は、k個の生成子によって与えられたブラックボックス群が可換であるかどうかを判断することです。ブラックボックス群とは、群演算 (乗算、反転、恒等式との比較) を実行するために使用する必要があるオラクル関数を持つ群です。このコンテキストで重要なのは、クエリの複雑性、つまり問題を解くために必要なオラクル呼び出しの数です。決定論的クエリの複雑性とランダム化クエリの複雑性は、それぞれとです。^[37]量子アルゴリズムはクエリを必要としますが、最もよく知られている古典的アルゴリズムはクエリを使用します。^[38]${\displaystyle \Theta (k^{2})}$${\displaystyle \Theta (k)}$${\displaystyle \Omega (k^{2/3})}$${\displaystyle O(k^{2/3}\log k)}$

計算量クラス BQP（限界誤差量子多項式時間）は、すべてのインスタンスに対してエラー確率が最大1/3で、量子コンピュータが多項式時間で解ける決定問題の集合である。 ^{[39]これは古典的な計算量クラス}BPPの量子版である。

問題がBQP完全であるとは、それがBQPにあり、 BQPのどの問題も多項式時間でその問題に簡約できる場合です。非公式には、 BQP完全な問題のクラスは、 BQPの最も難しい問題と同じくらい難しく、それ自体が量子コンピュータによって効率的に解決できる問題です (制限された誤差で)。

ウィッテンは、チャーン・サイモンズの 位相量子場理論（TQFT）がジョーンズ多項式で解けることを示した。量子コンピュータはTQFTをシミュレートし、それによってジョーンズ多項式を近似することができるが^[40]、我々の知る限り、最悪のシナリオでは古典的に計算することは困難である。^[要出典]

量子コンピュータが古典コンピュータよりも強力であるかもしれないという考えは、古典コンピュータは多粒子量子システムをシミュレートするのに指数関数的な時間を必要とするように見えるが、量子多体系は「自己解決」できるというリチャード・ファインマンの観察に端を発している。^{[41]それ以来、量子コンピュータは古典コンピュータよりも指数関数的に高速に量子物理プロセスをシミュレートできるという考えは、大きく具体化され、精緻化されてきた。ボソン系とフェルミオン系の両方をシミュレートするための効率的な（つまり多項式時間）量子アルゴリズムが開発されており、 [42]}数百キュービットしか使用しない現在の古典スーパーコンピュータの能力を超える化学反応のシミュレーションも行われている。^[43]量子コンピュータは、位相量子場理論も効率的にシミュレートできる。^[44]この結果は、その本質的な興味に加えて、ジョーンズ^[45]やHOMFLY多項式^{[46 ]、3次元多様体のTuraev-Viro不変量[47} ]などの量子位相不変量を推定するための効率的な量子アルゴリズムにつながりました。

2009年、アラム・ハロー、アビナタン・ハシディム、セス・ロイドは、線形システムを解くための量子アルゴリズムを策定した。このアルゴリズムは、与えられた線形方程式の解ベクトルに対するスカラー測定の結果を推定する。^[48]

線形システムがスパースで条件数 が低く、ユーザーが解ベクトルのスカラー測定の結果 (解ベクトル自体の値ではなく) に関心がある場合、アルゴリズムの実行時間は になります。ここで、 は線形システムの変数の数です。これにより、 で(または半正定値行列の場合)実行される最も高速な従来のアルゴリズムに比べて指数関数的に高速化されます。 ${\displaystyle \kappa }$${\displaystyle O(\log(N)\kappa ^{2})}$${\displaystyle N}$${\displaystyle O(N\kappa )}$${\displaystyle O(N{\sqrt {\kappa }})}$

ハイブリッド量子/古典アルゴリズムは、量子状態の準備と測定を古典的な最適化と組み合わせたものです。^[49]これらのアルゴリズムは一般に、エルミート演算子の基底状態の固有ベクトルと固有値を決定することを目的としています。

量子近似最適化アルゴリズムは量子アニーリングからヒントを得て、量子回路を使用して量子アニーリングの離散近似を実行します。グラフ理論の問題を解くために使用できます。^[50]このアルゴリズムは、量子演算の古典的な最適化を利用して「目的関数」を最大化します。

変分量子固有値解析（VQE）アルゴリズムは、古典的な最適化を適用して、分子のハミルトニアンなどのエルミート演算子の基底状態を見つけるための仮説状態のエネルギー期待値を最小化する。 ^[51]また、分子ハミルトニアンの励起エネルギーを見つけるために拡張することもできる。^[52]

縮約量子固有値ソルバー（CQE）アルゴリズムは、シュレーディンガー方程式を2個（またはそれ以上）の電子空間に縮約（または投影）した残差を最小化し、分子の基底状態または励起状態のエネルギーと2電子縮約密度行列を求めます。^[53] これは、反エルミート縮約シュレーディンガー方程式から直接エネルギーと2電子縮約密度行列を解く古典的な方法に基づいています。^[54]

• 量子機械学習
• 量子最適化アルゴリズム
• 量子ソート
• 素数判定テスト

• 量子アルゴリズム動物園: 既知の最速の古典的アルゴリズムよりも高速な量子アルゴリズムの包括的なリスト。
• アンドリュー・チャイルズの量子アルゴリズムに関する講義ノート
• 量子探索アルゴリズム - ブルートフォース 2018 年 9 月 1 日にWayback Machineにアーカイブされました。

• Dalzell, Alexander M.; et al. (2023). 「量子アルゴリズム: アプリケーションとエンドツーエンドの複雑性の調査」. arXiv : 2310.03011 [quant-ph].
• Smith, J.; Mosca, M. ( 2012). 「量子コンピュータのアルゴリズム」。自然コンピューティングハンドブック。pp. 1451–1492。arXiv : 1001.0767。doi : 10.1007 / 978-3-540-92910-9_43。ISBN 978-3-540-92909-3. S2CID  16565723。
• Childs, AM; Van Dam, W. (2010). 「代数問題に対する量子アルゴリズム」.現代物理学レビュー. 82 (1): 1–52. arXiv : 0812.0380 . Bibcode :2010RvMP...82....1C. doi :10.1103/RevModPhys.82.1. S2CID  119261679.