論文の概要: On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition

• arxiv url: http://arxiv.org/abs/2502.01433v3
• Date: Tue, 11 Feb 2025 15:37:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:03:48.277364
• Title: On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition
• Title（参考訳）: トッフォリ多層分解における宇宙深度トレーディングオフについて
• Authors: Suman Dutta, Siyi Wang, Anubhab Baksi, Anupam Chattopadhyay, Subhamoy Maitra,
• Abstract要約: Clifford $+$ T ゲートセットを用いた Multi Toffoli (MCT) の最適化実装について検討する。 古典的2制御トフォリを用いたトフォリ深度と深度とのトレードオフの定量化を行う。
• 参考スコア（独自算出の注目度）: 5.286310769012741
• License:
• Abstract: In this paper, we consider the optimized implementation of Multi Controlled Toffoli (MCT) using the Clifford $+$ T gate sets. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulae) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli) of the $n$-controlled Toffoli (hereform we will tell $n$-MCT) and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli depth (and consequently, T-depth), which is an extension of the technique introduced by Khattar et al. (2024). In terms of a negative result, we first show that using such conditionally clean ancilla techniques, Toffoli depth can never achieve exactly $\ceil{\log_2 n}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancilla [Nie et al., 2024, Khattar et al., 2024]. Then we prove that, in a more general setup, the T-Depth in the Clifford + T decomposition, via Toffoli gates, is lower bounded by $\ceil{\log_2 n}$, and this bound is achieved following the complete binary tree structure. Since the ($2$-controlled) Toffoli gate can further be decomposed using Clifford $+$ T, various methodologies are explored too in this regard for trade-off related implications.
• Abstract（参考訳）: 本稿では,Clifford $+$T ゲートセットを用いたマルチコントロールトフォリ(MCT)の最適化実装について検討する。 この方向の最近の研究はいくつかあるが、ここでは、$n$制御された Toffoli の Toffoli 深さ(これは古典的な 2-制御された Toffoli を用いた深さを意味する)とクリーンな ancilla qubit の数の間のトレードオフ(具体的な公式を含む)を明示的に定量化する。 さらに,Khattar et al (2024) が導入したテクニックの拡張である Toffoli 深さの低減(T-deepth)を実現した。 負の結果に関して、我々はまず、そのような条件付きクリーンアンシラ手法を用いることで、Toffoli depthは正確に$\ceil{\log_2 n}$を達成できないことを示した。 これは条件付きクリーンアンシラ(Nie et al , 2024, Khattar et al , 2024)を利用する手法の限界を強調するものである。 そして、より一般的な設定では、トッホリゲートを経由したクリフォード+T分解のT-ディープスが$\ceil{\log_2 n}$で下界であることが証明され、この境界は完全二分木構造に従って達成される。 2$制御されたトフォリゲートはさらにクリフォード$+$Tで分解できるので、この点に関しても様々な方法論が検討されている。

関連論文リスト

• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  閾値秘密共有方式により、ディーラーは、秘密が一定量の株式から正しく回収されたことをすべての参加者に分配することができる。 我々は、リング上の$ell$-bitシークレットのための、進化する$k$-thresholdシークレット共有スキームを、正確性と完全なセキュリティで新たに構築することを提案する。
  論文  参考訳（メタデータ） (2024-02-02T05:04:01Z)
• Synthesizing Toffoli-optimal quantum circuits for arbitrary multi-qubit unitaries [0.0]
  Clifford+Toffoli普遍耐故障ゲート集合について検討する。 ほぼかつ正確に実装可能なマルチキュービットユニタリのためのToffoli-count最適合成アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-01-17T03:53:37Z)
• A T-depth two Toffoli gate for 2D square lattice architectures [49.88310438099143]
  本稿ではトフォリゲートのクリフォード+T分解について述べる。 量子ビットの2次元正方格子上に実装するためにSWAPゲートは不要である。 この分解により、NISQとエラー修正アーキテクチャの両方において、より浅く、よりフォールトトレラントな量子計算が可能になる。
  論文  参考訳（メタデータ） (2023-11-21T10:33:51Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  本稿では,QFT付加回路をToffoliベースの加算器に初めて体系的に変換する。 QFT回路からゲートを近似分解する代わりに、ゲートをマージする方が効率的である。
  論文  参考訳（メタデータ） (2022-09-30T02:36:42Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。 境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。 治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2022-08-12T15:05:07Z)
• Constructing all qutrit controlled Clifford+T gates in Clifford+T [0.0]
  我々は、Clifford+Tゲートのみを用いて、任意のクォート多重制御クリフォード+Tユニタリを構築する方法を示す。 この結果から,マルチコントロールされたTゲートのアンシラフリー実装と,キュートマルチコントロールされたToffoliのすべてのバージョンを構築することができる。 結果の適用例として,3次古典可逆関数を$n$tritsでアンシラフリーなクォートユニタリとして実装する手順を提案する。
  論文  参考訳（メタデータ） (2022-04-01T16:21:43Z)
• Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits [12.462608802359936]
  Zimmert and Seldin (2021) の Tsallis-INF アルゴリズムに対する後悔の境界を改善した。 特に、$C = Thetaleft(fracTlog Tlog T$)$の場合、$T$が時空である場合、乗算因子による改善を達成します。 また, time horizon 上の後悔の依存性を $log t$ から $log frac(k-1)t(sum_ineq i*frac1delta_ に改善する。
  論文  参考訳（メタデータ） (2021-03-23T12:26:39Z)
• 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)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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