論文の概要: Approximately Decoding the Colour Code

• arxiv url: http://arxiv.org/abs/2606.18035v1
• Date: Tue, 16 Jun 2026 15:10:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-17 17:15:32.505862
• Title: Approximately Decoding the Colour Code
• Title（参考訳）: カラーコードのほぼ復号化
• Authors: Mark Walters,
• Abstract要約: 近年, (6.6.6) 色符号の最小重み復号化はNPハードであることが判明した。 本稿では,最小ウェイト復号を任意の時間で近似することが可能であることを証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently we showed that minimum weight decoding in the (6.6.6 planar) colour code is NP-hard. However, it remained an open question as to whether it was possible to approximate the minimum weight decoding arbitrarily closely in polynomial time. In this paper we prove that it is possible: for any $\varepsilon>0$ there is an polynomial time algorithm that, given a syndrome, can find an error-set generating that syndrome whose weight is at most $1+\varepsilon$ times the weight of the minimum weight decoding. As a consequence we see that, for any $\varepsilon>0$, there is a polynomial time algorithm that can correct all errors of weight up to $(1-\varepsilon)d/2$ in the distance $d$ colour code (so almost up to the theoretical $d/2$ limit). The polynomial we give is impractically large, but it does open the door for sensible polynomial time algorithms that approximate minimum weight decoding and, in particular, shows that approximate decoding is not NP-hard.
• Abstract（参考訳）: 近年, (6.6.6) 色符号の最小重み復号法はNPハードであることが判明した。 しかし、多項式時間において最小ウェイト復号を任意に近似できるかどうかについては、未解決の問題のままである。 任意の$\varepsilon>0$に対して、あるシンドロームが与えられた場合、そのシンドロームを最大で1+\varepsilon$の重さで生成する誤差セットを生成する多項式時間アルゴリズムが存在する。 その結果、任意の$\varepsilon>0$に対して、1-\varepsilon)d/2$までの全ての重みの誤差を、距離$d$カラーコードで補正できる多項式時間アルゴリズムが存在する(従って理論的な$d/2$制限まで)。 私たちが与える多項式は極端に大きいが、最小ウェイト復号法を近似する感度の高い多項式時間アルゴリズムの扉を開けており、特に、近似復号法がNPハードではないことを示す。

関連論文リスト

• A polynomial-time approximation scheme for minimum-weight decoding of topological codes [42.44256445495892]
  2D TTI)安定化符号の2次元トポロジカル変換は、フォールトトレラント量子計算の中心に位置する。 これらの符号の最小重復号化は、最近、基本的な設定でもNPハードであることが示されている。
  論文  参考訳（メタデータ） (2026-06-16T16:44:08Z)
• Minimum Weight Decoding in the Colour Code is NP-hard [0.0]
  色コードの正確な復号化は NP-hard -- すなわち、P=NP でない限りアルゴリズムが存在しないことを示す。 これは、カラーコードの主要な競合相手であるサーフェスコードと顕著な対比である。
  論文  参考訳（メタデータ） (2026-03-04T16:18:18Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
  ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。 一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
  論文  参考訳（メタデータ） (2022-10-20T19:35:50Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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