論文の概要: Quantum Algorithms for Variants of Average-Case Lattice Problems via
Filtering
- arxiv url: http://arxiv.org/abs/2108.11015v2
- Date: Wed, 6 Oct 2021 06:28:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-17 05:36:08.469809
- Title: Quantum Algorithms for Variants of Average-Case Lattice Problems via
Filtering
- Title（参考訳）: フィルタリングによる平均型格子問題の変数の量子アルゴリズム
- Authors: Yilei Chen and Qipeng Liu and Mark Zhandry
- Abstract要約: 以下の問題に対する時間量子アルゴリズムを示す。
我々の主な貢献は、LWEに似た量子状態と興味深いパラメータをフィルタリング技術を用いて解くことである。
- 参考スコア（独自算出の注目度）: 13.70673475846529
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show polynomial-time quantum algorithms for the following problems:
(*) Short integer solution (SIS) problem under the infinity norm, where the
public matrix is very wide, the modulus is a polynomially large prime, and the
bound of infinity norm is set to be half of the modulus minus a constant.
(*) Learning with errors (LWE) problem given LWE-like quantum states with
polynomially large moduli and certain error distributions, including bounded
uniform distributions and Laplace distributions.
(*) Extrapolated dihedral coset problem (EDCP) with certain parameters.
The SIS, LWE, and EDCP problems in their standard forms are as hard as
solving lattice problems in the worst case. However, the variants that we can
solve are not in the parameter regimes known to be as hard as solving
worst-case lattice problems. Still, no classical or quantum polynomial-time
algorithms were known for the variants of SIS and LWE we consider. For EDCP,
our quantum algorithm slightly extends the result of Ivanyos et al. (2018).
Our algorithms for variants of SIS and EDCP use the existing quantum
reductions from those problems to LWE, or more precisely, to the problem of
solving LWE given LWE-like quantum states. Our main contribution is solving LWE
given LWE-like quantum states with interesting parameters using a filtering
technique.
- Abstract（参考訳）: 例えば, (*) 公開行列が非常に広く, 係数は多項式的に大きい素数であり, 無限小ノルムの境界は定数を除いた定数の半分に設定されている, 無限大ノルムの下での短い整数解(SIS)問題である。
(*) 多項式的に大きなモジュライを持つLWE型量子状態と、有界均一分布やラプラス分布を含む特定の誤差分布を与えられた誤差(LWE)問題による学習。
(*)特定のパラメータを持つ2面コセット外挿問題(EDCP)。
SIS、LWEおよびEDCPの標準形式における問題は、最悪の場合において格子問題を解くのと同じくらい難しい。
しかし、我々が解決できる変種は、最悪の格子問題の解決ほど難しいパラメータ構造では知られていない。
それでも、SISとLWEの変種について古典的あるいは量子的多項式時間アルゴリズムは知られていない。
EDCPの場合、我々の量子アルゴリズムはIvanyos et al. (2018) の結果をわずかに拡張する。
SIS と EDCP の変種に対する我々のアルゴリズムは、これらの問題から LWE への既存の量子還元を使い、より正確には LWE のような量子状態から LWE を解く問題を解く。
我々の主な貢献は、LWEに似た量子状態と興味深いパラメータをフィルタリング技術を用いて解くことである。
関連論文リスト
- A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。
我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。
我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
論文 参考訳（メタデータ） (2024-08-15T05:11:35Z) - 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) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳（メタデータ） (2023-11-16T09:19:01Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳（メタデータ） (2023-04-12T18:10:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - An entanglement perspective on the quantum approximate optimization
algorithm [0.0]
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。
また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
論文 参考訳（メタデータ） (2022-06-14T17:37:44Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Fast algorithm for quantum polar decomposition, pretty-good
measurements, and the Procrustes problem [0.0]
量子極分解の問題は量子特異値 QSVT を介して単純で簡潔な実装を持つことを示す。
我々は、量子状態の区別のための、かなり良い測定方法、最適に近い測定方法、および量子Procrustes問題への応用に焦点を当てる。
論文 参考訳（メタデータ） (2021-06-14T17:50:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。