論文の概要: Minimum Weight Decoding in the Colour Code is NP-hard

• arxiv url: http://arxiv.org/abs/2603.04234v1
• Date: Wed, 04 Mar 2026 16:18:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-05 21:29:15.394932
• Title: Minimum Weight Decoding in the Colour Code is NP-hard
• Title（参考訳）: カラーコードにおける最小ウェイトデコーディングはNPハードである
• Authors: Mark Walters, Mark L. Turner,
• Abstract要約: 色コードの正確な復号化は NP-hard -- すなわち、P=NP でない限りアルゴリズムが存在しないことを示す。 これは、カラーコードの主要な競合相手であるサーフェスコードと顕著な対比である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: All utility-scale quantum computers will require some form of Quantum Error Correction in which logical qubits are encoded in a larger number of physical qubits. One promising encoding is known as the colour code which has broad applicability across all qubit types and can decisively reduce the overhead of certain logical operations when compared to other two-dimensional topological codes such as the surface code. However, whereas the surface code decoding problem can be solved exactly in polynomial time by finding minimum weight matchings in a graph, prior to this work, it was not known whether exact and efficient colour code decoding was possible. Optimism in this area, stemming from the colour code's significant structure and well understood similarities to the surface code, fanned this uncertainty. In this paper we resolve this, proving that exact decoding of the colour code is NP-hard -- that is, there does not exist a polynomial time algorithm unless P=NP. This highlights a notable contrast to some of the colour code's key competitors, such as the surface code, and motivates continued work in the narrower space of heuristic and approximate algorithms for fast, accurate and scalable colour code decoding.
• Abstract（参考訳）: すべてのユーティリティスケールの量子コンピュータは、論理量子ビットがより多くの物理量子ビットに符号化される量子誤り補正(Quantum Error Correction)を必要とする。 1つの有望なエンコーディングはカラーコードと呼ばれ、全てのキュービット型に適用可能であり、サーフェスコードのような他の2次元トポロジカルコードと比較して、ある論理演算のオーバーヘッドを決定的に低減することができる。 しかし, 表面符号復号化問題は, グラフ内の最小重みマッチングを求めることによって多項式時間で正確に解けるが, この研究以前には, 正確かつ効率的な色符号復号化が可能かは分かっていなかった。 この領域の最適化は、色コードの重要な構造と表面コードとのよく理解された類似性に起因し、この不確実性を扇動した。 本稿では、色符号の正確な復号化がNPハードであること、すなわち、P=NPでない限り多項式時間アルゴリズムは存在しないことを証明して、これを解決する。 これは、表面コードなど、カラーコードの主要な競合相手のいくつかと顕著な対比を示しており、高速で正確でスケーラブルなカラーコード復号のためのヒューリスティックおよび近似アルゴリズムの狭い領域での作業の動機となっている。

関連論文リスト

• Decoding 3D color codes with boundaries [0.9744114320491685]
  3次元(3D)カラーコードは、フォールトトレラント量子計算の有望な候補である。 従来の2次元カラーコード用デコーダを3次元に拡張する。 2Dおよび3Dカラーコード、エラー設定、デコードパスを視覚化するPythonパッケージであるqCodePlot3Dを提示する。
  論文  参考訳（メタデータ） (2025-12-15T15:30:54Z)
• Colour Codes Reach Surface Code Performance using Vibe Decoding [0.5242869847419834]
  2次元の量子色符号は、量子誤り訂正に重要な可能性を秘めている。 理論上の魅力にもかかわらず、これらのコードの実践的な展開は課題に直面している。 本稿では、表面コードと同等のカラーコード性能を初めてもたらすビブデコーディングについて紹介する。
  論文  参考訳（メタデータ） (2025-08-21T17:38:42Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  大規模計算には量子エラー補正(QEC)が必要であるが、かなりのリソースオーバーヘッドが発生する。 近年の進歩により、論理ゲートからなるアルゴリズムにおいて論理キュービットを共同で復号化することにより、症候群抽出ラウンドの数を削減できることが示されている。 ここでは、回路を介して伝播する関連する論理演算子製品を直接復号することで、回路の復号化の問題を修正する。
  論文  参考訳（メタデータ） (2025-05-19T18:00:00Z)
• Scaling and logic in the color code on a superconducting quantum processor [109.61104855764401]
  本稿では,超伝導プロセッサ上でのカラーコードのデモを行い,論理的誤りの抑制と論理的操作を行う。 汎用計算の鍵となるマジックステートを注入し、選択後99%以上の忠実性を達成する。 この研究は、超伝導プロセッサ上でのフォールトトレラント量子計算を実現するための、魅力的な研究方向としてカラーコードを確立する。
  論文  参考訳（メタデータ） (2024-12-18T19:00:05Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  低密度パリティ・チェック (LDPC) コードは、他の種類のコードに対していくつかの利点がある。 提案手法は,既存の人気符号の復号性能を桁違いに向上させる。
  論文  参考訳（メタデータ） (2024-06-09T12:08:56Z)
• Near-optimal decoding algorithm for color codes using Population Annealing [44.99833362998488]
  回復操作を高い確率で行うデコーダを実装した。 異なる雑音モデルの下で4.8.8色符号格子上でのデコーダ性能について検討する。
  論文  参考訳（メタデータ） (2024-05-06T18:17:42Z)
• Facilitating Practical Fault-tolerant Quantum Computing Based on Color Codes [0.6963971634605797]
  本研究では,カラーコードに基づく実用的なフォールトトレラント量子コンピューティングを実現するために,いくつかの重要な課題に対処する。 まず, 誤り率関連重み付き復号グラフを導入することにより, 三角色符号の0.57%の閾値を得た。 第2に,カラーコード格子手術の回路レベルの復号化について検討し,効率的な復号化アルゴリズムを提案する。 第3に, 三角カラーコードの新しい状態注入プロトコルを提案し, 従来の粗いプロトコルに比べて1ラウンド15～1の蒸留における出力マジック状態エラー率を2桁減らした。
  論文  参考訳（メタデータ） (2023-09-11T03:56:18Z)
• The domain wall color code [0.7224497621488285]
  量子誤り訂正カラーコードの新しい変種であるドメインウォールカラーコードを導入する。 この符号は、バイアスノイズを受ける量子ビットに対して、非常に高いコード容量エラー閾値を示す。
  論文  参考訳（メタデータ） (2023-06-30T18:00:06Z)
• Decoding quantum color codes with MaxSAT [4.29377170477633]
  我々は,LightsOut パズルに基づく MaxSAT 問題として定式化を用いた量子カラーコードのための新しいデコーダを提案する。 提案するデコーダの復号化性能は,カラーコード上での最先端の復号化性能を実現する。
  論文  参考訳（メタデータ） (2023-03-24T19:00:02Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• Morphing quantum codes [77.34726150561087]
  我々は15キュービットのReed-Muller符号を変形し、フォールトトレラントな論理的な$T$ゲートを持つ最小の安定化器符号を得る。 色符号を変形させることにより、ハイブリッドな色履歴符号の族を構築する。
  論文  参考訳（メタデータ） (2021-12-02T17:43:00Z)
• Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders [77.34726150561087]
  Restriction Decoderは、対応するトーリックコード復号が成功した場合に限り、カラーコードのエラーを修正する。 ビットフリップと位相フリップの雑音に対して、2次元、3次元のカラーコードに対する制限デコーダ閾値を数値的に推定する。
  論文  参考訳（メタデータ） (2019-05-17T17:41:50Z)

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

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