論文の概要: The Quantum Decoding Problem

• arxiv url: http://arxiv.org/abs/2310.20651v1
• Date: Tue, 31 Oct 2023 17:21:32 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-01 13:49:40.771364
• Title: The Quantum Decoding Problem
• Title（参考訳）: 量子デコード問題
• Authors: Andr\'e Chailloux, Jean-Pierre Tillich
• Abstract要約: 量子復号問題について考察し、そこでは、符号語のノイズバージョンを重畳する。 ノイズレートが十分小さい場合、量子復号化問題は量子時間で解けることを示す。 また、関連する古典復号問題の解けない雑音率に対して、原理的に量子的に解けることを示す。
• 参考スコア（独自算出の注目度）: 0.23310087539224286
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.
• Abstract（参考訳）: 格子ベースの暗号の創始した成果の1つは、短い整数解問題からRegevが導入したLearning with Errors問題への量子還元である。 近年、Chen、Liu、Zhandryによって、この還元は、学習を量子重ね合わせで与えられる量子同値に置き換えることで、より強力にすることができると指摘されている。 符号の文脈では、これは、短い符号語を見つけることからランダムな線形符号の量子復号問題への還元に適応することができる。 そこで本論文では,量子復号問題について考察する。そこでは,コーデワードのノイズバージョンを重畳して,対応するコーデワードを復元する。 重ね合わせを測ると、最もよく知られたアルゴリズムが定数レートであり、符号長が指数関数的な誤り率である通常の古典復号問題に戻る。 しかし、ノイズ率が十分に小さい場合、量子復号問題は量子多項式時間で解くことができることを示す。 さらに, 情報理論上の理由から, 関連する古典的復号問題を解くことができない雑音率について, 原理上, 量子的に解くことができることを示した。 次に、コードのコンテキストにおけるRegevの削減を再考する。 regevの減算における量子復号問題に対するアルゴリズムの使用は、短い符号語問題の最もよく知られた量子アルゴリズムと一致することを示す。 このことは、量子復号問題を考えるときのレゼフの縮小の厳密さを示し、また短い符号語問題に対する新しい量子アルゴリズムの道を開いた。

関連論文リスト

• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  LPN問題(Learning Parity with Noise)は、いくつかの古典的な暗号プリミティブの根底にある問題である。 本稿では,線形符号の復号化問題から,難易度がいくつか存在することの低減を試みている。 我々は、復号化の効率を、復号化のパラメータと問題の観点から特徴づける。
  論文  参考訳（メタデータ） (2024-08-07T12:54:43Z)
• Breadth-first graph traversal union-find decoder [0.0]
  我々はその実装を単純化し、潜在的な復号速度の利点を提供するUnion-findデコーダの変種を開発する。 これらの手法が、非トポロジカル量子低密度パリティチェック符号のデコードにどのように適用できるかを示す。
  論文  参考訳（メタデータ） (2024-07-22T18:54:45Z)
• Deep Quantum Error Correction [73.54643419792453]
  量子誤り訂正符号(QECC)は、量子コンピューティングのポテンシャルを実現するための鍵となる要素である。 本研究では,新しいエンペンド・ツー・エンドの量子誤りデコーダを効率的に訓練する。 提案手法は,最先端の精度を実現することにより,QECCのニューラルデコーダのパワーを実証する。
  論文  参考訳（メタデータ） (2023-01-27T08:16:26Z)
• 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)
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings [0.0]
  行列のブロック符号化のための近似量子回路を高速に生成するFABLEを提案する。 FABLE回路は単純な構造であり、1ビットと2ビットのゲートで直接定式化されている。 FABLE回路は圧縮・スパシファイド可能であることを示す。
  論文  参考訳（メタデータ） (2022-04-29T21:06:07Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。 すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。 我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
  論文  参考訳（メタデータ） (2020-09-15T15:10:50Z)
• Efficiently computing logical noise in quantum error correcting codes [0.0]
  実効論理ノイズに対する再正規化として,読み出し量子ビット上の測定誤差が現れることを示す。 実効的論理ノイズの計算複雑性を,数桁のオーダーで低減する一般手法を導出する。
  論文  参考訳（メタデータ） (2020-03-23T19:40:56Z)

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

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