論文の概要: An Efficient Quantum Decoder for Prime-Power Fields
- arxiv url: http://arxiv.org/abs/2210.11552v2
- Date: Tue, 12 Sep 2023 15:12:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-13 18:00:23.693519
- Title: An Efficient Quantum Decoder for Prime-Power Fields
- Title(参考訳): プライマリパワーフィールドのための効率的な量子デコーダ
- Authors: Lior Eldar
- Abstract要約: ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。
一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
- 参考スコア(独自算出の注目度): 1.0878040851638
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We consider a version of the nearest-codeword problem on finite fields
$\mathbb{F}_q$ using the Manhattan distance, an analog of the Hamming metric
for non-binary alphabets. Similarly to other lattice related problems, this
problem is NP-hard even up to constant factor approximation. We show, however,
that for $q = p^m$ where $p$ is small relative to the code block-size $n$,
there is a quantum algorithm that solves the problem in time ${\rm poly}(n)$,
for approximation factor $1/n^2$, for any $p$. On the other hand, to the best
of our knowledge, classical algorithms can efficiently solve the problem only
for much smaller inverse polynomial factors. Hence, the decoder provides an
exponential improvement over classical algorithms, and places limitations on
the cryptographic security of large-alphabet extensions of code-based
cryptosystems like Classic McEliece.
- Abstract(参考訳): 有限体 $\mathbb{F}_q$ 上の最寄り符号語問題のバージョンを、非二進アルファベットに対するハミング計量の類似であるマンハッタン距離を用いて検討する。
他の格子関連問題と同様に、この問題は定数係数近似までNPハードである。
しかし、$q = p^m$ の場合、$p$ はコードブロックサイズ $n$ と比較して小さいので、任意の$p$ に対して近似係数 $1/n^2$ に対して、時間で問題を解く量子アルゴリズムが存在することを示す。
一方、我々の知識を最大限に活用するために、古典的アルゴリズムはこの問題をはるかに小さな逆多項式因子に対してのみ効率的に解くことができる。
したがって、デコーダは古典的なアルゴリズムよりも指数関数的に改善され、classic mcelieceのようなコードベースの暗号システムの大きなalphabet拡張の暗号セキュリティに制限を課す。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳(メタデータ) (2024-08-14T19:04:13Z) - Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code [0.0]
Psi_b ラングル$ に対する高忠実度近似を量子回路で効率的に構築できることを実証する。
これらの状態を構築するのに使用されるテクニックは興味深く、コードを超えたアプリケーションを提供できることを願っています。
論文 参考訳(メタデータ) (2024-04-24T18:37:15Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳(メタデータ) (2024-02-09T19:01:48Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳(メタデータ) (2023-05-19T00:07:32Z) - Noisy decoding by shallow circuits with parities: classical and quantum [0.0]
符号語が正の誤差率で雑音の多いチャネル上で送信される場合, 従来の回路では, 消滅した少数のメッセージのみを正確に復元できることが示される。
我々は、コードワードの$(1/2 - varepsilon)$-fractionが逆向きに破損しても、確率$Omega(varepsilon2)$でアダマール符号を正しく復号する単純な量子回路を与える。
論文 参考訳(メタデータ) (2023-02-06T15:37:32Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳(メタデータ) (2022-04-22T12:37:56Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳(メタデータ) (2020-12-03T14:03:20Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳(メタデータ) (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。