論文の概要: The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
- arxiv url: http://arxiv.org/abs/2603.22064v1
- Date: Mon, 23 Mar 2026 14:57:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-24 19:11:39.739469
- Title: The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
- Title（参考訳）: カラーコード、サーフェスコード、およびトランスバーサルCNOT:最小重復号のNP硬度
- Authors: Shouzhen Gu, Lily Wang, Aleksander Kubica,
- Abstract要約: 最小ウェイトデコーディングは3つのクインテシデント設定においてNPハードであることを示す。
この結果から,最小重復号法とその近似実現法の間の計算複雑性の急激な分離が明らかとなった。
- 参考スコア（独自算出の注目度）: 42.44256445495892
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The decoding problem is a ubiquitous algorithmic task in fault-tolerant quantum computing, and solving it efficiently is essential for scalable quantum computing. Here, we prove that minimum-weight decoding is NP-hard in three quintessential settings: (i) the color code with Pauli $Z$ errors, (ii) the surface code with Pauli $X$, $Y$ and $Z$ errors, and (iii) the surface code with a transversal CNOT gate, Pauli $Z$ and measurement bit-flip errors. Our results show that computational intractability already arises in basic and practically relevant decoding problems central to both quantum memories and logical circuit implementations, highlighting a sharp computational complexity separation between minimum-weight decoding and its approximate realizations.
- Abstract（参考訳）: 復号化問題はフォールトトレラント量子コンピューティングにおけるユビキタスアルゴリズムの課題であり、それを効率的に解くことはスケーラブルな量子コンピューティングにとって不可欠である。
ここでは、最小ウェイトデコーディングが3つのクインテシデント設定においてNPハードであることを証明する。
(i)Pauli$Z$エラーのカラーコード。
(ii) Pauli $X$, $Y$, $Z$エラー付きサーフェスコード
3) CNOT ゲートを横切り、Pauli $Z$ とビットフリップ誤差の測定を行う。
この結果から,量子メモリと論理回路実装の両面において,計算の難解性はすでに基本的かつ実用的な復号化問題で発生しており,最小重復号法とその近似実現法との間の計算複雑性の急激な分離が注目されている。
関連論文リスト
- Minimum Weight Decoding in the Colour Code is NP-hard [0.0]
色コードの正確な復号化は NP-hard -- すなわち、P=NP でない限りアルゴリズムが存在しないことを示す。
これは、カラーコードの主要な競合相手であるサーフェスコードと顕著な対比である。
論文 参考訳（メタデータ） (2026-03-04T16:18:18Z) - Bidirectional Decoding for Concatenated Quantum Hamming Codes [6.26319455798863]
スケーリングに要する時間を要する量子符号のハード決定デコーダを導入する。
独立したビットフリップノイズ下での量子ハミング符号 [15,3] に対して、双方向デコーダはしきい値を改善する。
この結果により,低オーバーヘッド型フォールトトレラント量子計算の競争性を高めることができる。
論文 参考訳（メタデータ） (2026-01-14T04:09:37Z) - Generative Decoding for Quantum Error-correcting Codes [6.964959672843989]
機械学習における生成モデリングを利用した復号化アルゴリズムを提案する。
自己回帰ニューラルネットワークを用いて、論理演算子とシンドロームの結合確率を教師なしで学習する。
提案手法は,実時間および高レートの量子誤り訂正符号をリアルタイムに復号化するための潜在的な解決策として,生成人工知能を強調している。
論文 参考訳（メタデータ） (2025-03-27T11:08:03Z) - Efficient and Universal Neural-Network Decoder for Stabilizer-Based Quantum Error Correction [44.698141103370546]
GraphQECは、線形時間複雑性を持つ安定化器コードのグラフ構造を機械学習に活用した、コードに依存しないデコーダである。
我々の手法は、任意の安定化符号をまたいだリアルタイム量子誤り訂正のための最初の普遍解である。
論文 参考訳（メタデータ） (2025-02-27T10:56:53Z) - Demonstrating dynamic surface codes [118.67046728951689]
曲面符号の3つの時間力学的実装を実験的に実証した。
まず、曲面コードを六角格子上に埋め込んで、キュービットあたりの結合を4つから3つに減らした。
第二に、サーフェスコードを歩き、データの役割を交換し、各ラウンドごとにキュービットを測定し、蓄積した非計算エラーの組込み除去による誤り訂正を達成する。
第3に、従来のCNOTの代わりにiSWAPゲートを用いた表面コードを実現し、追加のオーバーヘッドを伴わずに、エラー訂正のための実行可能なゲートセットを拡張した。
論文 参考訳（メタデータ） (2024-12-18T21:56:50Z) - Near-optimal decoding algorithm for color codes using Population Annealing [44.99833362998488]
回復操作を高い確率で行うデコーダを実装した。
異なる雑音モデルの下で4.8.8色符号格子上でのデコーダ性能について検討する。
論文 参考訳（メタデータ） (2024-05-06T18:17:42Z) - Comparative study of quantum error correction strategies for the heavy-hexagonal lattice [41.94295877935867]
トポロジカル量子誤差補正は、量子コンピュータのスケーリングロードマップにおけるマイルストーンである。
四角い格子面のコードは、この問題に対処するための作業場となっている。
しかし、一部のプラットフォームではゲートエラーを最小限に抑えるために接続性はさらに低く保たれている。
論文 参考訳（メタデータ） (2024-02-03T15:28:27Z) - 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) - Constant-Overhead Fault-Tolerant Quantum Computation with Reconfigurable
Atom Arrays [5.542275446319411]
再構成可能な原子配列上の高速qLDPC符号を用いて、フォールトトレラントな量子計算を行うハードウェア効率の手法を提案する。
本研究は,qLDPC符号を用いた低オーバヘッド量子コンピューティングの実用化への道を開くものである。
論文 参考訳（メタデータ） (2023-08-16T19:47:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。