論文の概要: Lower bounds for the CNOT-complexity of linear reversible operators
- arxiv url: http://arxiv.org/abs/2607.22248v1
- Date: Fri, 24 Jul 2026 12:31:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-27 20:58:57.124048
- Title: Lower bounds for the CNOT-complexity of linear reversible operators
- Title（参考訳）: 線型可逆作用素のCNOT-複素性に対する下界
- Abstract要約: $mathbbF$ 上の可逆行列の CNOT-複素性は、対応する線形可逆作用素を合成するのに必要となる CNOT ゲートの最小数である。
必要でない可逆線型作用素の加法的複雑性に対する下限は、小さな損失のみを伴って可逆集合へ持ち上げることができることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The CNOT-complexity of an invertible matrix over $\mathbb{F}_2$ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all $n \times n$ matrices is known to be $Θ(n^2 / \log n)$, no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity $3(n-1)$. We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least $4n - o(n)$, asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix $A \in \mathrm{GL}_{n}(\mathbb{F}_2)$, $n = 17167$, whose CNOT-complexity exceeds that of the cyclic permutation on $n$ symbols.
- Abstract（参考訳）: $\mathbb{F}_2$ 上の可逆行列の CNOT-複素性は、対応する線型可逆作用素を合成するのに必要となる CNOT ゲートの最小数である。
すべての$n \times n$ の行列の最大 CNOT-複素性は$(n^2 / \log n)$ であることが知られているが、超線型数の CNOT ゲートを必要とする行列の明示的な族は知られていない。
必要でない可逆線型作用素の加法的複雑性に対する下限は、小さな損失のみを伴って可逆集合へ持ち上げることができることを示す。
アプリケーションでは、誤り訂正符号のパリティチェック行列から構築された明示的な行列の族を記述し、CNOT-複素性は少なくとも4n - o(n)$で、周期置換を漸近的に上回っている。
さらに、この構成により、明示的な行列 $A \in \mathrm{GL}_{n}(\mathbb{F}_2)$, $n = 17167$ が得られる。
関連論文リスト
- CNOT-Distance is NP-complete under all-to-all connectivity [0.69670060449041]
固定ラベリングワイヤ上で全接続で$A$を少なくとも$K$CNOTゲートで実装可能であることを示す。
この問題がNP完全であることを証明する。
論文 参考訳（メタデータ） (2026-08-04T15:34:26Z) - Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates [0.0]
我々は、CNOT および行の複雑さが少なくとも 4n-texto(n)$ であるような、$mathbb Zn$ 上の可逆な$ntimes n$行列の明示的な族を提示する。
同じ複雑さの下位境界は、CNOTゲートを任意の局所線形論理ゲートに置き換える強い計算モデルである。
論文 参考訳（メタデータ） (2026-07-30T17:48:15Z) - Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。
我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
論文 参考訳（メタデータ） (2026-07-14T18:42:40Z) - The tetrahedral Horn problem and asymptotics of U(n) 6j symbols [2.2633707287259868]
ホーンの問題は、固有値 $(a,b,c,d,e,f)$ of Hermitian matrices $(A,B,C,D,E,F)$ を特徴づけることである。
本稿では,テトラシェドラ固有値 $(a,b,c,d,e,f)$ of Hermitian matrices $(A,B,C,D,E,F)$ of a tetrahedron。
論文 参考訳（メタデータ） (2025-10-06T15:00:25Z) - New Hardness Results for Low-Rank Matrix Completion [2.7624021966289605]
本稿では,低ランク行列補完問題に対する新しい$mathsfNP $-hardness結果を提案する。
十分大きな整数 $d$ と [ 2-O(d),frac17]$ の任意の実数 $varepsilon に対して、最大で 1 ドルの値が露出する部分行列 $A$ が与えられたとき、ランク $d$ の正の半有限完備化を許容するとすると、正の半定行列を見つけることは $mathsfNP$-hard である。
私たちの証明にはaが含まれる
論文 参考訳（メタデータ） (2025-06-23T09:22:28Z) - Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Word Linear Complexity of sequences and Local Inversion of maps over finite fields [0.0]
本稿では、有限体上のベクトル値列の概念を、そのアンサンブルの線形複素性$の拡張として展開する。
行列極小は、列が周期的であるとき、一意の局所逆の$x$ in $ffn$を解くために与えられた$ffn$ in $ffn$において、写像$F:ffnが反復的に生成したベクトルで使用できることを示す。
論文 参考訳（メタデータ） (2023-11-11T14:06:23Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
我々は、M$の回復のために証明不可能な非漸近誤差を伴い、M$の適切な低ランク条件下で核ノルム最小化問題を解くことで、M$を回復可能であることを示す。
シミュレーションデータの実験、MovieLens 100KデータセットとYale Bデータベースは、$textM3textOがいくつかのベースラインで最先端のパフォーマンスを達成し、高精度な地上真実対応を回復できることを示した。
論文 参考訳（メタデータ） (2021-10-15T09:27:50Z) - On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of
$\mathbb{R}^N$ with Boundary [0.4125187280299246]
mathbbRm × N$ のランダム行列 $A がバイリプシッツ函数 $A: MathcalM rightarrow mathbbRm$ とビリプシッツ定数が 1 に近い確率を考える。
我々は、$mathbbRN$ の十分低次元部分多様体を埋め込むための、高度に構造化された分布の新しいクラスを示す。
論文 参考訳（メタデータ） (2021-10-08T15:27:52Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Algebraic and geometric structures inside the Birkhoff polytope [0.0]
Birkhoff polytope $mathcalB_d$ は位数 $d$ のすべての双確率行列からなる。
我々は、$mathcalL_d$ と $mathcalF_d$ が平面行列に対して星型であることを証明する。
論文 参考訳（メタデータ） (2021-01-27T09:51:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。