論文の概要: Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

• arxiv url: http://arxiv.org/abs/2511.20618v1
• Date: Tue, 25 Nov 2025 18:43:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-26 17:37:04.624109
• Title: Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations
• Title（参考訳）: GF($2^m$)乗算と除算演算を実装した量子回路の漸近的かつ実用的な最適化
• Authors: Noureldin Yosri, Dmitri Maslov,
• Abstract要約: 我々は、$(2m)$乗算および除算演算のために最適化された量子回路を提案する。 我々のアシラフリーGF回路はゲートカウントの複雑性が$O(mlog3)$であり、以前の最高値の$O(m2)$よりも改善されている。
• 参考スコア（独自算出の注目度）: 1.3143894450493425
• 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 $\cnotgate$ 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$. 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$の定数による乗算の実装において、$\cnotgate$ gate countsを100以上改善する要因に変換される。 GF除算に対しては、定数多項式乗算と場乗法の両方の効率的な実装を可能にする既約多項式を選択することにより、ゲートカウントの複雑性を$O(m^2 \log(m))$から$O(m^2 \log \log(m)/\log(m))$に削減する。 暗号関連値が$m$の実用的な利点を示す。 さらに、線形可逆ユニタリの平方根の実装の複雑さを考察し、ルート自体がまだ線形可逆変換であるにもかかわらず、元のユニタリよりも漸近的に深い回路実装を必要とすることを示す。

関連論文リスト

• Compact Circuits for Constrained Quantum Evolutions of Sparse Operators [0.0]
  我々は、コンパクトな量子回路を構築するための一般的な枠組みを導入し、ハミルトンのリアルタイム進化を$H = sigma P_B$という形で実現する。 我々はまた、量子コンピューティングで広く使われているトランスポジションゲートを構築し、文学における最もよく知られた構成よりも効率的にスケールする。
  論文  参考訳（メタデータ） (2025-04-12T08:47:59Z)
• 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)
• 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)
• 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)

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

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