HHL アルゴリズムを使用して多変量多項式系を解くためのマコーレー行列アプローチの制限

HHL アルゴリズムを使用して多変量多項式系を解くためのマコーレー行列アプローチの制限

タイムスタンプ：26年2023月6日午前40時XNUMX分
ソースノード： 2786385

ジンタイ・ディン1、ヴラド・ゲオルギュウ2、アンドラス・ギリエン3、ショーンハグレン4、李建強4

1シンシナティ大学、オハイオ州、米国
2量子コンピューティング研究所/ウォータールー大学、カナダ、オンタリオ州、組み合わせ論・最適化学科
3量子情報物質研究所、カリフォルニア工科大学、パサデナ、米国
4米国ペンシルバニア州立大学コンピュータサイエンス工学部

この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.

抽象

最近のチェンとガオ [15] は、いくつかのポスト量子暗号システムの暗号解析を動機として、ブール多項式システムを解くための新しい量子アルゴリズムを提案しました。 彼らのアプローチの重要なアイデアは、ブール多項式システムから導出される $mathbb{C}$ 上のマコーレー線形システムに量子線形システム (QLS) アルゴリズムを適用することです。 彼らのアルゴリズムの効率は、マコーレー行列の条件数に依存します。 この論文では、ブール解のハミング重みの関数として条件数に強力な下限を与え、すべてではないにしても多くの場合において、Grover ベースの網羅的検索アルゴリズムがそのアルゴリズムよりも優れていることを示します。 次に、元の Macaulay 線形システムを削減して $mathbb{C}$ に Boolean Macaulay 線形システムを導入することで、Chen と Gao のアルゴリズムを改良します。 この改良されたアルゴリズムは、解のハミング重みがブール変数の数において対数である場合、ブルート フォース アルゴリズムよりも大幅に優れたパフォーマンスを発揮する可能性があります。
さらに、Valiant-Vazirani アフィン ハッシュ法を使用したリダクションを使用して、改良されたアルゴリズムの正確さの単純かつ初歩的な証明を提供し、その結果を $mathbb{F}_q$ 上の多項式システムに拡張して、Chen による後続の研究を改善しました。 、ガオとユアンはChenGao2018を引用しています。 また、量子クーポンコレクター問題の一般化を通じてブール多項式システムの解を抽出するための新しいアプローチも提案します。2].

[埋め込まれたコンテンツ]

►BibTeXデータ

►参照

【1] スコット・アーロンソン。 詳細の閲覧。 自然物理学 Nat. 物理学。 、11(4):291–293、2015。
https：/ / doi.org/ 10.1038 / nphys3272

【2] スリニヴァサン・アルナーチャラム、アレクサンドル・ベロフス、アンドリュー・M・チャイルズ、ロビン・コタリ、アンシス・ロスマニス、ロナルド・デ・ウルフ。 クォンタムクーポンコレクター。 第 15 回量子計算、通信、および暗号理論に関する会議議事録 (TQC) TQC、10:1–10:17、2020 年。arXiv: 2002.07688。
https：/ / doi.org/ 10.4230 / LIPIcs.TQC.2020.10
arXiv：2002.07688

【3] グウェノーレ・アルス、ジャン＝シャルル・フォージェール、今井秀樹、川添充、杉田真。 XL アルゴリズムとグレブナー基底アルゴリズムの比較。 暗号学と情報セキュリティの理論と応用に関する国際会議、338 ～ 353 ページ。 スプリンガー、2004 年。
https:/​/​doi.org/​10.1007/​978-3-540-30539-2_24

【4] アンドリス・アンバイニス。 線形代数問題に対する可変時間振幅増幅および量子アルゴリズム。 第 29 回コンピュータ サイエンスの理論的側面に関するシンポジウム (STACS) の議事録、STACS、636 ～ 647 ページ、2012 年。arXiv: 1010.4458。
https：/ / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
arXiv：1010.4458

