論文の概要: NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

• arxiv url: http://arxiv.org/abs/2311.09503v1
• Date: Thu, 16 Nov 2023 01:58:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-17 17:05:16.479782
• Title: NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes
• Title（参考訳）: 低レート量子LDPC符号からのNLTSハミルトニアンと強指数SoS下界
• Authors: Louis Golowich and Tali Kaufman
• Abstract要約: 我々は NLTS (No Low-Energy Trivial States) 定理の改善と Sum-of-Squares 階層の線形数に対する明示的な下界を示す。 我々は、線形距離qLDPC符号に強い明示的非自明なコードワードを植え付ける新しい方法を導入し、その結果、強い明示的なSoS下界が得られる。
• 参考スコア（独自算出の注目度）: 0.7088856621650764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22). In this work, we obtain improvements to both of these results using qLDPC codes of low rate: - Whereas Anshu et al. only obtained NLTS Hamiltonians from qLDPC codes of linear dimension, we show the stronger result that qLDPC codes of arbitrarily small positive dimension yield NLTS Hamiltonians. - The SoS lower bounds of Hopkins and Lin are only weakly explicit because they require running Gaussian elimination to find a nontrivial codeword, which takes polynomial time. We resolve this shortcoming by introducing a new method of planting a strongly explicit nontrivial codeword in linear-distance qLDPC codes, which in turn yields strongly explicit SoS lower bounds. Our "planted" qLDPC codes may be of independent interest, as they provide a new way of ensuring a qLDPC code has positive dimension without resorting to parity check counting, and therefore provide more flexibility in the code construction.
• Abstract（参考訳）: 最初の漸近的に優れた量子ldpc(qldpc)符号の構成は、nlts(no low-energy trivial states)定理(anshu, breuckmann, nirkhe, stoc'23)とsos階層の線形数に対する明示的な下界(hopkins and lin, focs'22)という2つの複雑性理論のブレークスルーをもたらした。 本研究では, qldpc符号を低速で用いることにより, 両結果の改善が得られた: アンシュー等は線形次元のqldpc符号からnltsハミルトニアンのみを得たが, 任意に小さい正次元のqldpc符号ではnltsハミルトニアンが得られるという強い結果を示す。 -ホプキンスとlinのsos下限は、多項式時間を要する非自明なコードワードを見つけるためにガウス除去を実行する必要があるため、弱明示的である。 我々は、線形距離qLDPC符号に強い明示的非自明なコードワードを植え付ける新しい方法を導入することで、この欠点を解消する。 我々の「移植された」qLDPCコードは、パリティチェックカウントに頼らずに正次元のqLDPCコードを保証する新しい方法を提供し、コード構築においてより柔軟性を提供するため、独立した関心を持つかもしれない。

関連論文リスト

• 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)
• Decoding Quantum LDPC Codes Using Graph Neural Networks [52.19575718707659]
  グラフニューラルネットワーク(GNN)に基づく量子低密度パリティチェック(QLDPC)符号の新しい復号法を提案する。 提案したGNNベースのQLDPCデコーダは,QLDPC符号のスパースグラフ構造を利用して,メッセージパスデコーダとして実装することができる。
  論文  参考訳（メタデータ） (2024-08-09T16:47:49Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  LPN問題(Learning Parity with Noise)は、いくつかの古典的な暗号プリミティブの根底にある問題である。 本稿では,線形符号の復号化問題から,難易度がいくつか存在することの低減を試みている。 我々は、復号化の効率を、復号化のパラメータと問題の観点から特徴づける。
  論文  参考訳（メタデータ） (2024-08-07T12:54:43Z)
• Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [55.8930142490617]
  BPガイドデシミテーション(BPGD)に基づくQLDPC符号のデコーダを提案する。 BPGDは非収束によるBP故障率を著しく低下させる。
  論文  参考訳（メタデータ） (2023-12-18T05:58:07Z)
• Semidefinite programming bounds on the size of entanglement-assisted codeword stabilized quantum codes [5.13422222472898]
  我々は、CWS群の等方部分群とCWS型量子コードのワード演算子の集合を用いて、最小距離上の上限を導出する。 この特徴付けは、関連する距離列挙子に組み込むことができ、半定値制約を構築することができる。 SDP が LP のバウンダリよりも優れており、LP が有意義な結果を得るのに失敗するケースもいくつかある。
  論文  参考訳（メタデータ） (2023-11-13T07:01:58Z)
• Hierarchical memories: Simulating quantum LDPC codes with local gates [0.05156484100374058]
  一定のレートの低密度パリティチェック(LDPC)符号は、効率的なフォールトトレラント量子メモリを構築する上で有望な候補である。 我々は、多くの論理量子ビット K = Omega(N/log(N)2) を符号化する階層符号の新しい族を構築する。 保守的な仮定の下では、階層的コードは、全ての論理量子ビットが曲面コードに符号化される基本符号化よりも優れていることが分かる。
  論文  参考訳（メタデータ） (2023-03-08T18:48:12Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• Symbolic Distillation for Learned TCP Congestion Control [70.27367981153299]
  TCP渋滞制御は、深層強化学習(RL)アプローチで大きな成功を収めた。 ブラックボックスポリシーは解釈可能性と信頼性に欠けており、しばしば従来のTCPデータパスの外で運用する必要がある。 本稿では,まず深部RLエージェントを訓練し,次にNNポリシーをホワイトボックスの軽量なルールに蒸留する,両世界の長所を達成するための新しい2段階のソリューションを提案する。
  論文  参考訳（メタデータ） (2022-10-24T00:58:16Z)
• Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High Performance [5.33024001730262]
  我々は、線形符号化率、スケーリング距離、効率的な復号方式を用いて、低密度パリティチェック(LDPC)量子コード群を構築し、解析する。 コードファミリーは、Guth と Lubotzky が最初に示唆したように、閉じた4次元の双曲型のテッセルレーションに基づいている。
  論文  参考訳（メタデータ） (2020-01-10T17:21:27Z)

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

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