論文の概要: Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
- arxiv url: http://arxiv.org/abs/2206.14408v3
- Date: Tue, 19 Sep 2023 14:08:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-20 20:40:45.727133
- Title: Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
- Title（参考訳）: dihedral coset問題に対する時間とクエリの複雑さのトレードオフ
- Authors: Maxime Remaud and Andr\'e Schrottenloher and Jean-Pierre Tillich
- Abstract要約: Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。
Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。
本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.19731444261635428
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Dihedral Coset Problem (DCP) in $Z_N$ has been extensively studied in
quantum computing and post-quantum cryptography, as for instance, the Learning
with Errors problem reduces to it. While the Ettinger-Hoyer algorithm is known
to solve the DCP in $O(log(N))$ queries, it runs inefficiently in time $O(N)$.
The first time-efficient algorithm was introduced (and later improved) by
Kuperberg (SIAM J. Comput. 2005). These algorithms run in a subexponential
amount of time and queries $O{2^{\sqrt{c_{DCP}log(N)}}}$, for some constant
$c_{DCP}$.
The sieving algorithms \`a la Kuperberg admit many trade-offs between quantum
and classical time, memory and queries. Some of these trade-offs allow the
attacker to reduce the number of queries if they are particularly costly, which
is notably the case in the post-quantum key-exchange CSIDH. Such optimizations
have already been studied, but they typically fall into two categories: the
resulting algorithm is either based on Regev's approach of reducing the DCP
with quadratic queries to a subset-sum instance, or on a re-optimization of
Kuperberg's sieve where the time and queries are both subexponential.
In this paper, we introduce the first algorithm to improve in the linear
queries regime over the Ettinger-Hoyer algorithm. We then show that we can in
fact interpolate between this algorithm and Kuperberg's sieve, by using the
latter in a pre-processing step to create several quantum states, and solving a
quantum subset-sum instance to recover the full secret in one pass from the
obtained states. This allows to interpolate smoothly between the linear
queries-exponential time complexity case and the subexponential query and time
complexity case, thus allowing a fine tuning of the complexity taking into
account the query cost. We also give on our way a precise study of quantum
subset-sum algorithms in the non-asymptotic regime.
- Abstract（参考訳）: z_n$のディヘドラルコセット問題(英語版)(dcp)は量子コンピューティングや量子後暗号において広範囲に研究されてきた。
Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られているが、時間で$O(N)$で非効率に実行される。
最初の時間効率のよいアルゴリズムはkuperberg (siam j. comput. 2005) によって導入された。
これらのアルゴリズムはサブ指数的に実行され、一定の$c_{dcp}$ に対して$o{2^{\sqrt{c_{dcp}log(n)}}}$ というクエリが実行される。
シービングアルゴリズム \`a la Kuperberg は、量子時間と古典時間、メモリ、クエリ間の多くのトレードオフを認めている。
これらのトレードオフのいくつかは、特にコストがかかる場合、攻撃者がクエリの数を減らすことを可能にする。
このような最適化はすでに研究されているが、一般的には2つのカテゴリに分類される: 結果のアルゴリズムはRegevの2次クエリをサブセットサムのインスタンスに還元するアプローチと、時間とクエリが共に指数関数であるKuperbergのシーブの再最適化に基づいている。
本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
次に、このアルゴリズムとクパーベルグのシーブの間に実際に補間できることを示し、後者を前処理でいくつかの量子状態を生成するために使用し、得られた状態から完全な秘密を回復するために量子サブセット-サムインスタンスを解く。
これにより、線形クエリ-指数時間複雑性ケースとサブ指数クエリと時間複雑性ケースとをスムーズに補間することができ、クエリコストを考慮した複雑性の微調整が可能になる。
また、非漸近状態における量子部分集合-sumアルゴリズムの正確な研究も行います。
関連論文リスト
- Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Intermediate-qudit assisted Improved quantum algorithm for string
matching with an Advanced Decomposition of Fredkin gate [1.9798034349981157]
本稿では,高次元中間クォーディットを用いた文字列マッチング問題に対する量子回路の実装について述べる。
また、中間クォーディットの助けを借りれば、深さの複雑さを低減できるだけでなく、クエリの複雑さを減らせることも示される。
論文 参考訳（メタデータ） (2023-04-06T13:11:07Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳（メタデータ） (2022-05-16T05:16:15Z) - Quantum Topological Data Analysis with Linear Depth and Exponential
Speedup [9.820545418277305]
我々はQTDAアルゴリズムを完全にオーバーホールし、$O(n4/(epsilon2 delta))の指数的高速化深度を改良した。
理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。
論文 参考訳（メタデータ） (2021-08-05T18:56:17Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。