論文の概要: Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

• arxiv url: http://arxiv.org/abs/2609.22669v1
• Date: Sat, 19 Sep 2026 00:57:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:00.516001
• Title: Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance
• Title（参考訳）: 量子及びグラフ状態距離に対する平均自己双対補完と最適付加硬度
• Abstract要約: 量子符号距離はNPハードであり、加算誤差が$c N$であることを示す。 また,Grigorescu,Jha,Sampertonのグラフ状態距離の硬さギャップも改善する。 私たちの結果は、同じ$X$-と$Z$-checkスペースを持つCSSコードに対して成り立ちます。
• 参考スコア（独自算出の注目度）: 10.743153145077686
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.
• Abstract（参考訳）: 量子符号距離は、ある定数$c >0$に対して$c N$の加算誤差内で近似するNPハードであることが証明される。 私たちの削減は決定論的です。 これにより、以前の平方根加法ギャップが$Ω(N)$に改善され、カプシカールとクンドゥの明示された線型ギャップ問題が解決される。 この結果は、同一の$X$-および$Z$-checkスペースを持ち、一定のレートと一定の相対距離を持つCSSコードに対して成り立つ。 すべての固定された $λ>1$ に対して、一定の $c>0$ が存在し、全ての非恒等安定器が量子距離の $λ$ 以上の重みを持つときでさえ硬さが保たれる。 また、Grigorescu, Jha, Samperton の頂点上でのグラフ状態距離の硬さギャップを立方根から $Ω(N)$ に改善し、明示された開問題を解決する。 どちらの硬度も、どちらの距離も最高$N$であるため、漸近的に最適である。 我々のグラフ状態距離硬度結果は、その逆行列である2値の隣接行列を持つバランスの取れた二部グラフに対して成り立つ(mod 2)。 上記の2つのハードネス境界に対する我々の主要なテクニックは古典的であり、任意のコード$C$ of length $m$を自己双対コード$A(C)$ of length $N=\(m)$に変換する方法を示しながら、元のコセット計量を正確に2倍にする。 変換は決定論的かつ効率的である。 これを$C$の自己双対完備化と呼ぶ。 線型埋め込みは$τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$である。 埋め込みは、$\mathbb F_2^m$ のベクトル間のハミング距離と、対応する余集合間のすべてのペア距離を2倍にする。 埋め込みはまた、$A(C)$のすべてのコードワードが$200m$でちょうど$τ(C)$であることを保証する。

関連論文リスト

• Quantum Query Complexity of Persistence Statistics in Graph Zigzags [2.895030292351388]
  本研究では、スナップショット・アジャシエンスビットからジグザグバー寿命のスカラーサマリーを推定するクエリ複雑性について検討した。 ランクがグラフの回路ランクであるグラフの場合、非線形バーコード関数はエッジと成分数の平均となる。 すべての固定パワーウェイトに対して$xr$,$rge2$、均一ウィンドウ平均では、最悪のケースの複雑さは$widetilde(nsqrt m/varepsilon)$ Quantumと$(n2m)$ classicalである。
  論文  参考訳（メタデータ） (2026-09-05T02:16:28Z)
• 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)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• 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)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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