論文の概要: On the Hardness of the Minimum Distance Problem of Quantum Codes

• arxiv url: http://arxiv.org/abs/2203.04262v2
• Date: Mon, 6 Nov 2023 13:42:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 02:08:23.223604
• Title: On the Hardness of the Minimum Distance Problem of Quantum Codes
• Title（参考訳）: 量子コードの最小距離問題の硬さについて
• Authors: Upendra Kapshikar and Srijita Kundu
• Abstract要約: 安定化器量子符号の最小距離を求めることはNPハードであることを示す。 この結果に使用される主要な技術ツールは、4サイクル自由グラフのいわゆるグラフ状態距離の低い値である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximate form. For quantum codes, various problems related to decoding are known to be NP-hard, but the hardness of the distance problem has not been studied before. In this work, we show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard. This result is obtained by reducing the classical minimum distance problem to the quantum problem, using the CWS framework for quantum codes, which constructs a quantum code using a classical code and a graph. A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs. In particular, we show that for a 4-cycle free graph $G$, its graph state distance is either $\delta$ or $\delta+1$, where $\delta$ is the minimum vertex degree of $G$. Due to a well-known reduction from stabilizer codes to CSS codes, our results also imply that finding the minimum distance of CSS codes is also NP-hard.
• Abstract（参考訳）: 量子誤り訂正符号の距離を求める問題の難しさについて検討する。 古典符号の類似問題は、近似形式でさえNPハードであることが知られている。 量子符号の場合、復号に関する様々な問題はNPハードであることが知られているが、距離問題の硬さは以前にも研究されていない。 本研究では,安定化器量子符号の最小距離を求めることはNPハードであることを示す。 この結果は、古典的な符号とグラフを用いて量子コードを構成する量子コードのためのCWSフレームワークを用いて、古典的な最小距離問題を量子問題に還元することで得られる。 この結果に使用される主要な技術ツールは、4サイクル自由グラフのいわゆるグラフ状態距離の低い値である。 特に、4サイクル自由グラフ $G$ の場合、そのグラフ状態距離は $\delta$ または $\delta+1$ のいずれかであり、$\delta$ は$G$ の最小頂点次数である。 安定化器コードからCSSコードへのよく知られた削減により,CSSコードから最小距離の発見もNPハードであることが示唆された。

関連論文リスト

• 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)

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

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