基本的な量子サブルーチン: マークされた複数の要素の検索と数値の合計

【1] スリニヴァサン・アルナーチャラムとロナルド・デ・ウルフ。量子探索におけるゲート数の最適化。量子情報Comput.、17(3-4):251–261、2017。doi:10.26421/ qic17.3-4。
https：/ / doi.org/ 10.26421 / qic17.3-4

【2] ホセ・A・アデルとP・ホドラ。正確なコルモゴロフと、いくつかのよく知られた離散分布間の総変動距離。 Journal of Inequalities and Applications、2006(1):1–8、2006 年。doi:10.1155/JIA/2006/64307。
https:/ / doi.org/ 10.1155/ JIA/ 2006/ 64307

【3] ヨラン・ファン・アペルドールン、サンダー・グリブリング、イーナン・リー、ハロルド・ニューボーア、マイケル・ウォルター、ロナルド・デ・ウルフ。マトリックス スケーリングとマトリックス バランシングのための量子アルゴリズム。第 48 回オートマトン、言語、およびプログラミングに関する国際コロキウム (ICALP'21) の議事録、ボリューム 198、ページ 110:1–110:17、2021。arXiv:2011.12823、doi:10.4230/ LIPIcs.ICALP.2021.110。
https：/ / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv：2011.12823

【4] スコット・アーロンソンとパトリック・ラル。量子近似カウント、簡略化。アルゴリズムの単純さに関するシンポジウム、24 ～ 32 ページ、2020 年。doi:10.1137/ 1.9781611976014.5。
https：/ / doi.org/ 10.1137 / 1.9781611976014.5

【5] ミシェル・ボワイエ、ジル・ブラサール、ピーター・ホワイエ、アラン・タップ。量子検索の限界が狭い。 Fortschritte der Physik、46(4–5):493–505、1998。Physcomp'96 の初期バージョン。 arXiv:quant-ph/9605034。
arXiv：quant-ph / 9605034

【6] ハリー・バーマン、リチャード・クリーブ、ロナルド・デ・ウルフ、クリストフ・ザルカ。小エラーおよびゼロエラーの量子アルゴリズムの境界。第 40 回コンピュータ サイエンスの基礎に関する年次シンポジウム (FOCS'99)、358 ～ 368 ページ。 IEEE コンピュータ協会、1999 年。

【7] ジル・ブラッサール、ピーター・ホイヤー、ミケーレ・モスカ、アラン・タップ。量子振幅の増幅と推定。 『Quantum Computation and Quantum Information: A Millennium Volume』、『現代数学』第 305 巻、53 ～ 74 ページ。アメリカ数学協会、2002 年。doi:10.1002/ (SICI)1521-3978(199806)46:4/ 5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

【8] リチャード・ブレントとポール・ジマーマン。 『Modern Computer Arithmetic』、第 18 巻、ケンブリッジ大学出版局、2010 年。

【9] ラン・カネッティ、ガイ・イーブン、オーデッド・ゴールドライヒ。平均を推定するためのサンプリング アルゴリズムの下限。 Information Processing Letters、53(1):17–25、1995 年 10.1016 月。doi:0020/ 0190-94(00171)XNUMX-T。
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

【10] カルロ・シリベルト、マーク・ハーブスター、アレッサンドロ・ダヴィデ・イアロンゴ、マッシミリアーノ・ポンティル、アンドレア・ロッケット、シモーネ・セヴェリーニ、レナード・ウォスニッヒ。量子機械学習: 古典的な視点。英国王立協会会議録 A: 数学、物理および工学科学、474(2209):20170551、2018 年 10.1098 月。doi:2017.0551/rspa.XNUMX。
https：/ / doi.org/ 10.1098 / rspa.2017.0551

【11] トーマス・H・コーメン、チャールズ・E・ライザーソン、ロナルド・L・リベスト、クリフォード・スタイン。アルゴリズムの紹介。 MIT プレス、第 4 版、2022 年。

【12] P. ディアコニスと D. フリードマン。有限の交換可能なシーケンス。 The Annals of Probability、8(4):745–764、1980。URL: https://www.jstor.org/stable/2242823。
https：/ / www.jstor.org/ stable / 2242823

【13] クリストフ・デュールとピーター・ホイヤー。最小値を見つけるための量子アルゴリズム、1996 年。doi:10.48550/ arXiv.quant-ph/ 9607014。
https：/ / doi.org/ 10.48550 / arXiv.quant-ph / 9607014
arXiv：quant-ph / 9607014

【14] クリストフ・デュール、マーク・ハイリグマン、ピーター・ホイヤー、メディ・マーラ。一部のグラフ問題の量子クエリの複雑さ。 SIAM Journal on Computing、35(6):1310–1328、2006 年 10.1137 月。doi:050644719/ XNUMX。
https：/ / doi.org/ 10.1137 / 050644719

