論文の概要: Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations
- arxiv url: http://arxiv.org/abs/2511.20618v2
- Date: Wed, 26 Nov 2025 14:57:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-27 14:46:34.531311
- Title: Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations
- Title（参考訳）: GF($2^m$)乗算と除算演算を実装した量子回路の漸近的かつ実用的な最適化
- Authors: Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov,
- Abstract要約: 乗算演算と除算演算に最適化された量子回路を提案する。
我々のアシラフリーGF乗算回路はゲートカウントの複雑さが$O(mlog3)$である。
我々は,CNOTとToffoliゲート数の両方の削減を含む,$m$の暗号関連値に対して,実用的な利点を示す。
- 参考スコア（独自算出の注目度）: 1.1694898979785655
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present optimized quantum circuits for GF$(2^m)$ multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of $O(m^{\log_2{3}})$, an improvement over the previous best bound of $O(m^2)$. This was achieved by developing an efficient $O(m)$ circuit for multiplication by the constant polynomial $1+x^{\lceil{m/2}\rceil}$, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters $m$ of practical importance. For the GF division, we reduce gate count complexity from $O(m^2 \log(m))$ to $O(m^2 \log \log(m)/\log(m))$ by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.
- Abstract（参考訳）: 本稿では,GF$(2^m)$乗算および除算演算に最適化された量子回路を提案する。
我々のアシラフリーGF乗算回路はゲートカウントの複雑さが$O(m^{\log_2{3}})$であり、以前の最境界の$O(m^2)$よりも改善されている。
これは、ファン・フーフの構成の重要な構成要素である定数多項式 $1+x^{\lceil{m/2}\rceil}$ による乗算のための効率的な$O(m)$回路を開発することで達成された。
この漸近的還元は、定数$m$の実用的重要性の定数による乗算の実装において、CNOTゲート数が100以上向上する要因に変換される。
GF除算に対しては、定数多項式乗算と場乗法の両方の効率的な実装を可能にする既約多項式を選択することにより、ゲートカウントの複雑性を$O(m^2 \log(m))$から$O(m^2 \log \log(m)/\log(m))$に削減する。
我々は,CNOTとToffoliゲート数の両方の削減を含む,$m$の暗号関連値に対して,実用的な利点を示す。
さらに、線形可逆ユニタリの平方根の実装の複雑さを考察し、ルート自体がまだ線形可逆変換であるにもかかわらず、元のユニタリよりも漸近的に深い回路実装を必要とすることを示す。
関連論文リスト
- Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - Compact Circuits for Constrained Quantum Evolutions of Sparse Operators [0.0]
我々は、コンパクトな量子回路を構築するための一般的な枠組みを導入し、ハミルトンのリアルタイム進化を$H = sigma P_B$という形で実現する。
我々はまた、量子コンピューティングで広く使われているトランスポジションゲートを構築し、文学における最もよく知られた構成よりも効率的にスケールする。
論文 参考訳（メタデータ） (2025-04-12T08:47:59Z) - Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
ウィンドウ演算は、空間時間トレードオフを伴う量子回路のコストを削減する手法である。
この作業では、ウィンドウ化されたモジュラー指数に4つの最適化を導入する。
これにより、暗号化アプリケーションに関連するモジュール型指数回路において、Toffoli数とToffoli深度が3%向上する。
論文 参考訳（メタデータ） (2025-02-24T16:59:16Z) - Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost [3.129187821625805]
本稿では,$GF(2n)$を$mathcalO(nlog_(n))ビットで乗算する量子回路を構築するアルゴリズムを提案する。
トリノミアル (trinomials) のようなプリミティブでは、掛け算は対数深さと $mathcalO(nlog_(n)) ビットで行うことができる。
論文 参考訳（メタデータ） (2025-01-27T15:26:11Z) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - Lower T-count with faster algorithms [2.488003578430483]
低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。
様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。
我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
論文 参考訳（メタデータ） (2024-07-11T17:31:20Z) - Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。
関連するキュービットは入力と出力レジスタ自身のみである。
我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
論文 参考訳（メタデータ） (2024-03-26T18:00:03Z) - Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳（メタデータ） (2024-02-20T10:11:03Z) - Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
Regevの最近の量子ファクタリングアルゴリズムに2つの改善がある。
レゲフの回路は$O(n3/2)$ qubitsと$O(n3/2 log n)$ gatesを必要とする。
Regev氏の古典的な後処理手順の分析は、すべての$approx sqrtn$の実行を成功させる必要がある。
論文 参考訳（メタデータ） (2023-10-02T04:31:21Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。