【5] エリック・R・アンシュエッツ、ジョナサン・P・オルソン、アラン・アスプル＝グジク、曹裕東。 変分量子因数分解。 arXiv: 1808.08927、2018。
https:/​/​doi.org/​10.1007/​978-3-030-14082-3_7
arXiv：1808.08927

【6] ブルーノ・ブッフベルガーらグレブナーは、マコーレー行列を三角形化することによって計算を基礎とします。 『グレブナー基地 50 周年記念』、25 ～ 33 ページ。 日本数学会、2018.
https:/ / doi.org/ 10.2969/ aspm/ 07710025

【7] キム・バトセリエ。 多変量多項式の問題を解決するための数値線形代数フレームワーク。 博士論文、ルーヴェン大学 (ベルギー、ルーヴェン)、2013 年。
https:/ / doi.org/ 10.13140/ RG.2.1.3137.9608

【8] ミシェル・ボワイエ、ジル・ブラサール、ピーター・ホワイエ、アラン・タップ。 量子検索の限界が狭い。 Fortschritte der Physik、46(4–5):493–505、1998。arXiv: quant-ph/9605034。
<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
arXiv：quant-ph / 9605034

【9] マガリ・バルデ、ジャン＝シャルル・フォージェール、ブルーノ・サルヴィ、ピエール＝ジャン・スパエンルハウアー。 二次ブール系を解く複雑さについて。 ジャーナル・オブ・複雑性、29(1):53–75、2013。
https:/ / doi.org/ 10.1016/ j.jco.2012.07.001

【10] アンドレアス・ビョルクルンド、ペテリ・カスキー、ライアン・ウィリアムズ。 パリティカウント自己縮約による GF(2) 上の多項方程式系の解法。 第 46 回オートマトン、言語、プログラミングに関する国際コロキウム (ICALP) の議事録、ICALP、2019 年。
https：/ / doi.org/ 10.4230 / LIPIcs.ICALP.2019.26

【11] クリストファー・J・C・バージェス。 最適化としての因数分解。 マイクロソフト リサーチ MSR-TR-200、2002 年。

【12] イーサン・バーンスタインとウメシュ・ヴァジラニ。 量子複雑性理論。 コンピューティングに関する SIAM ジャーナル、26(5):1411–1473、1997。
https：/ / doi.org/ 10.1137 / S0097539796300921

【13] ダニエル・J・バーンスタインとボー・イン・ヤン。 多変量二次方程式を解くための漸近的に高速な量子アルゴリズム。 ポスト量子暗号に関する国際会議、487 ～ 506 ページ。 スプリンガー、2018年。
https:/​/​doi.org/​10.1007/​978-3-319-79063-3_23

【14] アレッシオ・カミナータとエリサ・ゴーラ。 可換代数から多変量多項式系と不変式を解きます。 arXiv: 1706.06319、2017。
https:/​/​doi.org/​10.1007/​978-3-030-68869-1_1
arXiv：1706.06319

【15] ユーアオ・チェンとシャオシャン・ガオ。 ブール方程式解法と暗号システムに対する量子代数攻撃のための量子アルゴリズム。 システム科学と複雑性ジャーナル、2021 年。arXiv: 1712.06239。
https:/​/​doi.org/​10.1007/​s11424-020-0028-6
arXiv：1712.06239

【16] シャンタナフ・チャクラボルティ、アンドラーシュ・ギレン、ステイシー・ジェフリー。 ブロックエンコードされた行列累乗の能力: より高速なハミルトニアン シミュレーションによる回帰手法の改善。 第 46 回オートマトン、言語、およびプログラミングに関する国際コロキウム (ICALP) の議事録、ICALP、33:1–33:14、2019 年。arXiv: 1804.01973。
https：/ / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33
arXiv：1804.01973

