論文の概要: Prefix Sums via Kronecker Products

• arxiv url: http://arxiv.org/abs/2512.16309v1
• Date: Thu, 18 Dec 2025 08:49:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-19 18:10:31.988978
• Title: Prefix Sums via Kronecker Products
• Title（参考訳）: Kronecker Products による Sums の修正
• Authors: Aleksandros Sobczyk, Anastasios Zouzias,
• Abstract要約: 三角全対行列を2つのクロネッカー積の和として分解する恒等式を記述する。 これらの回路を用いて1.893log(n) + O(1)$ Toffoli depth, $O(n)$ Toffoli gates, $O(n)$ additional qubits の量子加算器を設計する方法を示す。
• 参考スコア（独自算出の注目度）: 47.600794349481966
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this work, we revisit prefix sums through the lens of linear algebra. We describe an identity that decomposes triangular all-ones matrices as a sum of two Kronecker products, and apply it to design recursive prefix sum algorithms and circuits. Notably, the proposed family of circuits is the first one that achieves the following three properties simultaneously: (i) zero-deficiency, (ii) constant fan-out per-level, and (iii) depth that is asymptotically strictly smaller than $2\log(n)$ for input length n. As an application, we show how to use these circuits to design quantum adders with $1.893\log(n) + O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits, improving the Toffoli depth and/or Toffoli size of existing constructions.
• Abstract（参考訳）: 本研究では、線型代数のレンズを通してプレフィックス和を再考する。 三角全対行列を2つのクロネッカー積の和として分解し、再帰的なプレフィックス和アルゴリズムと回路の設計に適用する。 特に、提案された回路群は、次の3つの特性を同時に達成する最初のものである。 (i)ゼロ欠陥 (二)一定レベル毎のファンアウト、及び (iii)入力長 n に対して、漸近的に$2\log(n)$より小さい深さ。 応用として、これらの回路を用いて1.893\log(n) + O(1)$ Toffoli depth, $O(n)$ Toffoli gates, $O(n)$ additional qubits を用いて量子加算器を設計する方法を示し、既存の構成の Toffoli depth および/または Toffoli size を改善する。

関連論文リスト

• Stesso: A reconfigurable decomposition of $n$-bit Toffoli gates using symmetrical logical structures and adjustable support qubits [2.349579657464914]
  本稿では, アンシラ量子ビットを用いて, $(n+1)$-bit Toffoli ゲートを効率的に分解する構造設計手法を提案する。 実験により、$(n+1)$-bit Toffoli ゲートは常に従来の合成法よりも量子コストが低いことが証明されている。
  論文  参考訳（メタデータ） (2025-10-30T03:58:02Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  この研究において、ラベルは(ガウス)$d$-次元入力にのみ依存し、低次元$r = O_d(1)$部分空間への射影を通して得られる。 生成的跳躍指数 $kstar$, [Damian et al.'24] から生成的指数の自然拡張をマルチインデックス設定に導入する。
  論文  参考訳（メタデータ） (2025-06-05T18:34:56Z)
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  ウィンドウ演算は、空間時間トレードオフを伴う量子回路のコストを削減する手法である。 この作業では、ウィンドウ化されたモジュラー指数に4つの最適化を導入する。 これにより、暗号化アプリケーションに関連するモジュール型指数回路において、Toffoli数とToffoli深度が3%向上する。
  論文  参考訳（メタデータ） (2025-02-24T16:59:16Z)
• Ancilla-free Quantum Adder with Sublinear Depth [2.784223169208082]
  サブ線形深さとアンシラ量子ビットを持たない最初の正確な量子加算器を提示する。 我々の構成は古典的な可逆論理のみに基づいている。 また、量子レジスタに定数を増分し、加算するための新しい構成も提示する。
  論文  参考訳（メタデータ） (2025-01-28T09:05:49Z)
• 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)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  我々は,N-1(N-1)時間行列の行列式と逆行列を計算するために,純粋に量子的な量子アルゴリズムを提案する。 基本的な考え方は、行列の各行を量子系の純粋な状態にエンコードすることである。
  論文  参考訳（メタデータ） (2024-01-29T23:23:27Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  本稿では,QFT付加回路をToffoliベースの加算器に初めて体系的に変換する。 QFT回路からゲートを近似分解する代わりに、ゲートをマージする方が効率的である。
  論文  参考訳（メタデータ） (2022-09-30T02:36:42Z)
• Halving the width of Toffoli based constant modular addition to n+3 qubits [69.43216268165402]
  本稿では,Toffoli ゲートの深さが $mathcalO(n)$ の固定モジュラ加算を行う演算回路を提案する。 これは、最先端のToffoliベースの定数モジュラー加算器の幅と比較して2倍の改善である。
  論文  参考訳（メタデータ） (2021-02-06T17:07:48Z)

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

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