論文の概要: On the hardness of approximating minimum distances of quantum codes

• arxiv url: http://arxiv.org/abs/2509.21469v1
• Date: Thu, 25 Sep 2025 19:35:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:53.945282
• Title: On the hardness of approximating minimum distances of quantum codes
• Title（参考訳）: 量子符号の最小距離近似の硬さについて
• Authors: Elena Grigorescu, Vatsal Jha, Eric Samperton,
• Abstract要約: 誤り訂正符号の計算距離の問題は古典的設定と量子的設定の両方において基本的な問題である。 特に、古典的線形符号の最小距離問題から、最も一般的に使用される量子符号であるCSS符号の直接削減が得られる。 グラフの隣接行列が入力であるとき、グラフ状態の距離を計算/近似することはNPハードであることが示される。
• 参考スコア（独自算出の注目度）: 2.8636943749206423
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed these problems are also hard in the quantum setting. As our first main result, we reprove this using arguably simpler arguments based on hypergraph product codes. In particular, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state when the adjacency matrix of the graph is the input. In fact, we show this is true even if we only consider X-type errors of a graph state. Our techniques moreover imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.
• Abstract（参考訳）: 誤り訂正符号の計算距離の問題は古典的設定と量子的設定の両方において基本的な問題である。 これらの問題の古典的なバージョンに対する困難さは、(正確な設定と近似的な設定の両方において)しばらく前から知られていたが、KapshikarとKunduが量子的設定においてもこれらの問題が困難であることを示したのはつい最近のことである。 最初の主要な結果として、ハイパーグラフ製品コードに基づくより単純な議論を用いてこれを再検証する。 特に、古典的線形符号の最小距離問題から、最も一般的に使用される量子符号であるCSS符号の直接削減が得られる。 結果の2つ目の集合は、符号語安定化形式により得られる量子符号のキーパラメータであるグラフ状態の距離を考察する。 グラフの隣接行列が入力であるときにグラフ状態の距離を計算/近似することはNPハードであることが示される。 実際、グラフ状態のX型誤差のみを考えると、これは事実であることがわかる。 さらに、我々の手法は、計算の難しさや、古典的符号の距離を1/2に近似するという、興味深い古典的な結果を示している。 本研究の主な動機の1つは、量子符号の長さに比例した加法誤差が存在する場合の近似のNP硬度に関するKapshikarとKunduによって提起された疑問である。 ハイパーグラフの製品コードにはそのような硬さは持たないことが示されています。 これらの観測は、新しい種類の平方根障壁の可能性を示している。

関連論文リスト

• Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
  量子量列挙子を最も一般的な形式で計算するための最初のテンソルネットワーク法を提供する。 非(Pauli)安定化器符号の場合、これはコード距離を計算するのに最適なアルゴリズムである。 これらの列挙子は論理的誤り率を正確に計算するために使用することができ、従って任意の単一キュービットやキューディットのエラーチャネルに対してデコーダを構築することができる。
  論文  参考訳（メタデータ） (2023-08-09T18:00:02Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
  本稿では,1次元に制約された量子ビット格子の幅と物理閾値の関係について検討する。 我々は、表面コードを用いた最小レベルのエンコーディングでエラーバイアスを設計する。 このバイアスを格子サージャリングサーフェスコードバスを用いて高レベルなエンコーディングで処理する。
  論文  参考訳（メタデータ） (2022-12-03T06:16:07Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• On the Hardness of the Minimum Distance Problem of Quantum Codes [0.0]
  安定化器量子符号の最小距離を求めることはNPハードであることを示す。 この結果に使用される主要な技術ツールは、4サイクル自由グラフのいわゆるグラフ状態距離の低い値である。
  論文  参考訳（メタデータ） (2022-03-08T18:33:43Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)
• 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)

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

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