論文の概要: Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q

• arxiv url: http://arxiv.org/abs/2503.23939v2
• Date: Thu, 24 Apr 2025 12:51:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-25 21:09:46.505415
• 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をオーダーする。 p$ が等しければ、セーフプライム群とシュノール群の強みがどの程度同じかを示す。 特に、加算回路で搬送器を用いる場合、ショアのアルゴリズムの下では$p=$48$ビットのシュノーラー群の暗号強度は$p=$48$ビットの安全プリム群のそれとほぼ同値であることが実験的に理論的に示された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of order $q$, was clarified. 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} でヒューリスティックに解析されていた成功確率の値が得られた。 その結果、$q$の周期関数として知られるDLPを解くためのShorのアルゴリズムの成功確率の詳細な波形形状が明らかにされた。 さらに、より大きいペアの$p$と$q$に対して1,015の量子回路を生成し、得られた回路サイズを補間し、安全なプライム群とシュノーラー群間で$p=2048$ビットで比較した。 古典暗号では、セーフプライム群とシュノーア群の暗号強度は、$p$が等しい場合と同じであるが、Shorの量子アルゴリズムを使用すると、後者の強度が前者のビット長$p$にどれだけ減少するかを定量的に示す。 特に、加算回路でリップルキャンピング加算器を使用する場合、ショアのアルゴリズムの下で2048$ビットのシュノーラー群の暗号強度は、$p=1024$ビットの安全プライム群の暗号強度とほぼ同値であることが実験的に理論的に示された。

関連論文リスト

• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  線形微分方程式に対する量子アルゴリズムを提案する。 アルゴリズムのゲートの複雑さは、次元に依存する$mathcalO(dlog(Nd))$を示す。 アルゴリズムはOrnstein-Uhlenbeck過程、ブラウン運動、L'evy飛行に対して数値的に検証される。
  論文  参考訳（メタデータ） (2024-12-19T14:04:11Z)
• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  格子ベースの暗号は、量子後暗号の主要な候補の1つである。 量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
  論文  参考訳（メタデータ） (2024-10-17T16:54:41Z)
• 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)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• 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)
• 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 Algorithm for Fidelity Estimation [8.270684567157987]
  2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。 我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-16T13:57:01Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Emulating Quantum Interference with Generalized Ising Machines [0.0]
  本稿では、量子ゲートの任意の列を確率的pビットのネットワークにマッピングするための、正確で一般的な手順を提案する。 この構造をボルツマンマシンとみなすことができ、それぞれが初期構成から最終構成へと導かれるファインマンパスを表す。 任意の量子回路を複雑なエネルギー関数を持つボルツマンマシンにマッピングする結果は、確率的資源を持つ量子回路のシミュレーション可能性の境界を推し進める助けとなる。
  論文  参考訳（メタデータ） (2020-07-14T22:10:29Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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