論文の概要: 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コードを保証する新しい方法を提供し、コード構築においてより柔軟性を提供するため、独立した関心を持つかもしれない。
関連論文リスト
- Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [54.30748817277323]
BP Guided decimation (BPGD) を用いたQLDPC符号の復号化を提案する。
BPGDは非収束性によるBP障害を著しく減少させる。
誤差収束の確率は低く、BP-OSDやBP-SIと同等の性能を発揮する。
論文 参考訳(メタデータ) (2023-12-18T05:58:07Z) - Semidefinite programming bounds on the size of entanglement-assisted
codeword stabilized quantum codes [5.770351255180495]
我々は、CWS群の等方部分群とCWS型量子コードのワード演算子の集合を用いて、最小距離上の上限を導出する。
この特徴付けは、関連する距離列挙子に組み込むことができ、半定値制約を構築することができる。
SDP が LP のバウンダリよりも優れており、LP が有意義な結果を得るのに失敗するケースもいくつかある。
論文 参考訳(メタデータ) (2023-11-13T07:01:58Z) - Quaternary Neural Belief Propagation Decoding of Quantum LDPC Codes with
Overcomplete Check Matrices [45.997444794696676]
量子低密度パリティチェック(QLDPC)符号は、量子コンピュータにおける誤り訂正の候補として有望である。
量子コンピュータでQLDPCコードを実装する際の大きな課題の1つは、普遍デコーダの欠如である。
まず、オーバーコンプリートチェック行列で動作する信念伝搬(BP)デコーダを用いてQLDPC符号を復号する。
我々は,QLPDC符号の最適2値BPデコーダとして研究されたNBPデコーダを,第4次BPデコーダに拡張する。
論文 参考訳(メタデータ) (2023-08-16T08:24:06Z) - 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) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳(メタデータ) (2021-08-10T15:00:20Z) - Sample Efficient Reinforcement Learning In Continuous State Spaces: A
Perspective Beyond Linearity [50.38337893712897]
線形性を仮定しないMDP上の構造条件であるEPW(Effective Planning Window)条件を導入する。
EPW条件は、この条件を満たすMDPを確実に解くアルゴリズムを提供することで、サンプル効率のよいRLを許容することを示した。
また, EPW のような条件の必要性も示し, わずかに非線形な単純な MDP を効率的にサンプリングできないことを示した。
論文 参考訳(メタデータ) (2021-06-15T00:06:59Z) - Circuit lower bounds for low-energy states of quantum code Hamiltonians [17.209060627291315]
量子誤り訂正符号から生じる局所ハミルトニアンの低エネルギー状態の回路境界を証明した。
物理系においても,低深度状態では地盤エネルギーを正確に近似することはできない。
論文 参考訳(メタデータ) (2020-11-03T22:36:22Z) - Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High
Performance [5.33024001730262]
我々は、線形符号化率、スケーリング距離、効率的な復号方式を用いて、低密度パリティチェック(LDPC)量子コード群を構築し、解析する。
コードファミリーは、Guth と Lubotzky が最初に示唆したように、閉じた4次元の双曲型のテッセルレーションに基づいている。
論文 参考訳(メタデータ) (2020-01-10T17:21:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。