Fugu-MT 論文翻訳(概要): The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding

論文の概要: 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硬度
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$ とビットフリップ誤差の測定を行う。この結果から,量子メモリと論理回路実装の両面において,計算の難解性はすでに基本的かつ実用的な復号化問題で発生しており,最小重復号法とその近似実現法との間の計算複雑性の急激な分離が注目されている。

関連論文リスト

Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes [0.0]
位相量子符号の最小重復号法の計算複雑性について検討する。独立な$X$-および$Z$-errorモデルの下でのカラーコードについては、分離最小ウェイトデコードを考える。
論文参考訳（メタデータ） (2026-08-17T20:37:08Z)
Quantum error correction at ultra-low overhead [0.0]
大規模な量子コンピューティングにとって、エラーの抑制が中心的な課題である。実用的でハードウェア効率のよい量子低密度パリティチェック符号のファミリーであるCornucopia符号を紹介する。結果は、短期量子プロセッサの範囲内で超低オーバーヘッドの量子エラー補正のデモンストレーションをもたらす。
論文参考訳（メタデータ） (2026-08-03T18:13:57Z)
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)
Bidirectional Decoding for Concatenated Quantum Hamming Codes [6.26319455798863]
スケーリングに要する時間を要する量子符号のハード決定デコーダを導入する。独立したビットフリップノイズ下での量子ハミング符号 [15,3] に対して、双方向デコーダはしきい値を改善する。この結果により,低オーバーヘッド型フォールトトレラント量子計算の競争性を高めることができる。
論文参考訳（メタデータ） (2026-01-14T04:09:37Z)
Fast correlated decoding of transversal logical algorithms [67.01652927671279]
大規模計算には量子エラー補正(QEC)が必要であるが、かなりのリソースオーバーヘッドが発生する。近年の進歩により、論理ゲートからなるアルゴリズムにおいて論理キュービットを共同で復号化することにより、症候群抽出ラウンドの数を削減できることが示されている。ここでは、回路を介して伝播する関連する論理演算子製品を直接復号することで、回路の復号化の問題を修正する。
論文参考訳（メタデータ） (2025-05-19T18:00:00Z)
An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
量子機械学習(QML)は、量子コンピューティングの利点をデータ駆動タスクに移行しようとする分野である。入力をパウリ弦の有限集合にマッピングすることで、データ符号化に伴うコストを回避できる効率的な手法を提案する。我々は、古典的および量子モデルに対して、テキストおよび画像分類タスクに対する我々のアプローチを評価する。
論文参考訳（メタデータ） (2025-04-13T11:49:53Z)
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)
Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。 GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
論文参考訳（メタデータ） (2022-04-18T21:45:13Z)
Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文参考訳（メタデータ） (2021-08-03T17:49:09Z)

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