論文の概要: Average-Case Complexity of Quantum Stabilizer Decoding

• arxiv url: http://arxiv.org/abs/2509.20697v1
• Date: Thu, 25 Sep 2025 03:04:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-26 20:58:12.671398
• Title: Average-Case Complexity of Quantum Stabilizer Decoding
• Title（参考訳）: 量子安定化器デコーディングにおける平均ケース複雑性
• Authors: Andrey Boris Khesin, Jonathan Z. Lu, Alexander Poremba, Akshar Ramkumar, Vinod Vaikuntanathan,
• Abstract要約: 1つの論理量子ビットでさえも、ランダムな安定化符号を復号化することは、ランダムな古典符号を一定速度で復号化することと同じくらい難しいことを証明している。 この結果は、最も簡単なランダム量子復号問題は、少なくとも最も難しいランダム古典復号問題と同じくらい難しいことを示唆している。
• 参考スコア（独自算出の注目度）: 42.770940323689445
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate--the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any rate, would immediately imply a breakthrough in cryptography. More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. We also demonstrate several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decoding--all of which are classically identical--to have distinct or non-trivially equivalent complexity.
• Abstract（参考訳）: ランダムな古典的線形符号は復号が難しいと広く信じられている。 符号化速度が十分に急速に消えるとき、わずかに指数時間以下のアルゴリズムが存在するが、一定の速度で既知の全てのアルゴリズムは指数時間を必要とする。 対照的に、ランダムな量子安定化器コードの復号化の複雑さは、かなり前から未解決の問題であった。 この研究は、ランダム量子とランダム古典符号の復号化のアルゴリズム的困難さに対する理解のギャップを埋める。 1つの論理量子ビットでさえもランダムな安定化器符号を復号化することは、ランダムな古典符号を一定速度で復号化するのと同じくらい、少なくとも困難である。 この結果は、最も簡単なランダムな量子デコード問題は、少なくとも最も難しいランダムな古典的なデコード問題と同じくらい難しいことを示唆し、任意の確率で典型的な安定化器符号をデコードするサブ指数アルゴリズムが即座に暗号のブレークスルーを示唆していることを示している。 より一般的には、安定化器符号の他の多くの複雑性理論的性質を特徴づける。 古典的復号法はランダムな自己還元を許容するが、量子の場合におけるランダムな自己還元の存在に対する重要な障壁を証明している。 この結果は、クリフォードエントロピーとパウリ混合時間に関する新たな境界から導かれる。 補完的な結果として,探索と決定の中間といった,実際に達成可能な様々な自己還元を実証する。 また、量子退化のような量子現象が安定化器の復号化の合理的な定義を強制するいくつかの方法を示す。

関連論文リスト

• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。 量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
  論文  参考訳（メタデータ） (2024-09-23T17:45:33Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum Error Correction via Noise Guessing Decoding [0.0]
  量子誤り訂正符号(QECC)は、量子通信と量子計算の両方において中心的な役割を果たす。 本稿では,有限ブロック長レジームの最大性能を達成できるQECCの構築と復号化が可能であることを示す。
  論文  参考訳（メタデータ） (2022-08-04T16:18:20Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)

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

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