論文の概要: 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 22:35:51.776488
- 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: http://creativecommons.org/licenses/by/4.0/
- 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次優位性に近づき,近い将来に量子セキュア暗号システムに必要な格子次元に関する新たな議論を動機付けていることを示す。
関連論文リスト
- Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
量子乱数置換と理想的な暗号モデルにおけるセキュリティを確立するための最初の持ち上げ定理を導出する。
これらの定理は、任意の量子逆数の成功確率と、少数の古典的クエリのみを作る古典的アルゴリズムの成功確率を関連付ける。
論文 参考訳（メタデータ） (2025-04-25T09:07:55Z) - 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) - Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。
私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。
基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
論文 参考訳（メタデータ） (2024-05-22T18:11:42Z) - Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent [0.0]
ブロック符号化は、最近開発された量子特異値変換(QSVT)フレームワークにおいて重要な要素である。
本稿では、ブロック符号化を利用して、2つの従来提案されていた量子アルゴリズムを大幅に強化することで、この視点を裏付ける。
この結果から,単位ブロック符号化フレームワークの基本的な操作だけでも,大きなスケーリング要因を排除できることが示唆された。
論文 参考訳（メタデータ） (2023-12-22T15:59:03Z) - Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes [32.07657827173262]
我々は,未知のMDPとエージェントのエンゲージメントのための革新的な量子フレームワークを提案する。
平均推定における量子的優位性は、無限の地平線強化学習に対する後悔の保証において指数的な進歩をもたらすことを示す。
論文 参考訳（メタデータ） (2023-10-18T03:17:51Z) - 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) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。