論文の概要: Quantum message-passing algorithm for optimal and efficient decoding
- arxiv url: http://arxiv.org/abs/2109.08170v2
- Date: Wed, 17 Aug 2022 16:02:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-14 20:49:38.771566
- Title: Quantum message-passing algorithm for optimal and efficient decoding
- Title（参考訳）: 最適かつ効率的な復号化のための量子メッセージパッシングアルゴリズム
- Authors: Christophe Piveteau and Joseph M. Renes
- Abstract要約: 我々はBPQMアルゴリズムの理解、形式、適用性を拡張する。
BPQMアルゴリズムの完全かつ曖昧さのない最初の公式記述を提供する。
BPQM がサイクルを持つ因子グラフ上で最も優れた古典デコーダを著しく上回ることを示す有望な数値結果を示す。
- 参考スコア（独自算出の注目度）: 8.122270502556372
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, Renes proposed a quantum algorithm called belief propagation with
quantum messages (BPQM) for decoding classical data encoded using a binary
linear code with tree Tanner graph that is transmitted over a pure-state CQ
channel [Renes, NJP 19 072001 (2017)]. The algorithm presents a genuine quantum
counterpart to decoding based on the classical belief propagation algorithm,
which has found wide success in classical coding theory when used in
conjunction with LDPC or Turbo codes. More recently Rengaswamy et al. [npj
Quantum Information 7 97 (2021)] observed that BPQM implements the optimal
decoder on a small example code. Here we significantly expand the
understanding, formalism, and applicability of the BPQM algorithm with the
following contributions. First, we prove analytically that BPQM realizes
optimal decoding for any binary linear code with tree Tanner graph. We also
provide the first formal description of the BPQM algorithm in full detail and
without any ambiguity. In so doing, we identify a key flaw overlooked in the
original algorithm and subsequent works which implies quantum circuit
realizations will be exponentially large in the code dimension. Although BPQM
passes quantum messages, other information required by the algorithm is
processed globally. We remedy this problem by formulating a truly
message-passing algorithm which approximates BPQM and has quantum circuit
complexity $\mathcal{O}(\text{poly } n, \text{polylog } \frac{1}{\epsilon})$,
where $n$ is the code length and $\epsilon$ is the approximation error.
Finally, we also propose a novel method for extending BPQM to factor graphs
containing cycles by making use of approximate cloning. We show some promising
numerical results that indicate that BPQM on factor graphs with cycles can
significantly outperform the best possible classical decoder.
- Abstract（参考訳）: 近年では、純粋状態CQチャネル(Renes, NJP 19 072001 (2017))を介して伝送される木タナーグラフを持つバイナリ線形コードを用いて符号化された古典的データを復号化するための、BPQMを用いた信念伝播と呼ばれる量子アルゴリズムが提案されている。
このアルゴリズムは、LDPCやTurboコードと組み合わせて使用する場合、古典的符号化理論において広く成功した古典的信念伝播アルゴリズムに基づく復号法と真に相反する量子を提示する。
最近ではRengaswamyなど。
[npj Quantum Information 7 97 (2021)] はBPQMが小さなサンプルコードに最適なデコーダを実装していることを観測した。
ここでは,BPQMアルゴリズムの理解,形式性,適用性を大幅に拡張し,次のような貢献を行う。
まず、bpqm がツリータナーグラフを持つ任意のバイナリ線形コードに対して最適な復号を実現することを解析的に証明する。
また,bpqmアルゴリズムの完全かつ曖昧さのない,最初の形式的記述も提供する。
このようにして、元のアルゴリズムで見過ごされている重要な欠陥を特定し、量子回路の実現がコード次元において指数関数的に大きくなることを示唆する。
BPQMは量子メッセージを渡すが、アルゴリズムが必要とする他の情報は世界中で処理される。
我々は、bpqmに近似し、量子回路の複雑性$\mathcal{o}(\text{poly } n, \text{polylog } \frac{1}{\epsilon})$を持つ真にメッセージパッシングアルゴリズムを定式化し、この問題を解決した。
最後に, bpqmを近似クローニングを用いて周期を含む因子グラフに拡張する新しい手法を提案する。
BPQM がサイクルを持つ因子グラフ上で最も優れた古典デコーダを著しく上回ることを示す有望な数値結果を示す。
関連論文リスト
- Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
量子量列挙子を最も一般的な形式で計算するための最初のテンソルネットワーク法を提供する。
非(Pauli)安定化器符号の場合、これはコード距離を計算するのに最適なアルゴリズムである。
これらの列挙子は論理的誤り率を正確に計算するために使用することができ、従って任意の単一キュービットやキューディットのエラーチャネルに対してデコーダを構築することができる。
論文 参考訳（メタデータ） (2023-08-09T18:00:02Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum Sparse Coding [5.130440339897477]
我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。
量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。
我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
論文 参考訳（メタデータ） (2022-09-08T13:00:30Z) - Belief Propagation with Quantum Messages for Symmetric Classical-Quantum
Channels [6.831109886531548]
2016年、リースは量子メッセージ(BPQM)を用いた信念の伝播を導入した。
我々は、BPQMを、対称的「ペアド計測」の実装に基づいて、一般二項入力対称古典量子(BSCQ)チャネルに拡張することを提案する。
論文 参考訳（メタデータ） (2022-07-11T16:14: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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Log-domain decoding of quantum LDPC codes over binary finite fields [4.340338299803562]
2次有限体 GF$(q=2l)$ 上での量子低密度パリティチェック(LDPC)符号の復号について、総和積アルゴリズム(英語版)を用いて検討する。
従来のBPに必要なベクトルメッセージよりも,非二項量子符号のBP復号に十分であることを示す。
論文 参考訳（メタデータ） (2021-04-01T07:15:41Z) - Classical Coding Approaches to Quantum Applications [2.5382095320488665]
深宇宙光通信では、純状態量子チャネルの電流受信機がまず各キュービットチャネルの出力を測定し、古典的にその測定を後処理する。
本論文では, 古典的信念伝達アルゴリズムに触発された近年提案された量子アルゴリズムについて考察する。
提案アルゴリズムは各ビットに対して最適であり,全送信メッセージを決定する際に最適な性能が得られることを示す。
論文 参考訳（メタデータ） (2020-04-14T23:31:46Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Pruning Neural Belief Propagation Decoders [77.237958592189]
本稿では,機械学習を用いたBPデコードに対して,過剰完全パリティチェック行列を調整する手法を提案する。
我々は,デコーダの複雑さを低減しつつ,0.27dB,1.5dBのML性能を実現する。
論文 参考訳（メタデータ） (2020-01-21T12:05:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。