【15] ポール・ダガム、リチャード・カープ、マイケル・ルビー、シェルドン・ロス。モンテカルロ推定の最適アルゴリズム。 SIAM Journal on Computing、29(5):1484–1496、2000 年 10.1137 月。doi:0097539797315306/ SXNUMX。
https：/ / doi.org/ 10.1137 / S0097539797315306

【16] ヴィットリオ・ジョヴァネッティ、セス・ロイド、ロレンツォ・マッコーネ。量子ランダムアクセスメモリ。 Physical Review Letters、100(16)、2008 年 10.1103 月。doi:100.160501/physrevlett.XNUMX。
https：/ / doi.org/ 10.1103 / physrevlett.100.160501

【17] サンダー・グリブリングとハロルド・ニューボーア。行列スケーリングの量子下限と上限が改善されました。第 39 回コンピュータ サイエンスの理論的側面に関する国際シンポジウム (STACS'22) の議事録、219 巻、35:1 ～ 35:23、2022 年。arXiv:2109.15282、doi:10.4230/ LIPIcs.STACS.2022.35。
https：/ / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv：2109.15282

【18] マルト・デ・グラーフとロナルド・デ・ウルフ。ヤオ原理の量子バージョンについて。コンピュータ サイエンスの理論的側面に関する第 19 回シンポジウム (STACS'02)、コンピュータ サイエンスの講義ノートの第 2285 巻、347 ～ 358 ページ、ベルリン、ハイデルベルク、2002 年。Springer。土井:10.1007/ 3-540-45841-7_28。
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

【19] ロブ・K・グローバー。データベース検索のための高速量子力学的アルゴリズム。第 38 回コンピューティング理論に関する年次 ACM シンポジウム (STOC'96) の議事録、212 ～ 219 ページ、1996 年。arXiv:quant-ph/ 9605043、doi:10.1145/ 237814.237866。
https：/ / doi.org/ 10.1145 / 237814.237866
arXiv：quant-ph / 9605043

【20] ロブ・K・グローバー。量子テレコンピューティング、1997 年。ベル研究所技術覚書 ITD97-31630F。 doi:10.48550/arXiv.quant-ph/9704012。
https：/ / doi.org/ 10.48550 / arXiv.quant-ph / 9704012
arXiv：quant-ph / 9704012

【21] ロブ・K・グローバー。高速量子力学的アルゴリズムのためのフレームワーク。コンピューティング理論に関する第 98 回年次 ACM シンポジウム (STOC'53) の議事録、62 ～ 1998 ページ、9711043 年。arXiv:quant-ph/10.1145、doi:276698.276712/XNUMX。
https：/ / doi.org/ 10.1145 / 276698.276712
arXiv：quant-ph / 9711043

【22] ヤシン・ハモウディ。量子サブガウス平均推定器。第 29 回アルゴリズムに関する欧州年次シンポジウム (ESA 2021)、ライプニッツ国際情報学論文集 (LIPIcs) の第 204 巻、50:1–50:17、2021 年。doi:10.4230/ LIPIcs.ESA.2021.50。
https：/ / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

【23] スヴァンテ・ヤンソン。幾何変数と指数変数の合計の裾限界。 Statistics & Probability Letters、135:1–6、2018。doi:10.1016/j.spl.2017.11.017。
https:/ / doi.org/ 10.1016/ j.spl.2017.11.017

【24] ドナルド・アービン・クヌース。コンピューター プログラミングの芸術、第 2 巻。 Addison-Wesley、第 1998 版、312994415 年。URL: https://www.worldcat.org/oclc/XNUMX。
https://www.worldcat.org/oclc/312994415

【25] ロビン・コタリとライアン・オドネル。ソースコードがある場合の平均推定値。または、量子モンテカルロ法。離散アルゴリズムに関する 2023 年度 ACM-SIAM シンポジウム (SODA'23) の議事録、1186 ～ 1215 ページ、2023 年。doi:10.1137/ 1.9781611977554.ch44。
https：/ / doi.org/ 10.1137 / 1.9781611977554.ch44

【26] マイケル・A・ニールセンとアイザック・L・チュアン。 量子計算と量子情報。 ケンブリッジ大学出版局、2002。

【27] アシュウィン・ナヤックとフェリックス・ウー。中央値および関連統計を近似する量子クエリの複雑さ。第 31 回年次 ACM SIGACT Symposium on Theory of Computing (STOC'99) の議事録、384 ～ 393 ページ、1999 年。arXiv:quant-ph/ 9804066、doi:10.1145/ 301250.301349。
https：/ / doi.org/ 10.1145 / 301250.301349
arXiv：quant-ph / 9804066

【28] B.ルース。ポアソン二項分布への二項近似: クローチョーク展開。確率論とその応用、45(2):258–272、2001。doi:10.1137/ S0040585X9797821X。
https:/ / doi.org/ 10.1137/ S0040585X9797821X

【29] ロバート・M・ヤング75.9 オイラー定数。 The Mathematical Gazette、75(472):187–190、1991。doi:10.2307/ 3620251。
https：/ / doi.org/ 10.2307 / 3620251