論文の概要: Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

• arxiv url: http://arxiv.org/abs/2106.02747v1
• Date: Fri, 4 Jun 2021 22:42:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-27 21:03:33.282180
• Title: Quantum Reduction of Finding Short Code Vectors to the Decoding Problem
• Title（参考訳）: 復号問題に対する短符号ベクトル探索の量子化
• Authors: Thomas Debris-Alazard, Maxime Remaud and Jean-Pierre Tillich
• Abstract要約: ランダムな線形コード中の短いコードワードの発見から、ハミング計量の復号化まで、量子的に低減する。 このような還元(古典的あるいは量子的)が得られたのはこれが初めてである。
• 参考スコア（独自算出の注目度）: 0.9269394037577176
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehl\'{e}-Steinfield-Tanaka-Xagawa' re-interpretation of Regev's quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and can not be used for the reduction with codes. Instead we choose here the uniform distribution over errors of a fixed weight and bring in orthogonal polynomials tools to perform the analysis and an additional amplitude amplification step to obtain the aforementioned result.
• Abstract（参考訳）: ランダムな線形コード中の短い符号語の発見からハミング計量の復号まで、量子的に減少する。 このような還元(古典的あるいは量子的)が得られたのはこれが初めてである。 我々の還元は線形符号Stehl\'{e}-Steinfield-Tanaka-Xgawaの量子還元の短い格子ベクトルの発見から最も近いベクトル問題への再解釈に適応する。 ハミング計量はユークリッド計量よりもはるかに粗い計量であり、この適応にはいくつかの新しい材料が必要である。 例えば、有意義な減少を得るためには、ハミング計量において非常に大きな復号半径を選択する必要があり、多くの場合、復号が一意である半径を超える必要がある。 削減分析のためのもう1つの重要なステップは、デコードアルゴリズムに供給されるエラーの選択である。 格子の場合、誤差は通常ガウス分布に従ってサンプリングされる。 しかし、ベルヌーイ分布(ガウスの符号の類似体)があまりに広く広がりすぎて、符号の縮小には利用できないことが判明した。 代わりに、ここで固定重みの誤差に対する一様分布を選択し、解析を行う直交多項式ツールと、上記の結果を得るために追加の振幅増幅ステップをもたらす。

関連論文リスト

• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  LPN問題(Learning Parity with Noise)は、いくつかの古典的な暗号プリミティブの根底にある問題である。 本稿では,線形符号の復号化問題から,難易度がいくつか存在することの低減を試みている。 我々は、復号化の効率を、復号化のパラメータと問題の観点から特徴づける。
  論文  参考訳（メタデータ） (2024-08-07T12:54:43Z)
• The Quantum Decoding Problem [0.23310087539224286]
  量子復号問題について考察し、そこでは、符号語のノイズバージョンを重畳する。 ノイズレートが十分小さい場合、量子復号化問題は量子時間で解けることを示す。 また、関連する古典復号問題の解けない雑音率に対して、原理的に量子的に解けることを示す。
  論文  参考訳（メタデータ） (2023-10-31T17:21:32Z)
• Analysis of the Error-Correcting Radius of a Renormalisation Decoder for Kitaev's Toric Code [0.0]
  北エフのトーリック符号は間違いなく最も研究されている量子符号である。 再正規化デコーダは、効率と速度の最良のトレードオフの1つを示します。
  論文  参考訳（メタデータ） (2023-09-21T15:23:41Z)
• Bounds on Autonomous Quantum Error Correction [3.9119979887528125]
  我々は、幅広い量子ビットおよびボソニックな誤り訂正符号で実装できるマルコフの自律デコーダを解析する。 多体量子符号の場合、能動的誤り訂正に匹敵する誤り抑制を達成するために、自律デコーダは一般にコードサイズに応じて増大する修正率を必要とする。
  論文  参考訳（メタデータ） (2023-08-30T18:00:07Z)
• Fault-Tolerant Computing with Single Qudit Encoding [49.89725935672549]
  単一マルチレベルキューディットに実装された安定化器量子エラー訂正符号について論じる。 これらのコードは、quditの特定の物理的エラーに合わせてカスタマイズすることができ、効果的にそれらを抑制することができる。 分子スピン四重項上のフォールトトレラントな実装を実証し、線形キューディットサイズのみの成長を伴うほぼ指数関数的な誤差抑制を示す。
  論文  参考訳（メタデータ） (2023-07-20T10:51:23Z)
• The END: An Equivariant Neural Decoder for Quantum Error Correction [73.4384623973809]
  データ効率のよいニューラルデコーダを導入し、この問題の対称性を活用する。 本稿では,従来のニューラルデコーダに比べて精度の高い新しい同変アーキテクチャを提案する。
  論文  参考訳（メタデータ） (2023-04-14T19:46:39Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。 RM符号は制限されたレートのみを許容する。 効率的なデコーダは、RM符号に対して有限長で利用可能である。
  論文  参考訳（メタデータ） (2023-01-16T04:11:14Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
  本稿では,1次元に制約された量子ビット格子の幅と物理閾値の関係について検討する。 我々は、表面コードを用いた最小レベルのエンコーディングでエラーバイアスを設計する。 このバイアスを格子サージャリングサーフェスコードバスを用いて高レベルなエンコーディングで処理する。
  論文  参考訳（メタデータ） (2022-12-03T06:16:07Z)
• Quantum Sparse Coding [5.130440339897477]
  我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。 量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。 我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
  論文  参考訳（メタデータ） (2022-09-08T13:00:30Z)
• Correcting spanning errors with a fractal code [7.6146285961466]
  立方体符号のフラクタル特性を模倣した2次元古典符号であるフィボナッチ符号の効率的な復号器を提案する。 我々は,デコーダが一次元相関誤差に対して頑健であることを示す数値実験を行った。
  論文  参考訳（メタデータ） (2020-02-26T19:00:06Z)

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

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