論文の概要: Locality vs Quantum Codes
- arxiv url: http://arxiv.org/abs/2409.15203v1
- Date: Mon, 23 Sep 2024 16:50:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-26 14:02:53.163829
- Title: Locality vs Quantum Codes
- Title（参考訳）: 局所性対量子符号
- Authors: Samuel Dai, Ray Li,
- Abstract要約: 量子符号は量子フォールトトレランスへの有望な道を提供するが、局所性の実践的な制約はそれらの品質を制限している。
本稿では,量子誤り訂正符号の局所性とパラメータ間の最適トレードオフを証明した。
- 参考スコア（独自算出の注目度）: 8.747606955991708
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper proves optimal tradeoffs between the locality and parameters of quantum error-correcting codes. Quantum codes give a promising avenue towards quantum fault tolerance, but the practical constraint of locality limits their quality. The seminal Bravyi-Poulin-Terhal (BPT) bound says that a $[[n,k,d]]$ quantum stabilizer code with 2D-locality must satisfy $kd^2\le O(n)$. We answer the natural question: for better code parameters, how much "non-locality" is needed? In particular, (i) how long must the long-range interactions be, and (ii) how many long-range interactions must there be? We give a complete answer to both questions for all $n,k,d$: above the BPT bound, any 2D-embedding must have at least $\Omega(\#^*)$ interactions of length $\Omega(\ell^*)$, where $\#^*= \max(k,d)$ and $\ell^*=\max\big(\frac{d}{\sqrt{n}}, \big( \frac{kd^2}{n} \big)^{1/4} \big)$. Conversely, we exhibit quantum codes that show, in strong ways, that our interaction length $\ell^*$ and interaction count $\#^*$ are asymptotically optimal for all $n,k,d$. Our results generalize or improve all prior works on this question, including the BPT bound and the results of Baspin and Krishna. One takeaway of our work is that, for any desired distance $d$ and dimension $k$, the number of long-range interactions is asymptotically minimized by a good qLDPC code of length $\Theta(\max(k,d))$. Following Baspin and Krishna, we also apply our results to the codes implemented in the stacked architecture and obtain better bounds. In particular, we rule out any implementation of hypergraph product codes in the stacked architecture.
- Abstract（参考訳）: 本稿では,量子誤り訂正符号の局所性とパラメータ間の最適トレードオフを証明した。
量子符号は量子フォールトトレランスへの有望な道を提供するが、局所性の実践的な制約はそれらの品質を制限している。
半正則ブラヴィ・プーリン・ターハル境界(BPT)は、[[n,k,d]]$ 2D-局所性を持つ量子安定化符号は、$kd^2\le O(n)$を満たす必要があると述べている。
より優れたコードパラメータには、どの程度の"非ローカル性"が必要ですか?
特に
i) 長距離の相互作用がどのくらい長くなければならないか、そして
(ii) どのくらいの長距離相互作用が必要か?
BPT境界の上に、任意の2D埋め込みは少なくとも$\Omega(\#^*)$長さ$\Omega(\ell^*)$と$\ell^*= \max(k,d)$と$\ell^*=\max(\frac{d}{\sqrt{n}}, \big( \frac{kd^2}{n} \big)^{1/4} \big)$の相互作用を持つ必要がある。
逆に、強い方法で、相互作用長$\ell^*$と相互作用数$\#^*$がすべての$n,k,d$に対して漸近的に最適であることを示す量子符号を示す。
我々の結果は、BPT境界やバスピンとクリシュナの結果を含む、この問題に関するすべての先行研究を一般化または改善する。
我々の研究の要点は、任意の所望距離$d$と次元$k$に対して、長距離相互作用の数は、長さ$\Theta(\max(k,d))$のよいqLDPCコードによって漸近的に最小化されることである。
BaspinとKrishnaに続いて、スタック化されたアーキテクチャで実装されたコードにも結果を適用し、より良いバウンダリを得る。
特に、積み重ねられたアーキテクチャにおけるハイパーグラフ製品コードの実装は除外します。
関連論文リスト
- Stabilizer codes for Heisenberg-limited many-body Hamiltonian estimation [0.0]
雑音下での多体ハミルトニアン推定における安定化器量子誤差補正符号の性能について検討した。
本稿では,それぞれ$(nt)-1$,$(n2t)-1$,$(n3t)-1$のスケーリングを実現する安定化符号の3つのファミリを紹介する。
論文 参考訳（メタデータ） (2024-08-20T18:00:09Z) - Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳（メタデータ） (2024-04-25T12:09:16Z) - Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code [0.0]
Psi_b ラングル$ に対する高忠実度近似を量子回路で効率的に構築できることを実証する。
これらの状態を構築するのに使用されるテクニックは興味深く、コードを超えたアプリケーションを提供できることを願っています。
論文 参考訳（メタデータ） (2024-04-24T18:37:15Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Quantifying nonlocality: how outperforming local quantum codes is
expensive [0.06091702876917279]
量子低密度パリティチェック(LDPC)符号は、スケーラブルな量子回路の構築コストを削減するための有望な方法である。
局所的な相互作用によって実装された量子LDPC符号は、その次元$k$と距離$d$の制約に従うことを示す。
特に2Dでは、距離$n1/2 + epsilon$符号を持つ量子LDPCが$Omega(n1/2 + epsilon)$長さ$widetildeOmega(nepsilon)$相互作用を必要とすることを示す。
論文 参考訳（メタデータ） (2021-09-22T18:55:45Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Quantum LDPC Codes with Almost Linear Minimum Distance [0.0]
次元 $Theta(log N)$ と距離 $Theta(N/log N)$ の量子LDPC符号をコード長 $Ntoinfty$ として構成する。
固定された$R 1$に対して、コード長$Ntoinfty$として最適循環サイズ$Omega(N/log N)$の古典LDPC符号の準循環的に良い族が少なくとも$R$で存在することを示す。
論文 参考訳（メタデータ） (2020-12-07T21:20:53Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。