論文の概要: An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor
- arxiv url: http://arxiv.org/abs/2201.13450v1
- Date: Mon, 31 Jan 2022 18:58:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 05:15:57.868511
- Title: An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor
- Title（参考訳）: 部分指数近似係数を実現する格子問題の効率的な量子アルゴリズム
- Authors: Lior Eldar and Sean Hallgren
- Abstract要約: 整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
- 参考スコア（独自算出の注目度）: 2.3351527694849574
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a quantum algorithm for solving the Bounded Distance Decoding (BDD)
problem with a subexponential approximation factor on a class of integer
lattices. The quantum algorithm uses a well-known but challenging-to-use
quantum state on lattices as a type of approximate quantum eigenvector to
randomly self-reduce the BDD instance to a random BDD instance which is
solvable classically. The running time of the quantum algorithm is polynomial
for one range of approximation factors and subexponential time for a second
range of approximation factors.
The subclass of lattices we study has a natural description in terms of the
lattice's periodicity and finite abelian group rank. This view makes for a
clean quantum algorithm in terms of finite abelian groups, uses very relatively
little from lattice theory, and suggests exploring approximation algorithms for
lattice problems in parameters other than dimension alone.
A talk on this paper sparked many lively discussions and resulted in a new
classical algorithm matching part of our result. We leave it as a challenge to
give a classcial algorithm matching the general case.
- Abstract（参考訳）: 我々は、整数格子のクラス上の部分指数近似係数を用いて、境界距離復号(bdd)問題を解決する量子アルゴリズムを与える。
量子アルゴリズムは、格子上のよく知られたが難しい量子状態を近似量子固有ベクトルの一種として利用し、BDDインスタンスを古典的に解けるランダムBDDインスタンスにランダムに自己複製する。
量子アルゴリズムの実行時間は1つの近似因子の多項式であり、第2の近似因子の指数時間である。
私たちが研究する格子のサブクラスは、格子の周期性および有限アーベル群ランクの観点から自然な記述を持つ。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論からはほとんど利用せず、次元のみ以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
この論文は、多くの活発な議論を巻き起こし、結果にマッチする新しい古典的アルゴリズムを生み出した。
一般の場合と一致する分類アルゴリズムを与えるという課題として残す。
関連論文リスト
- 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) - Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。
また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
論文 参考訳（メタデータ） (2024-07-10T14:08:58Z) - A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum
Factoring, and More [1.1893324664457547]
本稿では,古典的および量子的設定における暗号問題の解法における汎用的アプローチの限界について検討する。
両方のモデルにおいて、両方のモデルの量子的下界は、ある種の古典的な前処理を可能にする。
論文 参考訳（メタデータ） (2024-02-17T13:00:47Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
時間複雑性を持つ整数乗算の量子アルゴリズムをO(sqrtnlog2 n)$で提案する。
Harveyアルゴリズムとは異なり、我々のアルゴリズムは極大数にのみ適用できるという制限はない。
また、古典的乗法アルゴリズムの歴史と発展を概観し、量子資源がこの根本的な問題に対してどのように新たな視点と可能性を提供できるかを探求する動機付けとなる。
論文 参考訳（メタデータ） (2023-06-14T12:40:54Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Simpler (classical) and faster (quantum) algorithms for Gibbs partition
functions [4.2698418800007865]
古典ハミルトニアンの分配関数を所定の温度で近似するための古典的および量子的アルゴリズムを提案する。
我々は,vStefankovivc,Vempala,Vigodaの古典的アルゴリズムを改良し,サンプルの複雑さを改善する。
我々はこの新しいアルゴリズムを量子化し、HarrowとWeiにより、この問題に対してこれまで最速の量子アルゴリズムを改善した。
論文 参考訳（メタデータ） (2020-09-23T17:27:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。