論文の概要: The Learning Stabilizers with Noise problem
- arxiv url: http://arxiv.org/abs/2410.18953v3
- Date: Sat, 16 Nov 2024 17:09:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-19 14:29:55.000333
- Title: The Learning Stabilizers with Noise problem
- Title（参考訳）: 騒音問題を考慮した学習安定化装置
- Authors: Alexander Poremba, Yihui Quek, Peter Shor,
- Abstract要約: 雑音のある学習パリティ(Learning Parity with Noise, LPN)問題は、雑音の存在下でランダムな線形コードを復号するタスクとみなすことができる。
LSNは特殊なケースとして含まれており、これは古典的なケースと同程度に難しいことを示唆している。
我々は、量子ビットスキームの構築から量子データからの学習の計算限界まで、LSN仮定のいくつかの応用を同定する。
- 参考スコア（独自算出の注目度）: 46.623273455512106
- License:
- Abstract: Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove a worst-case to average-case reduction for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.
- Abstract（参考訳）: ランダム古典符号はエラー訂正特性が優れているが、実際には復号化が難しいことで知られている。
数十年にわたる大規模な研究にもかかわらず、最も高速に知られているアルゴリズムは指数時間で実行されている。
学習パリティ・ウィズ・ノイズ(LPN)問題は、ノイズの存在下でランダムな線形コードを復号するタスクと見なすことができるため、暗号理論と学習理論の両方において多くの応用がなされた際、顕著な硬さの仮定として現れてきた。
LPN問題の自然量子アナログは存在するか?
本研究では、局所的な非偏極雑音の存在下でランダムな安定化器コードを復号するタスクであるLearning Stabilizers with Noise (LSN)問題を紹介する。
極低雑音,低定音率,さらには閾値までの高雑音率など,様々な非偏極雑音状態におけるLSNの解く多項式時間および指数時間量子アルゴリズムを提案する。
次に、LSNが難しいという具体的な証拠を提供する。
まず LSN が LPN を特別な場合として含んでいることを示す。
第2に, LSN の変種に対して, 平均ケース削減が最悪の場合であることを示す。
LSNを解く際の計算複雑性は何か?
タスクは量子入力を特徴とするので、その複雑さは従来の複雑性クラスによって特徴づけられない。
代わりに、LSN問題は最近導入された(分配とオラクル)ユニタリ合成クラスにあることを示す。
最後に、量子ビットコミットメントスキームの構築から量子データからの学習の計算制限まで、LSN仮定のいくつかの応用を同定する。
関連論文リスト
- Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
LPN問題(Learning Parity with Noise)は、いくつかの古典的な暗号プリミティブの根底にある問題である。
本稿では,線形符号の復号化問題から,難易度がいくつか存在することの低減を試みている。
我々は、復号化の効率を、復号化のパラメータと問題の観点から特徴づける。
論文 参考訳（メタデータ） (2024-08-07T12:54:43Z) - A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
雑音量子回路のための時空古典的アルゴリズムを提供する。
我々のアプローチは、雑音が非局所的相関を指数的に減衰させるという直感に基づいている。
定音率の場合、ほとんどの入力状態において誤差緩和が効率的である任意の量子回路は、古典的にはほとんどの入力状態においてシミュレート可能である。
論文 参考訳（メタデータ） (2024-07-17T17:48:39Z) - Comparing resource requirements of noisy quantum simulation algorithms
for the Tavis-Cummings model [0.0]
フォールトトレラントな量子コンピュータは、古典的な計算では不可能な量子システムのシミュレーションを促進することができる。
デバイスノイズを緩和するための量子エラー緩和(QEM)や、古典的な最適化とパラメータ化量子回路を組み合わせた変分量子アルゴリズム(VQA)などがある。
ゼロノイズ外挿法(ZNE)と回路折り畳みによる雑音増幅法、インクリメンタル構造学習法(ISL)を比較した。
システムサイズが小さい場合,ISL は ZNE よりも誤差が小さいが,ZNE が優れている 4 キュービットに対して正しいダイナミクスを生成できないことがわかった。
論文 参考訳（メタデータ） (2024-02-26T16:06:24Z) - QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum
Circuits [82.50620782471485]
QuantumSEAはノイズ適応型量子回路のインタイムスパース探索である。
1)トレーニング中の暗黙の回路容量と(2)雑音の頑健さの2つの主要な目標を達成することを目的としている。
提案手法は, 量子ゲート数の半減と回路実行の2倍の時間節約で, 最先端の計算結果を確立する。
論文 参考訳（メタデータ） (2024-01-10T22:33:00Z) - Hardness results for decoding the surface code with Pauli noise [0.0]
曲面符号に対する量子極大極大復号法(QMLD)と退化量子極大復号法(DQMLD)はそれぞれNP-hardと#P-hardであることを示す。
我々は、式を立方体依存のパウリノイズモデルと、公式の満足度特性を符号化するシンドロームの集合に変換する。
論文 参考訳（メタデータ） (2023-09-19T05:29:01Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - On the Hardness of PAC-learning stabilizer States with Noise [5.584060970507507]
我々は、量子状態の学習のためのAaronson (2007) の確率的近似(PAC)フレームワークにおいて、雑音を伴う安定化器状態の学習問題を考察する。
PAC学習量子状態に対する統計的クエリ(SQ)モデルを導入する。
このモデルにおけるアルゴリズムは、分類や偏極ノイズを含む一般的なノイズに耐性があることを証明している。
論文 参考訳（メタデータ） (2021-02-09T23:06:54Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Noise-Induced Barren Plateaus in Variational Quantum Algorithms [0.3562485774739681]
変分量子アルゴリズム(VQA)は、ノイズ中間スケール量子(NISQ)コンピュータ上での量子優位性への道のりである。
騒音がトレーニングランドスケープに不規則な台地を生じさせることで、ノイズの多いVQAの深刻な制限を厳格に証明する。
論文 参考訳（メタデータ） (2020-07-28T17:52:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。