【17] ナイ・ホイ・チア、アンドラス・ギレン、トンヤン・リー、ハン・シュアン・リン、エウィン・タン、チュンハオ・ワン。 量子機械学習を逆量子化するためのサンプリングベースのサブリニア低ランク行列演算フレームワーク。 第 52 回 ACM コンピューティング理論に関するシンポジウム (STOC) の議事録 STOC、387 ～ 400 ページ、2020 年。arXiv: 1910.06151。
https：/ / doi.org/ 10.1145 / 3357713.3384314
arXiv：1910.06151

【18] ユアオ・チェン、シャオシャン・ガオ、チュンミン・ユアン。 最適化のための量子アルゴリズム、有限体上で解く多項式システム、および暗号解析への応用、2018。arXiv: 1802.03856。
arXiv：1802.03856

【19] B デビッド クレイダー、ブライアン C ジェイコブス、チャド R スプラウス。 事前条件付けされた量子線形システム アルゴリズム。 フィジカルレビューレター、110(25):250504、2013。
https：/ / doi.org/ 10.1103 / PhysRevLett.110.250504

【20] ニコラ・クルトワ、アレクサンダー・クリモフ、ジャック・パタラン、アディ・シャミール。 多変量多項方程式の過剰定義系を解くための効率的なアルゴリズム。 暗号技術の理論と応用に関する国際会議、392 ～ 407 ページ。 Springer、2000 (24 年 2004 月 XNUMX 日時点の拡張版。http://www.minrank.org/xlfull.pdf)。
https:/​/​doi.org/​10.1007/​3-540-45539-6_27
http:// / www.minrank.org/ xlfull.pdf）

【21] アンドリュー・M・チャイルズ、ロビン・コタリ、ロランド・D・ソンマ。 精度への依存性が指数関数的に改善された線形方程式系の量子アルゴリズム。 SIAM Journal on Computing SIAM J. Comp.、46(6):1920–1950、2017。arXiv: 1511.02306。
https：/ / doi.org/ 10.1137 / 16M1087072
arXiv：1511.02306

【22] クラウス・ディエム。 XL アルゴリズムと可換代数からの推測。 暗号学と情報セキュリティの理論と応用に関する国際会議、323 ～ 337 ページ。 スプリンガー、2004 年。
https:/​/​doi.org/​10.1007/​978-3-540-30539-2_23

【23] ジンタイ・ディンとディーター・シュミット。 有限体上の多項式系の次数と規則性の程度を解きます。 数理論と暗号、34 ～ 49 ページ。 スプリンガー、2013 年。
https:/​/​doi.org/​10.1007/​978-3-642-42001-6_4

【24] ジャン＝シャルル・フォージェール、ケルシー・ホーラン、デララム・カーロバイ、マーク・カプラン、エルハム・カシェフィ、ルドヴィク・ペレ。 多変量二次方程式を解くための高速量子アルゴリズム。 arXiv: 1712.07211、2017。
arXiv：1712.07211

【25] アンドラーシュ・ギレン、ユアン・スー、グアン・ハオ・ロウ、ネイサン・ウィーブ。 量子特異値変換とその先: 量子行列演算の指数関数的改善 [完全版]、2018. arXiv: 1806.01838。
arXiv：1806.01838

【26] アンドラーシュ・ギレン、ユアン・スー、グアン・ハオ・ロウ、ネイサン・ウィーブ。 量子特異値変換とその先: 量子行列演算の指数関数的な改善。 第 51 回 ACM コンピューティング理論に関するシンポジウム (STOC) の議事録、STOC、193 ～ 204 ページ、2019 年。arXiv: 1806.01838。
https：/ / doi.org/ 10.1145 / 3313276.3316366
arXiv：1806.01838

【27] アラム・W・ハロー、アヴィナタン・ハシディズム、そしてセス・ロイド。 線形方程式系の量子アルゴリズム。 フィジカルレビューレターRev. Lett.、103(15):150502、2009。arXiv: 0811.3171。
https：/ / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv：0811.3171

