論文の概要: Cycle Codes and Decoded Quantum Interferometry

• arxiv url: http://arxiv.org/abs/2609.40036v1
• Date: Wed, 30 Sep 2026 16:07:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.026468
• Title: Cycle Codes and Decoded Quantum Interferometry
• Title（参考訳）: サイクル符号と復号量子干渉計
• Abstract要約: 固定されたインスタンスに対して不完全復号化が存在する場合の満足度保証を導出し、ランダムなインスタンスに対する事前結果を一般化する。 最小重復号法は、二進サイクル符号の既知の結果とは対照的に、$q>2$のすべてのフィールドに対してNPハードであることが示される。
• 参考スコア（独自算出の注目度）: 1.2336438977950792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed that DQI achieves a nontrivial satisfaction fraction guarantee only on linear-girth graphs, for which MaxCut is classically easy. However, these no-go results rely on minimum distance assumptions that do not represent true decodability thresholds for common noise channels, thus underestimating actual DQI performance. To estimate the true performance, we derive DQI satisfaction guarantees in the presence of imperfect decoding for fixed instances and generalize prior results for random instances. We then study homological cycle codes over arbitrary finite fields, and show that minimum-weight decoding is NP-hard for every field of size $q>2$, in contrast with known results for binary cycle codes. On the Linial--Simkin ensemble of regular graphs with logarithmic girth, we prove maximum-likelihood recovery bounds and a strong converse for a family of non-uniform additive noise channels. Moreover, LP decoders provide polynomial-time recovery of a positive fraction of randomly located errors with arbitrary values. These results allow us to prove upper and lower bounds on the approximate optima achievable by DQI when restricted to classical decoders. These bounds rule out quantum advantage in the regimes we analyze but also identify a family of regular Max-$k$-Cut instances on which DQI efficiently achieves a nontrivial satisfaction fraction guarantee.
• Abstract（参考訳）: 復号化量子干渉法(Decoded Quantum Interferometry, DQI)は、復号化サイクル符号に対する2変数制約による最適化問題を削減する。 そのような問題、すなわち MaxCut について、以前の研究は、DQI が古典的に簡単であるような線型グラフのみにおいて、非自明な満足度を保証できることを示した。 しかし、これらのno-goの結果は、一般的なノイズチャネルの真の陰極性閾値を表さない最小距離の仮定に依存し、実際のDQI性能を過小評価する。 真の性能を推定するために、固定されたインスタンスに対する不完全復号が存在する場合のDQI満足度保証を導出し、ランダムなインスタンスに対する事前結果を一般化する。 次に、任意の有限体上のホモロジーサイクル符号について研究し、最小重復号法は、二進サイクル符号の既知の結果とは対照的に、サイズ$q>2$のすべての体に対してNPハードであることを示す。 対数的ギルスを持つ正則グラフのLinial-Simkinアンサンブルについて、我々は、一様でない加法的雑音チャネルの族に対する最大様の回復境界と強い逆を証明した。 さらに、LPデコーダは任意の値でランダムに位置付けられたエラーの正の分数の多項式時間回復を提供する。 これらの結果により、古典デコーダに制限された場合、DQIにより達成可能な近似オプティマ上の上下境界を証明できる。 これらの境界は、我々が分析したレジームにおける量子的優位性を排除し、DQIが非自明な満足度保証を効率的に達成する通常のMax-$k$-Cutインスタンスの族を識別する。

関連論文リスト

• Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming [4.207274960389197]
  ランク分解動的プログラミングに基づく新しい復号アルゴリズム(Rank DP)を提案する。 パンクされた量子リード・ミュラー符号のデコーダ時間デコードと、独立した単一量子ビットパウリ雑音の下で距離が増大するステイン結合族を与える。
  論文  参考訳（メタデータ） (2026-09-30T11:54:18Z)
• Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes [9.855041870231533]
  BPQM (Breief propagation with quantum message) は、古典的量子チャネル上で伝送される古典的符号を復号する量子アルゴリズムである。 ランダム$q$-ary LDPC符号に対する2段階BPQMデコーダを対称$q$-ary純状態チャネル上に構築する。 アンサンブル平均ブロックエラー確率はブロック長$N$が無限大になる傾向にあるため消滅することを示す。
  論文  参考訳（メタデータ） (2026-09-05T03:36:03Z)
• The Near-optimal Performance of Quantum Error Correction Codes [2.670972517608388]
  任意の符号と雑音に対する簡潔で最適化のない計量である準最適チャネル忠実度を導出する。 従来の最適化手法と比較して、計算コストの削減により、以前はアクセス不能なサイズであったシステムをシミュレートすることができる。 熱力学符号とGottesman-Kitaev-Preskill (GKP)符号のほぼ最適性能を解析的に導出した。
  論文  参考訳（メタデータ） (2024-01-04T01:44:53Z)
• Single-shot decoding of good quantum LDPC codes [38.12919328528587]
  量子タナー符号が逆雑音の単ショット量子誤り補正(QEC)を促進することを証明した。 本稿では,複数ラウンドのQECにおける誤りを抑えるために,並列復号アルゴリズムを各ラウンドで一定時間実行するのに十分であることを示す。
  論文  参考訳（メタデータ） (2023-06-21T18:00:01Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• Finite-rate sparse quantum codes aplenty [1.1279808969568252]
  本稿では、ランダムな二部グラフ上の制約満足度問題(CSP)を解決するために、ランダムなマルチキュービット安定化器符号を生成する手法を提案する。 現状のCSPソルバを用いて、満足度しきい値の存在を証明できる証拠を得る。 良好な位相にあるスパース符号は、消去ノイズのチャネル容量を実質的に達成する。
  論文  参考訳（メタデータ） (2022-07-07T20:39:39Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Tailored XZZX codes for biased noise [60.12487959001671]
  我々は,XZX型安定化器発生器を有する符号群について検討した。 これらのXZZX符号は、バイアスノイズに合わせると、非常に量子効率が高いことを示す。
  論文  参考訳（メタデータ） (2022-03-30T17:26:31Z)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  高速かつ高精度なデコーダを導入し、幅広い種類の量子誤り訂正符号で使用することができる。 我々のデコーダは、信仰マッチングと信念フィンドと呼ばれ、すべてのノイズ情報を活用し、QECの高精度なデモを解き放つ。 このデコーダは, 標準の正方形曲面符号に対して, 整形曲面符号において, より高いしきい値と低い量子ビットオーバーヘッドをもたらすことがわかった。
  論文  参考訳（メタデータ） (2022-03-09T18:48:54Z)

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

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