Fugu-MT 論文翻訳(概要): Upper bounding the quantum space complexity for computing class group and principal ideal problem

論文の概要: Upper bounding the quantum space complexity for computing class group and principal ideal problem

arxiv url: http://arxiv.org/abs/2405.12508v1
Date: Tue, 21 May 2024 05:37:04 GMT
ステータス: 処理完了
システム内更新日: 2024-05-22 14:18:37.214370
Title: Upper bounding the quantum space complexity for computing class group and principal ideal problem
Title（参考訳）: 計算類群に対する量子空間複雑性の上界と主イデアル問題
Authors: Iu-Iong Ng,
Abstract要約: Biasse と Song が提唱した量子アルゴリズムの量子空間複雑性の上限を計算する。私たちはBarbulescuとPoulalionのアプローチと、De Boer、Ducas、Fehrのフレームワークに従います。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we calculate the upper bound on quantum space complexity of the quantum algorithms proposed by Biasse and Song (SODA'16) for solving class group computation and the principal ideal problem using the reductions to $S$-unit group computation. We follow the approach of Barbulescu and Poulalion (AFRICACRYPT'23) and the framework given by de Boer, Ducas, and Fehr (EUROCRYPT'20) and Eisentr\"{a}ger, Hallgren, Kitaev, and Song (STOC'14).
Abstract（参考訳）: 本稿では、クラス群計算の解法としてBiasse and Song(SODA'16)が提唱した量子アルゴリズムの量子空間複雑性の上限値と、S$-unitグループ計算への還元法を用いて主理想問題を算出する。本稿では,Barbulescu and Poulalion (AFRICACRYPT'23) と de Boer, Ducas, Fehr (EUROCRYPT'20) と Eisentr\"{a}ger, Hallgren, Kitaev, Song (STOC'14) のアプローチに従う。

関連論文リスト

Krylov Complexity for Jacobi Coherent States [0.0]
我々は、クリロフ基底を反復的に生成するランツォスアルゴリズムが、ジャコビ群に関連するコヒーレントな状態を扱うためにどのように拡張されるかを示す。我々はこれを、より一般的なヤコビ群 $H_nrtimes Sp(2n,mathbbR)$ に一般化するランツォス係数を数値的に計算するスキームのベンチマークに利用する。
論文参考訳（メタデータ） (2022-12-28T09:21:58Z)
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)
QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文参考訳（メタデータ） (2022-05-24T03:49:10Z)
BILP-Q: Quantum Coalition Structure Generation [0.0]
我々は、結合構造生成問題(CSGP)を解決するための最初の一般量子アプローチであるBILP-Qを提案する。実量子アニール(D-Wave)を用いた中規模問題に対するBILP-Qの実行
論文参考訳（メタデータ） (2022-04-28T22:19:50Z)
An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文参考訳（メタデータ） (2022-01-31T18:58:33Z)
Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。最近の研究は、低次手法のクラスに対する低い境界を確立している。意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文参考訳（メタデータ） (2021-12-07T18:50:17Z)
Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文参考訳（メタデータ） (2021-08-03T17:49:09Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文参考訳（メタデータ） (2021-06-22T11:07:38Z)
Quantum Logarithmic Space and Post-selection [0.4588028371034406]
ポストセレクション(Post-Selection)は、アーロンソンによって量子複雑性理論の分野に導入された影響力ある概念である(Royal Society A, 2005 の論文)。我々の主な結果は、$sf PostBQL=$、すなわち、選択後(sf PostBQL$)で境界付きエラー(polynomial-time)対数空間量子アルゴリズムによって解決できる問題のクラスを示す。また、$sf$は時間制限のない有界誤差対数空間量子アルゴリズムによって解くことができる問題のクラスと一致することを示す。
論文参考訳（メタデータ） (2021-05-06T14:02:01Z)
Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
グラフ最大カット問題(MaxCut)の課題に対処するため,Divide-and-Conquer QAOA(DC-QAOA)を提案する。 DC-QAOAは97.14%の近似比(20.32%)を達成するまた、従来のQAOAの時間的複雑さを指数関数から二次的に減少させる。
論文参考訳（メタデータ） (2021-02-26T03:10:30Z)

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