論文の概要: CNOT-Distance is NP-complete under all-to-all connectivity

• arxiv url: http://arxiv.org/abs/2608.03825v1
• Date: Tue, 04 Aug 2026 15:34:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-05 15:30:23.26882
• Title: CNOT-Distance is NP-complete under all-to-all connectivity
• Title（参考訳）: CNOT-Distanceは全接続下でNP完全である
• Abstract要約: 固定ラベリングワイヤ上で全接続で$A$を少なくとも$K$CNOTゲートで実装可能であることを示す。 この問題がNP完全であることを証明する。
• 参考スコア（独自算出の注目度）: 0.69670060449041
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given $A\in\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)$, where $τ(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.
• Abstract（参考訳）: A\in\operatorname{GL}(N,2)$ と整数 $K$ が与えられたら、$A$ が少なくとも$K$ CNOT ゲートで実装できるかどうかを問う。 この問題がNP完全であることを証明する。 有限単純グラフ $G=(V,E)$ から、上単位角行列 $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ を満たす$\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)$ を構築する。 各対象行列は$O(N)$ 0 でないエントリを持ち、ハミング重みは最大 4 である。 下界は任意のCNOT回路をXOR有向非巡回グラフに展開し、プロジェクション・コントラクション演算を適用し、中間パリティのキャンセルと非制限再利用を可能にする。 この族にとって、最適条件は、回復しなければならない有限個の清浄または借用された補助ワイヤによって変化しない。 多項式時間デコーダは、任意の固定加法定数内での近似のNP硬度と、関連するCNOT回路最適化問題のAPX硬度を3乗グラフ上の最小頂点被覆からL還元することによって、さらに得られる。

関連論文リスト

• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Phase Transition in Convex Relaxations for Graph Alignment [6.515592049126884]
  相関したガウス直交アンサンブル(GOE)行列に対するグラフアライメント問題について検討する。 我々の結果は、$|Xstar-star|_F2$ が $= tildeo(n-1/2)$ から $= tilde(n-1/2)$ への遷移を正確に特徴づけている。
  論文  参考訳（メタデータ） (2026-06-14T03:47:45Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry [2.6140509675507384]
  我々は、$n$-vertex graph $G$の頂点を$n$-leafのルートツリー$mathcalB$の葉に埋め込む問題を考える。 我々は、グラフの異なる族における渋滞境界を、正規構造(ハイパーキューブと格子)、ランダムグラフ、量子回路のテンソルネットワーク表現と数値的に比較する。
  論文  参考訳（メタデータ） (2025-10-03T04:58:40Z)
• On Exact Sizes of Minimal CNOT Circuits [2.831145157553215]
  我々は、可逆性と量子コンピューティングの基本的なバイナリゲートであるCNOTゲートの回路を考える。 我々はG_n$で距離を計算する新しい手法を開発し、これまでは到達できなかった最小限の回路を合成する。 また、すべての$nleq 8$に対して、長い周期の置換が3(n-1)$で、以前の$nleq 5$の範囲を延ばすという予想も確認する。
  論文  参考訳（メタデータ） (2025-03-03T12:20:48Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice Gauge Theory [9.83302372715731]
  グラフ理論におけるハミルトンサイクル(HC)問題は、よく知られたNP完全問題である。 グラフを双対とする格子上で定義される$mathbbZ$格子ゲージ理論の観点でアプローチを提案する。 小さなグラフのランダムなサンプルでは、$sqrtN_hc$における$g_c$、$N_hc$がHCの数であり、$Nにおける$frac1g_c$の平均値に依存することが示される。
  論文  参考訳（メタデータ） (2022-02-17T18:39:42Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。 この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-10-29T07:35:46Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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