論文の概要: Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q
- arxiv url: http://arxiv.org/abs/2503.23939v1
- Date: Mon, 31 Mar 2025 10:39:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-01 14:34:39.667922
- Title: Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q
- Title（参考訳）: モジュラーpと順序qの包括対を用いた離散対数問題のShorアルゴリズムのシミュレーション
- Authors: Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu, Noboru Kunihiro,
- Abstract要約: 量子回路をシミュレートし、モジュロ$pの一般的なペアで動作させ、$qをオーダーする。
その結果,Shorのアルゴリズムが,$q$の順序で決定される非対称周期性(英語版)を解くための成功確率が外挿された。
特に、Shorのアルゴリズムの下で、$p=48$ビットのシュノーラー群において、搬送器が使われるとき、$p=$ビットのシュノーラー群のリップル強度は、$p=$ビットのセーフプライム群のものとほぼ同値であることが理論的に示されている。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulo $p$ and order $q$. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs of $p$ and $q$ up to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by Eker\r{a}. As a result, we found that the success probability of Shor's algorithm for solving the DLP exhibits periodicity with an asymmetric waveform determined by the order $q$. Additionally, we generated 1,015 quantum circuits for larger pairs of $p$ and $q$, extrapolated the circuit sizes obtained, and compared them for $p=2048$ bits between safe-prime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if $p$ is equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of $p$ in the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a ripple carry adder is used in the addition circuit, the cryptographic strength of a Schnorr group with $p=2048$ bits under Shor's algorithm is almost equivalent to that of a safe-prime group with $p=1024$ bits.
- Abstract（参考訳）: 古典暗号でよく用いられる有限体上の離散対数問題(DLP)は、古典的コンピュータ上での多項式時間アルゴリズムは知られていない。
しかし、Shorは多項式時間アルゴリズムを量子コンピュータに提供している。
それにもかかわらず、量子回路をシミュレートする例はわずかになく、モジュロ$p$と順序$q$の一般的なペアで動く。
本稿では,これらの量子回路を構築し,PRIMEHPC FX700を用いた量子シミュレータを用いて1,860対の$p$と$q$の最大32キュービットのDLPを解いた。
この結果から,従来Eker\r{a} でヒューリスティックに解析されていた成功確率の値が得られた。
その結果,DLPの解法におけるショアのアルゴリズムの成功確率は,次数$q$で決定される非対称波形で周期性を示すことがわかった。
さらに、より大きいペアの$p$と$q$に対して1,015の量子回路を生成し、得られた回路サイズを補間し、安全なプライム群とシュノーラー群間で$p=2048$ビットで比較した。
古典暗号では、セーフプライム群とシュノーア群の暗号強度は、$p$が等しい場合と同じであるが、Shorの量子アルゴリズムを使用すると、後者の強度が前者のビット長$p$にどれだけ減少するかを定量的に示す。
特に、加算回路でリップルキャンピング加算器を使用する場合、ショアのアルゴリズムの下で2048$ビットのシュノーラー群の暗号強度は、$p=1024$ビットの安全プライム群の暗号強度とほぼ同値であることが実験的に理論的に示された。
関連論文リスト
- 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Efficient quantum algorithms for some instances of the semidirect
discrete logarithm problem [2.90985742774369]
SDLPは,いくつかの重要な症例においてさらに容易であることを示す。
SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
論文 参考訳（メタデータ） (2023-12-21T16:58:59Z) - The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
問合せモデルにおける深度計算のトレードオフについて検討し、その深さは適応的な問合せラウンドの数と1ラウンド当たりの並列クエリ数に対応する。
我々は、量子アルゴリズム間の最も強力な分離を$r$対$r-1$の適応性を持つラウンドで達成する。
論文 参考訳（メタデータ） (2023-11-27T18:21:32Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Digital-analog co-design of the Harrow-Hassidim-Lloyd algorithm [0.0]
方程式の線形系を解くために、Harrow-Hassidim-Lloyd量子アルゴリズムが提案された。
問題行列の逆行列である$A$を補助量子ビットにマッピングするサブルーチンに対する明示的な量子回路は存在しない。
本稿では,アルゴリズムの深さを減らした共設計量子プロセッサを提案する。
論文 参考訳（メタデータ） (2022-07-27T13:58:13Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。