量子アルゴリズム

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

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

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

概要

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

量子アルゴリズムは、アルゴリズムに用いられる主要な手法によって分類できます。量子アルゴリズムで一般的に用いられる手法／概念としては、位相キックバック、位相推定、量子フーリエ変換、量子ウォーク、振幅増幅、位相量子場理論などが挙げられます。量子アルゴリズムは、解く問題の種類によっても分類できます。例えば、代数問題に対する量子アルゴリズムの概説を参照してください。^[8]

量子フーリエ変換に基づくアルゴリズム

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

ドイチュ・ジョザアルゴリズム

ドイチュ・ジョザアルゴリズム

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

バーンスタイン・ヴァジラニアルゴリズム

バーンスタイン・ヴァジラニアルゴリズムは、最もよく知られている古典アルゴリズムよりも効率的に問題を解く最初の量子アルゴリズムです。このアルゴリズムは、BQPとBPPの間にオラクル分離を生み出すために設計されました。

サイモンのアルゴリズム

サイモンのアルゴリズムは、ブラックボックス問題を、限界誤差確率アルゴリズムを含むあらゆる古典的アルゴリズムよりも指数関数的に高速に解きます。このアルゴリズムは、効率的と考えられるあらゆる古典的アルゴリズムよりも指数関数的な高速化を実現しており、ショアの因数分解アルゴリズムの着想の源となりました。

量子位相推定アルゴリズム

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

ショアのアルゴリズム

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

隠れたサブグループ問題

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

ガウス和の推定

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

フーリエフィッシングとフーリエチェック

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

${\displaystyle |{\tilde {f}}(z_{i})|\geqslant 1}$

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

${\displaystyle |{\tilde {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 \varepsilon }$ ${\displaystyle \Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)}$ ${\displaystyle k}$ ${\displaystyle k'}$ ${\displaystyle k}$ ${\displaystyle |k-k'|\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})}$

三角形を見つける問題

三角形検索問題とは、 N個の頂点を持つグラフに三角形（サイズ 3 のクリーク）が含まれているかどうかを判定する問題です。グラフの隣接行列にオラクルからアクセスできる場合、古典的なクエリ複雑度は です。これは、三角形が 1 つだけのグラフの場合、任意のエッジを見つけるために必要なクエリ複雑度が だからです。一方、量子アルゴリズムの場合、下限は で、グローバーのアルゴリズムで任意のエッジを見つけるために必要なクエリ数です。ただし、任意のエッジを見つけても、三角形が存在する場合にその三角形が見つかるとは限りません。すべての潜在的な三角形に対してグローバー検索を実行すれば問題は解決しますが、クエリ複雑度 O( N ^3/2 ) は改善可能です。^[31]${\displaystyle \Theta (N^{2})}$ ${\displaystyle \Omega (N)}$ ${\displaystyle \Theta (N^{3})}$

は量子アルゴリズムの最もよく知られている下限値のままであるが、知られている最良のアルゴリズムはO( N5 ^/4 )回のクエリを必要とし、^{[32]これまでの最良のO(} N1.3 )回^のクエリよりも改善されている。^{[21] [33]}${\displaystyle \Omega (N)}$

式の評価

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

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

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

群の可換性

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

BQP完全問題

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

ある問題がBQP完全であるとは、 BQPに属す問題であり、 BQPの任意の問題が多項式時間でその問題に帰着できる場合を言う。非公式には、BQP完全問題とは、 BQPにおける最も難しい問題と同程度に難しく、かつ量子コンピュータによって（誤差が制限された状態で）効率的に解ける問題を指す。

結び目の不変量の計算

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

量子シミュレーション

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

線形方程式を解く

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

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

ハイブリッド量子/古典アルゴリズム

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

QAOA

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

変分量子固有ソルバー

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

縮約量子固有値解析

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

参照

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

参考文献

