論文の概要: Viderman's algorithm for quantum LDPC codes
- arxiv url: http://arxiv.org/abs/2310.07868v1
- Date: Wed, 11 Oct 2023 20:17:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-14 13:54:11.492090
- Title: Viderman's algorithm for quantum LDPC codes
- Title（参考訳）: 量子LDPC符号に対するバイダーマンのアルゴリズム
- Authors: Anirudh Krishna, Inbal Livni Navon, Mary Wootters
- Abstract要約: 本稿では,量子LDPC符号に対するバイダーマンのアルゴリズムの一般化について述べる。
これは、定数レート量子LDPC符号に対して最大$Omega(D)$エラーを補正できる最初の消去変換アルゴリズムである。
- 参考スコア（独自算出の注目度）: 13.916368399461895
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum low-density parity-check (LDPC) codes, a class of quantum error
correcting codes, are considered a blueprint for scalable quantum circuits. To
use these codes, one needs efficient decoding algorithms. In the classical
setting, there are multiple efficient decoding algorithms available, including
Viderman's algorithm (Viderman, TOCT 2013). Viderman's algorithm for classical
LDPC codes essentially reduces the error-correction problem to that of
erasure-correction, by identifying a small envelope $L$ that is guaranteed to
contain the error set.
Our main result is a generalization of Viderman's algorithm to quantum LDPC
codes, namely hypergraph product codes (Tillich, Z\'emor, IEEE T-IT, 2013).
This is the first erasure-conversion algorithm that can correct up to
$\Omega(D)$ errors for constant-rate quantum LDPC codes, where $D$ is the
distance of the code. In that sense, it is also fundamentally different from
existing decoding algorithms, in particular from the small-set-flip algorithm
(Leverrier, Tillich, Z\'emor, FOCS, 2015). Moreover, in some parameter regimes,
our decoding algorithm improves on the decoding radius of existing algorithms.
We note that we do not yet have linear-time erasure-decoding algorithms for
quantum LDPC codes, and thus the final running time of the whole decoding
algorithm is not linear; however, we view our linear-time envelope-finding
algorithm as an important first step.
- Abstract（参考訳）: 量子誤り訂正符号のクラスであるLDPC符号は、スケーラブルな量子回路の青写真と見なされている。
これらのコードを使用するには、効率的な復号アルゴリズムが必要である。
古典的な設定では、Vidermanのアルゴリズム(Viderman, TOCT 2013)を含む複数の効率的な復号アルゴリズムが利用可能である。
古典的LDPC符号に対するビダーマンのアルゴリズムは、エラー集合を含むことが保証される小さなエンベロープ$L$を識別することにより、エラー訂正問題を消去補正の問題に本質的に還元する。
我々の主な成果は、バイダーマンのアルゴリズムを量子LDPC符号、すなわちハイパーグラフ製品符号(Tillich, Z\'emor, IEEE T-IT, 2013)に一般化することである。
これは、定数レートの量子LDPC符号に対して最大$\Omega(D)$エラーを修正できる最初の消去変換アルゴリズムである。
その意味では、既存の復号アルゴリズム、特に小さなセット・フリップアルゴリズム(leverrier, tillich, z\'emor, focs, 2015)とは根本的に異なる。
さらに,一部のパラメータでは,デコードアルゴリズムは既存のアルゴリズムのデコード半径を改善する。
我々は、量子ldpc符号に対する線形時間消去復号アルゴリズムが未だ存在していないので、復号アルゴリズム全体の最終的な実行時間は線形ではないことに注意する。
関連論文リスト
- Decoding Quasi-Cyclic Quantum LDPC Codes [23.22566380210149]
量子低密度パリティチェック(qLDPC)符号は耐故障性を求める上で重要な要素である。
近年のqLDPC符号の進歩は、量子的に良好であり、線形時間デコーダが符号ワード量子ビットの一定数に影響を与える誤りを正すという構成に繋がった。
実際には、2つの繰り返し符号の産物である表面/履歴符号は依然としてqLDPC符号として選択されることが多い。
論文 参考訳（メタデータ） (2024-11-07T06:25:27Z) - List Decodable Quantum LDPC Codes [49.2205789216734]
我々は、ほぼ最適レート距離のトレードオフを持つ量子低密度パリティチェック(QLDPC)符号の構成を行う。
復号化可能なQLDPCコードとユニークなデコーダを効率よくリストアップする。
論文 参考訳（メタデータ） (2024-11-06T23:08:55Z) - Engineering Quantum Error Correction Codes Using Evolutionary Algorithms [0.0]
量子誤り訂正と量子誤り訂正符号の使用は、実用的な量子コンピューティングの実現に不可欠である可能性が高い。
与えられたエラーモデルに対して最適な安定化器符号を求める新しい進化的アルゴリズムを提案する。
この研究の一環として、量子誤り訂正符号の距離を求める進化的アルゴリズムQDistEvolを導入する。
論文 参考訳（メタデータ） (2024-09-19T18:00:02Z) - Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。
本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
論文 参考訳（メタデータ） (2024-01-30T11:40:24Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Improved belief propagation decoding algorithm based on decoupling
representation of Pauli operators for quantum LDPC codes [8.811819329067285]
パウリ作用素を表す表現を、$GF(2)$ 上のベクトルとして分離する。
量子低密度パリティチェック符号に対する部分的に分離された信念伝搬と完全分離された信念伝搬復号アルゴリズム。
論文 参考訳（メタデータ） (2023-05-27T15:59:42Z) - Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。
RM符号は制限されたレートのみを許容する。
効率的なデコーダは、RM符号に対して有限長で利用可能である。
論文 参考訳（メタデータ） (2023-01-16T04:11:14Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - An efficient decoder for a linear distance quantum LDPC code [0.1657441317977376]
近年の量子的に優れたqLDPC符号に対する線形時間デコーダを提案する。
我々のデコーダは、一定サイズの領域内で補正を探索する反復アルゴリズムである。
論文 参考訳（メタデータ） (2022-06-14T02:17:09Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum message-passing algorithm for optimal and efficient decoding [2.3020018305241328]
我々はBPQMアルゴリズムの理解、形式、適用性を拡張する。
BPQMアルゴリズムの完全かつ曖昧さのない最初の公式記述を提供する。
BPQM がサイクルを持つ因子グラフ上で最も優れた古典デコーダを著しく上回ることを示す有望な数値結果を示す。
論文 参考訳（メタデータ） (2021-09-16T18:01:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。