論文の概要: Diagonal distance of quantum codes and hardness of the minimum distance problem

• arxiv url: http://arxiv.org/abs/2203.04262v1
• Date: Tue, 8 Mar 2022 18:33:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-22 19:55:09.369778
• Title: Diagonal distance of quantum codes and hardness of the minimum distance problem
• Title（参考訳）: 量子コードの対角距離と最小距離問題の硬さ
• Authors: Upendra Kapshikar and Srijita Kundu
• Abstract要約: 対角距離は、コードが退化しているかどうかを特徴付ける量子誤り訂正符号の重要なパラメータである。 CWSフレームワークでは、古典的なコードとグラフを使用して量子コードを構築する。 CWSコードの距離を正確に計算することはNP完全であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The diagonal distance or graph distance is an important parameter of a quantum error-correcting code that characterizes whether the code is degenerate or not. Degeneracy is a property unique to quantum codes, which allows quantum codes, unlike their classical counterparts, to correct more errors than they can uniquely identify. In the CWS framework introduced by Cross, Smith, Smolin and Zeng (2009), a quantum code is constructed using a classical code and a graph. It is known that the diagonal distance of such a code is upper bounded by $\delta+1$, where $\delta$ is the minimum degree of the associated graph. In this paper, we give sufficient conditions on a graph such that a CWS code constructed from it has diagonal distance at least $\delta$, and in fact most of the graphs in our sufficient class achieve the upper bound of $\delta+1$. Using this result, first we give necessary conditions for a CWS code to be degenerate. Secondly, we prove hardness results for the problem of finding the distance of a CWS code. We construct a CWS code from a given classical code, with the distance of the CWS code being equal to the distance of the classical code. This allows us to translate well-known hardness results for computing the minimum distance in classical codes to quantum codes. Specifically, we show that exactly computing the distance of a CWS code is NP-complete, and multiplicatively or additively approximating it is NP-hard under polynomial-time randomized reductions. Our reduction from the classical problems to the quantum problems results in a non-degenerate quantum code, hence our result implies that the quantum problems remain NP-hard even with the promise that the code is non-degenerate. Moreover, using a mapping from stabilizer codes to CSS codes due to Bravyi, Terhal and Leemhuis (2010), we are able to show that the hardness results hold for CSS codes as well.
• Abstract（参考訳）: 対角距離またはグラフ距離は、コードが退化しているか否かを特徴付ける量子誤り訂正符号の重要なパラメータである。 デジェネリアシーは量子符号に固有の性質であり、古典的な符号とは異なり、量子符号が独自に識別できるよりも多くの誤りを修正できる。 Cross, Smith, Smolin and Zeng (2009)によって導入されたCWSフレームワークでは、古典的なコードとグラフを使って量子コードを構築する。 そのようなコードの対角距離が$\delta+1$で上界であることは知られているが、$\delta$は関連するグラフの最小次である。 本稿では、そのグラフ上に、そのグラフから構築されたCWSコードが少なくとも$\delta$の対角距離を持つような十分な条件を与え、実際、我々の十分クラスのグラフのほとんどが$\delta+1$の上限を達成する。 この結果を用いて、まずCWSコードを退化させるために必要な条件を与える。 第二に、CWS符号の距離を求める問題に対する難易度結果を示す。 与えられた古典的なコードからCWSコードを構築し、CWSコードの距離は古典的なコードの距離と等しい。 これにより、古典符号における最小距離を計算するためによく知られたハードネス結果を量子コードに変換することができる。 具体的には、cws符号の距離を正確に計算することはnp完全であり、乗算的または加法的に近似することは多項式時間ランダム化還元の下でnpハードであることを示す。 古典問題から量子問題への我々の還元は、非退化量子コードをもたらすので、この結果は、コードが非退化であることを約束しても、量子問題はnp困難であることを示唆している。 さらに、Bravyi, Terhal, Leemhuis (2010) による安定化器符号からCSS符号へのマッピングを用いることで、CSS符号の硬さが保持されることを示すことができる。

関連論文リスト

• Creating entangled logical qubits in the heavy-hex lattice with topological codes [0.0]
  この作業では、このバグが機能にどのように変換されるかを示します。 コード距離が最大$d = 4$の論理量子ビット間の絡み合いを示す。 我々は、94%の忠実さを特徴とするポストセレクションを持つ$d=2$のケースに対して、ベルの不平等の違反を検証する。
  論文  参考訳（メタデータ） (2024-04-24T17:02:35Z)
• Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
  本稿では,1次元に制約された量子ビット格子の幅と物理閾値の関係について検討する。 我々は、表面コードを用いた最小レベルのエンコーディングでエラーバイアスを設計する。 このバイアスを格子サージャリングサーフェスコードバスを用いて高レベルなエンコーディングで処理する。
  論文  参考訳（メタデータ） (2022-12-03T06:16:07Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。 本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
  論文  参考訳（メタデータ） (2021-11-19T12:35:26Z)
• 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)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)
• The Diagonal Distance of CWS Codes [0.0]
  量子コードの対角距離は、量子コードが退化しているかどうかを特徴付ける重要なパラメータである。 長さ4の周期を持たないCWS符号のほとんどは、対角距離d+1の上限に達することを示す。 グラフ $G$ と古典符号 C の縮退 CWS コードは、グラフ $G$ の短いサイクルを持つか、あるいは古典符号 C がすべての符号語に対して自明にゼロとなるようなものであることを示す。
  論文  参考訳（メタデータ） (2021-07-23T14:59:29Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Connectivity constrains quantum codes [0.06091702876917279]
  本稿では,D$次元双曲空間における局所グラフに付随する量子LDPC符号の限界について検討する。 接続グラフが拡張器を含まない限り、コードは著しく制限されている。 応用として、D$次元双曲空間における局所グラフに付随する量子LDPC符号の新たな境界を示す。
  論文  参考訳（メタデータ） (2021-06-01T20:03:16Z)
• Describing quantum metrology with erasure errors using weight distributions of classical codes [9.391375268580806]
  我々は、古典的な$[n,k,d]$二進ブロック符号に対応する構造を持つ量子プローブ状態について検討する。 これらのプローブ状態が古典場の未知の大きさを推定できるという究極の精度の限界を得る。
  論文  参考訳（メタデータ） (2020-07-06T16:22:40Z)
• 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)

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

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