論文の概要: A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum
Factoring, and More
- arxiv url: http://arxiv.org/abs/2402.11269v1
- Date: Sat, 17 Feb 2024 13:00:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-20 22:09:48.929228
- Title: A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum
Factoring, and More
- Title（参考訳）: ジェネリックな下界への新しいアプローチ:クラシック/量子mdl、量子ファクタリングなど
- Authors: Minki Hhan
- Abstract要約: 本稿では,古典的および量子的設定における暗号問題の解法における汎用的アプローチの限界について検討する。
両方のモデルにおいて、両方のモデルの量子的下界は、ある種の古典的な前処理を可能にする。
- 参考スコア（独自算出の注目度）: 1.1893324664457547
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the limitations of the generic approaches to solving
cryptographic problems in classical and quantum settings in various models.
- In the classical generic group model (GGM), we find simple alternative
proofs for the lower bounds of variants of the discrete logarithm (DL) problem:
the multiple-instance DL and one-more DL problems (and their mixture). We also
re-prove the unknown-order GGM lower bounds, such as the order finding, root
extraction, and repeated squaring.
- In the quantum generic group model (QGGM), we study the complexity of
variants of the discrete logarithm. We prove the logarithm DL lower bound in
the QGGM even for the composite order setting. We also prove an asymptotically
tight lower bound for the multiple-instance DL problem. Both results resolve
the open problems suggested in a recent work by Hhan, Yamakawa, and Yun.
- In the quantum generic ring model we newly suggested, we give the
logarithmic lower bound for the order-finding algorithms, an important step for
Shor's algorithm. We also give a logarithmic lower bound for a certain generic
factoring algorithm outputting relatively small integers, which includes a
modified version of Regev's algorithm.
- Finally, we prove a lower bound for the basic index calculus method for
solving the DL problem in a new idealized group model regarding smooth numbers.
The quantum lower bounds in both models allow certain (different) types of
classical preprocessing. All of the proofs are significantly simpler than the
previous proofs and are through a single tool, the so-called compression lemma,
along with linear algebra tools. Our use of this lemma may be of independent
interest.
- Abstract（参考訳）: 本稿では,様々なモデルにおける古典的および量子的設定における暗号問題に対する一般的なアプローチの限界について検討する。
-古典的総称群モデル(GGM)では、離散対数問題(DL)の変項の下限に対する単純な代替証明として、多重インスタンスDLと1つ以上のDL問題(およびそれらの混合)が見つかる。
また, 順序探索, 根抽出, 繰り返しスクアリングなど, 未知の階数 GGM の下限も再検討した。
-量子ジェネリック・グループ・モデル(QGGM)において、離散対数の変異の複雑さについて検討する。
合成順序設定においてもQGGMの対数DLが低いことを証明した。
また,マルチインスタンスdl問題に対する漸近的にきつく下界を証明した。
どちらの結果も、Hhan, Yamakawa, Yun の最近の研究で示唆されたオープンな問題を解決している。
-新しく提案した量子ジェネリック環モデルにおいて、順序探索アルゴリズムに対して対数下限を与え、これはショアのアルゴリズムにとって重要なステップである。
また、Regevのアルゴリズムの修正版を含む比較的小さな整数を出力する一般的な分解アルゴリズムに対して、対数下界を与える。
最終的に、滑らかな数に関する新しい理想化群モデルにおいて、dl問題を解くための基本指標計算法の下限が証明される。
両方のモデルにおける量子下界は、古典前処理のある種の(異なる)タイプを許容する。
すべての証明は以前の証明よりもはるかに単純であり、圧縮補題と呼ばれる1つのツールと線形代数ツールによって実現される。
私たちのこの補題の使用は独立した関心事かもしれない。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Unitary property testing lower bounds by polynomials [0.15229257192293197]
我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。
これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。
我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
論文 参考訳（メタデータ） (2022-10-12T03:01:00Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Infinite-Dimensional Sparse Learning in Linear System Identification [0.2867517731896504]
本稿では,原子ノルム正規化に基づく無限次元スパース学習アルゴリズムを提案する。
この問題の解決の難しさは、無限の原子モデルが存在するという事実にある。
論文 参考訳（メタデータ） (2022-03-28T13:18:48Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文 参考訳（メタデータ） (2022-01-31T18:58:33Z) - Bregman divergence based em algorithm and its application to classical
and quantum rate distortion theory [61.12008553173672]
本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。
このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
論文 参考訳（メタデータ） (2022-01-07T13:33:28Z) - Quantum algorithms for learning a hidden graph and beyond [0.05076419064097732]
本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。
ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。
さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-11-17T13:12:43Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。