論文の概要: Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost

• arxiv url: http://arxiv.org/abs/2501.16136v1
• Date: Mon, 27 Jan 2025 15:26:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-28 13:55:49.778258
• Title: Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost
• Title（参考訳）: 準4次トフォリゲート数と低時空間コストを用いた量子二乗場乗算法
• Authors: Vivien Vandaele,
• Abstract要約: 本稿では,$GF(2n)$を$mathcalO(nlog_(n))ビットで乗算する量子回路を構築するアルゴリズムを提案する。 トリノミアル (trinomials) のようなプリミティブでは、掛け算は対数深さと $mathcalO(nlog_(n)) ビットで行うことができる。
• 参考スコア（独自算出の注目度）: 3.129187821625805
• License:
• Abstract: Multiplication over binary fields is a crucial operation in quantum algorithms designed to solve the discrete logarithm problem for elliptic curve defined over $GF(2^n)$. In this paper, we present an algorithm for constructing quantum circuits that perform multiplication over $GF(2^n)$ with $\mathcal{O}(n^{\log_2(3)})$ Toffoli gates. We propose a variant of our construction that achieves linear depth by using $\mathcal{O}(n\log_2(n))$ ancillary qubits. This approach provides the best known space-time trade-off for binary field multiplication with a subquadratic number of Toffoli gates. Additionally, we demonstrate that for some particular families of primitive polynomials, such as trinomials, the multiplication can be done in logarithmic depth and with $\mathcal{O}(n^{\log_2(3)})$ gates.
• Abstract（参考訳）: 二項体上の乗算は、GF(2^n)$で定義される楕円曲線の離散対数問題を解決するために設計された量子アルゴリズムにおいて重要な演算である。 本稿では,$GF(2^n)$と$\mathcal{O}(n^{\log_2(3)})$Toffoliゲートを乗算する量子回路を構築するアルゴリズムを提案する。 我々は、$\mathcal{O}(n\log_2(n))$ ancillary qubits を用いて線形深さを達成する構成の変種を提案する。 このアプローチは、二進体乗法とトフォリゲートの四進数との最もよく知られた時空トレードオフを提供する。 さらに、トリノミアルのような原始多項式の特定の族に対して、乗法は対数的な深さと$\mathcal{O}(n^{\log_2(3)})$ゲートで行うことができる。

関連論文リスト

• Transformation of the discrete logarithm problem over $\mathbb F_{2^n}$ to the QUBO problem using normal bases [0.0]
  本稿では、二項体上の離散対数問題の準非制約二項最適化問題への変換について述べる。 推定では、与えられたフィールドに最適なII型正規基底が存在すると仮定する。
  論文  参考訳（メタデータ） (2024-09-27T08:12:44Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
  我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。 関連するキュービットは入力と出力レジスタ自身のみである。 我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
  論文  参考訳（メタデータ） (2024-03-26T18:00:03Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
  制御された演算は量子アルゴリズムの基本的な構成要素である。 n$-control-NOT ゲートを任意の単一量子ビットと CNOT ゲートに分解することは重要な作業である。
  論文  参考訳（メタデータ） (2023-12-20T17:23:11Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。 この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
  論文  参考訳（メタデータ） (2021-02-03T09:20:32Z)

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

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