1. ニールセン, マイケル・A. ;チュアン, アイザック・L. (2000). 『量子計算と量子情報』ケンブリッジ大学出版局. ISBN 978-0-521-63503-5。
2. Mosca, M. (2008). 「量子アルゴリズム」. arXiv : 0808.0369 [quant-ph].
3. ランザゴルタ, マルコ; ウルマン, ジェフリー・K. (2009年1月1日). 量子コンピュータサイエンス. Morgan & Claypool Publishers. ISBN 978-1-59829-732-4。
4. ニールセン, マイケル・A. ;チュアン, アイザック・L. (2010). 『量子計算と量子情報』（第2版）. ケンブリッジ: ケンブリッジ大学出版局. ISBN 978-1-107-00217-3。
5. “Shor's algorithm”. 2023年1月12日時点のオリジナルよりアーカイブ。2020年10月21日閲覧。
6. 「IBM quantum composer ユーザーガイド：グローバーのアルゴリズム」. quantum-computing.ibm.com . 2022年9月27日時点のオリジナルよりアーカイブ。 2022年6月7日閲覧。
7. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2008). 「ハミルトンNANDツリーのための量子アルゴリズム」.コンピューティング理論. 4 : 169–190 . arXiv : quant-ph/0702144 . doi : 10.4086/toc.2008.v004a008 .
8. Childs, Andrew M. ; van Dam, W. (2010). 「代数問題のための量子アルゴリズム」Reviews of Modern Physics . 82 (1): 1– 52. arXiv : 0812.0380 . Bibcode :2010RvMP...82....1C. doi :10.1103/RevModPhys.82.1. S2CID  119261679.
9. Shor, PW (1997). 「量子コンピュータにおける素因数分解と離散対数のための多項式時間アルゴリズム」. SIAM Journal on Scientific and Statistical Computing . 26 (5): 1484– 1509. arXiv : quant-ph/9508027 . Bibcode :1995quant.ph..8027S. doi :10.1137/s0097539795293172. S2CID  2337707.
10. Boneh, D.; Lipton, RJ (1995). 「隠れた線形関数の量子暗号解析」. Coppersmith, D. (編). Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology . Springer-Verlag . pp.  424– 437. ISBN 3-540-60221-6。
11. Moore, C. ; Russell, A. ; Schulman, LJ (2005). 「対称群は強フーリエサンプリングの限界を示す：パートI」. arXiv : quant-ph/0501056 .
12. Regev, O. (2003). 「量子計算と格子問題」. arXiv : cs/0304005 .
13. van Dam, W.; Seroussi, G. (2002). 「ガウス和を推定するための効率的な量子アルゴリズム」. arXiv : quant-ph/0207131 .
14. Aaronson, S. (2009). 「BQPと多項式階層」. arXiv : 0910.4698 [quant-ph].
15. Grover, Lov K. (1996). 「データベース検索のための高速量子力学アルゴリズム」. arXiv : quant-ph/9605043 .
16. アーロンソン、スコット「量子コンピューティングと隠れた変数」（PDF）。
17. Brassard, G.; Hoyer, P.; Tapp, A. (1998). 「量子計数」.オートマトン、言語、プログラミング. コンピュータサイエンス講義ノート. 第1443巻. pp.  820– 831. arXiv : quant-ph/9805082 . doi :10.1007/BFb0055105. ISBN  978-3-540-64781-2. S2CID  14147978。
18. Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A. (2002). 「量子振幅増幅と推定」. Samuel J. Lomonaco, Jr. (編).量子計算と量子情報. AMS Contemporary Mathematics. Vol. 305. pp.  53– 74. arXiv : quant-ph/0005055 . Bibcode :2000quant.ph..5055B. doi :10.1090/conm/305/05215. ISBN  978-0-8218-2140-4. S2CID  54753。
19. Childs, AM; Cleve, R.; Deotto, E.; Farhi, E.; Gutmann, S.; Spielman, DA (2003). 「量子ウォークによる指数関数的アルゴリズム高速化」.第35回計算理論シンポジウム論文集. Association for Computing Machinery . pp.  59– 68. arXiv : quant-ph/0209131 . doi :10.1145/780542.780552. ISBN  1-58113-674-9。
20. Childs, AM; Schulman, LJ; Vazirani, UV (2007). 「隠れた非線形構造のための量子アルゴリズム」.第48回IEEEコンピュータサイエンス基礎シンポジウム議事録. IEEE . pp.  395– 404. arXiv : 0705.2784 . doi :10.1109/FOCS.2007.18. ISBN  978-0-7695-3010-9。
21. Magniez, F.; Nayak, A.; Roland, J.; Santha, M. (2007). 「量子ウォークによる探索」.第39回ACM計算理論シンポジウム議事録. Association for Computing Machinery . pp.  575– 584. arXiv : quant-ph/0608026 . doi :10.1145/1250790.1250874. ISBN  978-1-59593-631-8。
22. Ralph, TC (2013年7月). 「図1：ボソンサンプリング問題」 . Nature Photonics . 7 (7). Nature: 514– 515. doi :10.1038/nphoton.2013.175. S2CID  110342419. 2014年9月12日閲覧。
23. ペルッツォ、アルベルト;ロビノ、ミルコ。マシューズ、ジョナサンCF。松田宣之；ポリティ、アルベルト。ポリオス、コンスタンティノス。周、シャオチー。ラヒニ、ヨアヴ。イスマイル、ヌール。ヴェルホフ、カースティン。ブロンバーグ、ヤロン。ヤロン、シルバーバーグ。トンプソン、マーク G.ジェレミー・L・オブライエン（2010年9月17日）。 「相関光子の量子ウォーク」。科学。329 ( 5998) : 1500–1503。arXiv : 1006.4764 。Bibcode :2010Sci...329.1500P。土井：10.1126/science.11​​93515。hdl :10072/53193。ISSN  0036-8075. PMID  20847264. S2CID  13896075.
24. Lund, AP; Laing, A.; Rahimi-Keshari, S.; Rudolph, T.; O'Brien, JL; Ralph, TC (2014年9月5日). 「ガウス状態からのボソンサンプリング」. Phys. Rev. Lett . 113 (10) 100502. arXiv : 1305.4346 . Bibcode :2014PhRvL.113j0502L. doi :10.1103/PhysRevLett.113.100502. PMID  25238340. S2CID  27742471.
25. 「量子革命は一歩近づいた」Phys.org . Omicron Technology Limited . 2014年9月12日閲覧。
26. Seshadreesan, Kaushik P.; Olson, Jonathan P.; Motes, Keith R.; Rohde, Peter P.; Dowling, Jonathan P. (2015). 「変位した単一光子フォック状態と単一光子付加コヒーレント状態によるボソンサンプリング：線形光学における量子論的・古典論的分岐と計算複雑度の遷移」. Physical Review A. 91 ( 2) 022334. arXiv : 1402.0531 . Bibcode :2015PhRvA..91b2334S. doi :10.1103/PhysRevA.91.022334. S2CID  55455992.
27. Ambainis, A. (2007). 「要素の識別性のための量子ウォークアルゴリズム」. SIAM Journal on Computing . 37 (1): 210– 239. arXiv : quant-ph/0311001 . doi :10.1137/S0097539705447311. S2CID  6581885.
28. Shi, Y. (2002). 「衝突問題と要素の区別問題における量子下限値」.第43回IEEEコンピュータサイエンス基礎シンポジウム, 2002. Proceedings . Proceedings of the 43rd Symposium on Foundations of Computer Science . pp.  513– 519. arXiv : quant-ph/0112086 . doi :10.1109/SFCS.2002.1181975. ISBN  0-7695-1822-2。
29. Ambainis, A. (2005). 「量子計算量における多項式次数と下限値：小範囲における衝突と要素の区別」.計算理論. 1 (1): 37– 46. doi : 10.4086/toc.2005.v001a003 .
30. Kutin, S. (2005). 「小範囲衝突問題に対する量子下界」.計算理論. 1 (1): 29– 36. doi : 10.4086/toc.2005.v001a002 .
31. Li, Guanzhong; Li, Lvzhou (2025年5月). 「三角形探索のための量子アルゴリズムのデランダム化」. Information and Computation . 304 : 105295. doi :10.1016/j.ic.2025.105295. ISSN  0890-5401.
32. Le Gall, François (2014年10月)、「組み合わせ論的議論による三角形探索のための改良量子アルゴリズム」、第55回コンピュータサイエンス基礎シンポジウム (FOCS 2014) の議事録、IEEE、pp.  216– 225、arXiv : 1407.0085、doi :10.1109/focs.2014.31、ISBN 978-1-4799-6517-5、S2CID  5760574
33. Magniez, F.; Santha, M.; Szegedy, M. (2007). 「三角形問題に対する量子アルゴリズム」. SIAM Journal on Computing . 37 (2): 413– 424. arXiv : quant-ph/0310134 . doi :10.1137/050643684. S2CID  594494.
34. Aaronson, S. (2007年2月3日). 「NANDは今、全く異なるものへ」. Shtetl-Optimized . 2009年12月17日閲覧。
35. Saks, ME; Wigderson, A. (1986). 「確率的ブール決定木とゲーム木評価の複雑さ」(PDF) .第27回コンピュータサイエンス基礎シンポジウム議事録. IEEE . pp.  29– 38. doi :10.1109/SFCS.1986.44. ISBN  0-8186-0740-8。
36. Ambainis, A. (2007). 「NAND式を評価するためのほぼ最適な離散クエリ量子アルゴリズム」. arXiv : 0704.3628 [quant-ph].
37. Reichardt, BW; Spalek, R. (2008). 「式を評価するためのスパンプログラムベースの量子アルゴリズム」.第40回ACM計算理論シンポジウム議事録. Association for Computing Machinery . pp.  103– 112. arXiv : 0710.2630 . doi :10.1145/1374376.1374394. ISBN  978-1-60558-047-0。
38. Pak, Igor (2012). 「群の可換性の検証とランダム化の威力」. LMS Journal of Computation and Mathematics . 15 : 38–43 . doi : 10.1112/S1461157012000046 .
39. Magniez, F.; Nayak, A. (2007). 「群の可換性検証の量子計算量」. Algorithmica . 48 (3): 221– 232. arXiv : quant-ph/0506265 . doi :10.1007/s00453-007-0057-8. S2CID  3163328.
40. マイケル・ニールセン、アイザック・チュアン (2000).『量子計算と量子情報』 ケンブリッジ: ケンブリッジ大学出版局. ISBN 0-521-63503-9。
41. Aharonov, D.; Jones, V.; Landau, Z. (2006). 「ジョーンズ多項式を近似する多項式量子アルゴリズム」.第38回ACM計算理論シンポジウム議事録. Association for Computing Machinery . pp.  427– 436. arXiv : quant-ph/0511096 . doi :10.1145/1132516.1132579. ISBN  1-59593-134-1。
42. ファインマン, RP (1982). 「コンピュータによる物理学のシミュレーション」.国際理論物理学ジャーナル. 21 ( 6–7 ): 467–488 . Bibcode :1982IJTP...21..467F. CiteSeerX 10.1.1.45.9310 . doi :10.1007/BF02650179. S2CID  124545445.  
43. Abrams, DS; Lloyd, S. (1997). 「汎用量子コンピュータによる多体フェルミ系のシミュレーション」. Physical Review Letters . 79 (13): 2586– 2589. arXiv : quant-ph/9703054 . Bibcode :1997PhRvL..79.2586A. doi :10.1103/PhysRevLett.79.2586. S2CID  18231521.
44. Kassal, I.; Jordan, SP; Love, PJ; Mohseni, M.; Aspuru-Guzik, A. (2008). 「化学ダイナミクスシミュレーションのための多項式時間量子アルゴリズム」. Proceedings of the National Academy of Sciences of the United States of America . 105 (48): 18681–86 . arXiv : 0801.2986 . Bibcode :2008PNAS..10518681K. doi : 10.1073/pnas.0808245105 . PMC 2596249. PMID  19033207 .  
45. Freedman, M.; Kitaev, A.; Wang, Z. (2002). 「量子コンピュータによる位相場理論のシミュレーション」. Communications in Mathematical Physics . 227 (3): 587– 603. arXiv : quant-ph/0001071 . Bibcode :2002CMaPh.227..587F. doi :10.1007/s002200200635. S2CID  449219.
46. Aharonov, D.; Jones, V.; Landau, Z. (2009). 「ジョーンズ多項式を近似するための多項式量子アルゴリズム」. Algorithmica . 55 (3): 395– 421. arXiv : quant-ph/0511096 . doi :10.1007/s00453-008-9168-0. S2CID  7058660.
47. Wocjan, P.; Yard, J. (2008). 「ジョーンズ多項式：量子アルゴリズムと量子複雑性理論への応用」.量子情報・計算. 8 (1): 147– 180. arXiv : quant-ph/0603069 . Bibcode :2006quant.ph..3069W. doi :10.26421/QIC8.1-2-10. S2CID  14494227.
48. Alagic, G.; Jordan, SP; König, R.; Reichardt, BW (2010). 「Turaev-Viro 3次元多様体不変量の近似は量子計算において普遍的である」. Physical Review A. 82 ( 4) 040302. arXiv : 1003.0923 . Bibcode :2010PhRvA..82d0302A. doi :10.1103/PhysRevA.82.040302. S2CID  28281402.
49. Harrow, Aram W; Hassidim, Avinatan; Lloyd, Seth (2008). 「線形方程式系を解くための量子アルゴリズム」. Physical Review Letters . 103 (15) 150502. arXiv : 0811.3171 . Bibcode :2009PhRvL.103o0502H. doi :10.1103/PhysRevLett.103.150502. PMID :  19905613. S2CID  : 5187993.
50. Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S.; Chow, Jerry M.; Cross, Andrew; Egger, Daniel J.; Filipp, Stefan; Fuhrer, Andreas; Gambetta, Jay M.; Ganzhorn, Marc; Kandala, Abhinav; Mezzacapo, Antonio; Müller, Peter; Riess, Walter; Salis, Gian; Smolin, John; Tavernelli, Ivano; Temme, Kristan (2018). 「近未来の量子デバイスにおける変分アルゴリズムを用いた量子最適化」.量子科学技術. 3 (3): 030503. arXiv : 1710.01022 . Bibcode :2018QS&T....3c0503M. doi :10.1088/2058-9565/aab822. S2CID  56376912.
51. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014年11月14日). 「量子近似最適化アルゴリズム」. arXiv : 1411.4028 [quant-ph].
52. Peruzzo, Alberto; McClean, Jarrod; Shadbolt, Peter; Yung, Man-Hong; Zhou, Xiao-Qi; Love, Peter J.; Aspuru-Guzik, Alán; O'Brien, Jeremy L. (2014年7月23日). 「光子量子プロセッサにおける変分固有値ソルバー」. Nature Communications . 5 (1): 4213. arXiv : 1304.3061 . Bibcode :2014NatCo...5.4213P. doi :10.1038/ncomms5213. ISSN  2041-1723. PMC 4124861. PMID 25055053  . 
53. Higgott, Oscar; Wang, Daochen; Brierley, Stephen (2019). 「励起状態の変分量子計算」. Quantum . 3.156 . arXiv : 1805.08138 . Bibcode :2019Quant...3..156H. doi :10.22331/q-2019-07-01-156. S2CID  119185497.
54. Smart, Scott; Mazziotti, David (2021年2月18日). 「量子コンピューティングデバイス上でのスケーラブルな分子シミュレーションのための縮約固有値方程式の量子ソルバー」. Phys. Rev. Lett . 125 (7) 070504. arXiv : 2004.11416 . Bibcode :2021PhRvL.126g0504S. doi :10.1103/PhysRevLett.126.070504. PMID:  33666467. S2CID  : 216144443.
55. Mazziotti, David (2006年10月6日). 「反エルミート縮約シュレーディンガー方程式：多電子分子の2電子縮約密度行列の直接決定」. Phys. Rev. Lett . 97 (14) 143002. Bibcode :2006PhRvL..97n3002M. doi :10.1103/PhysRevLett.97.143002. PMID  17155245.

外部リンク

• 量子アルゴリズム動物園: 既知の最速の古典的アルゴリズムよりも高速化を実現する量子アルゴリズムの包括的なリスト。
• アンドリュー・チャイルズの量子アルゴリズムに関する講義ノート
• 量子探索アルゴリズム - ブルートフォース Archived 1 September 2018 at the Wayback Machine .
• http://computetube.de/#quantum 擬似コード

調査

• Dalzell, Alexander M.; et al. (2025).量子アルゴリズム. arXiv : 2310.03011 . doi :10.1017/9781009639651. ISBN 978-1-009-63965-1。
• 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). 「代数問題のための量子アルゴリズム」Reviews of Modern Physics . 82 (1): 1– 52. arXiv : 0812.0380 . Bibcode :2010RvMP...82....1C. doi :10.1103/RevModPhys.82.1. S2CID  119261679.