論文の概要: The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction

• arxiv url: http://arxiv.org/abs/2509.24796v1
• Date: Mon, 29 Sep 2025 13:48:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:20.021718
• Title: The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction
• Title（参考訳）: 量子デコード問題 : 達成可能性境界の厳密化とRegevの低減への応用
• Authors: Agathe Blanvillain, André Chailloux, Jean-Pierre Tillich,
• Abstract要約: 我々は、$l_infty$ノルムに対するショート・ソリューション(SIS)問題に対する量子的優位性を示す。 最近の論文で、Chailloux と Tillich はベルヌーイ分布に従えば、量子復号問題はアルゴリズム時間で解くことができることを示した。
• 参考スコア（独自算出の注目度）: 6.140129238616484
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry's work showing a quantum advantage for the Short Integer Solution (SIS) problem for the $l_\infty$ norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev's reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev's reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.
• Abstract（参考訳）: 量子復号化問題を考える。 これは、このコードワードのうるさいバージョンの重ね合わせを与えられたコードワードを復元することで構成される。 重ね合わせを測ることで、古典的復号問題に戻る。 これはChen, Liu, Zhandryの業績で初めて、$l_\infty$ノルムに対するショート・インテガー・ソリューション(SIS)問題に対する量子的優位性を示した。 最近の論文で、Chailloux と Tillich はベルヌーイ分布の後にノイズがある場合、量子復号問題は多項式時間で解くことができ、したがって最もよく知られたアルゴリズムが指数関数的な複雑性を持つ古典的復号法よりも容易であることを示した。 彼らはまた、この問題を解くことができるコードレートに情報理論の限界を与え、シャノン限界を超えることが判明した。 本稿では,最後の結果をすべてのメモリレスノイズモデルに一般化する。 また、メモリレスでないノイズモデルに対応するランクメートル法においても同様の結果を示す。 この問題に対して情報理論の限界を導出するPretty Good Measurementを分析した。 量子デコード問題に対するアルゴリズムとRegevの還元法を用いて、元のノイズの双対である確率分布に従って、二重符号から量子アルゴリズムでコードワードをサンプリングする。 情報理論の限界では、おそらく2つのコードの非ゼロなコードワードが得られます。 分布が重みの減少関数である場合、最小零でない符号語が見つかる。 なお、Regevの減算と古典的な復号化は、これらの最小ウェイトコードワードを出力できないため、はるかに満足できないことに注意されたい。

関連論文リスト

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• Quantum advantage from soft decoders [0.7728149002473877]
  最適多項式補間法(OPI)問題におけるいくつかのインスタンス化の改善について述べる。 我々の結果は自然で説得力のある復号問題をもたらし、量子的優位性を持っていると信じている。 本稿では,Regevのリダクションの設定にデコーダを利用できるように,シンドロームからコセットサンプリング問題への新たなリダクションを提案する。
  論文  参考訳（メタデータ） (2024-11-19T15:12:03Z)
• The Quantum Decoding Problem [0.23310087539224286]
  量子復号問題について考察し、そこでは、符号語のノイズバージョンを重畳する。 ノイズレートが十分小さい場合、量子復号化問題は量子時間で解けることを示す。 また、関連する古典復号問題の解けない雑音率に対して、原理的に量子的に解けることを示す。
  論文  参考訳（メタデータ） (2023-10-31T17:21:32Z)
• Quantum Lego Expansion Pack: Enumerators from Tensor Networks [1.489619600985197]
  量子量列挙子を最も一般的な形式で計算するための最初のテンソルネットワーク法を提供する。 非(Pauli)安定化器符号の場合、これはコード距離を計算するのに最適なアルゴリズムである。 これらの列挙子は論理的誤り率を正確に計算するために使用することができ、従って任意の単一キュービットやキューディットのエラーチャネルに対してデコーダを構築することができる。
  論文  参考訳（メタデータ） (2023-08-09T18:00:02Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  安定猫量子ビットの既存システムに動機づけられたビットフリップ誤差のみに影響されるバイアスノイズ量子ビットを考察する。 現実的なノイズモデルでは、位相フリップは無視できないが、Pauli-Twirling近似では、ベンチマークが最大106ドルのゲートを含む回路の正しさを確認できる。
  論文  参考訳（メタデータ） (2023-05-03T11:27:50Z)
• Noisy decoding by shallow circuits with parities: classical and quantum [0.0]
  符号語が正の誤差率で雑音の多いチャネル上で送信される場合, 従来の回路では, 消滅した少数のメッセージのみを正確に復元できることが示される。 我々は、コードワードの$(1/2 - varepsilon)$-fractionが逆向きに破損しても、確率$Omega(varepsilon2)$でアダマール符号を正しく復号する単純な量子回路を与える。
  論文  参考訳（メタデータ） (2023-02-06T15:37:32Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)

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

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