論文の概要: A polynomial-time approximation scheme for minimum-weight decoding of topological codes

• arxiv url: http://arxiv.org/abs/2606.18145v1
• Date: Tue, 16 Jun 2026 16:44:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-17 17:15:32.55486
• Title: A polynomial-time approximation scheme for minimum-weight decoding of topological codes
• Title（参考訳）: 位相符号の最小重復号のための多項式時間近似法
• Authors: Shouzhen Gu, Lily Wang, Aleksander Kubica,
• Abstract要約: 2D TTI)安定化符号の2次元トポロジカル変換は、フォールトトレラント量子計算の中心に位置する。 これらの符号の最小重復号化は、最近、基本的な設定でもNPハードであることが示されている。
• 参考スコア（独自算出の注目度）: 42.44256445495892
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli $Z$ errors and the toric code with Pauli $X$, $Y$ and $Z$ errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant $\varepsilon>0$, a recovery operator of weight within a multiplicative factor of $1+\varepsilon$ of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.
• Abstract（参考訳）: 2次元トポロジカル変換不変(2D TTI)安定化符号は、フォールトトレラント量子計算の中心にあるが、それを用いることで復号問題を解く必要がある。 例えば、Pauli $Z$エラーのカラーコードや、Pauli $X$、$Y$、$Z$エラーのトーリックコードなどである。 ここでは、多項式時間近似スキーム(PTAS)、すなわち任意の定数$\varepsilon>0$に対して、最小値の1+\varepsilon$の乗算係数内の重みの回復作用素が多項式時間で見つかるにもかかわらず、2D TTI符号の最小ウェイト復号が可能であることを証明する。 提案手法は, 旅行セールスマン問題などのユークリッド問題に対するAroraのPTASに基づいており, 文字列のようなエラーで接続された点状励起をデコードする場合に適用する。 したがって、2次元を超えて、特定の高次元トポロジー符号と量子記憶をカバーし、表現論的または回路レベルのノイズを持つトーリック符号を含む。

関連論文リスト

• The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding [42.44256445495892]
  最小ウェイトデコーディングは3つのクインテシデント設定においてNPハードであることを示す。 この結果から,最小重復号法とその近似実現法の間の計算複雑性の急激な分離が明らかとなった。
  論文  参考訳（メタデータ） (2026-03-23T14:57:38Z)
• Parallel Logical Measurements via Quantum Code Surgery [42.95092131256421]
  量子符号手術(Quantum code surgery)は、量子誤り訂正符号の論理的測定を行うための、柔軟で低オーバーヘッドな技術である。 本稿では,量子ビット安定化器の低密度パリティチェック(LDPC)コードに適用可能なコード手術方式を提案する。
  論文  参考訳（メタデータ） (2025-03-06T22:05:52Z)
• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  クビットCSSコード間の手術を自動化するための,オープンソースの軽量PythonパッケージであるSSIP(Identifying Pushouts)による安全手術について述べる。 ボンネットの下では、鎖複体の圏における普遍構成によって支配される$mathbbF$上の線型代数を実行する。 高い符号距離を犠牲にすることなく,手術によって様々な論理的測定を安価に行うことができることを示す。
  論文  参考訳（メタデータ） (2024-07-12T16:50:01Z)
• Extracting topological orders of generalized Pauli stabilizer codes in two dimensions [5.593891873998947]
  本稿では,2次元システムにおける変換不変な一般化されたパウリ安定化符号から位相データを抽出するアルゴリズムを提案する。 このアルゴリズムは$mathbbZ_d$ quditsに適用される。
  論文  参考訳（メタデータ） (2023-12-18T13:18:19Z)
• Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders [77.34726150561087]
  Restriction Decoderは、対応するトーリックコード復号が成功した場合に限り、カラーコードのエラーを修正する。 ビットフリップと位相フリップの雑音に対して、2次元、3次元のカラーコードに対する制限デコーダ閾値を数値的に推定する。
  論文  参考訳（メタデータ） (2019-05-17T17:41:50Z)

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

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