論文の概要: 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の減算における量子復号問題に対するアルゴリズムの使用は、短い符号語問題の最もよく知られた量子アルゴリズムと一致することを示す。
このことは、量子復号問題を考えるときのレゼフの縮小の厳密さを示し、また短い符号語問題に対する新しい量子アルゴリズムの道を開いた。
関連論文リスト
- Decoding algorithms for surface codes [0.0]
現在、表面コードは、短期的エラー修正量子ビットを構築する最も有望な候補である。
アルゴリズムの復号化における重要な側面は、量子状態が時間の経過とともにさらなるエラーに遭うため、その速度である。
本稿では、これらの復号法の中核となる原理と、改良された結果の約束を示す既存の変種について述べる。
論文 参考訳(メタデータ) (2023-07-27T16:34:52Z) - 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) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。