【28] ステイシス・ジュクナ。 極限組み合わせ論 – コンピューターサイエンスへの応用 (第 2 版)。 理論的なコンピューターサイエンスのテキスト。 スプリンガー、2011 年。
https:/​/​doi.org/​10.1007/​978-3-642-17364-6

【29] ヨルダニス・ケレニディスとアヌパム・プラカシュ。 量子推奨システム。 第 8 回理論コンピュータ サイエンス会議 (ITCS) のイノベーションの議事録、ITCS、49:1 ～ 49:21、2017 年。arXiv: 1603.08675。
https：/ / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49
arXiv：1603.08675

【30] リンリンとユートン。 量子線形システムを解くためのアプリケーションを備えた最適な多項式ベースの量子固有状態フィルタリング。 Quantum Quant.、4:361、2020。arXiv: 1910.14596。
https:/​/​doi.org/​10.22331/​q-2020-11-11-361
arXiv：1910.14596

【31] ルドヴィク・ペレ。 グレブナーの基底暗号化ポストクアンティック。 博士論文、UPMC-パリ第 6 ソルボンヌ大学、2016 年。

【32] ハーバート・ロビンス。 スターリングの公式についてのコメント。 『The American Mathematical Monthly』、62(1):26–29、1955 年。
https：/ / doi.org/ 10.2307 / 2308012

【33] Mathematica のソースコードは、Woflram Notebook Archive (https://notebookarchive.org/2022-02-1ec5yyv、2022) からも入手できます。
https:/ / notebookarchive.org/ 2022-02-1ec5yyv

【34] イジット・スバス、ロランド・D・ソンマ、ダビデ・オルスッチ。 断熱量子コンピューティングにヒントを得た線形方程式系の量子アルゴリズム。 フィジカルレビューレターRev. Lett.、122(6):060504、2019。arXiv: 1805.10549。
https：/ / doi.org/ 10.1103 / PhysRevLett.122.060504
arXiv：1805.10549

【35] シャオ・チャンペンとファ・シャン。 線形方程式系の量子サーキュラント前処理装置。 フィジカル レビュー A、98(6):062321、2018。
https：/ / doi.org/ 10.1103 / PhysRevA.98.062321

【36] ユー・トン、ドン・アン、ネイサン・ウィーブ、リン・リン。 高速逆変換、事前条件付き量子線形システム ソルバー、行列関数の高速評価。 arXiv: 2008.13295、2020。
https：/ / doi.org/ 10.1103 / PhysRevA.104.032422
arXiv：2008.13295

【37] レスリー・G・ヴァリアントとビジェイ・V・ヴァジラニ。 NP は、固有のソリューションを検出するのと同じくらい簡単です。 理論的なコンピューターサイエンスの理論。 計算します。 Sci.、47:85–93、1986。STOC'85 の初期バージョン。
https:/​/​doi.org/​10.1016/​0304-3975(86)90135-0

【38] ロナルド・デ・ウルフ。 量子コンピューティング: 講義ノート、2019 年。arXiv: 1907.09415。
arXiv：1907.09415

【39] マヌエラ・ヴィージンガー・ヴィディ。 グレブナー基底と一般化シルベスター行列。 博士論文、ヨハネス・ケプラー大学リンツ、オーストリア、2015 年。
https：/ / doi.org/ 10.1145 / 2016567.2016594

によって引用

取得できませんでした クロスリファレンス被引用データ 最終試行中2023-07-26 10:46:19：10.22331 / q-2023-07-26-1069の被引用データをCrossrefから取得できませんでした。 DOIが最近登録された場合、これは正常です。 オン SAO / NASA ADS 作品の引用に関するデータは見つかりませんでした（最後の試行2023-07-26 10:46:19）。

この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。

タイムスタンプ：

より多くの 量子ジャーナル