論文の概要: 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符号に対する線形時間消去復号アルゴリズムが未だ存在していないので、復号アルゴリズム全体の最終的な実行時間は線形ではないことに注意する。
関連論文リスト
- 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) - Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
量子量列挙子を最も一般的な形式で計算するための最初のテンソルネットワーク法を提供する。
非(Pauli)安定化器符号の場合、これはコード距離を計算するのに最適なアルゴリズムである。
これらの列挙子は論理的誤り率を正確に計算するために使用することができ、従って任意の単一キュービットやキューディットのエラーチャネルに対してデコーダを構築することができる。
論文 参考訳(メタデータ) (2023-08-09T18:00:02Z) - 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) - Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
ショアのアルゴリズムは、ノイズ中間量子時代の最も重要な量子アルゴリズムの1つであると考えられている。
Shorのアルゴリズムに必要なリソースを削減するために、我々は新しい分散量子古典ハイブリッド順序決定アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-24T13:52:05Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。