論文の概要: An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition

• arxiv url: http://arxiv.org/abs/2107.04298v3
• Date: Wed, 3 Nov 2021 13:09:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-23 00:00:29.585909
• Title: An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• Title（参考訳）: テンソル分解に基づく可逆論理回路合成アルゴリズム
• Authors: Hochang Lee and Kyung Chul Jeong and Daewan Han and Panjin Kim
• Abstract要約: 可逆論理合成のためのアルゴリズムを提案する。 写像は階数 ($2n-2$) テンソルのテンソル積と 2 倍の恒等行列のテンソル積と書くことができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: An algorithm for reversible logic synthesis is proposed. The task is, for a given $n$-bit substitution map $P_n: \{0,1\}^n \rightarrow \{0,1\}^n$, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates denoted by $C^m\!X$, where $m$ is the number of control bits that ranges from 0 to $n-1$. Controlled gates with large $m \,\,(>2)$ are then further decomposed into $C^0\!X$, $C^1\!X$, and $C^2\!X$ gates. A primary concern in designing the algorithm is to reduce the use of $C^2\!X$ gate (also known as Toffoli gate) which is known to be universal. The main idea is to view an $n$-bit substitution map as a rank-$2n$ tensor and to transform it such that the resulting map can be written as a tensor product of a rank-($2n-2$) tensor and the $2\times 2$ identity matrix. Let $\mathcal{P}_n$ be a set of all $n$-bit substitution maps. What we try to find is a size reduction map $\mathcal{A}_{\rm red}: \mathcal{P}_n \rightarrow \{P_n: P_n = P_{n-1} \otimes I_2\}$. %, where $I_m$ is the $m\times m$ identity matrix. One can see that the output $P_{n-1} \otimes I_2$ acts nontrivially on $n-1$ bits only, meaning that the map to be synthesized becomes $P_{n-1}$. The size reduction process is iteratively applied until it reaches tensor product of only $2 \times 2$ matrices.
• Abstract（参考訳）: 可逆論理合成のためのアルゴリズムを提案する。 与えられた$n$-bit置換写像 $P_n: \{0,1\}^n \rightarrow \{0,1\}^n$ に対して、地図を実装する可逆論理ゲートの列を見つける。 この作品で採用されたゲートライブラリは、複数の制御された toffoli ゲートから成り、$c^m\! X$、$m$は0から$n-1$までの制御ビットの数である。 大きな$m \,\,(>2)$の制御ゲートはさらに$C^0\!に分解される。 X$, $C^1\! X$, and $C^2\! X$ゲート。 アルゴリズムの設計における主な関心事は、$C^2\!の使用を減らすことである。 X$ゲート(トフォリゲートとも呼ばれる)は普遍的であることが知られている。 主なアイデアは、n$-bit置換写像をランク-$2n$テンソルとして表示し、その結果の写像をランク-($2n-2$)テンソルと$2\times 2$の同一行列のテンソル積として書けるように変換することである。 $\mathcal{P}_n$ をすべての$n$-bit置換写像の集合とする。 サイズ縮小写像 $\mathcal{A}_{\rm red}: \mathcal{P}_n \rightarrow \{P_n: P_n = P_{n-1} \otimes I_2\}$ が見つかる。 ここで$i_m$は$m\times m$ identity matrixである。 出力の$p_{n-1} \otimes i_2$が$n-1$bitsのみに対して非自明に振る舞うことが分かるので、合成されるマップは$p_{n-1}$となる。 サイズ削減プロセスは、わずか2 \times 2$行列のテンソル積に達するまで反復的に適用される。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Efficient $1$-bit tensor approximations [1.104960878651584]
  我々のアルゴリズムは、20ドルの擬似符号で効率よく符号付きカット分解を行う。 オープンテキストMistral-7B-v0.1大言語モデルの重み行列を50%の空間圧縮に近似する。
  論文  参考訳（メタデータ） (2024-10-02T17:56:32Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• Synthesis and Arithmetic of Single Qutrit Circuits [0.9208007322096532]
  本稿では,Clifford+$mathcalD$ゲート集合上の単語からなる単一量子回路について検討する。 我々は、$mathbbZ[xi, frac1chi]$のエントリを持つクォート単位ベクトルのクラスを$z$で特徴づける。
  論文  参考訳（メタデータ） (2023-11-15T04:50:41Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Synthesis and upper bound of Schmidt rank of the bipartite controlled-unitary gates [0.0]
  2(N-1)$ Generalized Control-X$ (GCX) gates, 6$ single-qubit rotations about the $y$- and $z$-axes, $N+5$ single-partite $y$- and $z$-rotation-types is required tosimulated it。 $mathcalU_cu(2otimes N)$および$mathcalU_cd(Motimes N)$を実装するための量子回路を提示する。
  論文  参考訳（メタデータ） (2022-09-11T06:24:24Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Coresets for Decision Trees of Signals [19.537354146654845]
  仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。 これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
  論文  参考訳（メタデータ） (2021-10-07T05:49:55Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

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

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