論文の概要: Quantum and Classical Combinatorial Optimizations Applied to
Lattice-Based Factorization
- arxiv url: http://arxiv.org/abs/2308.07804v1
- Date: Tue, 15 Aug 2023 14:31:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-16 12:31:48.685354
- Title: Quantum and Classical Combinatorial Optimizations Applied to
Lattice-Based Factorization
- Title（参考訳）: 格子因子化への量子および古典的組合せ最適化の適用
- Authors: Willie Aboumrad, Dominic Widdows, Ananth Kaushik
- Abstract要約: 格子ベースのファクタリングは、より大きな数にうまくスケールしないことが示される。
我々は、CVPの特定の事例と、分解パイプラインの他の部分に量子技術を適用する機会について検討する。
- 参考スコア（独自算出の注目度）: 0.046040036610482664
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The availability of working quantum computers has led to several proposals
and claims of quantum advantage. In 2023, this has included claims that quantum
computers can successfully factor large integers, by optimizing the search for
nearby integers whose prime factors are all small.
This paper demonstrates that the hope of factoring numbers of commercial
significance using these methods is unfounded. Mathematically, this is because
the density of smooth numbers (numbers all of whose prime factors are small)
decays exponentially as n grows. Our experimental reproductions and analysis
show that lattice-based factoring does not scale successfully to larger
numbers, that the proposed quantum enhancements do not alter this conclusion,
and that other simpler classical optimization heuristics perform much better
for lattice-based factoring.
However, many topics in this area have interesting applications and
mathematical challenges, independently of factoring itself. We consider
particular cases of the CVP, and opportunities for applying quantum techniques
to other parts of the factorization pipeline, including the solution of linear
equations modulo 2. Though the goal of factoring 1000-bit numbers is still
out-of-reach, the combinatoric landscape is promising, and warrants further
research with more circumspect objectives.
- Abstract（参考訳）: 動作する量子コンピュータの可用性は、いくつかの提案と量子優位性の主張につながった。
2023年には、素因子が全て小さい近くの整数の探索を最適化することで、量子コンピュータが大きな整数をうまく分解できると主張している。
本稿は,これらの手法による商業的意義のファクタリングが期待できないことを実証する。
数学的には、これは n が成長するにつれて滑らかな数の密度(素数全体の数)が指数関数的に減少するためである。
実験により,格子ベースの因子分解はより大きい数に対してうまくスケールできないこと,提案する量子拡張はこの結論に影響を与えないこと,また,他の単純な古典的最適化ヒューリスティックは格子に基づく因子分解にはるかに優れていることを示した。
しかし、この分野の多くのトピックは、ファクタリング自身とは独立に興味深い応用と数学的課題を持っている。
我々は、cvpの特別な場合と、線形方程式の解であるmodulo 2を含む分解パイプラインの他の部分に量子技術を適用する機会について考察する。
1000ビットの数値を分解する目的はまだ未定だが、コンビネータ的な展望は有望であり、より遠近な目的でさらなる研究を保証している。
関連論文リスト
- Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography [0.0]
本研究は、整数分解問題と離散対数問題に基づくスキームの暗号解析のための量子的手法に焦点を当てる。
本稿では、量子計算と古典計算を組み合わせたアプローチを改善することにより、分解問題の最大の事例を現実的に解く方法を示す。
論文 参考訳（メタデータ） (2024-10-07T11:55:23Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Integer Factorization by Quantum Measurements [0.0]
量子アルゴリズムは、古典的コンピュータでは解けない計算問題を解くために量子力学を使うことが進行中の努力の中心である。
既知の量子アルゴリズムの中で、特別な役割はShorアルゴリズム、すなわち整数分解のための量子時間アルゴリズムによって演じられる。
ここでは、別の真の量子特性(量子計測)に基づく整数分解の異なるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-19T17:00:01Z) - Shallow Depth Factoring Based on Quantum Feasibility Labeling and
Variational Quantum Search [0.0]
整数分解は、特に量子コンピューティングの文脈において顕著な研究課題である。
本稿では,新しい量子アルゴリズムShallow Depth Factoring (SDF)を提案する。
論文 参考訳（メタデータ） (2023-05-31T04:18:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - An Algebraic-Geometry Approach to Prime Factorization [0.0]
素因数分解のための新しいアルゴリズムは、暗号アルゴリズムの現在の実装に実践的な影響を与える可能性がある。
n/2以上のパラメータを効率的に評価できる多様体が存在することを示す。
ある場合、 n/2 以上のパラメータが与えられたとき、効率的に点を評価できる多様体が存在することを示す。
論文 参考訳（メタデータ） (2022-09-23T15:31:07Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
我々は、ノイズの多い量子デバイス上で分解可能な数値の範囲を拡大するステップを推し進めるShorのアルゴリズムの縮小版を導入する。
特に、ほとんどのケースで注目すべき結果が得られており、しばしば提案されたアルゴリズムの1つで与えられた数を分解できる。
論文 参考訳（メタデータ） (2021-12-23T15:36:59Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。
本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
論文 参考訳（メタデータ） (2021-09-06T14:35:15Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。