論文の概要: Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

• arxiv url: http://arxiv.org/abs/2608.17109v3
• Date: Tue, 25 Aug 2026 08:28:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-26 14:09:33.644047
• Title: Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes
• Title（参考訳）: 2次元位相量子符号の最小重復号に対する近似の硬さ
• Abstract要約: 位相量子符号の最小重復号法の計算複雑性について検討する。 独立な$X$-および$Z$-errorモデルの下でのカラーコードについては、分離最小ウェイトデコードを考える。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, there exists a constant $c>0$ such that no polynomial-time algorithm can always produce a solution whose weight is within $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $Ω(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
• Abstract（参考訳）: フォールトトレラント量子コンピュータの実現には、効率的な復号化が不可欠である。 位相量子符号の最小重復号法の計算複雑性について検討する。 分極チャネル下の曲面符号に対しては、最小重み付きパウリ誤差を求める最小重み付きデコードを考える。 独立な$X$-および$Z$-errorモデルの下でのカラーコードについては、分離最小ウェイトデコードを考える。 P\neq NP$ を仮定すると、これらの問題に対して多項式加法的不近似ギャップが成立する。 具体的には、トーラス上のトーリックコードと4.8.8ドルのカラーコードに対して、多項式時間アルゴリズムが常に最適な$cN^{1/14}$以内の解を生成できないような定数$c>0$が存在する。 平面曲面符号に対して、$Ω(N^{1/18})$ギャップを得る。 我々は,Håstad の MAX-3SAT に対する近似の硬さを利用する。 我々の還元は、論理的制約を結合された原始的結合問題に埋め込むための一般的なモジュラーな枠組みを格子上に展開する。 鍵となる要素は、構成の異なる部分間の意図しない相互作用を制御するローカライズ引数である。

関連論文リスト

• Entropic Rigidity in Quantum Memories: How Geometry and Algebra Control the Onset of Degeneracy Corrections [4.226475360842309]
  それらの論理的勝者集合が不随意となるとき、最初の物理的誤差重量$m$を決定する。 オンセットは、物理ノイズ強度の$m$2のパワーに比例して、主要な動作障害ギャップを修正する。
  論文  参考訳（メタデータ） (2026-08-19T01:17:59Z)
• 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)
• 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)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks [18.20811830109862]
  我々は、線形次元と距離が非クリフォードゲートをサポートする最初の既知の量子符号を構築した。 これらの符号に対する効率的な復号化アルゴリズムを設計する。 我々の結果は、関数を変換への部分アクセスから再構成するPronyの手法の新たな一般化と見なすことができる。
  論文  参考訳（メタデータ） (2025-10-08T09:27:41Z)
• Demonstrating dynamic surface codes [118.67046728951689]
  曲面符号の3つの時間力学的実装を実験的に実証した。 まず、曲面コードを六角格子上に埋め込んで、キュービットあたりの結合を4つから3つに減らした。 第二に、サーフェスコードを歩き、データの役割を交換し、各ラウンドごとにキュービットを測定し、蓄積した非計算エラーの組込み除去による誤り訂正を達成する。 第3に、従来のCNOTの代わりにiSWAPゲートを用いた表面コードを実現し、追加のオーバーヘッドを伴わずに、エラー訂正のための実行可能なゲートセットを拡張した。
  論文  参考訳（メタデータ） (2024-12-18T21:56:50Z)
• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  クビットCSSコード間の手術を自動化するための,オープンソースの軽量PythonパッケージであるSSIP(Identifying Pushouts)による安全手術について述べる。 ボンネットの下では、鎖複体の圏における普遍構成によって支配される$mathbbF$上の線型代数を実行する。 高い符号距離を犠牲にすることなく,手術によって様々な論理的測定を安価に行うことができることを示す。
  論文  参考訳（メタデータ） (2024-07-12T16:50:01Z)
• The closed-branch decoder for quantum LDPC codes [0.0]
  実時間復号化は論理レベルで任意の量子計算を実装する上で必要である。 本稿では,量子低密度パリティチェック(QLDPC)のための新しいデコーダを提案する。
  論文  参考訳（メタデータ） (2024-02-02T16:22:32Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
  ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。 一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
  論文  参考訳（メタデータ） (2022-10-20T19:35:50Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)

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

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