論文の概要: A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles

• arxiv url: http://arxiv.org/abs/2503.08403v1
• Date: Tue, 11 Mar 2025 13:06:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:44:35.731474
• Title: A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles
• Title（参考訳）: 固定角付きQAOAによる最接近ベクトル問題に対する実用的スケーラブルアプローチ
• Authors: Ben Priestley, Petros Wallden,
• Abstract要約: 最も近いベクトル問題(CVP)のNP硬度は、量子セキュア暗号の重要な基盤である。 量子アルゴリズムによる最近の研究は、(制約のある)CVPインスタンスの近似を見つける可能性を示している。 この研究は、その後の因数分解の主張を考慮せずに、近似CVPに対する量子的優位性の可能性を探究する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography, in much the same way that integer factorisation's conjectured hardness is at the foundation of cryptosystems like RSA. Recent work with heuristic quantum algorithms (arXiv:2212.12372) indicates the possibility to find close approximations to (constrained) CVP instances that could be incorporated within fast sieving approaches for factorisation. This work explores both the practicality and scalability of the proposed heuristic approach to explore the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims. We also extend the proposal to include an antecedent "pre-training" scheme to find and fix a set of parameters that generalise well to increasingly large lattices, which both optimises the scalability of the algorithm, and permits direct numerical analyses. Our results further indicate a noteworthy quantum speed-up for lattice problems obeying a certain `prime' structure, approaching fifth order advantage for QAOA of fixed depth p=10 compared to classical brute-force, motivating renewed discussions about the necessary lattice dimensions for quantum-secure cryptosystems in the near-term.
• Abstract（参考訳）: 最も近いベクトル問題(CVP)のNP硬度は、整数分解の予想硬度がRSAのような暗号体系の基礎にあるのとほとんど同じように、量子セキュア暗号の重要な基礎である。 近年のヒューリスティック量子アルゴリズム(arXiv:2212.12372)による研究は、因数分解のための高速な解法に組み込むことができる(制限された)CVPインスタンスの近似を見つける可能性を示している。 この研究は、提案されたヒューリスティックアプローチの実用性とスケーラビリティの両方を探求し、その後のファクタリングの主張を考慮せずに、近似CVPに対する量子的優位性の可能性を探究する。 また,アルゴリズムのスケーラビリティを最適化し,直接数値解析を可能にする,より大規模な格子によく一般化するパラメータの集合を探索し,修正するための先行的な事前学習スキームを含むように提案を拡張した。 さらに,ある「プライム」構造に従う格子問題に対する量子スピードアップが,古典的ブライト力と比較して,固定深さp=10のQAOAに対する第5次優位性に近づき,近い将来に量子セキュア暗号システムに必要な格子次元に関する新たな議論を動機付けていることを示す。

関連論文リスト

• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation [3.9857517408503567]
  量子近似最適化アルゴリズム (quantum Approximate optimization algorithm, Qaoa) は、最適化のための量子古典的反復法として広く研究されている。 インスタンスに依存しないが問題固有の非定型計算に基づく新しいアルゴリズム変種を導入する。 我々のアプローチは、カオの量子非依存構造に関する長年の予想を証明することに基づいている。
  論文  参考訳（メタデータ） (2024-08-12T21:02:58Z)
• Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs [0.39901365062418315]
  本研究では, ランダム制約満足度問題 (CSP) に対するメッセージパッシングアルゴリズムの構築と解析を行う。 偶数述語を持つ CSP に対して、アルゴリズムはパリの変分原理の拡張に双対する最適制御問題を解く。 これにより、Huang と Sellke の分岐オーバーラップギャップ特性によって妨げられるアルゴリズム間の満足度制約の最適分数が得られる。
  論文  参考訳（メタデータ） (2023-10-02T18:55:26Z)
• Integer Factorization through Func-QAOA [0.0]
  暗号時間整数分解のための効率的な古典的アルゴリズムは発見されていない。 本稿では,Func-QAOAによる因子化手法を提案する。
  論文  参考訳（メタデータ） (2023-09-26T18:00:25Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。 学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。 また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
  論文  参考訳（メタデータ） (2021-05-14T11:31:14Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。